Two-pointer strategies Flashcards
Pair with Target Sum
Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.
Write a function to return the indices of the two numbers (i.e. the pair) such that they add up to the given target.
Example 1
Input: [1, 2, 3, 4, 6], target=6
Output: [1, 3]
Explanation: The numbers at index 1 and 3 add up to 6: 2+4=6
Example 2
Input: [2, 5, 9, 11], target=11
Output: [0, 2]
Explanation: The numbers at index 0 and 2 add up to 11: 2+9=11
Since the given array is sorted, a brute-force solution could be to iterate through the array, taking one number at a time and searching for the second number through Binary Search. The time complexity of this algorithm will be O(N*logN). Can we do better than this?
We can follow the Two Pointers approach. We will start with one pointer pointing to the beginning of the array and another pointing at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do, we have found our pair; otherwise, we will do one of two things:
- If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.
- If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.
The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.
The algorithm runs in constant space O(1).
Remove Duplicates
Given an array of sorted numbers, remove all duplicates from it. You should not use any extra space; after removing the duplicates in-place return the new length of the array.
Example 1
Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4
Explanation: The first four elements after removing the duplicates will be [2, 3, 6, 9].
Example 2
Input: [2, 2, 2, 11]
Output: 2
Explanation: The first two elements after removing the duplicates will be [2, 11].
In this problem, we need to remove the duplicates in-place such that the resultant length of the array remains sorted. As the input array is sorted, therefore, one way to do this is to shift the elements left whenever we encounter duplicates. In other words, we will keep one pointer for iterating the array and one pointer for placing the next non-duplicate number. So our algorithm will be to iterate the array and whenever we see a non-duplicate number we move it next to the last non-duplicate number we’ve seen.
Squaring a Sorted Array
Given a sorted array, create a new array containing squares of all the number of the input array in the sorted order.
Example 1
Input: [-2, -1, 0, 2, 3]
Output: [0, 1, 4, 4, 9]
Example 2
Input: [-3, -1, 0, 1, 2]
Output: [0 1 1 4 9]
This is a straightforward question. The only trick is that we can have negative numbers in the input array, which will make it a bit difficult to generate the output array with squares in sorted order.
An easier approach could be to first find the index of the first non-negative number in the array. After that, we can use Two Pointers to iterate the array. One pointer will move forward to iterate the non-negative numbers and the other pointer will move backward to iterate the negative numbers. At any step, whichever number gives us a bigger square will be added to the output array.
The time complexity of the above algorithm will be O(N) as we are iterating the input array only once.
The space complexity of the above algorithm will also be O(N); this space will be used for the output array.
Triplet Sum to Zero
Given an array of unsorted numbers, find all unique triplets in it that add up to zero.
Example 1
Input: [-3, 0, 1, 2, -1, 1, -2]
Output: [-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]
Explanation: There are four unique triplets whose sum is equal to zero.
Example 2
Input: [-5, 2, -1, -2, 3]
Output: [[-5, 2, 3], [-2, -1, 3]]
Explanation: There are two unique triplets whose sum is equal to zero.
This problem follows the Two Pointers pattern and shares similarities with Pair with Target Sum. A couple of differences are that the input array is not sorted and instead of a pair we need to find triplets with a target sum of zero.
To follow a similar approach, first, we will sort the array and then iterate through it taking one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ and ‘Z’ such that X + Y + Z == 0. At this stage, our problem translates into finding a pair whose sum is equal to “-X” (as from the above equation Y + Z == -X).
Another difference from Pair with Target Sum is that we need to find all the unique triplets. To handle this, we have to skip any duplicate number. Since we will be sorting the array, so all the duplicate numbers will be next to each other and are easier to skip.
Sorting the array will take O(N * logN). The searchPair() function will take O(N). As we are calling searchPair() for every number in the input array, this means that overall searchTriplets() will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).
Ignoring the space required for the output array, the space complexity of the above algorithm will be O(N) which is required for sorting.
Triplet Sum Close to Target
Given an array of unsorted numbers and a target number, find a triplet in the array whose sum is as close to the target number as possible, return the sum of the triplet. If there are more than one such triplet, return the sum of the triplet with the smallest sum.
Example 1
Input: [-2, 0, 1, 2], target=2
Output: 1
Explanation: The triplet [-2, 1, 2] has the closest sum to the target.
Example 2
Input: [-3, -1, 1, 2], target=1
Output: 0
Explanation: The triplet [-3, 1, 2] has the closest sum to the target.
Example 3
Input: [1, 0, 1, 1], target=100
Output: 3
Explanation: The triplet [1, 1, 1] has the closest sum to the target.
This problem follows the Two Pointers pattern and is quite similar to Triplet Sum to Zero.
We can follow a similar approach to iterate through the array, taking one number at a time. At every step, we will save the difference between the triplet and the target number, so that in the end, we can return the triplet with the closest sum.
Sorting the array will take O(N* logN). Overall searchTriplet() will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).
The space complexity of the above algorithm will be O(N) which is required for sorting.
Triplets with Smaller Sum
Given an array arr of unsorted numbers and a target sum, count all triplets in it such that arr[i] + arr[j] + arr[k] < target where i, j, and k are three different indices. Write a function to return the count of such triplets.
Example 1
Input: [-1, 0, 2, 3], target=3
Output: 2
Explanation: There are two triplets whose sum is less than the target: [-1, 0, 3], [-1, 0, 2]
Example 2
Input: [-1, 4, 2, 1, 3], target=5
Output: 4
Explanation: There are four triplets whose sum is less than the target: [-1, 1, 4], [-1, 1, 3], [-1, 1, 2], [-1, 2, 3]
This problem follows the Two Pointers pattern and shares similarities with Triplet Sum to Zero. The only difference is that, in this problem, we need to find the triplets whose sum is less than the given target. To meet the condition i != j != k we need to make sure that each number is not used more than once.
Following a similar approach, first we can sort the array and then iterate through it, taking one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ and ‘Z’ such that X + Y + Z < targetX+Y+Z
Sorting the array will take O(N * logN). The searchPair() will take O(N). So, overall searchTriplets() will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).Ignoring the space required for the output array, the space complexity of the above algorithm will be O(N) which is required for sorting if we are not using an in-place sorting algorithm.
Subarrays with Product Less than a Target
Given an array with positive numbers and a target number, find all of its contiguous subarrays whose product is less than the target number.
Example 1
Input: [2, 5, 3, 10], target=30
Output: [2], [5], [2, 5], [3], [5, 3], [10]
Explanation: There are six contiguous subarrays whose product is less than the target.
Example 2
Input: [8, 2, 6, 5], target=50
Output: [8], [2], [8, 2], [6], [2, 6], [5], [6, 5]
Explanation: There are seven contiguous subarrays whose product is less than the target.
This problem follows the Sliding Window and the Two Pointers pattern and shares similarities with Triplets with Smaller Sum with two differences:
- In this problem, the input array is not sorted.
- Instead of finding triplets with sum less than a target, we need to find all subarrays having a product less than the target.
The implementation will be quite similar to Triplets with Smaller Sum.
The main for-loop managing the sliding window takes O(N) but creating subarrays can take up to O(N^2) in the worst case. Therefore overall, our algorithm will take O(N^3).
Ignoring the space required for the output list, the algorithm runs in O(N) space which is used for the temp list.
Can you try estimating how much space will be required for the output list?
Dutch National Flag Problem
Given an array containing 0s, 1s and 2s, sort the array in-place. You should treat numbers of the array as objects, hence, we can’t count 0s, 1s, and 2s to recreate the array.
The flag of the Netherlands consists of three colors: red, white and blue; and since our input array also consists of three different numbers that is why it is called Dutch National Flag problem.
Example 1
Input: [1, 0, 2, 1, 0]
Output: [0 0 1 1 2]
Example 2
Input: [2, 2, 0, 1, 2, 0]
Output: [0 0 1 2 2 2]
The brute force solution will be to use an in-place sorting algorithm like Heapsort which will take O(N*logN). Can we do better than this? Is it possible to sort the array in one iteration?
We can use a Two Pointers approach while iterating through the array. Let’s say the two pointers are called low and high which are pointing to the first and the last element of the array respectively. So while iterating, we will move all 0s before low and all 2s after high so that in the end, all 1s will be between low and high.
The time complexity of the above algorithm will be O(N) as we are iterating the input array only once.
The algorithm runs in constant space O(1).
Quadruple Sum to Target
Given an array of unsorted numbers and a target number, find all unique quadruplets in it, whose sum is equal to the target number.
Example 1
Input: [4, 1, 2, -1, 1, -3], target=1
Output: [-3, -1, 1, 4], [-3, 1, 1, 2]
Explanation: Both the quadruplets add up to the target.
Example 2
Input: [2, 0, -1, 1, -2, 2], target=2
Output: [-2, 0, 2, 2], [-1, 0, 1, 2]
Explanation: Both the quadruplets add up to the target.
This problem follows the Two Pointers pattern and shares similarities with Triplet Sum to Zero.
We can follow a similar approach to iterate through the array, taking one number at a time. At every step during the iteration, we will search for the quadruplets similar to Triplet Sum to Zero whose sum is equal to the given target.
Sorting the array will take O(N*logN). Overall searchQuadruplets() will take O(N * logN + N^3), which is asymptotically equivalent to O(N^3).
The space complexity of the above algorithm will be O(N) which is required for sorting.
Comparing Strings containing Backspaces
Given two strings containing backspaces (identified by the character ‘#’), check if the two strings are equal.
Example 1
Input: str1=”xy#z”, str2=”xzz#”
Output: true
Explanation: After applying backspaces the strings become “xz” and “xz” respectively.
Example 2
Input: str1=”xy#z”, str2=”xyz#”
Output: false
Explanation: After applying backspaces the strings become “xz” and “xy” respectively.
Example 3
Input: str1=”xp#”, str2=”xyz##”
Output: true
Explanation: After applying backspaces the strings become “x” and “x” respectively. In “xyz##”, the first ‘#’ removes the character ‘z’ and the second ‘#’ removes the character ‘y’.
Example 4
Input: str1=”xywrrmp”, str2=”xywrrmu#p”
Output: true
Explanation: After applying backspaces the strings become “xywrrmp” and “xywrrmp” respectively.
To compare the given strings, first, we need to apply the backspaces. An efficient way to do this would be from the end of both the strings. We can have separate pointers, pointing to the last element of the given strings. We can start comparing the characters pointed out by both the pointers to see if the strings are equal. If, at any stage, the character pointed out by any of the pointers is a backspace (’#’), we will skip and apply the backspace until we have a valid character available for comparison.
The time complexity of the above algorithm will be O(M+N) where ‘M’ and ‘N’ are the lengths of the two input strings respectively.
The algorithm runs in constant space O(1).
Minimum Window Sort
Given an array, find the length of the smallest subarray in it which when sorted will sort the whole array.
Example 1
Input: [1, 2, 5, 3, 7, 10, 9, 12]
Output: 5
Explanation: We need to sort only the subarray [5, 3, 7, 10, 9] to make the whole array sorted
Example 2
Input: [1, 3, 2, 0, -1, 7, 10]
Output: 5
Explanation: We need to sort only the subarray [1, 3, 2, 0, -1] to make the whole array sorted
Example 3
Input: [1, 2, 3]
Output: 0
Explanation: The array is already sorted
Example 4
Input: [3, 2, 1]
Output: 3
Explanation: The whole array needs to be sorted.
Our final algorithm will look like:
- From the beginning and end of the array, find the first elements that are out of the sorting order. The two elements will be our candidate subarray.
- Find the maximum and minimum of this subarray.
- Extend the subarray from beginning to include any number which is bigger than the minimum of the subarray.
- Similarly, extend the subarray from the end to include any number which is smaller than the maximum of the subarray.
The time complexity of the above algorithm will be O(N).
The algorithm runs in constant space O(1).
Maximum Trapping Water
Suppose you are given an array containing non-negative numbers representing heights of a set of buildings. Now, because of differences in heights of buildings water can be trapped between them. Find the two buildings that will trap the most amount of water. Write a function that will return the maximum volume of water that will be trapped between these two buildings.
Example 1
Input: [1, 3, 5, 4, 1]
Output: 6
Explanation: The maximum water will be trapped between buildings of height 3 and 4.
Example 2
Input: [3, 2, 5, 4, 2]
Output: 9
Explanation: The maximum water will be trapped between buildings of height 3 and 4.
Example 3
Input: [1, 4, 3, 2, 5, 8, 4]
Output: 20
Explanation: The maximum water will be trapped between buildings of height 4 and 4.
As we can clearly see, the amount of water trapped between two buildings is limited by the height of the shorter building. Which means that we can’t trap water more than the height of the shorter building. For example, if there are two buildings of height 3 and 4, the maximum water we can trap between them will be min(3, 4) = 3 units.
We can use a Two Pointers approach, starting with one pointer in the beginning and one at the end of the array. We will keep calculating the water trapped by the two buildings pointed out by the two pointers. As we discussed above, the limiting factor is the shorter building, therefore, whichever building is shorter, we will increment that pointer to see if we can get a better building.
The time complexity of the above algorithm will be O(N).
The algorithm runs in constant space O(1).
