Two Pointers - Design Approach

Two Pointers: A Powerful Technique for Efficient Problem-Solving

The two pointers design pattern is a versatile algorithmic approach that utilizes two pointers to traverse or manipulate data within an array, string, or linked list. This strategy fosters efficient solutions by avoiding redundant computations and often reduces time complexity from O(n^2) to O(n) in many cases.

Concept:

Imagine you have a data structure like an array or a string. The two pointers act as iterators, pointing to specific elements within the data. By strategically manipulating these pointers, you can perform various operations on the data in an efficient manner.

Types of Two Pointers:

• Two Pointers: This is the basic case where two pointers traverse the data structure in a coordinated fashion.
• Left and Right Pointers: Commonly used for problems involving window-based operations (e.g., finding the maximum sum subarray within a specific window size).
• Slow and Fast Pointers: Often employed for problems involving cycle detection (e.g., finding loops in linked lists).

Implementation:

The specific implementation of the two pointers pattern varies depending on the problem at hand. Here's a general breakdown:

1. Initialize Pointers: Set the initial positions of the two pointers based on the problem requirements.
2. Define Loop Condition: Establish a loop condition that determines when the traversal should stop.
3. Iterate and Process: The loop iterates, manipulating the data based on the values pointed to by the pointers. The pointers are updated strategically based on the problem logic (e.g., move one pointer forward, move both pointers in opposite directions, etc.).

Benefits:

• Efficiency: Compared to brute-force approaches, the two pointers pattern avoids unnecessary iterations, leading to significant performance improvements.
• Adaptability: This pattern can be applied to various problems with slight modifications in how the pointers move and interact with the data.

Examples:

1. Finding the Maximum Sum Subarray (Python and C#)

Problem: Given an array of integers, find the subarray with the maximum sum where the subarray size is fixed to k.

Python:

def max_sum_subarray(arr, k):
  """
  Finds the subarray with the maximum sum of size k in the given array.
  """
  window_sum = sum(arr[:k])  # Calculate sum of first k elements
  max_sum = window_sum
  left = 0
  
  for right in range(k, len(arr)):
    window_sum += arr[right] - arr[left]  # Update sum efficiently
    max_sum = max(max_sum, window_sum)
    left += 1
  
  return max_sum

# Example usage
arr = [1, 4, 2, 10, 6, 3, 5]
k = 3
max_sum = max_sum_subarray(arr, k)
print(f"Maximum sum subarray of size {k}: {max_sum}")
        

C#:

public static int MaxSumSubarray(int[] arr, int k)
{
  int windowSum = arr.Take(k).Sum();  // Use Linq for concise sum calculation
  int maxSum = windowSum;
  int left = 0;

  for (int right = k; right < arr.Length; right++)
  {
    windowSum += arr[right] - arr[left];
    maxSum = Math.Max(maxSum, windowSum);
    left++;
  }

  return maxSum;
}

// Example usage
int[] arr = { 1, 4, 2, 10, 6, 3, 5 };
int k = 3;
int maxSum = MaxSumSubarray(arr, k);
Console.WriteLine($"Maximum sum subarray of size {k}: {maxSum}");
        

This example demonstrates how the two pointers efficiently calculate the maximum sum subarray.

2. Finding the Longest Substring with K Unique Characters (Python and C#)

Problem: Given a string, find the length of the longest substring with at most k distinct characters.

Python:

from collections import defaultdict

def longest_substring_with_k_distinct(string, k):
  """
  Finds the length of the longest substring with at most k distinct characters.
  """
  char_count = defaultdict(int)
  left, max_length = 0, 0
  
  for right in range(len(string)):
    char_count[string[right]] += 1  # Increment count of current character
    
    # Slide window if we exceed the allowed distinct characters
    while len(char_count) > k:
      char_count[string[left]] -= 1  # Decrement count of leaving character
      if char_count[string[left]] == 0:
        del char_count[string[left]]  # Remove character if count becomes 0
      left += 1
    
    max_length = max(max_length, right - left + 1)  # Update max length

  return max_length

# Example usage
string = "eceba"
k = 2
max_length = longest_substring_with_k_distinct(string, k)
print(f"Length of longest substring with at most {k} distinct characters: {max_length}")
        

C#:

public static int LongestSubstringWithKDistinct(string str, int k)
{
  int[] charCount = new int[128]; // Assuming ASCII characters
  int left = 0, maxLen = 0;

  for (int right = 0; right < str.Length; right++)
  {
    charCount[str[right]]++;  # Increment count of current character

    // Slide window if we exceed the allowed distinct characters
    while (CountNonZeroElements(charCount) > k)
    {
      charCount[str[left]]--;  # Decrement count of leaving character
      left++;
    }

    maxLen = Math.Max(maxLen, right - left + 1);  # Update max length
  }

  return maxLen;
}

private static int CountNonZeroElements(int[] arr)
{
  int count = 0;
  for (int i = 0; i < arr.Length; i++)
  {
    if (arr[i] > 0)
    {
      count++;
    }
  }
  return count;
}

// Example usage
string str = "eceba";
int k = 2;
int maxLen = LongestSubstringWithKDistinct(str, k);
Console.WriteLine($"Length of longest substring with at most {k} distinct characters: {maxLen}");
        

Explanation:

1. We use a defaultdict (Python) or an integer array (C#) to keep track of the frequency of each character encountered in the string.
2. Two pointers, left and right, define the window boundaries.
3. The loop iterates through the string using the right pointer.
4. We increment the count of the current character (string[right]) in the frequency data structure.
5. We check if the number of distinct characters (len(char_count) in Python, CountNonZeroElements function in C#) exceeds the allowed limit k.
6. If the limit is exceeded, we slide the window by incrementing left. We also decrement the count of the leaving character and potentially remove it from the frequency data structure if its count reaches zero.
7. max_length is updated to track the longest valid substring seen so far.

Additional Problems Solvable with Two Pointers:

• Finding Pairs with a Specific Sum: Given an array of integers, find all pairs within the array that sum up to a specific target value.
• Trapping Rain Water: Given a 2D grid representing a terrain, find the amount of rainwater that could be trapped between the terrain blocks.
• Removing Duplicates from Sorted Array: Given a sorted array where duplicates are allowed, modify the array in-place to remove duplicates while maintaining relative order and returning the new length.
• Three Sum: Given an array of integers, find all triplets (three numbers) within the array that sum up to zero.
• Container With Most Water: Given an array of positive integers where the height of an index