Competitive Programming #2: Two Pointers

The two-pointer technique is a common algorithmic approach for solving problems on arrays or linked lists. It involves using two pointers to iterate through the data structure, often leading to more efficient solutions. This technique finds pairs, subarrays, or meeting conditions involving elements at different data structure positions.

Issue #1: Find an array's target sum of two elements.

Consideration: Sorted Array

Two Pointers * Photo By Author

In the above example, we are trying to find a target sum of two numbers from a sorted array where two pointers are started from two ends and iterate the array based on the following condition:

1. If P1 + P2 > Target; then move P2
2. If P1 + P2 < Target; then move P1

def tpa(target, arr):
    i = 0
    j = len(arr) - 1
    while i < j:
        find_sum = arr[i] + arr[j]
        if find_sum > target:
            j -= 1
        elif find_sum < target:
            i += 1
        else:
            return f"Found the target and the values are: {arr[i]}, {arr[j]}"
    return "Target not found!"


print(tpa(29, [3, 4, 8, 20, 25, 30]))

• Time Complexity: O(n)
• Space Complexity: O(1)

In the two-pointer technique, the pointers often move toward each other rather than maintaining a contiguous “window.”

Consideration: Unsorted Array

What about an unsorted array? Can we still apply the two-pointers?

The answer is yes. We still can, but we need to sort the array.

Sorting + Two Pointers:

• Step 1: First, sort the array. This takes O(n log⁡n) time.
• Step 2: Apply the two-pointer technique for a sorted array.
• Total Time Complexity: O(n log⁡n) due to the sorting step.

Question: Is there any way we can make the process faster?

Answer: Yes, we can use a hash set.

def tpa_unsorted_array(target, arr):
    store = set()
    for i in arr:
        find_sum = target - i
        if find_sum in store:
            return (find_sum, i)
        store.add(i)

• Time Complexity: O(n)
• Space Complexity: O(n) because of the hash set.

Let's consider a fairly complex example to understand the concept of the two pointers:

"Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' Means a backspace character.

Note that the text will continue empty after backspacing an empty text."

Reference: Backspace String Compare
Follow up: Can you solve it in O(n) time and O(1) space?

Target:

In the problem, "#" means a backspace needs to be done in the string. There can be multiple backspaces, and based on that, we need to do backspace, which means removing a character from the string.

1. Find a valid index to compare.
2. If the index number isn't valid, then return false.
3. If the comparison doesn't match, then return False.
4. Otherwise, return true.

def backspaceCompare(self, s: str, t: str) -> bool:
        def valid_index(s: str, index: int) -> int:
            backspace_count = 0
            while index >= 0:
                if s[index] == '#':
                    backspace_count += 1
                elif backspace_count > 0:
                    backspace_count -= 1
                else:
                    break
                index -= 1
            return index
                    
        s1 = len(s) - 1
        t1 = len(t) - 1

        while s1 >= 0 or t1 >= 0:
            s1 = valid_index(s, s1)
            t1 = valid_index(t, t1)

            if s1 >= 0 and t1 >= 0 and s[s1] != t[t1]:
                return False
            if (s1 >= 0) != (t1 >= 0):
                return False

            s1 -= 1
            t1 -= 1
        return True

Let's explain both if condition where it returns False.

Photo By: Author

In the solution, the valid_index() function sends back the current index after backspacing the string. After applying the backspace, these indexes are returned, and the index values are checked to see if they are valid. If valid and both characters match, return true; otherwise, return false.

The two-pointer is successfully applied in the above problem.

Photo By: Author

When to use the two-pointer technique?

1. Sorted Array/Linked Lists
2. Palindrome Check
3. Merging Two Sorted Arrays/Linked Lists
4. Partitioning Problems
5. Sliding Window Problems
6. Finding the Middle of a Linked List: Finding the middle element in one pass. Use two pointers: one that moves one step at a time (slow pointer) and another that moves two steps at a time (fast pointer). The slow pointer will be in the middle when the fast pointer reaches the end.

Early termination and reducing redundant operations could lead to an optimal solution during the two-pointer technique.

The two-pointer technique is robust for various problems, especially involving sorting. You can gain efficiency by moving pointers in opposite directions. The key to using it optimally lies in understanding the problem constraints and ensuring that the pointers are transferred in a way that progressively narrows down the search space.