> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Two Pointers Pattern

> Master the two pointers technique for array and string problems

<img className="block rounded-lg" src="https://mintcdn.com/devweeekends/8SzFxu49daVetHjN/images/dsa-techniques/01-two-pointers.svg?fit=max&auto=format&n=8SzFxu49daVetHjN&q=85&s=f946659961d52020120deabdc320fe22" alt="Two Pointers Pattern" width="1080" height="1080" data-path="images/dsa-techniques/01-two-pointers.svg" />

## Pattern Recognition Cheatsheet (Read This First)

<Tip>
  **Reach for Two Pointers when the problem statement says...**

  | Problem phrasing                                           | Variant                             |
  | ---------------------------------------------------------- | ----------------------------------- |
  | "sorted array" + "find pair / two numbers that sum to X"   | Converging (LC 167)                 |
  | "find all unique triplets that sum to zero"                | Sort + fix one + converge (LC 15)   |
  | "find all unique quadruplets that sum to target"           | Sort + fix two + converge (LC 18)   |
  | "is the string a palindrome (ignoring punctuation)"        | Converging from both ends (LC 125)  |
  | "container with most water" / "two lines forming max area" | Greedy converging (LC 11)           |
  | "trap rain water between bars"                             | Converging with running max (LC 42) |
  | "remove duplicates from sorted array in-place"             | Fast/slow (LC 26, LC 80)            |
  | "move all zeros to end / partition by parity"              | Fast/slow (LC 283)                  |
  | "sort array of 0s, 1s, 2s in-place"                        | Three pointers (Dutch flag, LC 75)  |
  | "merge two sorted arrays in-place into the first"          | Reverse converging from end (LC 88) |
  | "detect cycle / find middle of linked list"                | Fast/slow (Floyd's, LC 141, LC 876) |
  | "squares of sorted array (with negatives)"                 | Converging, write from end (LC 977) |
  | "valid palindrome after deleting at most one char"         | Converging with branch (LC 680)     |
  | "reverse string / vowels / array in-place"                 | Converging swap (LC 344, LC 345)    |

  **Hard signal:** the array is sorted (or you can sort), AND you need to find pairs / triplets / partitions, AND you want O(1) extra space. That is the Two Pointers calling card. If sorting is forbidden or destroys the answer, use HashMap instead.
</Tip>

## What is Two Pointers?

The **Two Pointers** pattern uses two pointers to traverse an array or string, typically moving towards each other or in the same direction. It transforms O(n squared) brute force solutions into O(n) optimal ones.

<Note>
  **Quick Recognition**: If you see a **sorted array** + need to find **pairs/triplets** + want **O(1) space**, Two Pointers is likely the answer.
</Note>

## Canonical Template Code

This is the boilerplate. Memorize it. Then specialize for the problem.

<CodeGroup>
  ```python Python theme={null}
  # THE Two Pointers template (converging variant). Memorize this shape.
  def two_pointers_converging(arr, target):
      # left starts at the smallest index, right at the largest -- gives us
      # control over the *sum* (or *area*, *length*, etc.) by moving inward
      left, right = 0, len(arr) - 1

      while left < right:                  # strict < because we never want left == right
                                            # (using the same index for both pointers is a bug
                                            #  for sum problems -- you would use one element twice)
          current = arr[left] + arr[right]  # the quantity we are optimizing / matching

          if current == target:
              return [left, right]          # found it -- return early
          elif current < target:
              left += 1                     # need a LARGER value; the smallest available is at left+1
          else:
              right -= 1                    # need a SMALLER value; the largest available is at right-1

      return [-1, -1]                      # exhausted all valid pairs without finding target


  # THE Two Pointers template (fast/slow variant). For in-place rewrites.
  def two_pointers_fast_slow(arr, predicate):
      # slow tracks the "write position" -- where the next valid element goes
      # fast scans through every element once
      slow = 0

      for fast in range(len(arr)):
          if predicate(arr[fast]):          # element passes the keep-it test
              arr[slow] = arr[fast]         # write it at the slow position
              slow += 1                     # advance write head only on a keep
                                             # (skipped elements get overwritten later)

      return slow                           # length of the kept prefix
  ```

  ```java Java theme={null}
  // THE Two Pointers template (converging variant). Memorize this shape.
  public int[] twoPointersConverging(int[] arr, int target) {
      // left starts at smallest index, right at largest -- so we can steer
      // the sum/area by moving the pointer that improves it
      int left = 0, right = arr.length - 1;

      while (left < right) {                 // strict <: same index would mean using one elem twice
          int current = arr[left] + arr[right]; // the quantity to compare against target

          if (current == target) {
              return new int[]{left, right}; // found
          } else if (current < target) {
              left++;                         // sum too small -> increase by moving left up (sorted)
          } else {
              right--;                        // sum too large -> decrease by moving right down
          }
      }
      return new int[]{-1, -1};
  }

  // THE Two Pointers template (fast/slow variant). For in-place rewrites.
  public int twoPointersFastSlow(int[] arr, java.util.function.IntPredicate keep) {
      int slow = 0;                          // write position
      for (int fast = 0; fast < arr.length; fast++) {
          if (keep.test(arr[fast])) {
              arr[slow] = arr[fast];         // overwrite slow with kept element
              slow++;                         // slow advances only on keep -> compacted prefix
          }
      }
      return slow;
  }
  ```
</CodeGroup>

## Pattern Recognition Checklist

Before using Two Pointers, ask yourself:

<CardGroup cols={2}>
  <Card title="Use Two Pointers When" icon="check">
    * Array is **sorted** (or can be sorted)
    * Need to find **pairs** with a property
    * **In-place** modification required
    * Need to **compare elements** from ends
    * Want to avoid **O(n²)** nested loops
  </Card>

  <Card title="Don't Use When" icon="xmark">
    * Need to preserve **original order**
    * Array is **unsorted** and sorting changes answer
    * Need to find **subarrays** (use Sliding Window)
    * Need **lookup by value** (use HashMap)
  </Card>
</CardGroup>

## When to Use

<CardGroup cols={2}>
  <Card title="Sorted Arrays" icon="arrow-up-1-9">
    Finding pairs, triplets, or elements with specific sum
  </Card>

  <Card title="Palindrome Problems" icon="rotate-left">
    Checking or creating palindromes
  </Card>

  <Card title="Merging Arrays" icon="code-merge">
    Merging sorted arrays or linked lists
  </Card>

  <Card title="Removing Duplicates" icon="filter">
    In-place array modifications
  </Card>
</CardGroup>

## Pattern Variations

### 1. Opposite Direction (Converging)

Pointers start at both ends and move towards the center.

<CodeGroup>
  ```python Python theme={null}
  def two_sum_sorted(arr, target):
      """Find two numbers in sorted array that sum to target"""
      left, right = 0, len(arr) - 1
      
      while left < right:
          current_sum = arr[left] + arr[right]
          
          if current_sum == target:
              return [left, right]
          elif current_sum < target:
              left += 1  # Need larger sum
          else:
              right -= 1  # Need smaller sum
      
      return [-1, -1]  # Not found
  ```

  ```java Java theme={null}
  public int[] twoSumSorted(int[] arr, int target) {
      // Find two numbers in sorted array that sum to target
      int left = 0, right = arr.length - 1;
      
      while (left < right) {
          int currentSum = arr[left] + arr[right];
          
          if (currentSum == target) {
              return new int[]{left, right};
          } else if (currentSum < target) {
              left++;  // Need larger sum
          } else {
              right--;  // Need smaller sum
          }
      }
      
      return new int[]{-1, -1};  // Not found
  }
  ```

  ```cpp C++ theme={null}
  vector<int> twoSumSorted(vector<int>& arr, int target) {
      // Find two numbers in sorted array that sum to target
      int left = 0, right = arr.size() - 1;
      
      while (left < right) {
          int currentSum = arr[left] + arr[right];
          
          if (currentSum == target) {
              return {left, right};
          } else if (currentSum < target) {
              left++;  // Need larger sum
          } else {
              right--;  // Need smaller sum
          }
      }
      
      return {-1, -1};  // Not found
  }
  ```
</CodeGroup>

### 2. Same Direction (Fast & Slow)

Both pointers move in the same direction at different speeds.

<CodeGroup>
  ```python Python theme={null}
  def remove_duplicates(arr):
      """Remove duplicates from sorted array in-place"""
      if not arr:
          return 0
      
      slow = 0  # Points to last unique element
      
      for fast in range(1, len(arr)):
          if arr[fast] != arr[slow]:
              slow += 1
              arr[slow] = arr[fast]
      
      return slow + 1  # Length of unique elements
  ```

  ```java Java theme={null}
  public int removeDuplicates(int[] arr) {
      // Remove duplicates from sorted array in-place
      if (arr.length == 0) return 0;
      
      int slow = 0;  // Points to last unique element
      
      for (int fast = 1; fast < arr.length; fast++) {
          if (arr[fast] != arr[slow]) {
              slow++;
              arr[slow] = arr[fast];
          }
      }
      
      return slow + 1;  // Length of unique elements
  }
  ```

  ```cpp C++ theme={null}
  int removeDuplicates(vector<int>& arr) {
      // Remove duplicates from sorted array in-place
      if (arr.empty()) return 0;
      
      int slow = 0;  // Points to last unique element
      
      for (int fast = 1; fast < arr.size(); fast++) {
          if (arr[fast] != arr[slow]) {
              slow++;
              arr[slow] = arr[fast];
          }
      }
      
      return slow + 1;  // Length of unique elements
  }
  ```
</CodeGroup>

### 3. Container With Most Water

<CodeGroup>
  ```python Python theme={null}
  def max_area(height):
      """Find two lines that form container with most water"""
      left, right = 0, len(height) - 1
      max_water = 0
      
      while left < right:
          width = right - left
          h = min(height[left], height[right])
          max_water = max(max_water, width * h)
          
          # Move the shorter line inward
          if height[left] < height[right]:
              left += 1
          else:
              right -= 1
      
      return max_water
  ```

  ```java Java theme={null}
  public int maxArea(int[] height) {
      // Find two lines that form container with most water
      int left = 0, right = height.length - 1;
      int maxWater = 0;
      
      while (left < right) {
          int width = right - left;
          int h = Math.min(height[left], height[right]);
          maxWater = Math.max(maxWater, width * h);
          
          // Move the shorter line inward
          if (height[left] < height[right]) {
              left++;
          } else {
              right--;
          }
      }
      
      return maxWater;
  }
  ```

  ```cpp C++ theme={null}
  int maxArea(vector<int>& height) {
      // Find two lines that form container with most water
      int left = 0, right = height.size() - 1;
      int maxWater = 0;
      
      while (left < right) {
          int width = right - left;
          int h = min(height[left], height[right]);
          maxWater = max(maxWater, width * h);
          
          // Move the shorter line inward
          if (height[left] < height[right]) {
              left++;
          } else {
              right--;
          }
      }
      
      return maxWater;
  }
  ```
</CodeGroup>

### 4. Valid Palindrome

<CodeGroup>
  ```python Python theme={null}
  def is_palindrome(s):
      """Check if string is palindrome (alphanumeric only)"""
      left, right = 0, len(s) - 1
      
      while left < right:
          # Skip non-alphanumeric characters
          while left < right and not s[left].isalnum():
              left += 1
          while left < right and not s[right].isalnum():
              right -= 1
          
          if s[left].lower() != s[right].lower():
              return False
          
          left += 1
          right -= 1
      
      return True
  ```

  ```java Java theme={null}
  public boolean isPalindrome(String s) {
      // Check if string is palindrome (alphanumeric only)
      int left = 0, right = s.length() - 1;
      
      while (left < right) {
          // Skip non-alphanumeric characters
          while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
              left++;
          }
          while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
              right--;
          }
          
          if (Character.toLowerCase(s.charAt(left)) != 
              Character.toLowerCase(s.charAt(right))) {
              return false;
          }
          
          left++;
          right--;
      }
      
      return true;
  }
  ```

  ```cpp C++ theme={null}
  bool isPalindrome(string s) {
      // Check if string is palindrome (alphanumeric only)
      int left = 0, right = s.length() - 1;
      
      while (left < right) {
          // Skip non-alphanumeric characters
          while (left < right && !isalnum(s[left])) {
              left++;
          }
          while (left < right && !isalnum(s[right])) {
              right--;
          }
          
          if (tolower(s[left]) != tolower(s[right])) {
              return false;
          }
          
          left++;
          right--;
      }
      
      return true;
  }
  ```
</CodeGroup>

### 5. 3Sum

<CodeGroup>
  ```python Python theme={null}
  def three_sum(nums):
      """Find all unique triplets that sum to zero"""
      nums.sort()
      result = []
      
      for i in range(len(nums) - 2):
          # Skip duplicates for first element
          if i > 0 and nums[i] == nums[i - 1]:
              continue
          
          left, right = i + 1, len(nums) - 1
          
          while left < right:
              total = nums[i] + nums[left] + nums[right]
              
              if total == 0:
                  result.append([nums[i], nums[left], nums[right]])
                  # Skip duplicates
                  while left < right and nums[left] == nums[left + 1]:
                      left += 1
                  while left < right and nums[right] == nums[right - 1]:
                      right -= 1
                  left += 1
                  right -= 1
              elif total < 0:
                  left += 1
              else:
                  right -= 1
      
      return result
  ```

  ```java Java theme={null}
  public List<List<Integer>> threeSum(int[] nums) {
      // Find all unique triplets that sum to zero
      Arrays.sort(nums);
      List<List<Integer>> result = new ArrayList<>();
      
      for (int i = 0; i < nums.length - 2; i++) {
          // Skip duplicates for first element
          if (i > 0 && nums[i] == nums[i - 1]) continue;
          
          int left = i + 1, right = nums.length - 1;
          
          while (left < right) {
              int total = nums[i] + nums[left] + nums[right];
              
              if (total == 0) {
                  result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                  // Skip duplicates
                  while (left < right && nums[left] == nums[left + 1]) left++;
                  while (left < right && nums[right] == nums[right - 1]) right--;
                  left++;
                  right--;
              } else if (total < 0) {
                  left++;
              } else {
                  right--;
              }
          }
      }
      
      return result;
  }
  ```

  ```cpp C++ theme={null}
  vector<vector<int>> threeSum(vector<int>& nums) {
      // Find all unique triplets that sum to zero
      sort(nums.begin(), nums.end());
      vector<vector<int>> result;
      
      for (int i = 0; i < (int)nums.size() - 2; i++) {
          // Skip duplicates for first element
          if (i > 0 && nums[i] == nums[i - 1]) continue;
          
          int left = i + 1, right = nums.size() - 1;
          
          while (left < right) {
              int total = nums[i] + nums[left] + nums[right];
              
              if (total == 0) {
                  result.push_back({nums[i], nums[left], nums[right]});
                  // Skip duplicates
                  while (left < right && nums[left] == nums[left + 1]) left++;
                  while (left < right && nums[right] == nums[right - 1]) right--;
                  left++;
                  right--;
              } else if (total < 0) {
                  left++;
              } else {
                  right--;
              }
          }
      }
      
      return result;
  }
  ```
</CodeGroup>

### 6. Trapping Rain Water

<CodeGroup>
  ```python Python theme={null}
  def trap(height):
      """Calculate trapped water between elevation bars"""
      if not height:
          return 0
      
      left, right = 0, len(height) - 1
      left_max, right_max = height[left], height[right]
      water = 0
      
      while left < right:
          if left_max < right_max:
              left += 1
              left_max = max(left_max, height[left])
              water += left_max - height[left]
          else:
              right -= 1
              right_max = max(right_max, height[right])
              water += right_max - height[right]
      
      return water
  ```

  ```java Java theme={null}
  public int trap(int[] height) {
      // Calculate trapped water between elevation bars
      if (height.length == 0) return 0;
      
      int left = 0, right = height.length - 1;
      int leftMax = height[left], rightMax = height[right];
      int water = 0;
      
      while (left < right) {
          if (leftMax < rightMax) {
              left++;
              leftMax = Math.max(leftMax, height[left]);
              water += leftMax - height[left];
          } else {
              right--;
              rightMax = Math.max(rightMax, height[right]);
              water += rightMax - height[right];
          }
      }
      
      return water;
  }
  ```

  ```cpp C++ theme={null}
  int trap(vector<int>& height) {
      // Calculate trapped water between elevation bars
      if (height.empty()) return 0;
      
      int left = 0, right = height.size() - 1;
      int leftMax = height[left], rightMax = height[right];
      int water = 0;
      
      while (left < right) {
          if (leftMax < rightMax) {
              left++;
              leftMax = max(leftMax, height[left]);
              water += leftMax - height[left];
          } else {
              right--;
              rightMax = max(rightMax, height[right]);
              water += rightMax - height[right];
          }
      }
      
      return water;
  }
  ```
</CodeGroup>

### 7. Move Zeroes

<CodeGroup>
  ```python Python theme={null}
  def move_zeroes(nums):
      """Move all zeroes to end while maintaining order"""
      slow = 0  # Position for next non-zero element
      
      for fast in range(len(nums)):
          if nums[fast] != 0:
              nums[slow], nums[fast] = nums[fast], nums[slow]
              slow += 1
  ```

  ```java Java theme={null}
  public void moveZeroes(int[] nums) {
      // Move all zeroes to end while maintaining order
      int slow = 0;  // Position for next non-zero element
      
      for (int fast = 0; fast < nums.length; fast++) {
          if (nums[fast] != 0) {
              int temp = nums[slow];
              nums[slow] = nums[fast];
              nums[fast] = temp;
              slow++;
          }
      }
  }
  ```

  ```cpp C++ theme={null}
  void moveZeroes(vector<int>& nums) {
      // Move all zeroes to end while maintaining order
      int slow = 0;  // Position for next non-zero element
      
      for (int fast = 0; fast < nums.size(); fast++) {
          if (nums[fast] != 0) {
              swap(nums[slow], nums[fast]);
              slow++;
          }
      }
  }
  ```
</CodeGroup>

### 8. Sort Colors (Dutch National Flag)

<CodeGroup>
  ```python Python theme={null}
  def sort_colors(nums):
      """Sort array of 0s, 1s, and 2s in-place"""
      low, mid, high = 0, 0, len(nums) - 1
      
      while mid <= high:
          if nums[mid] == 0:
              nums[low], nums[mid] = nums[mid], nums[low]
              low += 1
              mid += 1
          elif nums[mid] == 1:
              mid += 1
          else:  # nums[mid] == 2
              nums[mid], nums[high] = nums[high], nums[mid]
              high -= 1
  ```

  ```java Java theme={null}
  public void sortColors(int[] nums) {
      // Sort array of 0s, 1s, and 2s in-place
      int low = 0, mid = 0, high = nums.length - 1;
      
      while (mid <= high) {
          if (nums[mid] == 0) {
              int temp = nums[low];
              nums[low] = nums[mid];
              nums[mid] = temp;
              low++;
              mid++;
          } else if (nums[mid] == 1) {
              mid++;
          } else {  // nums[mid] == 2
              int temp = nums[mid];
              nums[mid] = nums[high];
              nums[high] = temp;
              high--;
          }
      }
  }
  ```

  ```cpp C++ theme={null}
  void sortColors(vector<int>& nums) {
      // Sort array of 0s, 1s, and 2s in-place
      int low = 0, mid = 0, high = nums.size() - 1;
      
      while (mid <= high) {
          if (nums[mid] == 0) {
              swap(nums[low], nums[mid]);
              low++;
              mid++;
          } else if (nums[mid] == 1) {
              mid++;
          } else {  // nums[mid] == 2
              swap(nums[mid], nums[high]);
              high--;
          }
      }
  }
  ```
</CodeGroup>

## Classic Problems

<AccordionGroup>
  <Accordion title="1. Two Sum II (Sorted Array)" icon="plus">
    **Problem**: Find two numbers in a sorted array that add up to target.

    **Approach**: Use converging pointers. If sum is too small, move left pointer right. If too large, move right pointer left.

    **Time**: O(n) | **Space**: O(1)
  </Accordion>

  <Accordion title="2. Container With Most Water" icon="droplet">
    **Problem**: Find two lines that form a container holding the most water.

    **Approach**: Start from both ends. Move the pointer with the shorter line inward (greedy choice).

    **Time**: O(n) | **Space**: O(1)
  </Accordion>

  <Accordion title="3. Valid Palindrome" icon="rotate-left">
    **Problem**: Check if a string is a palindrome (ignoring non-alphanumeric).

    **Approach**: Compare characters from both ends, skip non-alphanumeric.

    **Time**: O(n) | **Space**: O(1)
  </Accordion>

  <Accordion title="4. 3Sum" icon="hashtag">
    **Problem**: Find all unique triplets that sum to zero.

    **Approach**: Sort array, fix one element, use two pointers for remaining two.

    **Time**: O(n^2) | **Space**: O(1) excluding output
  </Accordion>

  <Accordion title="5. Trapping Rain Water" icon="water">
    **Problem**: Calculate trapped water between elevation bars.

    **Approach**: Two pointers with max height tracking from both sides.

    **Time**: O(n) | **Space**: O(1)
  </Accordion>
</AccordionGroup>

## Template Code

<CodeGroup>
  ```python Python theme={null}
  # Template 1: Converging Pointers
  def converging_template(arr):
      left, right = 0, len(arr) - 1
      result = None
      
      while left < right:
          # Process current pair
          # Update result if needed
          
          if condition_move_left:
              left += 1
          else:
              right -= 1
      
      return result

  # Template 2: Fast-Slow Pointers
  def fast_slow_template(arr):
      slow = 0
      
      for fast in range(len(arr)):
          if some_condition(arr[fast]):
              arr[slow] = arr[fast]
              slow += 1
      
      return slow
  ```

  ```java Java theme={null}
  // Template 1: Converging Pointers
  public Object convergingTemplate(int[] arr) {
      int left = 0, right = arr.length - 1;
      Object result = null;
      
      while (left < right) {
          // Process current pair
          // Update result if needed
          
          if (conditionMoveLeft) {
              left++;
          } else {
              right--;
          }
      }
      
      return result;
  }

  // Template 2: Fast-Slow Pointers
  public int fastSlowTemplate(int[] arr) {
      int slow = 0;
      
      for (int fast = 0; fast < arr.length; fast++) {
          if (someCondition(arr[fast])) {
              arr[slow] = arr[fast];
              slow++;
          }
      }
      
      return slow;
  }
  ```

  ```cpp C++ theme={null}
  // Template 1: Converging Pointers
  auto convergingTemplate(vector<int>& arr) {
      int left = 0, right = arr.size() - 1;
      
      while (left < right) {
          // Process current pair
          // Update result if needed
          
          if (conditionMoveLeft) {
              left++;
          } else {
              right--;
          }
      }
      
      return result;
  }

  // Template 2: Fast-Slow Pointers
  int fastSlowTemplate(vector<int>& arr) {
      int slow = 0;
      
      for (int fast = 0; fast < arr.size(); fast++) {
          if (someCondition(arr[fast])) {
              arr[slow] = arr[fast];
              slow++;
          }
      }
      
      return slow;
  }
  ```
</CodeGroup>

## Common Mistakes

<Warning>
  **Avoid These Pitfalls:**

  1. **Off-by-one errors**: Be careful with `left < right` vs `left <= right`
  2. **Infinite loops**: Ensure pointers always move towards termination
  3. **Missing edge cases**: Empty arrays, single elements, all duplicates
  4. **Modifying while iterating**: Be careful when removing elements in-place
</Warning>

## Debugging Checklist

When your Two Pointers solution fails, check:

<Steps>
  <Step title="Initialization">
    Are `left` and `right` starting at correct positions?
  </Step>

  <Step title="Loop Condition">
    Should it be `left < right` or `left <= right`?
  </Step>

  <Step title="Pointer Movement">
    Is at least one pointer moving in each iteration?
  </Step>

  <Step title="Edge Cases">
    Did you handle empty array, single element, all same elements?
  </Step>

  <Step title="Duplicates">
    Are you skipping duplicates correctly (for unique results)?
  </Step>
</Steps>

## Complexity Quick Reference

| Problem Type      | Time  | Space | Key Insight                  |
| ----------------- | ----- | ----- | ---------------------------- |
| Two Sum (sorted)  | O(n)  | O(1)  | Move based on sum comparison |
| 3Sum              | O(n²) | O(1)  | Fix one, two-pointer on rest |
| Remove Duplicates | O(n)  | O(1)  | Slow = write position        |
| Container Water   | O(n)  | O(1)  | Move shorter side inward     |
| Trap Rain Water   | O(n)  | O(1)  | Track max from both sides    |
| Valid Palindrome  | O(n)  | O(1)  | Skip non-alphanumeric        |

## Interview Problems by Company

<Tabs>
  <Tab title="Easy">
    | Problem                 | Company         | Key Concept             |
    | ----------------------- | --------------- | ----------------------- |
    | Two Sum II              | Amazon, Google  | Basic converging        |
    | Valid Palindrome        | Meta, Microsoft | Character comparison    |
    | Move Zeroes             | Meta, Amazon    | Fast-slow technique     |
    | Remove Duplicates       | All FAANG       | In-place modification   |
    | Squares of Sorted Array | Amazon          | Converging with squares |
  </Tab>

  <Tab title="Medium">
    | Problem              | Company         | Key Concept             |
    | -------------------- | --------------- | ----------------------- |
    | 3Sum                 | All FAANG       | Fix + two pointers      |
    | Container With Water | Amazon, Google  | Greedy + converging     |
    | Sort Colors          | Microsoft, Meta | Dutch flag (3 pointers) |
    | 3Sum Closest         | Google, Meta    | Tracking closest sum    |
    | Partition Labels     | Amazon          | Multiple passes         |
  </Tab>

  <Tab title="Hard">
    | Problem             | Company        | Key Concept               |
    | ------------------- | -------------- | ------------------------- |
    | Trapping Rain Water | Google, Amazon | Track max from both sides |
    | 4Sum                | Google         | Nested two pointers       |
    | Minimum Window Sort | Meta           | Find unsorted subarray    |
  </Tab>
</Tabs>

## Interview Tips

<AccordionGroup>
  <Accordion title="How to Explain Your Approach" icon="comments">
    **Script for interviews:**

    1. "I notice the array is sorted, which suggests Two Pointers might work here."
    2. "I'll use two pointers starting at opposite ends."
    3. "If the sum is too small, I move left pointer right to increase it."
    4. "If too large, I move right pointer left to decrease it."
    5. "This gives us O(n) time and O(1) space."
  </Accordion>

  <Accordion title="When Interviewer Says..." icon="user-tie">
    | Interviewer Says                | You Should Think           |
    | ------------------------------- | -------------------------- |
    | "Can you do better than O(n²)?" | Two Pointers or HashMap    |
    | "Can you do it in O(1) space?"  | Two Pointers (not HashMap) |
    | "The array is sorted"           | Definitely Two Pointers!   |
    | "Find a pair/triplet"           | Two Pointers likely        |
    | "Modify array in-place"         | Fast-slow pointers         |
  </Accordion>

  <Accordion title="Common Follow-ups" icon="puzzle-piece">
    Be ready for these follow-ups:

    * "What if there are duplicates?" → Skip duplicates in loop
    * "What if no solution exists?" → Return appropriate default
    * "Can you handle negative numbers?" → Usually yes, same logic
    * "What if array is not sorted?" → Sort first, or use HashMap
  </Accordion>
</AccordionGroup>

## Practice Problems

| Problem                   | Difficulty | Link                                                                            |
| ------------------------- | ---------- | ------------------------------------------------------------------------------- |
| Two Sum II                | Easy       | [LeetCode 167](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/) |
| Valid Palindrome          | Easy       | [LeetCode 125](https://leetcode.com/problems/valid-palindrome/)                 |
| 3Sum                      | Medium     | [LeetCode 15](https://leetcode.com/problems/3sum/)                              |
| Container With Most Water | Medium     | [LeetCode 11](https://leetcode.com/problems/container-with-most-water/)         |
| Trapping Rain Water       | Hard       | [LeetCode 42](https://leetcode.com/problems/trapping-rain-water/)               |

## Practice Roadmap

<Steps>
  <Step title="Day 1: Basics">
    * Solve: Two Sum II, Valid Palindrome
    * Focus: Understanding when to move which pointer
  </Step>

  <Step title="Day 2: Fast-Slow">
    * Solve: Move Zeroes, Remove Duplicates
    * Focus: In-place modifications
  </Step>

  <Step title="Day 3: Multi-pointer">
    * Solve: 3Sum, Sort Colors
    * Focus: Managing multiple pointers
  </Step>

  <Step title="Day 4: Advanced">
    * Solve: Container With Water, Trapping Rain Water
    * Focus: Greedy decisions with pointers
  </Step>
</Steps>

<Tip>
  **Interview Tip**: When you see a sorted array or need to find pairs/triplets, immediately consider Two Pointers before jumping to HashMap.
</Tip>

## Worked LeetCode Problems

Five canonical problems. For each: signal that triggers Two Pointers, brute force first, optimized solution, and the bugs that fail edge cases.

### LC 167 -- Two Sum II (Input Array Is Sorted)

**Problem.** Given a 1-indexed sorted array of integers and a target, return the indices of two numbers that add up to the target. Exactly one solution exists.

**Pattern fit.** "Sorted array" + "two numbers summing to target" -- the textbook Two Pointers signal.

**Brute force.** Two nested loops, O(n squared) time, O(1) space. Even though the array is sorted, brute force ignores that signal.

**Optimized with Two Pointers.**

```python theme={null}
def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]   # 1-indexed
        elif s < target:
            left += 1                       # need larger sum, advance left
        else:
            right -= 1                      # need smaller sum, retreat right
    return [-1, -1]
```

**Why it works.** Each step eliminates one row or column of the implicit pair matrix. We never miss the answer because moving inward on the wrong side would only worsen the sum direction.

**Complexity.** O(n) time, O(1) space.

**Common bugs.**

* **Forgetting 1-indexed return.** LC 167 wants 1-indexed indices. Off-by-one fails 100% of test cases.
* **Using `left <= right`.** Allows using the same element twice. Returns wrong pair when `target == 2 * arr[i]`.

***

### LC 15 -- 3Sum

**Problem.** Given an integer array, find all unique triplets that sum to zero.

**Pattern fit.** "All triplets summing to X" -- fix one element, run Two Pointers on the rest.

**Brute force.** Three nested loops, O(n cubed). Use a set of sorted tuples to dedupe -- messy.

**Optimized.**

```python theme={null}
def threeSum(nums):
    nums.sort()                             # required for both two-pointer scan AND dedupe
    result = []
    n = len(nums)

    for i in range(n - 2):
        if nums[i] > 0:
            break                            # all remaining are positive, sum cannot be zero
        if i > 0 and nums[i] == nums[i - 1]:
            continue                         # skip duplicate first elements

        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1                # skip duplicate seconds
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1               # skip duplicate thirds
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result
```

**Complexity.** O(n squared) time (sort dominated by inner scan), O(1) extra space ignoring output.

**Common bugs.**

* **Skipping duplicates after recording, but only on one side.** You must skip on both `left` and `right`, otherwise `[-2, 0, 0, 2, 2]` produces `[[-2, 0, 2], [-2, 0, 2]]`.
* **Forgetting to break when `nums[i] > 0`.** Not a correctness bug, but a 5x performance loss on large inputs with many positives.

***

### LC 11 -- Container With Most Water

**Problem.** Given an array of heights, find two lines that together with the x-axis form a container holding the most water.

**Pattern fit.** "Pair from sorted-by-position array" + "maximize area" -- greedy converging Two Pointers.

**Brute force.** All pairs, O(n squared).

**Optimized.**

```python theme={null}
def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h = min(height[left], height[right])
        best = max(best, h * (right - left))
        # Move the SHORTER side -- moving the taller side cannot help
        # because the height is bounded by the shorter side regardless
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best
```

**Why moving the shorter side is correct.** The area is bounded by the shorter line. Moving the taller side cannot increase the area (height is still bounded by the shorter side, and width decreases). Moving the shorter side at least gives a chance to find a taller pair.

**Complexity.** O(n) time, O(1) space.

**Common bugs.**

* **Moving the taller side.** Misses the optimum on inputs like `[1, 8, 6, 2, 5, 4, 8, 3, 7]`.
* **Updating area after moving pointers.** Then you skip the current pair's contribution. Always update before moving.

***

### LC 125 -- Valid Palindrome

**Problem.** Return true if string is a palindrome considering only alphanumeric characters and ignoring case.

**Pattern fit.** "Palindrome check" -- converging Two Pointers from both ends.

**Brute force.** Build a filtered, lowercased string and compare with its reverse. O(n) time, O(n) space.

**Optimized.**

```python theme={null}
def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1                            # skip non-alphanumeric on the left
        while left < right and not s[right].isalnum():
            right -= 1                           # skip non-alphanumeric on the right
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
```

**Complexity.** O(n) time, O(1) space.

**Common bugs.**

* **Forgetting `left < right` inside the inner skip loops.** Causes index out-of-range when the entire string is non-alphanumeric, e.g., `"....,"` or `"...."` (returning true is correct).
* **Comparing characters without `.lower()`.** Fails on `"A man, a plan, a canal: Panama"`.

***

### LC 42 -- Trapping Rain Water

**Problem.** Given an array of bar heights, compute the total water trapped after rain.

**Pattern fit.** "Compute aggregate over array using boundaries from both sides" -- converging Two Pointers with running maxes.

**Brute force.** For each index, find max to left and max to right, take min, subtract bar height. O(n squared).

**Better but still not optimal.** Precompute left-max and right-max arrays. O(n) time, O(n) space.

**Optimized (Two Pointers).**

```python theme={null}
def trap(height):
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            # left side is the bottleneck -- water at left is bounded by left_max
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            # right side is the bottleneck
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water
```

**Why it works.** When `height[left] < height[right]`, we know the right side has at least one bar taller than `left_max` somewhere to the right. So water at `left` is determined purely by `left_max` (the right bound is already known to be at least as tall). Process the bottleneck side first.

**Complexity.** O(n) time, O(1) space.

**Common bugs.**

* **Initializing `left_max = height[0]`** then accidentally double-counting position 0. Initialize to 0 and let the first comparison update it.
* **Comparing `left_max` against `right_max`** instead of `height[left]` against `height[right]`. The decision is which *current bar* is shorter, not which max.

***

<Warning>
  **Caveats and Traps -- Two Pointers**

  * **Using `left <= right` when you should use `left < right`.** The `<=` allows the same index for both pointers, which means using one element twice. Catastrophic for sum problems where `target = 2 * arr[i]`. Use `<=` only when single-element processing is meaningful (Dutch flag, binary search variants).
  * **Not sorting before applying converging pointers.** Two Pointers requires monotonic order to make meaningful comparisons. On unsorted input, the pointer movement logic breaks because moving "right" on an unsorted array does not predictably increase or decrease anything.
  * **Skipping duplicates only on one side in 3Sum.** You must skip duplicate `nums[left]` AND duplicate `nums[right]` after recording a triplet. Otherwise `[0, 0, 0, 0]` outputs `[0, 0, 0]` multiple times.
  * **Forgetting to update the result before moving pointers.** In Container With Most Water, if you move pointers first and then update area, you miss the contribution of the current pair.
  * **Using sort + Two Pointers on a problem that requires original indices.** LC 1 (Two Sum, unsorted) wants original indices. Sorting destroys them unless you store `(value, original_index)` pairs. Use HashMap instead.
  * **Confusing fast/slow with converging variants.** Fast/slow rewrites in-place (LC 26, 283). Converging searches for pairs (LC 167, 15). They have different invariants -- pick deliberately.
  * **Off-by-one on the reverse merge (LC 88).** Place pointers at `m - 1`, `n - 1`, `m + n - 1`. Forgetting to copy remaining nums2 elements after p1 finishes is the most common bug.
  * **Trapping Rain Water with the wrong comparison.** Compare `height[left]` to `height[right]`, not `left_max` to `right_max`. The current-bar comparison is what tells you which side is the bottleneck.
</Warning>

<Tip>
  **Solutions and Patterns -- Two Pointers Idioms**

  * **Always sort first** unless the problem says "preserve order" or "indices required." Sorting is O(n log n), often dominated by the O(n) or O(n squared) main scan -- effectively free.
  * **Use `<` for converging, `<=` for fast/slow inclusive scans.** The mental check: "When `left == right`, is there meaningful work left?" If no, use `<`.
  * **Skip duplicates by checking against the previous element.** `if i > 0 and nums[i] == nums[i-1]: continue` is the canonical idiom in 3Sum / 4Sum.
  * **For "fix-and-converge" patterns,** wrap the converging two-pointer scan in an outer loop that fixes the first 1, 2, or k-2 elements. This generalizes 2Sum to kSum naturally.
  * **For in-place modifications,** the slow pointer always points to the next *write* position (not the current valid element). After the loop, `slow` is the new length.
  * **For trapping rain water and similar,** process the bottleneck side first. The side with the smaller current height is the binding constraint; you can compute its contribution without knowing the other side's exact future.
  * **For palindrome checks,** wrap inner skip loops with `while left < right and ...`. Otherwise inner loops can run past each other on degenerate inputs.
  * **For merging from the end (LC 88),** write from the back to avoid overwriting unread data. After the main loop, only nums2 leftovers need to be copied -- nums1 leftovers are already in place.
</Tip>

## Curated LeetCode Practice List

Group your practice by difficulty. Solve every Easy, then move to Medium. Hard problems are useful only after Easy and Medium feel mechanical.

### Easy (start here, 5-8 problems)

| LC #   | Title                               | Variant tested                        |
| ------ | ----------------------------------- | ------------------------------------- |
| LC 167 | Two Sum II - Input Array Is Sorted  | Converging, classic baseline          |
| LC 125 | Valid Palindrome                    | Converging with skip logic            |
| LC 344 | Reverse String                      | Converging swap, in-place             |
| LC 26  | Remove Duplicates from Sorted Array | Fast/slow, in-place rewrite           |
| LC 283 | Move Zeroes                         | Fast/slow with swap to preserve order |
| LC 977 | Squares of a Sorted Array           | Converging, write to result from end  |
| LC 88  | Merge Sorted Array                  | Reverse converging, in-place from end |
| LC 392 | Is Subsequence                      | Two pointers across two arrays        |

### Medium (the meat of interview prep, 6-8 problems)

| LC #    | Title                                  | Variant tested                         |
| ------- | -------------------------------------- | -------------------------------------- |
| LC 15   | 3Sum                                   | Sort + fix-one + converging, dedupe    |
| LC 16   | 3Sum Closest                           | Same as 3Sum but track closest sum     |
| LC 11   | Container With Most Water              | Greedy converging on heights           |
| LC 75   | Sort Colors                            | Three pointers (Dutch flag)            |
| LC 80   | Remove Duplicates from Sorted Array II | Fast/slow with `slow - 2` trick        |
| LC 18   | 4Sum                                   | Fix-two + converging, generalizes 3Sum |
| LC 845  | Longest Mountain in Array              | Two pointers expanding from peaks      |
| LC 1248 | Count Subarrays with K Odd Numbers     | Two-pointer + sliding (atMost trick)   |

### Hard (after you have grinded the above, 5-6 problems)

| LC #    | Title                                 | Variant tested                                       |
| ------- | ------------------------------------- | ---------------------------------------------------- |
| LC 42   | Trapping Rain Water                   | Converging with running maxes                        |
| LC 4    | Median of Two Sorted Arrays           | Binary search disguised as two pointers              |
| LC 76   | Minimum Window Substring              | Two pointers + frequency map (sliding window flavor) |
| LC 632  | Smallest Range Covering K Lists       | K pointers via min-heap                              |
| LC 581  | Shortest Unsorted Continuous Subarray | Two passes from both ends                            |
| LC 1782 | Count Pairs Of Nodes                  | Two pointers on sorted degree counts                 |

## Interview Questions

Deep-dive questions that test real understanding of the Two Pointers pattern, not just pattern matching. Expect interviewers to push past your initial answer.

<AccordionGroup>
  <Accordion title="Q1: Why does moving the shorter line inward work in Container With Most Water? Prove it doesn't skip the optimal answer." icon="brain">
    **Difficulty:** Senior

    **What interviewers are really testing:** Whether you understand the *greedy correctness proof* behind the pointer movement, not just that it works. This separates candidates who memorize solutions from those who can reason about algorithmic correctness and would be able to derive similar greedy strategies for novel problems.

    **Strong answer:**

    * The area is `min(height[left], height[right]) * (right - left)`. When we move a pointer inward, the width always decreases by 1. The only way to get a larger area is if the height increases enough to compensate.
    * Suppose `height[left] < height[right]`. If we moved `right` inward instead, the new height is still capped by `height[left]` (since `min(anything, height[left]) <= height[left]`), AND the width decreased. So area strictly decreases or stays the same. We can safely discard all pairs involving current `left` with any `right' < right`.
    * This is essentially an **elimination argument**: by moving the shorter side, we only eliminate pairs that provably cannot beat the current best. We never skip a pair that could be optimal.
    * **Complexity:** O(n) time, O(1) space. Each pointer moves at most n times total.

    ```python theme={null}
    # The key insight in code: we MUST move the shorter side
    if height[left] < height[right]:
        left += 1   # All pairs (left, right'), right' < right are dominated
    else:
        right -= 1  # All pairs (left', right), left' > left are dominated
    ```

    **Red flag answer:** "You move the shorter one because a taller line might give more water." This is hand-waving. If a candidate cannot articulate *why no optimal pair is skipped*, they memorized the pattern without understanding it. Another red flag: saying "it's like binary search" -- it is not, and that analogy breaks down immediately.

    **Follow-ups:**

    1. What if there are many lines with the same height? Does the algorithm degenerate? What is the worst-case number of comparisons? (Answer: still O(n), each pointer moves at most n/2 times regardless of duplicates.)
    2. Can you modify this to return ALL pairs of lines whose area is within 10% of the maximum? Does the two-pointer approach still work, or do you need a different strategy? (Answer: two-pointer no longer works cleanly because the elimination argument breaks -- you would need to explore more pairs, potentially O(n^2) in the worst case, or use a sorted/stack-based approach.)
  </Accordion>

  <Accordion title="Q2: Given an unsorted array of integers, find if there exist two elements whose sum equals a target. What approach do you use and why?" icon="circle-question">
    **Difficulty:** Foundational (but the trap is the real test)

    **What interviewers are really testing:** Whether you blindly apply two pointers to every "find a pair" problem, or whether you recognize when a **HashMap is the better tool**. This is a pattern-recognition trap -- strong candidates explain the trade-off; weak candidates force two pointers.

    **Strong answer:**

    * For an **unsorted** array, the right answer is a **HashMap/HashSet**, not two pointers. Insert each element and check if `target - current` exists. O(n) time, O(n) space.
    * Two pointers *requires sorting first*, which is O(n log n) and also **destroys original indices** -- if the problem asks for indices (like LeetCode Two Sum), you lose that information unless you store original indices separately.
    * The trade-off: HashMap gives O(n) time but O(n) space. Sorting + two pointers gives O(n log n) time but O(1) space (if you do not need indices). **Choose based on constraints.**
    * In an interview, I would state: "Since the array is unsorted and we need O(n) time, I will use a HashMap. If the interviewer constrains me to O(1) space and does not need original indices, I would sort then use two pointers."

    ```python theme={null}
    # HashMap approach for unsorted arrays
    def two_sum_unsorted(nums, target):
        seen = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        return [-1, -1]
    ```

    **Red flag answer:** Immediately jumping to "sort the array and use two pointers" without considering that sorting is O(n log n) and destroys index information. Or even worse: not knowing that two pointers requires a sorted input at all.

    **Follow-ups:**

    1. What if memory is extremely constrained (embedded system, 2MB RAM) but the array has 100 million elements on disk? Now sorting + two pointers (external sort) might beat the HashMap approach. Walk me through that trade-off.
    2. What if there are many duplicate values? Does the HashMap approach need modification? (Answer: depends on whether you need all pairs or just one. For all pairs, you need to store counts or lists of indices.)
  </Accordion>

  <Accordion title="Q3: In the 3Sum problem, why do we sort the array first? What breaks if we skip sorting?" icon="triangle-exclamation">
    **Difficulty:** Intermediate

    **What interviewers are really testing:** Whether you understand that sorting is not an arbitrary choice but a *structural prerequisite* that enables both the two-pointer scan and duplicate elimination. Also tests whether you can reason about alternatives and their costs.

    **Strong answer:**

    * Sorting serves **two critical purposes** in 3Sum:
      1. **Enables two-pointer scanning:** After fixing one element, the remaining subarray is sorted, so converging pointers can systematically search in O(n) instead of O(n^2).
      2. **Makes duplicate skipping trivial:** In a sorted array, duplicates are adjacent. You just check `if nums[i] == nums[i-1]: continue`. Without sorting, you would need a HashSet to track which triplets you have already seen, which is messier and uses O(k) extra space for k results.
    * Without sorting, you would need a **HashMap-based approach**: for each pair `(i, j)`, check if `-(nums[i] + nums[j])` exists. This is O(n^2) time (same as sorted approach) but requires O(n) extra space for the map and a **set of sorted tuples** to deduplicate results, which is error-prone.
    * The sorting cost is O(n log n), and the two-pointer scan is O(n^2), so sorting does not change the overall O(n^2) complexity. It is essentially "free."

    ```python theme={null}
    # Without sorting, duplicate handling becomes a nightmare:
    # You would need something like:
    seen_triplets = set()
    for i in range(n):
        complement_map = {}
        for j in range(i + 1, n):
            comp = -(nums[i] + nums[j])
            if comp in complement_map:
                triplet = tuple(sorted([nums[i], nums[j], comp]))
                seen_triplets.add(triplet)
            complement_map[nums[j]] = j
    # Messy, harder to get right, same time complexity
    ```

    **Red flag answer:** "We sort because two pointers needs a sorted array" without explaining WHY two pointers needs sorted input or mentioning the duplicate-skipping benefit. Another red flag: not realizing the sorting cost is dominated by the O(n^2) scan.

    **Follow-ups:**

    1. If the problem changes to 4Sum, how does the complexity change? Can you still use two pointers? (Answer: yes, fix two elements O(n^2), two-pointer scan O(n) for each = O(n^3) total. The pattern generalizes: k-Sum is O(n^(k-1)) with sorting + two pointers.)
    2. What if the array is already sorted and has 10 million elements? What practical optimizations would you add? (Answer: early termination -- if `nums[i] > 0`, no triplet starting here can sum to zero. If `nums[i] + nums[i+1] + nums[i+2] > 0`, break. These prune aggressively.)
  </Accordion>

  <Accordion title="Q4: Explain the difference between `left < right` and `left <= right` as loop conditions. When does picking the wrong one cause bugs?" icon="bug">
    **Difficulty:** Foundational

    **What interviewers are really testing:** Attention to off-by-one errors, which are the #1 source of bugs in pointer-based code. This also reveals whether a candidate *tests their code mentally* with small inputs or just writes and hopes.

    **Strong answer:**

    * `left < right` means the pointers must have at least one element between them or be adjacent. When `left == right`, the loop exits. **Use this when you are comparing/processing pairs of distinct elements** (e.g., Two Sum, palindrome check, Container With Most Water).
    * `left <= right` means even when both pointers point to the same element, you still process it. **Use this when a single element might still need processing** (e.g., Dutch National Flag / Sort Colors, binary search).
    * **Concrete bug example:** In the palindrome check, using `left <= right` would not cause a bug (checking a single middle character against itself is fine), but in Two Sum, using `left <= right` could cause you to **use the same element twice** -- returning `[i, i]` as a valid pair when `arr[i] * 2 == target`.
    * **The mental model I use:** Ask yourself: "When `left == right`, is there still meaningful work to do, or have I already considered everything?" If the answer is no, use `<`. If yes, use `<=`.

    ```python theme={null}
    # Two Sum: left < right (never use same element twice)
    while left < right:
        if arr[left] + arr[right] == target:
            return [left, right]

    # Dutch Flag: mid <= high (single element still needs classification)
    while mid <= high:
        if nums[mid] == 0:
            swap(nums, low, mid)
            low += 1
            mid += 1
    ```

    **Red flag answer:** "I always use `left < right` for two pointers." This shows the candidate does not think about *why*, just memorizes. Another red flag: being unable to produce a concrete input where the wrong condition causes a failure.

    **Follow-ups:**

    1. In binary search, when do you use `left < right` vs `left <= right` vs `left + 1 < right`? What bug does each variant prevent? (Tests whether the candidate connects two-pointer reasoning to binary search, which is fundamentally a two-pointer technique.)
    2. Walk me through what happens with the input `[1, 2, 3, 4, 5]` and target `6` using Two Sum with `left <= right`. Where exactly does it break? (Answer: when `left = right = 2`, it would return `[2, 2]` claiming `3 + 3 = 6`, but you cannot use the same element twice.)
  </Accordion>

  <Accordion title="Q5: How does the two-pointer solution for Trapping Rain Water work, and why is it correct? What alternatives exist and when would you prefer them?" icon="droplet">
    **Difficulty:** Senior

    **What interviewers are really testing:** Deep understanding of a Hard-level problem with multiple valid approaches. The interviewer wants to see if you can explain the invariant that makes the two-pointer version work, and whether you have the judgment to discuss trade-offs between approaches.

    **Strong answer:**

    * **Core invariant:** At any position, the water trapped equals `min(max_left, max_right) - height[i]`. The two-pointer approach works because we always process from the side with the **smaller known maximum**. If `left_max < right_max`, we know the water at `left` is determined by `left_max` regardless of what lies between the pointers (since `right_max` is already larger, and anything in between could only increase the right maximum further).
    * **Why it is correct:** We process the "bottleneck side" first. When `left_max < right_max`, the constraining factor at position `left` is `left_max`, not `right_max`. So we can safely compute water at `left` without knowing the exact `right_max` -- we just know it is at least as large.
    * **Three approaches compared:**

    | Approach                 | Time | Space | When to prefer                                                                                                |
    | ------------------------ | ---- | ----- | ------------------------------------------------------------------------------------------------------------- |
    | Prefix/suffix max arrays | O(n) | O(n)  | Easiest to understand and code correctly in an interview. Good default.                                       |
    | Two pointers             | O(n) | O(1)  | When the interviewer explicitly asks for O(1) space or you are confident in the invariant.                    |
    | Monotonic stack          | O(n) | O(n)  | When the problem is framed as "horizontal layers" or you need to process bars left-to-right only (streaming). |

    * **My interview strategy:** I would start by explaining the prefix/suffix approach (simpler, harder to get wrong), then optimize to two pointers if asked for O(1) space.

    ```python theme={null}
    # Two-pointer: process the bottleneck side first
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]  # safe: right_max >= left_max
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]  # safe: left_max >= right_max
    ```

    **Red flag answer:** Jumping straight to the two-pointer solution without being able to explain the invariant. If a candidate says "we track the max from both sides and add the difference" but cannot explain WHY processing the smaller-max side first is valid, they memorized the code. Also a red flag: not knowing the prefix array approach exists.

    **Follow-ups:**

    1. What if this is a 2D grid instead of 1D bars (LC 407 -- Trapping Rain Water II)? Does two-pointer generalize? (Answer: no. You need a priority queue / BFS approach processing the boundary inward. The 1D invariant does not extend to 2D because water can escape in multiple directions.)
    2. If the input is a stream of heights arriving one at a time and you need a running total of trapped water, which approach adapts best? (Answer: the monotonic stack approach adapts most naturally to streaming, since it processes left-to-right. Two pointers requires the full array upfront.)
  </Accordion>

  <Accordion title="Q6: Given a string, find the length of the longest substring without repeating characters. Is two pointers the right approach?" icon="text">
    **Difficulty:** Intermediate (pattern misidentification trap)

    **What interviewers are really testing:** Whether the candidate distinguishes between **two pointers** and **sliding window** -- they are related but not identical. This problem is sliding window, not classic two pointers. Candidates who lump them together reveal shallow pattern understanding.

    **Strong answer:**

    * This is a **sliding window** problem, not a classic two-pointer problem. The distinction matters:
      * **Two pointers** typically work on sorted data or compare elements at both ends. Pointer movement is driven by **comparison logic** (sum too big/small, palindrome match/mismatch).
      * **Sliding window** maintains a **window with an invariant** (in this case, "no repeating characters") and expands/shrinks to maintain it. Pointer movement is driven by **window validity**.
    * The approach: expand the right pointer to grow the window. When a duplicate is found, shrink from the left until the window is valid again. Use a HashSet or HashMap to track characters in the current window.
    * **Complexity:** O(n) time (each character is added and removed from the set at most once), O(min(n, alphabet\_size)) space.

    ```python theme={null}
    def length_of_longest_substring(s):
        char_index = {}
        left = 0
        max_length = 0

        for right in range(len(s)):
            if s[right] in char_index and char_index[s[right]] >= left:
                left = char_index[s[right]] + 1
            char_index[s[right]] = right
            max_length = max(max_length, right - left + 1)

        return max_length
    ```

    **Red flag answer:** "I would use two pointers starting from both ends" -- this is completely wrong for this problem since you need to scan left-to-right maintaining a window. Another red flag: calling it "two pointers" without distinguishing the sliding window invariant. If a candidate cannot explain why converging pointers would fail here, they do not understand either pattern deeply enough.

    **Follow-ups:**

    1. What if instead of "no repeating characters" the constraint is "at most K distinct characters"? How does your approach change? (Answer: same sliding window, but the HashMap tracks character counts. Shrink when distinct count exceeds K.)
    2. Can you solve this with O(1) space if the input is guaranteed to be lowercase English letters only? (Answer: yes, use a fixed-size array of 26 instead of a HashMap. Space is O(1) since it does not grow with input size.)
  </Accordion>

  <Accordion title="Q7: You have a sorted array with duplicates. Remove duplicates in-place so each element appears at most twice. How does this change the fast-slow pointer approach?" icon="filter">
    **Difficulty:** Intermediate

    **What interviewers are really testing:** Whether the candidate can **adapt a known template** to a modified constraint, rather than only solving the exact problem they memorized. This is LC 80 (Remove Duplicates II) and tests flexible thinking with the fast-slow pattern.

    **Strong answer:**

    * The standard remove-duplicates uses `slow` to track the write position and skips when `arr[fast] == arr[slow]`. For "at most twice," we need to compare `arr[fast]` against `arr[slow - 1]` (two positions back) instead of `arr[slow]`.
    * **Key insight:** If `arr[fast] == arr[slow - 1]`, we already have two copies of this value, so skip. Otherwise, write it.
    * **Generalization:** For "at most K duplicates," compare `arr[fast]` against `arr[slow - (K-1)]`. This is a clean generalization that interviewers love.
    * **Complexity:** O(n) time, O(1) space. Single pass.

    ```python theme={null}
    def remove_duplicates_at_most_twice(nums):
        if len(nums) <= 2:
            return len(nums)

        slow = 2  # First two elements are always valid

        for fast in range(2, len(nums)):
            if nums[fast] != nums[slow - 2]:
                nums[slow] = nums[fast]
                slow += 1

        return slow

    # Generalized for at most K duplicates:
    def remove_duplicates_at_most_k(nums, k):
        if len(nums) <= k:
            return len(nums)
        slow = k
        for fast in range(k, len(nums)):
            if nums[fast] != nums[slow - k]:
                nums[slow] = nums[fast]
                slow += 1
        return slow
    ```

    **Red flag answer:** Using a counter variable to track how many times the current element has appeared. While this works, it is more complex and error-prone than the `slow - 2` comparison trick. An even worse red flag: not realizing the array must be sorted for this approach to work, or wanting to use extra space.

    **Follow-ups:**

    1. What if the array is not sorted? Can you still remove elements appearing more than twice in O(n) time? (Answer: you need a HashMap to count frequencies, then a second pass to filter. O(n) time but O(n) space. Two pointers alone cannot solve this on unsorted input.)
    2. The interviewer says: "Now do it where each element appears at most K times, and K is a parameter." Write it generalized. (Answer: shown above. Tests whether the candidate can abstract a pattern into a parameter.)
  </Accordion>

  <Accordion title="Q8: Given an array of n integers and a target, find the number of unique quadruplets that sum to the target. What is the best approach?" icon="cubes">
    **Difficulty:** Senior

    **What interviewers are really testing:** Whether the candidate can extend the two-pointer pattern to higher dimensions (4Sum), reason about time complexity of nested approaches, and apply pruning optimizations that show real problem-solving maturity.

    **Strong answer:**

    * **Approach:** Sort the array. Use two nested loops to fix the first two elements. For the remaining two, use converging two pointers. This gives O(n^3) time.
    * **Duplicate handling:** Skip duplicates at each level -- for the first loop, second loop, and within the two-pointer scan. Same logic as 3Sum but applied at more levels.
    * **Critical pruning optimizations** (what separates good from great):
      1. **Early termination (too small):** If `nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target`, break the outer loop -- all remaining sums are larger.
      2. **Early termination (too large):** If `nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target`, skip this `i` -- even the largest possible sum with this `i` is too small.
      3. Same pruning applies at the second loop level.
    * **Complexity:** O(n^3) time worst case, O(1) space (excluding output). With pruning, practical performance is much better.
    * **Why not HashMap?** You could use a HashMap of pair sums for O(n^2) time, but handling duplicates becomes extremely messy and the space is O(n^2). For an interview, the sorted + nested two-pointer approach is cleaner and safer to implement.

    ```python theme={null}
    def four_sum(nums, target):
        nums.sort()
        n = len(nums)
        result = []

        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # Pruning
            if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
                break
            if nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target:
                continue

            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                left, right = j + 1, n - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1
        return result
    ```

    **Red flag answer:** Not being able to articulate the time complexity (saying O(n^2) because "two pointers is O(n)"). The correct reasoning: two outer loops O(n^2) times the two-pointer scan O(n) = O(n^3). Another red flag: implementing it without any pruning, then being unable to suggest optimizations when prompted.

    **Follow-ups:**

    1. What is the general time complexity for K-Sum using this approach? (Answer: O(n^(K-1)). You nest K-2 loops and use two pointers for the innermost pair.)
    2. For very large arrays where O(n^3) is too slow, can you think of a meet-in-the-middle approach? What is its complexity? (Answer: compute all pair sums in O(n^2), sort them, then use two pointers on the pair-sum array to find complementary pairs. Time is O(n^2 log n), but duplicate handling and reconstructing original indices is tricky.)
  </Accordion>

  <Accordion title="Q9: Given an unsorted array, find the shortest subarray that, if sorted, would make the entire array sorted. Which technique applies?" icon="arrow-down-short-wide">
    **Difficulty:** Senior

    **What interviewers are really testing:** Whether the candidate can apply two pointers in a **non-obvious** setting. This is not the classic sorted-array two-pointer usage -- it requires finding boundaries from both ends using a monotonicity invariant. Tests creative application of the pattern beyond textbook scenarios.

    **Strong answer:**

    * **Approach:** Use two pointers, but not the classic converging pair. Scan from the left to find the rightmost element that is "out of order" (smaller than some element to its left). Scan from the right to find the leftmost element that is "out of order" (larger than some element to its right).
    * **Detailed steps:**
      1. Traverse left to right, tracking the running maximum. Whenever `nums[i] < max_so_far`, this position needs to be inside the sorted subarray. Track the rightmost such position as `right_bound`.
      2. Traverse right to left, tracking the running minimum. Whenever `nums[i] > min_so_far`, this position needs to be inside the sorted subarray. Track the leftmost such position as `left_bound`.
      3. The answer is `right_bound - left_bound + 1`. If no such bounds exist, the array is already sorted (return 0).
    * **Why this works:** Any element that violates the monotonicity when scanning from either end MUST be included in the subarray that needs sorting.
    * **Complexity:** O(n) time, O(1) space. Two passes.

    ```python theme={null}
    def find_unsorted_subarray(nums):
        n = len(nums)
        max_seen, min_seen = float('-inf'), float('inf')
        right_bound, left_bound = -1, -1

        # Left to right: find rightmost element out of place
        for i in range(n):
            if nums[i] < max_seen:
                right_bound = i
            max_seen = max(max_seen, nums[i])

        # Right to left: find leftmost element out of place
        for i in range(n - 1, -1, -1):
            if nums[i] > min_seen:
                left_bound = i
            min_seen = min(min_seen, nums[i])

        if right_bound == -1:
            return 0  # Already sorted
        return right_bound - left_bound + 1
    ```

    **Red flag answer:** "Sort the array and compare with the original to find the first and last mismatched positions." While this gives the correct answer, it is O(n log n) time and O(n) space. If a candidate cannot improve beyond this, they do not understand how to use pointer-based scanning. Another red flag: trying to use converging two pointers from both ends simultaneously, which does not work here because the "out of place" boundaries are not symmetric.

    **Follow-ups:**

    1. Can you prove that sorting just this subarray is sufficient? What if an element outside the subarray is affected? (Answer: by construction, all elements left of `left_bound` are smaller than everything in the subarray and already sorted, and all elements right of `right_bound` are larger and already sorted. So sorting the subarray restores global order.)
    2. How would you adapt this if the requirement changes to "find the shortest subarray to REVERSE (not sort) to make the array sorted"? (Answer: much harder. The subarray to reverse must form a decreasing sequence that, when flipped, creates a valid sorted array. This requires checking that the reversed subarray merges correctly with both ends.)
  </Accordion>

  <Accordion title="Q10: You need to merge two sorted arrays into the first array which has enough trailing space. The naive approach copies to a new array. Can you do better?" icon="code-merge">
    **Difficulty:** Foundational (but the insight is the real test)

    **What interviewers are really testing:** Whether the candidate recognizes that **starting from the end** (reverse two-pointer) avoids overwriting elements that have not been processed yet. This is LC 88 (Merge Sorted Array) and is a classic interview warm-up that reveals whether a candidate truly understands pointer mechanics or just memorizes forward-scanning patterns.

    **Strong answer:**

    * **The key insight:** If you merge from the front, you overwrite elements in `nums1` that you still need. By merging from the **back** (placing the largest elements first), you fill the trailing empty space and never overwrite unprocessed elements.
    * Use three pointers: `p1` at the last real element of `nums1`, `p2` at the last element of `nums2`, and `write` at the very end of `nums1`. Compare `nums1[p1]` and `nums2[p2]`, place the larger one at `write`, and decrement.
    * **Edge case:** If `p2` finishes first, `nums1`'s remaining elements are already in place. If `p1` finishes first, copy the rest of `nums2`. The second case is the one most candidates forget.
    * **Complexity:** O(m + n) time, O(1) space. Truly in-place.

    ```python theme={null}
    def merge(nums1, m, nums2, n):
        p1, p2, write = m - 1, n - 1, m + n - 1

        while p1 >= 0 and p2 >= 0:
            if nums1[p1] >= nums2[p2]:
                nums1[write] = nums1[p1]
                p1 -= 1
            else:
                nums1[write] = nums2[p2]
                p2 -= 1
            write -= 1

        # If nums2 has remaining elements, copy them
        while p2 >= 0:
            nums1[write] = nums2[p2]
            p2 -= 1
            write -= 1
        # No need to handle remaining nums1 -- already in place
    ```

    **Red flag answer:** "Create a temporary array, merge into it, copy back." This works but uses O(m + n) space and shows the candidate did not consider the reverse-direction insight. Also a red flag: writing the forward merge and not realizing it overwrites needed data until the interviewer points it out.

    **Follow-ups:**

    1. Why do we not need to handle the case where `p1` still has elements remaining? (Answer: those elements are already in their correct positions in `nums1`. Since we are writing from the back and `nums1` is sorted, any remaining `nums1` elements are the smallest and are already at the front.)
    2. What if instead of two sorted arrays, you had K sorted arrays and needed to merge them all? Does the two-pointer approach scale, or do you need a fundamentally different technique? (Answer: for K arrays, use a min-heap / priority queue of size K. Two pointers does not generalize to K-way merge efficiently -- pairwise merging would be O(nK) vs O(n log K) with a heap.)
  </Accordion>
</AccordionGroup>