1.
2Sum Problem
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < [Link]; i++) {
int complement = target - nums[i];
if ([Link](complement)) {
return new int[]{[Link](complement), i};
}
[Link](nums[i], i);
}
return new int[]{-1, -1};
}
// Input: [2,7,11,15], target = 9 -> Output: [0,1]
2. Sort an array of 0's, 1's and 2's
public static void sortColors(int[] nums) {
int low = 0, mid = 0, high = [Link] - 1;
while (mid <= high) {
switch (nums[mid]) {
case 0 -> swap(nums, low++, mid++);
case 1 -> mid++;
case 2 -> swap(nums, mid, high--);
}
}
}
// Input: [2,0,2,1,1,0] -> Output: [0,0,1,1,2,2]
3. Majority Element (> n/2 times)
public static int majorityElement(int[] nums) {
int count = 0, candidate = 0;
for (int num : nums) {
if (count == 0) candidate = num;
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
// Input: [3,2,3] -> Output: 3
4. Kadane's Algorithm
public static int maxSubArray(int[] nums) {
int maxSum = nums[0], currSum = nums[0];
for (int i = 1; i < [Link]; i++) {
currSum = [Link](nums[i], currSum + nums[i]);
maxSum = [Link](maxSum, currSum);
}
return maxSum;
}
// Input: [-2,1,-3,4,-1,2,1,-5,4] -> Output: 6
5. Print subarray with maximum subarray sum
public static void printMaxSubarray(int[] nums) {
int maxSum = nums[0], currSum = nums[0], start = 0, end = 0, temp = 0;
for (int i = 1; i < [Link]; i++) {
if (currSum < 0) {
currSum = nums[i];
temp = i;
} else {
currSum += nums[i];
}
if (currSum > maxSum) {
maxSum = currSum;
start = temp;
end = i;
}
}
[Link]("Max Sum: " + maxSum + ", Subarray: " + [Link]([Link](nums, start, end +
1)));
}
// Input: [-2,1,-3,4,-1,2,1,-5,4] -> Output: Max Sum: 6, Subarray: [4, -1, 2, 1]
6. Stock Buy and Sell
public static int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, maxProfit = 0;
for (int price : prices) {
if (price < minPrice) minPrice = price;
else maxProfit = [Link](maxProfit, price - minPrice);
}
return maxProfit;
}
// Input: [7,1,5,3,6,4] -> Output: 5
7. Rearrange Alternating Positive and Negative
public static void rearrangeAlt(int[] arr) {
List<Integer> pos = new ArrayList<>(), neg = new ArrayList<>();
for (int num : arr) if (num >= 0) [Link](num); else [Link](num);
int i = 0, j = 0, k = 0;
while (i < [Link]() && j < [Link]()) {
arr[k++] = [Link](i++);
arr[k++] = [Link](j++);
}
while (i < [Link]()) arr[k++] = [Link](i++);
while (j < [Link]()) arr[k++] = [Link](j++);
}
// Input: [1, 2, 3, -4, -1, 4] -> Output: [1, -4, 2, -1, 3, 4]
8. Next Permutation
public static void nextPermutation(int[] nums) {
int i = [Link] - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
int j = [Link] - 1;
while (nums[j] <= nums[i]) j--;
swap(nums, i, j);
}
reverse(nums, i + 1, [Link] - 1);
}
// Input: [1,2,3] -> Output: [1,3,2]
9. Leaders in an Array
public static void leaders(int[] arr) {
int maxFromRight = arr[[Link] - 1];
[Link](maxFromRight + " ");
for (int i = [Link] - 2; i >= 0; i--) {
if (arr[i] > maxFromRight) {
maxFromRight = arr[i];
[Link](maxFromRight + " ");
}
}
}
// Input: [16,17,4,3,5,2] -> Output: 2 5 17
10. Longest Consecutive Sequence
public static int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) [Link](num);
int longest = 0;
for (int num : nums) {
if () {
int curr = num, streak = 1;
while ([Link](curr + 1)) {
curr++;
streak++;
}
longest = [Link](longest, streak);
}
}
return longest;
}
// Input: [100,4,200,1,3,2] -> Output: 4
11. Set Matrix Zeros
public static void setZeroes(int[][] matrix) {
Set<Integer> rows = new HashSet<>();
Set<Integer> cols = new HashSet<>();
for (int i = 0; i < [Link]; i++)
for (int j = 0; j < matrix[0].length; j++)
if (matrix[i][j] == 0) {
[Link](i); [Link](j);
}
for (int i : rows)
[Link](matrix[i], 0);
for (int j : cols)
for (int i = 0; i < [Link]; i++)
matrix[i][j] = 0;
}
// Input: [[1,1,1],[1,0,1],[1,1,1]] -> Output: [[1,0,1],[0,0,0],[1,0,1]]
12. Rotate Matrix by 90 Degrees
public static void rotate(int[][] matrix) {
int n = [Link];
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
swapMatrix(matrix, i, j);
for (int[] row : matrix)
reverseRow(row);
}
// Input: [[1,2,3],[4,5,6],[7,8,9]] -> Output: [[7,4,1],[8,5,2],[9,6,3]]
13. Print Matrix in Spiral Order
public static void spiralPrint(int[][] matrix) {
int top = 0, bottom = [Link] - 1, left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int i = left; i <= right; i++) [Link](matrix[top][i] + " ");
top++;
for (int i = top; i <= bottom; i++) [Link](matrix[i][right] + " ");
right--;
if (top <= bottom)
for (int i = right; i >= left; i--) [Link](matrix[bottom][i] + " ");
bottom--;
if (left <= right)
for (int i = bottom; i >= top; i--) [Link](matrix[i][left] + " ");
left++;
}
}
// Input: [[1,2,3],[4,5,6],[7,8,9]] -> Output: 1 2 3 6 9 8 7 4 5
14. Count Subarrays with Given Sum
public static int countSubarrays(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
[Link](0, 1);
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
count += [Link](sum - k, 0);
[Link](sum, [Link](sum, 0) + 1);
}
return count;
}
// Input: [1,1,1], k=2 -> Output: 2
