We will be continuing our study of the two pointer pattern for solving LeetCode questions in this post. Let’s begin!

Problem #14 – Triplets with Smaller Sum

We are still on the genre of problems involving triplets i.e. three numbers in an array that satisfy a particular condition. In this case, we’re looking for three unique indices that are smaller than a given target number. Once again, we’ll be using our previous findings of having a main for loop with an additional while loop to use the two pointer pattern.

We have two if cases: one where the sum is lesser than the target (our goal condition) and another where the sum is greater than or equal to the target. The latter case is easy, as all we have to do is subtract our second pointer to make the sum smaller. But in the first case, we need to be careful to do one little track: we can add all valid combinations in one shot by adding the numbers in between our first and second pointer. Because our array is sorted, if we find a valid triplet i, j, k, by default all elements in between j and k are valid too. We add those and then shift j forward, so we can check everything from i, j + 1, and k similarly.

Problem #15 – Subarrays with Product Less than a Target

Now we are modifying the problem again to work with subarrays instead of pairs or triplets. With subarrays, there can be multiple numbers that satisfy the condition, so our solution needs to work with that in mind. We can not longer sort the array because we want contiguous subarrays of our array. Sorting would break the chain of elements and jumble them up, and we can’t have that.

My rating of this problem: 9/10 difficulty. There are various things to take care of in this problem. You need to add each valid subarray as a list, sorting isn’t allowed, and you need to do this efficiently. Of course, we have the brute-force two for loop solution which will be O(N^2). While the technique we will be using is also O(N^2) in time complexity, it is much better memory/space complexity wise. The solution is cleaner as well! Here, we will be combining a pattern we will look at deeper later on with the two pointer pattern. And that is the sliding window technique. For now, let’s just remember that this technique comes in handy with a lot of contiguous subarray problems.

The solution works like this. We begin loop through the array with a normal for loop. Let’s call our iterating variable ‘right’. Outside, we will have already declared a variable ‘left’ which will be the left side of our window. The point of this pattern is to shift our window i.e. our right pointer until the products we calculate till there are valid. The moment we notice a product that is greater than or equal to the target, we shrink our window. The way we do that is by removing the element that our left pointer contains and then shift the variable by one unit. We will do this within a while loop because there could be, plausibly, multiple elements we need to remove and it is efficient to get them all out of the way at that point.

Now, we will be left with a situation where all elements from left to right form a valid product. At this point, we will see a trick that is frequently used with subarrays that meet a certain target, exactly like this problem. At this point, default thinking leads us to calculate subarrays from the left to the right. But the cleaner and optimized approach will be to iterate backwards to build valid subarrays. This is called a prefix product. At this point, you’re probably as confused as I was, so let’s take an example to understand better. Array = [2, 3, 4], left = 0, right = 0, and target = 10. ‘Right’ is our iterating variable and left is the left boundary of our sliding window.

In the first iteration, we have element 2, which is valid, so we add [2] to our result. We move to the next element where our product becomes 6. Still valid. So we add numbers backwards, adding [3] as well as [2, 3]. We don’t need to recheck anything while going backwards because all prefixes of a valid product are also valid subarrays. This avoids the need to constantly start multiplying from any new outer loop element we find. The solution is still O(N^2) and O(1) memory, but it is much more efficient, especially in the case of large input arrays.

Problem #16 – Dutch National Flag Problem

Given an array containing 0s, 1s, and 2s, we need to sort the array in-place. Which means no additional memory allowance.

You have the obvious in-place sorting solution which will be O(N log N) time and space complexities, but we’re trying to impress our interviews, and this is probably only going to impress your grandmother and your dog. So, what can be done?

We create two key pointers low and high which let us keep track of the 0’s and the 2’s. We also have additional variables which are set to 1 – which we’re going to call the “pivot”, because elements less than 1 should be at the left (which are the 0’s) and elements greater should be at the right (the 2’s). Finally, we have our trusty iterating pointer that helps us go through the array. The idea is to keep checking every element in comparison to the pivot. Is it greater or smaller? If it is smaller, we want to swap it with our low pointer and increment it. You may ask:

If the current element is greater than the pivot, we want to swap that element with the element at the high pointer. There is an important thing to consider here. array[high] could be 2 as well. Meaning, we would not be changing anything in the array, so what we need to do is to decrement the high pointer but not increment the iterating index. This is so we can check that against the second last element. We didn’t have to do this in the first case because array[i] was guaranteed to be the lowest and going to the right spot. Even if there was another zero at the beginning and our swap did not do anything, we would eventually get to the second zero as well. In the second case, we would skip over a 2 which would make our answer incorrect. So, there’s the solution!

This solution is O(N) time complexity and O(1) space complexity.

Problem #17 – Quadruple Sum to Target

This problem is a good test to check your understanding of all the pairs and triplets problems we have been doing. The technique is exactly the same as we used before i.e. sorting the array first. We have two for loops, one for finding i and other for j. We need two more numbers for a quadruple which will be handled by the two pointers we create.

Similar to the triplets problem, we want to make sure all duplicates are handled properly, and for that, we need to check all elements with the element prior to them. If they’re equal, we want to skip this iteration. This is handled within the two pointer patter case in the equality case: if we find two valid numbers that create a quadruple, we increment both left and right pointers, and then skip over any duplicates found in both cases like so –

while left < right:
    sum_ = array[i] + array[j] + array[left] + array[right]
    
    if sum_ == target:
        result.append([array[i], array[j], array[left], array[right]])
        left += 1
        right -= 1

        while left < right and array[left] == array[left - 1]:
            left += 1

        while left < right and array[right] == array[right + 1]:
            right -= 1

Problem #18 – Comparing Strings Containing Backspaces

In this problem, we’re given two strings which can contain a backspace character, represented by ‘#’. We need to check if these strings are equal after the backspace is applied to the strings.

The immediate solution that pops to my head after reading the problem is to use two stacks. With a stack, we will be able to append the characters one by one and the moment we find a #, we can pop the previously added character from the stack. At the end, we compare the two stacks for the answer. With this solution, you do have to take care of an edge case where you can have strings with just the # character which would be a pop operation done in an empty list. No bueno.

The time complexity for this solution is O(N) whereas the space complexity will be O(N) as well. Can we do better?

We can use two pointers and a clever string indexing technique to reduce the space complexity to O(1). Let’s declare two pointers that tracks the indices of each string, starting from the back. We start iterating backwards. Now, the goal is to compare each element, and if they’re not equal, we return False immediately. If they’re equal, we shift both pointers to the next element. But the tricky part here is the backspace. My default thinking made me subtract 2 from the pointer every time you encounter a backspace because you need to remove the backspace as well as the prior element. Although this passed some easy test cases, it failed many because there can be multiple backspace characters joined into one.

Thus, your solution needs to be a bit more robust than that. The way to do that would be to have another loop that keeps a count of backspaces encountered and processed. If a backspace is found, increment the count. Shift the pointer back. If a valid letter is found, subtract the count i.e. process the backspace and shift the pointer back. Only stop this inner loop if our backspace count is zero and the current character is valid.

Doing this makes sure that the characters you end up with in string1 and string2 are both valid. Now you can check them normally. There two final edge cases you need to cover where both strings may reach -1, which can happen when you deal with strings like ‘#’ and ‘#’, for example. This means you have reached the end of both strings. In such cases, we need to return True, as both strings are equal. And the other case is when you reach the end of only one of the strings: string1[ptr1] < 0 or string2[ptr2] < 0.¹

Problem #19 – Minimum Sort Window

We need to find the length of the smallest subarray to sort in order to end up with a whole sorted array. Sometimes the array can already be sorted and sometimes the answer will be the entire array. But the goal is to find the smallest length, if available.

The answer is going to be the sliding window pattern once more. We will need to find the first cases from the front and the back where the items initially get unsorted. From the front, it’ll be when the the first element to the right is smaller than the current element. From the back, it’ll be when the first element to the left is larger than the current element.

You’d guess that this will be the answer, but no! We need to expand the window to capture any other items that are unsorted. Look at this test case: [1, 3, 2, 0, -1, 7, 10]. You would think that the answer is [3, 2, 0, -1] => 4 but it’s not! The answer is actually [1, 3, 2, 0, -1] => 5. The window we have in the beginning is [3, 2, 0, -1], so what’s missing? Although 1, 3 was sorted when we initially found our window, we could have foreseen that we would find a 0 later in the list! This is exactly why we must extend our sliding window further once we find it.

The logic of extending the window will be as follows: if you find an element to the left that is greater than the minimum of our current window, extend our window to the left; if you find an element to the right that is smaller than the maximum of our current window, extend our window to the right. When we return, we don’t need to supply the actual subarray, so we can return left – right + 1, which’ll be the length of the subarray.

1. An OR operator also returns True when both cases are True. Usually. But in this case, we will add the case of the same statement with an AND operator right before, so the OR only catches the case where one is empty and the other is not ↩︎