Typically the arr needs to be sorted for this pattern to work.
If we can somehow reduce time by moving one pointer from the start and a second from the end.
Here, both pointers start from one end, but one skips ahead of the other based on some condition.
Implementation: PairWithTargetSum
Since the arr is sorted, we can take a pointer at index 0 and another at index len-1 (0-indexed). If the sum of the elements at these two pointers is > target, we move the right pointer which should give us a smaller sum, else we move the left pointer, which should give us a greater sum. If the sum matches, we return the pair.
O(N) because in the worst case, we traverse through all elements.
O(1)
Implementation: RemoveDuplicates
Since the arr is sorted, the duplicates would appear one after the other. We keep track of the index of the array where there are no duplicates and increment the index iff its a unique element. If its a duplicate, we skip ahead.
O(N)
O(1)
Implementation: SquareSortedArray
We take two pointers, one starting from the start of the arr and one from the end. If the abs value of the start element is greater than the end element, the sq must also be greater. Since we want the result sorted, we put that element at the end. If its smaller, we do the reverse.
O(N)
O(1) if we ignore the result array.
Implementation: TripletSumToZero
The same as #1, for triplet sum, select one element and find the duplet sum to match.
One caveat is we dont want low to start from 0 for the duplet sum. The reason is, if there was a previous element that, with the current element, made the target, then we would have found that combination when we called duplet sum with that previous element.
O(N^2), which is still a savings from O(N^3)
O(1)
Implementation: TripletSumCloseToTarget
Pretty much the same as the last one.
Implementation: TripletsWithSmallerSum
Similar to the one above.
Sorting takes O(nlogn). The outer loop will take O(n) time. The inner while loop and for loop in searchDuplets() will take O(n^2) time, so the total time is O(n^3).
O(1)
Implementation: SubArraysWithProductLessThanTarget
As we progress with high, on every iteration, add that combination into the result list. If the product exceeds target, shrink the window by moving low to the right.
O(n^3)
O(1) for the temp list.
Implementation: DutchNationalFlag
Taking an example, [1, 0, 2, 1, 0], we can take three pointers: low(l), high(h) and counter(c)
That way, all 0's would shift to the left of l, all 1's will remain in the middle and all 2's would shift to the right. Making the arr sorted.
1 0 2 1 0
l/c h
0 1 2 1 0
l/c h
0 1 0 1 2
l c h
0 0 1 1 2
l c/h
We need to be careful when the current element is replaced with anything other than 1. We only move c when its equal to 1, so we dont miss swapping and 0 or 2.
The terminating condition is when c == h.
O(n)
O(1)
Implementation: CompareStringsWithBackspaces
Example:
Input: str1="xy#z", str2="xzz#"
Output: true
Explanation: After applying backspaces the strings become "xz" and "xz" respectively.
If we start comparing both strings from the left, since # comes after, we wouldnt know if what we are doing is a valid comparison.
If we start comparing from the right,
p1
x y # z
x z z #
p2, p2 is not a valid comparison, move left
p1
x y # z
x z z #
p2
comparison works, move both p1 and p2
p1
x y # z
x z z #
p2
cannot compare, move p1
p1
x y # z
x z z #
p2
comparison works
For, str1="xp#", str2="xyz##"
When there are more than 1 # in a row, we need to check from the inner-most one. Which means the "starting from right" logic wont work.
To tweak it, say
p
x y z # #
backspaceCnt = 1
p
x y z # #
backspaceCnt = 2
p
x y z # #
backspaceCnt = 2, backspaceCnt > 0, cannot return z, skip and reduce cnt
p
x y z # #
backspaceCnt = 1, backspaceCnt > 0, cannot return y, skip and reduce cnt
p
x y z # #
backspaceCnt = 0, can return this char
O(n)
O(1)
Implementation: MinWindowSort
To sort the array, we need to find the out of order min and max of the array. Any number thats not in order relative to the positions of min and max, needs to be moved to sort the array.
Example:
1 2 5 3 7 10 9 12
From the left, till 5 the array is sorted, so first non-sorted is 3
From right, till 9, the array is sorted.
So, 3 -> 10 becomes our candidate array. The min of this subarray is 3 and max 10.
Extend the subarray to include all numbers greater than min and lesser than max to include numbers not as part of the subarray but will need to be move if we are to sort the array.
O(n)
O(1)