Minimize memory requirements using two pointers

The two pointer technique is a programming technique used to efficiently solve problems by using two pointers or references, that iterate over elements in an array or a sequence. The technique involves initializing two pointers at different positions in the array and then adjusting the pointers based on the problem’s requirements (closer or further apart). It’s a practical approach to solving coding problems in linear time complexity O(n) using minimal additional memory space.

When might you consider using it?

This is a great approach to problems involving arrays or linked lists where the goal is to find pairs, check for palindromes, merging sorted arrays or linked lists, removing duplicates, checking for cycles and more. It’s not always a requirement for the data to be sorted but it will depend on the constraints of the problem.

There are a few different ways you can take advantage of the two-pointer technique. The main difference is in how the pointers move through the array in relation to one another. You could describe the different behavior as:

• Merging - Two pointers start on each end of the array and merge together until they meet
• Conditional merging - Two pointers start at each end but only one is adjusted based on a calculation
• Racing - Two pointers start at the same index but one is incremented at a different speed

Merging two-pointers

Checking for palindromes

To determine if a string or array is a palindrome (reading the same forwards and backwards) the two pointer technique is a great and simple approach. One pointer starts at the beginning and the other at the end, and they move towards the center (merging), comparing elements at each step. The loop is only broken if:

1. Both pointers point to the same index.
2. The value each pointer points to is not the same.

Implementing a two-pointer solution

To check a word or a sentence for a palindrome we can use the two-pointer technique. Some additional considerations that will need to be made are the occurrences of non-alphanumeric characters such as spaces and special characters (!, &, %, etc.).

The full source code can be found here.

def isPalindrome(self, s: str) -> bool:
    if len(s) == 1:
        return True

    left, right = 0, len(s) - 1

    while left <= right:
        # handle the case where left or right is pointing to a non-alphanumeric element
        if not s[left].isalnum():
            left += 1
            continue
        elif not s[right].isalnum():
            right -= 1
            continue

        # check that both pointers point to the same element
        if s[left].lower() != s[right].lower():
            return False

        # left and right merge together in step
        left += 1
        right -= 1

    return True

Setting things up

left, right = 0, len(nums) - 1

The left and right pointers need to start at opposite end of the array before they start merging to ensure we’ve checked all the elements. left is assigned the starting index 0 while right is assigned the last index in the array (len(s) - 1).

Merging the left and right pointers

while left < right:

To run the palindrome check we create a while loop that continues until left and right meet. The loop breaks if we find the left and the right pointer elements are not the same.

Handling the edges

if not s[left].isalnum():
    left += 1
    continue
elif not s[right].isalnum():
    right -= 1
    continue

If one of our pointers points to an element in s that’s not an alphanumeric character such as an exclamation point, that pointer will need to be adjusted to skip over for the next iteration.

Merge the left and right pointers

left += 1
right -= 1

If both pointer elements match, we need to adjust the left and the right for the next iteration of the loop. left moves toward the end while right moves toward the start.

Conditionally merging two-pointers

Finding a pair that sum to a target

When given a sorted array and asked to find a pair of elements that sum up to a target value, using the two pointer technique can be an efficient approach. By initializing one pointer at the beginning of the array and another at the end, you can adjust the pointers inward based on whether the current sum is too small or too large. Both pointers merge together until they point to the same index in the array, at which point we break out of the loop and return a result.

Implementing a two-pointer solution

Let’s take a look at implementing the two-pointer technique to solve the problem of finding the sum that equals a target. For this solution, the input must be sorted in order for the technique to work efficiently.

The full source code can be found here.

def FindPairSum(self, nums: List[int], target: int) -> List[int]:
    left, right = 0, len(nums) - 1

    while left < right:
         # get the current sum of the left and right pointers
        _sum = nums[left] + nums[right]

        # decide which pointer needs to move
        if _sum == target:
            return [left, right]
        elif _sum < target:
            left += 1
        else:
            right -= 1

    # target is not in the list
    return [0, 0]

Setting things up

left, right = 0, len(nums) - 1

Before we begin searching for the sum we need to set up our left and right pointers. left is initialized to 0 so it points to the starting element in the array while right points to the element at the last index of the array.

Merging the left and right pointers

while left < right:

This is a key part in using the two-pointer technique. We need a stopping point when adjusting our left and right pointers. If we haven’t found target, left and right will merge together until they meet, at which point we will leave the loop and return some value.

Deciding which pointer moves

if _sum == target:
    return [left, right]
elif _sum < target:
    left += 1
else:
    right -= 1

Our first check is to see if _sum adds up to the target. If that condition matches, you’ve found the indexes of the elements that add up to the target. If you haven’t found target then it’s time to decide which pointer needs to be adjusted.

This is where having a sorted array is crucial. When _sum is less than target we need to adjust the left pointer because the left side of nums will contain a larger integer that might add up to our target. Vice versa, if _sum is larger than target we need to adjust the right pointer because the right side of nums contains a smaller integer.

Container with the most water

This is a classic “maximum area” problem: given an array height, choose two walls such that the container they form holds the most water. Each element in height represents a wall, and the water level is always limited by the shorter of the two walls.

Instead of comparing every possible pair, use a two-pointer approach. Start with one pointer at each end of the array and gradually shrink the window. On each step, calculate the area and move only the pointer at the shorter wall, since that wall is the limiting factor. Both pointers move toward the center, efficiently exploring all viable candidates in linear time.

Implementing a two-pointer solution

Start with two pointers: left at the beginning of height and right at the end. Together they form a container with area (right - left) * min(height[left], height[right]). Track the maximum area seen so far.

On each iteration, move the pointer at the shorter wall inward, since the shorter wall limits the water level. Continue the loop until both pointers meet.

The full source code can be found here.

def MaxArea(self, height: List[int]) -> int:
    max_area = 0
    left, right = 0, len(height) - 1

    while left < right:
        container_width = right - left
        container_height = min(height[left], height[right])

        max_area = max(max_area, container_height * container_width)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

Setting things up

left, right = 0, len(height) - 1

left and right begin at opposite ends of height so the first area check uses the widest possible span. As we move these pointers closer, the width shrinks, so we only shift the pointer that currently limits the container height.

Calculating the container area

container_width = right - left
container_height = min(height[left], height[right])
max_area = max(max_area, container_height * container_width)

At each step we compute the rectangle formed by the two bars. Since water can only rise as high as the shorter bar, we take the min of the heights before multiplying by the distance. Tracking max_area lets us capture any improvement as the pointers converge.

Deciding which pointer moves

if height[left] < height[right]:
    left += 1
else:
    right -= 1

If the left bar is shorter, moving left might find something taller that beats the current area, whereas moving right would only reduce width without increasing height. Symmetrically, when the right bar is shorter we move right. This greedy rule ensures every iteration removes the limiting bar and keeps the algorithm at O(n) while still evaluating every viable container pair.

Racing two-pointers

Move the Zeros to the End

Imagine being given an array with a collection of integers and being asked to move all of the zeros to the end while keeping the relative position of all other numbers. You might think this is a fairly simple task and opt to copy the contents into a new array by looping over and pushing in elements that aren’t zero. Now what if you didn’t have an abundance of memory to make a second copy of the array? You’d need to find a way to adjust the elements in place. This is a great task for the two-pointer technique to solve.

Implementing a two-pointer solution

The solution begins by starting the left and right pointers at the beginning of the array. For the sake of consistency I’m going to keep using the variable names left and right but you can choose to give each pointer a more appropriate name such as fast and slow. Instead of both pointers merging together like we’ve seen in previous solutions, one of the pointers, right will maintain the loop as long as it doesn’t reach the end. If we detect a zero with the condition if left < len(nums) and nums[left] == 0: then we continue advancing the right pointer until either it gets to the end of nums or finds a suitable replacement for the swap. A simple swap is performed using a temporary variable (tmp) to move the zero while maintaining the relative order of all the non-zero elements. If instead there’s no zero detected with if left < len(nums) and nums[left] == 0: then we advance both left and right pointers for the next loop iteration.

The full source code can be found here.

def MoveZeroes(self, nums: List[int]) -> None:
    left, right = 0, 0

    # keep going until there are no more numbers to swap with
    while right != (len(nums) - 1):
        if left < len(nums) and nums[left] == 0:
            # advance right until its at the next non-zero
            while right != (len(nums) - 1) and nums[right] == 0:
                right += 1

            # do the swap
            tmp = nums[left]
            nums[left] = nums[right]
            nums[right] = tmp

            # only move the left
            left += 1
        else:
            # move the left and the right
            left += 1
            right += 1

    print(nums)

Setting things up

left, right = 0, 0

We start out setting the left and right pointers at the first index of nums.

Racing the left and right pointers

while right != (len(nums) - 1):

The right pointer dictates when the loop ends because it must search for a suitable position to swap the zero (if one is detected). This means the while loop will continue as long as the right pointer has not been advanced past the last index of nums.

Searching for a replacement

if left < len(nums) and nums[left] == 0:
    while right != (len(nums) - 1) and nums[right] == 0:
        right += 1

If left has not reached the end of nums and points to a zero then we begin the search with the right pointer. while right != (len(nums) - 1) is our guard to keep the right pointer in bounds while nums[right] == 0: continues advancing right until a non-zero integer is found.

Swapping the left and right elements

tmp = nums[left]
nums[left] = nums[right]
nums[right] = tmp

left += 1

A simple tmp variable is used to swap the elements left and right point to. This is how we achieve the movement of a zero in place without the need to make any copies. After the swap, we advance only the left pointer so we can move along to the next potential candidate for a swap and to maintain the relative ordering of all the non-zero elements in nums.

If we didn’t detect a zero

else:
    left += 1
    right += 1

If we didn’t detect that the left pointer was pointing to a zero, both left and right are advanced for the next loop iteration. To prevent us from getting caught in an infinite loop, it’s important that the right pointer is advanced along with the left pointer.

What we’re left with is an array (nums) that has all zeros moved to the end without changing the relative ordering of all the non-zero elements.