Two sum: input array not sorted
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Make a hashmap: number -> index it is present at
for each number in array check if difference = target - number is present, if yes it’s your answer
else add the number -> index in map
Two sum II: input array is sorted
Use two pointers and run until left < right
sum = arr[left] + arr[right]
if sum == target: you found it
if sum > target: arr[right] is too big, right–
else arr[left] if too small, left++
3Sum:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Sort array, iterate over it, and reduce finding the other two in the result triplet to 2 sum problem, searching from index+1 to end of array
for(int index=0; index < nums.length; index++) {
if (index>0 && nums[index-1] == nums[index])
continue; //eliminate duplicate pairs
modifiedTwoSearch(nums, index, result);
}
modifiedTwoSearch(int[] nums, int index, List<List<Integer>> result) {
int left=index+1, right = nums.length-1;
int target = -1 * nums[index];
while(left<right) {
int sum = nums[left] + nums[right];
if (sum==target) {
result.add(index, left and right); left++; right--;
//eliminate duplicate pairs
while(left<right && nums[left]==nums[left-1]) left++;
while(left < right && nums[right]==nums[right+1]) right--;
} else if (sum > target) {
right--;
} else {
left++;
}
}
}</Integer>
Move zeroes
Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Two pointers: use index to traverse array and nextNonZeroIndex to track where next non-zero needs to be placed
If at index there is non zero:
1. swap it with what is at nextNonZeroIndex
2. increment nextNonZeroIndex
[0,1,0,3,12] -> [1,0,0,2,12] -> [1,2,0,0,12] -> [1,2,12,0,0]
Sort colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library’s sort function.
Approach 1: count sort, which takes 2 O(n) loops
Approach 2: one O(n) loop with two pointers, p0 -> rightmost boundary for 0’s, p2 -> leftmost boundary for 2’s, and move them inward
p0 = 0, p2 = nums.length-1, index=0
while(index <= p2) {
if (nums[index]==0) {
swap(nums, index, p0); p0++; index++;
} else if (nums[index]==2) {
swap(nums, index, p2); p2–;
} else {
index++;
}
}
Trapping rain water - two pass solution
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: In this case, 6 units of rain water are being trapped.
Idea is to find the max height of any bar, including current one, to both left and right of current index.
Then the water that can be trapped at current index is = min(left_max,right_max)−height[i]
int[] maxLeft = new int[height.length];
int[] maxRight = new int[height.length];
maxLeft[0] = height[0];
maxRight[height.length-1] = height[height.length-1];
for(int index=height.length-2; index>=0; index–) {
maxRight[index] = Math.max(maxRight[index+1], height[index]);
}
int waterTrapped = 0;
for(int index=1; index<height.length-1; index++) {
maxLeft[index] = Math.max(height[index], maxLeft[index-1]);
waterTrapped += Math.min(maxLeft[index] , maxRight[index]) - height[index];
}
return waterTrapped;
Optimize this by reducing space needed for maxLeft array into O(1) by using one variable.
Trapping rain water - one pass solution
Start at both ends with two pointers, and wherever the height is lower, advance the pointer inwards. Combine with Math.min(maxLeft[index] , maxRight[index]) condition to:
1. if heights[left] < heights[right]: waterTrapped += heights[left] - heights[index] for index left, advance the left pointer in
2. if heights[right] < heights[left]: waterTrapped += heights[right] - heights[index] for index right, advance right pointer in
int left = 0, right=height.length-1;
int waterTrapped = 0;
int leftMax=0, rightMax=0;
while(left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
waterTrapped += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
waterTrapped += rightMax - height[right];
right--;
}
}
return waterTrapped;Longest Mountain in Array
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3
There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < … < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > … > arr[arr.length - 1]
Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.
Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.
Use two pointers and simulate the process of walking up and down a mountain
if (arr.length < 3) return 0;
int result=0, baseOfMountain = 0;
boolean uphill = false, downhill = false;
while(baseOfMountain < arr.length-1) {
if (arr[baseOfMountain] >= arr[baseOfMountain+1]) {
baseOfMountain++;
continue;
}
int end = baseOfMountain;
//we walk up and down a mountain starting at base and ending at end
while(end+1 < arr.length && arr[end] < arr[end+1]) { //increasing
end++;
uphill = true;
}
while(end < arr.length-1 && arr[end] > arr[end+1]) {
end++;
downhill = true;
}
if (uphill && downhill)
result = Math.max(end - baseOfMountain + 1, result);
uphill = false;
downhill = false;
baseOfMountain = end;
}
return result;Valid Palindrome
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.
Use two pointers, advance each as long as it is within bounds (left < right) and is not alphanumeric:
int left=0, right = s.length()-1;
while(left < right) {
while(left < right && !Character.isLetterOrDigit(s.charAt(left)))
left++;
while(left < right && !Character.isLetterOrDigit(s.charAt(right)))
right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
return false;
left++;
right--;
}
return true;Valid Palindrome II
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Input: s = “abca”
Output: true
Explanation: You could delete the character ‘c’.
Idea: use two pointers, if characters are the same, advance them inwards. If not, try to move one inwards and do the same check recursively
int left=0, right = s.length()-1;
while(left < right) {
if (s.charAt(left) != s.charAt(right)) {
return (isPalindrome(s, left+1, right) || isPalindrome(s, left, right-1));
}
left++;
right--;
}
return true;isPalindrome is the usual O(N) check using two pointers.
