🗓️ Day 12: Two Pointers Technique

🧠 Concept Deep Dive

The Two Pointers technique is a common and powerful pattern used to solve array and string problems efficiently. The idea is to use two pointers (or indices) that traverse the data structure — either from both ends, or one fast and one slow — to reduce the need for nested loops.

🔹 When to Use Two Pointers

• Sorted arrays or strings
• Searching for pairs, triplets, or subsequences
• Problems where brute-force takes O(n²), but optimized to O(n)

🔹 Common Two Pointer Patterns

1. Opposite Ends: Start one pointer at the beginning, the other at the end, and move them inward.
2. Same Direction: Start both at the beginning and move the fast pointer ahead of the slow one.
3. Sliding Variation: Combine with sliding window logic.

📖 Example 1: Two Sum in Sorted Array

Problem:

Given a sorted array, find two numbers that sum up to a target.

function twoSum(numbers: number[], target: number): number[] {
  let left = 0, right = numbers.length - 1;
  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) return [left + 1, right + 1]; // 1-based index
    else if (sum < target) left++;
    else right--;
  }
  return [];
}

Example:

Input: numbers = [2,7,11,15], target = 9  
Output: [1,2]  // 2 + 7 = 9

📖 Example 2: Remove Duplicates from Sorted Array

Problem:

Remove duplicates in-place from a sorted array and return the new length.

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
  let slow = 1;
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow] = nums[fast];
      slow++;
    }
  }
  return slow;
}

Example:

Input: nums = [1,1,2]  
Output: 2  // [1,2]

🔬 Real-world Analogy

Imagine two people scanning a long shelf of books for a match. One starts at the beginning, one at the end. They move inward until they both point to the perfect pair — fast, coordinated, and no need to check every combination.

📊 Big O Complexity

🧪 LeetCode-style Homework

Problem: Move Zeroes

Move all zeroes to the end of an array while maintaining the relative order of non-zero elements.

function moveZeroes(nums: number[]): void {
  let lastNonZero = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      [nums[i], nums[lastNonZero]] = [nums[lastNonZero], nums[i]];
      lastNonZero++;
    }
  }
}

Example:

Input: [0,1,0,3,12]  
Output: [1,3,12,0,0]

🗓️ Summary

• Two Pointers work on sorted or linear structures
• Efficient for pair search, partitioning, or compaction
• Often replaces brute-force O(n²) with O(n)

🔮 Up Next

▶️ Day 13: Binary Search Basics