Common patterns

Pre-requisite

Typically the arr needs to be sorted for this pattern to work.

Pointers from both sides

If we can somehow reduce time by moving one pointer from the start and a second from the end.

Skip-ahead pointers

Here, both pointers start from one end, but one skips ahead of the other based on some condition.

Questions

Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

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.

Time complexity

O(N) because in the worst case, we traverse through all elements.

Space complexity

O(1)

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 length of the subarray that has no duplicate in it.

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.

Time complexity

O(N)

Space complexity

O(1)

Given a sorted array, create a new array containing squares of all the numbers of the input array in the sorted order.

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.

Time complexity

O(N)

Space complexity

O(1) if we ignore the result array.

Given an array of unsorted numbers, find all unique triplets in it that add up to zero.

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.

Time complexity

O(N^2), which is still a savings from O(N^3)

Space complexity

O(1)

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.

Implementation: TripletSumCloseToTarget

Pretty much the same as the last one.

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.

Implementation: TripletsWithSmallerSum

Similar to the one above.

Time complexity

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).

Space complexity

O(1)

Given an array with positive numbers and a positive target number, find all of its contiguous subarrays whose product is less than the target number.

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.

Time complexity

O(n^3)

Space complexity

O(1) for the temp list.

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.

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.

Time complexity

O(n)

Space complexity

O(1)

Given two strings containing backspaces (identified by the character ‘#’), check if the two strings are equal.

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

Time complexity

O(n)

Space complexity

O(1)

Given an array, find the length of the smallest subarray in it which when sorted will sort the whole array.

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.

Time complexity

O(n)

Space complexity

O(1)

Return to Index