The two pointer technique is a must-know strategy for technical interview candidates. It allows solving a class of problems efficiently by using two pointers to iterate through arrays or linked lists.

In this post, we will cover:

• What is the two pointer technique and when should you use it?

• Common patterns that use the two pointer technique

• Examples of interview questions solved with two pointers along with complexity analysis

• Tips to identify if a problem can be solved with two pointers

What is the Two Pointer Technique?

The two pointer technique involves using two pointers to iterate through a data structure like an array or linked list. The key property is that the pointers move through the data structure in tandem, enabling us to compare or correlate the elements they point to.

This technique shines when we need to find paired elements that satisfy certain constraints or conditions. The pointers allow checking the elements in a single iteration.

When to Apply the Two Pointer Technique

Use two pointers when:

• The data is organized in a linear structure like an array, string, or linked list

• The problem constraints involve finding paired elements (e.g. comparing adjacent elements)

• The data has some order relevant to the problem (e.g. sorted or symmetric)

The two pointers move towards a target by closing in from different ends of the data structure. This exploits the existing order in the data without needing nested loops.

Common Two Pointer Patterns

Some standard patterns that use the two pointer technique are:

Left and Right Pointer

• Time Complexity: O(N)

• Space Complexity: O(1)

This pattern is used when the data has symmetry or requires comparing elements from each end. For example:

• Check if a string is a palindrome

• Check if a linked list is a palindrome

# Check if a word is palindrome

def check_palindrome(word):
    left, right = 0, len(word) - 1
    while left < right:
      if word[left] != word[right]: 
        return False
      left += 1
      right -= 1
    return True

Fast and Slow Pointer

• Time Complexity: O(N)

• Space Complexity: O(1)

This pattern uses two pointers moving at different speeds through the data structure. Examples:

• Detect if a linked list has a cycle

• Find the middle node of a linked list

# Detect cycle in linked list

def detect_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
      slow = slow.next 
      fast = fast.next.next
      if slow == fast: 
        return True # cycle exists
    return False

Window Pattern

• Time Complexity: O(N)

• Space Complexity: O(1)

This pattern constrains a “window” of elements between the pointers. Examples:

• Find maximum sum subarray of size k

• Longest substring with k distinct characters

# Find max sum subarray of size k
def max_subarray(arr, k):
    left = 0 
    curr_sum = 0
    
    for right in range(len(arr)):
      curr_sum += arr[right]
      if right >= k-1:
        max_sum = max(max_sum, curr_sum)
        curr_sum -= arr[left]
        left += 1

    return max_sum

Merge Arrays

In this pattern, you are given 2 arrays/lists to process using individual pointers. Examples:

• Merge two sorted arrays

• Find intersection of two unsorted arrays

def merge_sorted_arrays(nums1, nums2):
  
  # Set pointers for both arrays
  p1 = 0 
  p2 = 0

  # Initialize result array
  result = []

  # Compare elements at pointers and add smaller to result
  while p1 < len(nums1) and p2 < len(nums2):
    if nums1[p1] < nums2[p2]:
      result.append(nums1[p1])
      p1 += 1
    else:
      result.append(nums2[p2])
      p2 += 1

  # Add remaining elements from nums1  
  while p1 < len(nums1):
    result.append(nums1[p1])
    p1 += 1

  # Add remaining elements from nums2
  while p2 < len(nums2):
    result.append(nums2[p2])
    p2 += 1

  return result

Here are some tips to identify if a problem can be solved efficiently using the two pointer technique:

• The problem involves finding pairs or comparing elements

• The data is arranged sequentially like an array or string

• There is some inherent order in the data like sorting or symmetry

• The naive solution involves nested loops (quadratic complexity)

• Eliminating one potential solution does not affect other solutions

If these indicators are present, try modeling the problem with two pointers!

Conclusion

The two pointer technique is a simple but powerful pattern that every interview candidate should have in their toolkit. Practice applying it to questions involving arrays, strings, linked lists, and sliding windows. Getting good at efficiently iterating with pointers can make a difference in passing your technical interviews!

If you enjoyed this post and want to keep improving your coding interview skills, subscribe to our newsletter below for regular tips and Daily Interview Practice with LeetCode Questions delivered to your inbox.