2 Pointers

Last updated: Apr 3, 2026

Pointer types
- Fast - Slow pointers
  - fast, slow pointers from same start point
- Left- Right pointers
  - left, right pointers from idx = 0, idx = len(n) - 1 respectively
  - Usually set
    - left pointer = 0
    - right pointer = len(nums)
  - binary search
  - array reverse
  - 2 sum
  - sliding window
Expand from center (and Deal with odd, even cases)
- LC 680
- LC 647
- LC 005
Merge Sorted Array
- LC 88
Minimum Swaps to Group All 1’s Together
- LC 1151 (check sliding_window.md)
Boats to Save People
- LC 881
move right pointer first, then move left point per condition
- LC 567
- LC 209 (see sliding window cheatsheet)
Subsequence Matching with character type constraints
- One pointer always moves, one conditionally moves
- Extra validation on non-matching characters
- LC 392 (Is Subsequence)
- LC 1023 (Camelcase Matching - with uppercase/lowercase constraint)
Algorithm
- binary search
- sliding window
- for loop + “expand left, right from center”
Data structure
- Array
- Linked list

0-2-0) Remove Duplicates from Sorted Array

// java
// LC 26 (LC 83)
// https://labuladong.online/algo/essential-technique/array-two-pointers-summary/#%E5%8E%9F%E5%9C%B0%E4%BF%AE%E6%94%B9
/**
 *  //--------------------------------
 *  Example 1
 *  //--------------------------------
 *
 *  nums = [1,1,2]
 *
 *  [1,1,2]
 *   s f
 *
 *  [1,2, 1]     if nums[f] != nums[s], move s, then swap f, s
 *   s s  f
 *
 *
 *   //--------------------------------
 *   Example 2
 *   //--------------------------------
 *
 *   nums = [0,0,1,1,1,2,2,3,3,4]
 *
 *   [0,0,1,1,1,2,2,3,3,4]
 *    s f
 *
 *   [0,1,0,1,1,2,2,3,3,4]   if nums[f] != nums[s], move s, then swap f, s
 *    s s f
 *
 *   [0,1,0,1,1,2,2,3,3,4]
 *      s   f
 *
 *   [0,1,0,1,1,2,2,3,3,4]
 *      s     f
 *
 *   [0,1,2,1,1,0,2,3,3,4]   if nums[f] != nums[s], move s, then swap f, s
 *      s s     f
 *
 *   [0,1,2,1,1,0,2,3,3,4]
 *        s       f
 *
 *   [0,1,2,3,1,0,2,1,3,4]  if nums[f] != nums[s], move s, then swap f, s
 *        s s       f
 *
 *   [0,1,2,3,1,0,2,1,3,4]
 *          s         f
 *
 *   [0,1,2,3,4,0,2,1,3,1]   if nums[f] != nums[s], move s, then swap f, s
 *          s s         f
 *
 */
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            // NOTE !!! if slow pointer != fast pointer
            if (nums[fast] != nums[slow]) {
                // NOTE !!! move slow pointer first
                slow++;
                // 维护 nums[0..slow] 无重复
                // NOTE !!! swap slow, fast pointer val
                nums[slow] = nums[fast];
            }
            fast++;
        }
        // 数组长度为索引 + 1
        return slow + 1;
    }
}

0-2-1) Remove Element

// java
// LC 27
// https://labuladong.online/algo/essential-technique/array-two-pointers-summary/#%E5%8E%9F%E5%9C%B0%E4%BF%AE%E6%94%B9
/**
 *  //--------------------
 *  Example 1
 *  //--------------------
 *
 *  nums = [3,2,2,3], val = 3
 *
 *  [3,2,2,3]
 *   s
 *   f
 *
 *  [2,3,2,3]    if nums[f] != val, swap, move s
 *   s s
 *     f
 *
 *  [2,2,3,3]   if nums[f] != val, swap, move s
 *     s s
 *       f
 *
 * [2,2,3,3]
 *      s
 *        f
 *
 *
 *  //--------------------
 *  Example 2
 *  //--------------------
 *
 *  nums = [0,1,2,2,3,0,4,2], val = 2
 *
 *
 *  [0,1,2,2,3,0,4,2]   if nums[f] != val, swap, move s
 *   s s
 *   f
 *
 *  [0,1,2,2,3,0,4,2]     if nums[f] != val, swap, move s
 *     s s
 *     f
 *
 *  [0,1,2,2,3,0,4,2]
 *       s
 *       f
 *
 * [0,1,2,2,3,0,4,2]
 *      s
 *        f
 *
 * [0,1,3,2,2,0,4,2]   if nums[f] != val, swap, move s
 *      s s
 *          f
 *
 * [0,1,3,0,2,2,4,2]   if nums[f] != val, swap, move s
 *        s s
 *            f
 *
 * [0,1,3,0,4,2,2,2]    if nums[f] != val, swap, move s
 *          s s
 *              f
 *
 *  [0,1,3,0,4,2,2,2]
 *             s
 *                 f
 */
class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0, slow = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

0-2-1b) Remove Element (Bidirectional Two Pointers)

Pattern: Left-Right pointers, shrink from both ends

Key difference from the fast-slow (0-2-1) approach:

Fast-slow overwrites sequentially → preserves relative order
Bidirectional replaces nums[l] with nums[r] → does NOT preserve order, but may do fewer writes (good when val is rare)

// java
// LC 27 Remove Element - Bidirectional variant
/**
 * Key Idea:
 *   - l starts at 0, r starts at nums.length - 1
 *   - If nums[l] == val, OVERWRITE it with nums[r] and shrink r
 *     (do NOT advance l yet — the new nums[l] might also be val)
 *   - If nums[l] != val, it is a "good" element → advance l
 *   - When l > r, l equals the count of valid elements
 *
 * //--------------------
 * Example 1
 * //--------------------
 * nums = [3,2,2,3], val = 3
 *
 * [3,2,2,3]   nums[l]=3==val, nums[l]=nums[r]=3, r--
 *  l     r
 *
 * [3,2,2,3]   nums[l]=3==val, nums[l]=nums[r]=2, r--
 *  l   r
 *
 * [2,2,2,3]   nums[l]=2!=val, l++
 *  l r
 *
 * [2,2,2,3]   nums[l]=2!=val, l++
 *    lr
 *
 * l(2) > r(1), return l = 2
 *
 * //--------------------
 * Example 2
 * //--------------------
 * nums = [0,1,2,2,3,0,4,2], val = 2
 *
 * [0,1,2,2,3,0,4,2]   nums[l]=0!=val, l++
 *  l               r
 *
 * [0,1,2,2,3,0,4,2]   nums[l]=1!=val, l++
 *    l             r
 *
 * [0,1,2,2,3,0,4,2]   nums[l]=2==val, nums[l]=nums[r]=2, r--
 *      l           r
 *
 * [0,1,2,2,3,0,4,2]   nums[l]=2==val, nums[l]=nums[r]=4, r--
 *      l         r
 *
 * [0,1,4,2,3,0,4,2]   nums[l]=4!=val, l++
 *      l       r
 *
 * [0,1,4,2,3,0,4,2]   nums[l]=2==val, nums[l]=nums[r]=0, r--
 *        l     r
 *
 * [0,1,4,0,3,0,4,2]   nums[l]=0!=val, l++
 *        l   r
 *
 * [0,1,4,0,3,0,4,2]   nums[l]=3!=val, l++
 *          l r
 *
 * l(5) > r(4), return l = 5
 *
 * Time: O(N), Space: O(1)
 */
public int removeElement(int[] nums, int val) {
    int l = 0;
    int r = nums.length - 1;

    while (l <= r) {
        if (nums[l] == val) {
            // Overwrite with rightmost element, shrink right boundary
            // NOTE: do NOT advance l — new nums[l] might also be val
            nums[l] = nums[r];
            r--;
        } else {
            // Good element confirmed, advance left
            l++;
        }
    }

    // l is exactly the count of non-val elements
    return l;
}

Comparison: Fast-Slow vs Bidirectional

Aspect	Fast-Slow (0-2-1)	Bidirectional (this)
Order	Preserves relative order	Does NOT preserve order
Writes	One write per valid element	Fewer writes when val is rare
Loop style	`for` loop (fast advances always)	`while (l <= r)`
When to use	Order matters	Order doesn’t matter, minimal writes

Similar Problems:

LC 27 Remove Element (this pattern)
LC 905 Sort Array By Parity — move evens left, odds right (same bidirectional shrink idea)
LC 75 Sort Colors (Dutch National Flag) — three-way bidirectional partition
LC 283 Move Zeroes — order matters, use fast-slow instead
LC 26 Remove Duplicates from Sorted Array — order matters, use fast-slow instead
LC 80 Remove Duplicates from Sorted Array II — order matters, use fast-slow instead

0-2-2) Move Zeros to End

// java
// LC 283 Move Zeroes
// https://leetcode.com/problems/move-zeroes/
/**
 * Pattern: Move all zeros (or specific elements) to the end while maintaining
 * the relative order of non-zero elements. Must be done in-place.
 *
 * Key Idea:
 *   - Both pointers (l and r) start from index 0
 *   - l tracks the position where the next non-zero should be placed
 *   - r scans through the array
 *   - When r finds a non-zero, swap with l and move l forward
 *   - This moves all zeros to the end naturally
 *
 * Difference from "Remove Element" pattern:
 *   - Remove Element: overwrites without caring about moved elements
 *   - Move Zeros: uses SWAP to preserve all elements in array
 *
 *  //--------------------
 *  Example 1
 *  //--------------------
 *
 *  nums = [0,1,0,3,12]
 *
 *  [0,1,0,3,12]
 *   l
 *   r
 *
 *  [0,1,0,3,12]    nums[r]=0, no swap, move r
 *   l
 *     r
 *
 *  [1,0,0,3,12]    nums[r]!=0, swap(l,r), move l and r
 *   l l
 *     r
 *
 *  [1,0,0,3,12]    nums[r]=0, no swap, move r
 *     l
 *       r
 *
 *  [1,3,0,0,12]    nums[r]!=0, swap(l,r), move l and r
 *     l l
 *         r
 *
 *  [1,3,12,0,0]    nums[r]!=0, swap(l,r), move l and r
 *        l  l
 *            r
 *
 *  //--------------------
 *  Example 2
 *  //--------------------
 *
 *  nums = [0]
 *  [0]
 *   l
 *   r
 *  -> only one element, no change
 *
 *  //--------------------
 *  Example 3
 *  //--------------------
 *
 *  nums = [1,0,2,0,3]
 *
 *  [1,0,2,0,3]    nums[r]!=0, swap(l,r), move l and r
 *   l l
 *   r
 *
 *  [1,0,2,0,3]    nums[r]=0, no swap, move r
 *     l
 *     r
 *
 *  [1,2,0,0,3]    nums[r]!=0, swap(l,r), move l and r
 *     l l
 *       r
 *
 *  [1,2,0,0,3]    nums[r]=0, no swap, move r
 *       l
 *         r
 *
 *  [1,2,3,0,0]    nums[r]!=0, swap(l,r), move l and r
 *       l l
 *           r
 *
 * Time: O(N), Space: O(1)
 */
class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length <= 1)
            return;

        // 'l' is the position where the next non-zero number should be placed
        int l = 0;

        /** NOTE !!!
         *
         *  BOTH l, r start from idx = 0
         */
        // Iterate through the array with 'r'
        for (int r = 0; r < nums.length; r++) {
            // If we find a non-zero element
            if (nums[r] != 0) {
                // Swap it with the element at position 'l'
                int tmp = nums[r];
                nums[r] = nums[l];
                nums[l] = tmp;

                /** NOTE !!!
                 *
                 *  Move 'l' forward if `we swap`
                 */
                // Move 'l' forward
                l++;
            }
        }
    }
}

Similar Problems:

LC 283 Move Zeroes (this pattern)
LC 27 Remove Element (overwrite version)
LC 905 Sort Array By Parity (move even numbers to front)
LC 922 Sort Array By Parity II (even/odd positioning)
LC 2460 Apply Operations to an Array
LC 1089 Duplicate Zeros (expanding array version)

0-2-3) for loop + “expand `left`, `right` from center”

# LC 005  Longest Palindromic Substring
# LC 647 Palindromic Substrings
# python
# pseudo code
# ...
for i in range(lens(s)):

    # NOTE !!!
    # NO NEED to have logic like `if i % 2 == 1`..
    # we can just consider `odd, even len` cases directly

    #--------------------------------------
    # if odd
    # NOTE !!! if `odd`, left = right = i
    #--------------------------------------
    left = right = i
    while left >= 0 and right < len(s) and s[left] == s[right]:
        if right+1-left > len(res):
            res = s[left:right+1]
        left -= 1
        right += 1
    
    #--------------------------------------
    # if even
    # NOTE !!! if `odd`, left = i - 1, right = i
    #--------------------------------------
    left = i - 1
    right = i
    while left >= 0 and right < len(s) and s[left] == s[right]:
        if right+1-left > len(res):
            res = s[left:right+1]
        left -= 1
        right += 1
# ...

0-2-4) Move `right pointer`, then move `left point`

// java
// LC 567

int l = 0;
for (int r = 0; r < s2.length(); r++){
    // ...

    if(some_condition){

        // ...
        // update map and move left pointer
        l += 1;
    }
}


// ...

0-2-5) Subsequence Matching (One Always Moves, One Conditionally Moves)

// java
// LC 392 Is Subsequence
// https://leetcode.com/problems/is-subsequence/

/**
 * Pattern: Check if string s is a subsequence of string t
 *
 * Key Idea:
 *   - Use two pointers: i for s (target subsequence), j for t (main string)
 *   - ALWAYS move j (scan through entire t)
 *   - ONLY move i when characters match
 *   - If i reaches end of s, we found all characters in order
 *
 * Example:
 *   s = "abc", t = "ahbgdc"
 *
 *   [a h b g d c]    i=0, j=0, s[i]=a, t[j]=a, match! i++, j++
 *    i j
 *
 *   [a h b g d c]    i=1, j=1, s[i]=b, t[j]=h, no match, j++
 *      i j
 *
 *   [a h b g d c]    i=1, j=2, s[i]=b, t[j]=b, match! i++, j++
 *        i j
 *
 *   [a h b g d c]    i=2, j=3, s[i]=c, t[j]=g, no match, j++
 *          i j
 *
 *   [a h b g d c]    i=2, j=4, s[i]=c, t[j]=d, no match, j++
 *            i j
 *
 *   [a h b g d c]    i=2, j=5, s[i]=c, t[j]=c, match! i++, j++
 *              i j
 *
 *   i == s.length() -> return true
 */
public boolean isSubsequence(String s, String t) {
    if (s.isEmpty())
        return true;
    if (t.isEmpty())
        return false;

    int i = 0; // Pointer for s (target subsequence)
    int j = 0; // Pointer for t (main string)

    /** NOTE !!!
     *
     *  the while loop condition:
     *
     *     i < s.length()
     *     &&
     *     j < t.length()
     */
    while (i < s.length() && j < t.length()) {
        // If characters match, move the pointer for s
        if (s.charAt(i) == t.charAt(j)) {
            i++;
        }
        // Always move the pointer for t
        j++;
    }

    // If i reached the end of s, all characters were found in order
    return i == s.length();
}

Classic Problems:

LC 392 Is Subsequence
LC 524 Longest Word in Dictionary through Deleting
LC 792 Number of Matching Subsequences

0-2-6) Pattern Matching with Character Type Constraints (CamelCase Matching)

// java
// LC 1023 Camelcase Matching
// https://leetcode.com/problems/camelcase-matching/

/**
 * Pattern: Subsequence matching with character type validation
 *
 * Key Idea:
 *   - Similar to subsequence matching, but with EXTRA CONSTRAINT
 *   - Use two pointers: i for query, j for pattern
 *   - ALWAYS move i (scan through entire query)
 *   - ONLY move j when characters match
 *   - CRITICAL: Any non-matching character in query MUST be lowercase
 *     (uppercase non-match = invalid)
 *
 * Core Logic:
 *   1. All pattern characters must appear in query in same order (subsequence)
 *   2. Any extra characters in query MUST be lowercase
 *   3. If we encounter an extra uppercase letter → immediate failure
 *
 * Example 1:
 *   query = "FooBar", pattern = "FB"
 *
 *   [F o o B a r]    i=0, j=0, query[i]=F, pattern[j]=F, match! j++
 *    i j
 *
 *   [F o o B a r]    i=1, j=1, query[i]=o, pattern[j]=B, no match
 *      i j           but 'o' is lowercase → OK, i++
 *
 *   [F o o B a r]    i=2, j=1, query[i]=o, pattern[j]=B, no match
 *        i j         but 'o' is lowercase → OK, i++
 *
 *   [F o o B a r]    i=3, j=1, query[i]=B, pattern[j]=B, match! j++
 *          i j
 *
 *   [F o o B a r]    i=4, j=2, query[i]=a, pattern[j]=none, no match
 *            i       but 'a' is lowercase → OK, i++
 *
 *   [F o o B a r]    i=5, j=2, query[i]=r, pattern[j]=none, no match
 *              i     but 'r' is lowercase → OK, i++
 *
 *   j == pattern.length() → return true
 *
 * Example 2:
 *   query = "FooBarTest", pattern = "FB"
 *
 *   ... (matches F, o, o, B, a, r) ...
 *
 *   [F o o B a r T e s t]    i=6, j=2, query[i]=T
 *                  i         'T' is UPPERCASE but not in pattern
 *                            → return false immediately!
 *
 * Pointer Behavior:
 *   - i (Explorer): Moves EVERY step, scans all characters
 *   - j (Goal Tracker): ONLY moves when finding matching character
 *   - Safety Check: Non-matching uppercase → instant failure
 *
 * Time: O(M) where M = query length
 * Space: O(1)
 */
public List<Boolean> camelMatch(String[] queries, String pattern) {
    List<Boolean> result = new ArrayList<>();

    for (String query : queries) {
        result.add(isMatch(query, pattern));
    }

    return result;
}

private boolean isMatch(String query, String pattern) {
    /** NOTE !!!
     *
     *  Two pointers:
     *    i: query pointer (always moves)
     *    j: pattern pointer (conditionally moves)
     */
    int i = 0; // Pointer for query
    int j = 0; // Pointer for pattern

    while (i < query.length()) {
        char qChar = query.charAt(i);

        /** NOTE !!!
         *
         *  Three cases:
         *
         *  Case 1: Characters match
         *    → Move both pointers
         *
         *  Case 2: Characters don't match AND query char is lowercase
         *    → OK! This is allowed insertion, move i only
         *
         *  Case 3: Characters don't match AND query char is UPPERCASE
         *    → FAIL! Extra uppercase not allowed
         */

        // Case 1: If characters match, move the pattern pointer
        if (j < pattern.length() && qChar == pattern.charAt(j)) {
            j++;
        }
        // Case 3: If characters don't match, the extra character MUST be lowercase
        else if (Character.isUpperCase(qChar)) {
            return false;
        }
        // Case 2: Lowercase character that doesn't match → skip it

        // Always move the query pointer
        i++;
    }

    // Match is only valid if we successfully navigated through the entire pattern
    return j == pattern.length();
}

# python
# LC 1023 Camelcase Matching

def camelMatch(queries, pattern):
    """
    Pattern: Subsequence with character type constraints

    Core Trick:
      - query pointer ALWAYS moves (explorer)
      - pattern pointer ONLY moves on match (goal tracker)
      - Extra validation: non-matching chars MUST be lowercase

    Example:
      query = "FooBar", pattern = "FB"

      'F' == 'F' → match, j++
      'o' != 'B' → but lowercase, OK
      'o' != 'B' → but lowercase, OK
      'B' == 'B' → match, j++
      'a' (no pattern) → but lowercase, OK
      'r' (no pattern) → but lowercase, OK

      j reached end → True
    """
    result = []

    for query in queries:
        i, j = 0, 0
        is_valid = True

        while i < len(query):
            # Case 1: Match found
            if j < len(pattern) and query[i] == pattern[j]:
                j += 1
            # Case 2: Uppercase non-match → fail
            elif query[i].isupper():
                is_valid = False
                break
            # Case 3: Lowercase non-match → skip

            i += 1

        # Valid only if all pattern chars matched
        result.append(is_valid and j == len(pattern))

    return result

Key Differences from Standard Subsequence:

Aspect	Subsequence (LC 392)	CamelCase Matching (LC 1023)
Pattern	Any subsequence	Subsequence with type constraint
Non-match chars	Ignored	MUST be lowercase
Uppercase non-match	Ignored	Instant failure
Use case	General matching	Identifier/name matching

Visualization:

Pattern = "FB"

Query 1: "FooBar"
  F → match ✓
  o → lowercase non-match ✓
  o → lowercase non-match ✓
  B → match ✓
  a → lowercase non-match ✓
  r → lowercase non-match ✓
  Result: TRUE

Query 2: "FooBarTest"
  F → match ✓
  o → lowercase non-match ✓
  o → lowercase non-match ✓
  B → match ✓
  a → lowercase non-match ✓
  r → lowercase non-match ✓
  T → UPPERCASE non-match ✗ FAIL!
  Result: FALSE

Pointer Movement Rules:

i (Query Explorer):
- Moves forward EVERY step
- Scans every character in query
- Never goes backward
j (Pattern Goal Tracker):
- ONLY moves when finding matching character
- If j == pattern.length(), all pattern chars found
Safety Check:
- Non-matching uppercase → immediate return false
- Non-matching lowercase → continue (allowed insertion)

Classic Problems:

LC 1023 Camelcase Matching (this pattern)
LC 392 Is Subsequence (simpler version)
LC 524 Longest Word in Dictionary through Deleting
LC 792 Number of Matching Subsequences

0-2-3) QuickSelect (Partition Algorithm for Kth Element)

Pattern Overview: QuickSelect is a selection algorithm to find the Kth smallest/largest element in an unordered list. It’s related to QuickSort but only recurses into one side of the partition. This makes it O(n) average time instead of O(n log n).

Core Concept:

Given array: [3, 2, 1, 5, 6, 4], find 2nd largest (k=2)

QuickSort: Sorts entire array → O(n log n)
QuickSelect: Only finds the Kth element position → O(n) average

Key Insight:

After partitioning around a pivot, the pivot is in its final sorted position
If pivot index = k, we found the answer
If pivot index < k, search right partition
If pivot index > k, search left partition

Algorithm Steps:

Choose a pivot (usually last element, or random for better performance)
Partition array: elements < pivot on left, elements > pivot on right
If pivot position == k, return pivot value
If pivot position < k, recursively search right partition
If pivot position > k, recursively search left partition

Template 1: Kth Largest Element

# Python - QuickSelect for Kth Largest
def findKthLargest(nums, k):
    """
    Find Kth largest element using QuickSelect.

    Time: O(n) average, O(n^2) worst (if bad pivots)
    Space: O(1) iterative, O(log n) recursive

    Key: Kth largest means (n - k)th smallest in 0-indexed array
    """
    def partition(left, right):
        """
        Partition using last element as pivot.
        Returns pivot's final position.
        """
        pivot = nums[right]
        i = left  # Position where elements < pivot should go

        # Move all elements < pivot to the left
        for j in range(left, right):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

        # Place pivot in correct position
        nums[i], nums[right] = nums[right], nums[i]
        return i

    def quickselect(left, right, k_smallest):
        """
        QuickSelect to find k_smallest element (0-indexed).
        """
        if left == right:  # Only one element
            return nums[left]

        # Partition and get pivot position
        pivot_idx = partition(left, right)

        # Check if we found the answer
        if pivot_idx == k_smallest:
            return nums[pivot_idx]
        elif pivot_idx < k_smallest:
            # Search right partition
            return quickselect(pivot_idx + 1, right, k_smallest)
        else:
            # Search left partition
            return quickselect(left, pivot_idx - 1, k_smallest)

    # Kth largest = (n - k)th smallest (0-indexed)
    n = len(nums)
    return quickselect(0, n - 1, n - k)

# Example usage:
# nums = [3, 2, 1, 5, 6, 4], k = 2
# Result: 5 (2nd largest)

// Java - QuickSelect for Kth Largest
/**
 * LC 215 - Kth Largest Element in an Array
 *
 * time = O(N) average, O(N^2) worst
 * space = O(1) iterative, O(log N) recursive
 */
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        // Kth largest = (n - k)th smallest (0-indexed)
        return quickSelect(nums, 0, n - 1, n - k);
    }

    private int quickSelect(int[] nums, int left, int right, int kSmallest) {
        if (left == right) {
            return nums[left];
        }

        // Partition and get pivot position
        int pivotIdx = partition(nums, left, right);

        // Check if we found the answer
        if (pivotIdx == kSmallest) {
            return nums[pivotIdx];
        } else if (pivotIdx < kSmallest) {
            // Search right partition
            return quickSelect(nums, pivotIdx + 1, right, kSmallest);
        } else {
            // Search left partition
            return quickSelect(nums, left, pivotIdx - 1, kSmallest);
        }
    }

    private int partition(int[] nums, int left, int right) {
        // Use last element as pivot
        int pivot = nums[right];
        int i = left;  // Position for elements < pivot

        // Move all elements < pivot to the left
        for (int j = left; j < right; j++) {
            if (nums[j] < pivot) {
                swap(nums, i, j);
                i++;
            }
        }

        // Place pivot in correct position
        swap(nums, i, right);
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Visual Example: Finding 2nd Largest in [3, 2, 1, 5, 6, 4]

Target: k = 2 (2nd largest)
Array: [3, 2, 1, 5, 6, 4]
n = 6, so we need (n - k) = 4th smallest element (0-indexed)

Step 1: Partition with pivot = 4 (last element)
[3, 2, 1, 4, 6, 5]
         ↑
    pivot_idx = 3

  Elements < 4: [3, 2, 1]
  Pivot: 4 (at index 3)
  Elements > 4: [6, 5]

Check: pivot_idx (3) < k_smallest (4)
Action: Search right partition [6, 5]

Step 2: Partition right side [6, 5] with pivot = 5
[3, 2, 1, 4, 5, 6]
            ↑
    pivot_idx = 4

Check: pivot_idx (4) == k_smallest (4) ✓
Answer: nums[4] = 5 (2nd largest element)

Template 2: K Closest Points to Origin (LC 973)

# Python - K Closest Points using QuickSelect
def kClosest(points, k):
    """
    Find K closest points to origin using QuickSelect.

    Time: O(n) average
    Space: O(1)
    """
    def distance(point):
        return point[0] ** 2 + point[1] ** 2

    def partition(left, right):
        pivot_dist = distance(points[right])
        i = left

        for j in range(left, right):
            if distance(points[j]) < pivot_dist:
                points[i], points[j] = points[j], points[i]
                i += 1

        points[i], points[right] = points[right], points[i]
        return i

    def quickselect(left, right, k):
        if left == right:
            return

        pivot_idx = partition(left, right)

        if pivot_idx == k:
            return
        elif pivot_idx < k:
            quickselect(pivot_idx + 1, right, k)
        else:
            quickselect(left, pivot_idx - 1, k)

    # Find K smallest distances
    quickselect(0, len(points) - 1, k - 1)
    return points[:k]

// Java - K Closest Points
/**
 * LC 973 - K Closest Points to Origin
 *
 * time = O(N) average
 * space = O(1)
 */
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        quickSelect(points, 0, points.length - 1, k - 1);
        return Arrays.copyOfRange(points, 0, k);
    }

    private void quickSelect(int[][] points, int left, int right, int k) {
        if (left >= right) return;

        int pivotIdx = partition(points, left, right);

        if (pivotIdx == k) {
            return;
        } else if (pivotIdx < k) {
            quickSelect(points, pivotIdx + 1, right, k);
        } else {
            quickSelect(points, left, pivotIdx - 1, k);
        }
    }

    private int partition(int[][] points, int left, int right) {
        int[] pivot = points[right];
        int pivotDist = distance(pivot);
        int i = left;

        for (int j = left; j < right; j++) {
            if (distance(points[j]) < pivotDist) {
                swap(points, i, j);
                i++;
            }
        }

        swap(points, i, right);
        return i;
    }

    private int distance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }

    private void swap(int[][] points, int i, int j) {
        int[] temp = points[i];
        points[i] = points[j];
        points[j] = temp;
    }
}

Optimization: Randomized Pivot

# Randomized QuickSelect for better average performance
import random

def findKthLargest_randomized(nums, k):
    """
    Randomized pivot selection reduces worst-case probability.

    Time: O(n) average with high probability
    """
    def partition(left, right):
        # RANDOM pivot selection
        random_idx = random.randint(left, right)
        nums[random_idx], nums[right] = nums[right], nums[random_idx]

        pivot = nums[right]
        i = left

        for j in range(left, right):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

        nums[i], nums[right] = nums[right], nums[i]
        return i

    def quickselect(left, right, k_smallest):
        if left == right:
            return nums[left]

        pivot_idx = partition(left, right)

        if pivot_idx == k_smallest:
            return nums[pivot_idx]
        elif pivot_idx < k_smallest:
            return quickselect(pivot_idx + 1, right, k_smallest)
        else:
            return quickselect(left, pivot_idx - 1, k_smallest)

    n = len(nums)
    return quickselect(0, n - 1, n - k)

Partition Algorithm Variants

1. Hoare Partition (Two-Pointer from Ends):

def partition_hoare(nums, left, right):
    """
    Hoare's partition: pointers move from both ends.
    More efficient with fewer swaps.
    """
    pivot = nums[(left + right) // 2]  # Middle element as pivot
    i, j = left - 1, right + 1

    while True:
        # Move i right until element >= pivot
        i += 1
        while nums[i] < pivot:
            i += 1

        # Move j left until element <= pivot
        j -= 1
        while nums[j] > pivot:
            j -= 1

        if i >= j:
            return j

        nums[i], nums[j] = nums[j], nums[i]

2. Lomuto Partition (Single Pass):

def partition_lomuto(nums, left, right):
    """
    Lomuto's partition: single pointer from left.
    Simpler but may do more swaps.
    """
    pivot = nums[right]
    i = left

    for j in range(left, right):
        if nums[j] <= pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

    nums[i], nums[right] = nums[right], nums[i]
    return i

Classic LeetCode Problems

Problem	LC#	Difficulty	Variant	Key Insight
Kth Largest Element in Array	215	Medium	Basic QuickSelect	Find (n-k)th smallest
K Closest Points to Origin	973	Medium	Custom comparator	Partition by distance
Top K Frequent Elements	347	Medium	With frequency map	QuickSelect on frequencies
Top K Frequent Words	692	Medium	With frequency + trie	QuickSelect + lexicographic order
Kth Largest Element in Stream	703	Easy	Min heap alternative	QuickSelect for initialization
Find Kth Smallest Pair Distance	719	Hard	Binary search on answer	Not direct QuickSelect
Wiggle Sort II	324	Medium	3-way partition	Dutch national flag variant
Sort Colors	75	Medium	3-way partition	Dutch national flag
Kth Smallest Element in BST	230	Medium	In-order traversal	Not QuickSelect (tree structure)
Find Median from Data Stream	295	Hard	Two heaps	QuickSelect alternative

Performance Comparison

Algorithm	Average Time	Worst Time	Space	Use Case
QuickSelect	O(n)	O(n²)	O(1)	Find Kth element (unsorted)
QuickSelect (Randomized)	O(n)	O(n²) low prob	O(1)	Better average performance
Heap (Min/Max)	O(n log k)	O(n log k)	O(k)	Online/streaming data
Full Sort	O(n log n)	O(n log n)	O(1) or O(n)	Need sorted array anyway
Counting Sort	O(n + k)	O(n + k)	O(k)	Small integer range

When to Use QuickSelect:

✅ Need exactly Kth element, don’t need full sort
✅ Can modify input array (in-place)
✅ Offline algorithm (all data available)
✅ Large dataset where O(n) vs O(n log n) matters

When NOT to Use QuickSelect:

❌ Need all K elements in sorted order → Use heap or full sort
❌ Online/streaming data → Use heap
❌ Cannot modify input array → Use heap
❌ Worst-case guarantee needed → Use Median of Medians (O(n) worst-case)

Interview Tips

1. Common Mistakes:

Forgetting to convert “Kth largest” → “(n - k)th smallest”
Off-by-one errors with 0-indexed vs 1-indexed k
Not handling left == right base case
Infinite recursion when partition doesn’t move pivot

2. Optimization Techniques:

Randomized pivot: Reduces worst-case probability
Median-of-three: Choose median of first, middle, last elements as pivot
Iterative version: Avoid stack overflow for very large arrays
Tail recursion: Only recurse into smaller partition

3. Complexity Analysis:

Best/Average Case: O(n + n/2 + n/4 + ... + 1) = O(2n) = O(n)

Worst Case (bad pivots every time):
  O(n + (n-1) + (n-2) + ... + 1) = O(n²)

With randomized pivot:
  Worst case O(n²) probability → near zero for large n

4. Interview Talking Points:

“QuickSelect is like QuickSort but only recurses into one partition”
“Average O(n) is better than O(n log k) heap for finding single Kth element”
“Trade-off: Modifies array vs. heap keeps original”
“Randomized pivot gives O(n) with high probability”

5. Follow-up Questions:

Q: “What if we need all K elements sorted?”
- A: Use heap (O(n log k)) or partial QuickSort
Q: “What if array is read-only?”
- A: Copy to new array or use heap
Q: “Can we guarantee O(n) worst-case?”
- A: Yes, using Median of Medians algorithm (complex, rarely asked)

Advanced: Median of Medians (O(n) Worst-Case)

def findKthLargest_median_of_medians(nums, k):
    """
    Guaranteed O(n) worst-case using Median of Medians pivot selection.
    More complex but theoretically optimal.

    Time: O(n) worst-case
    Space: O(log n) recursion
    """
    def median_of_medians(left, right):
        """Find approximate median for good pivot."""
        if right - left < 5:
            return sorted(nums[left:right + 1])[len(nums[left:right + 1]) // 2]

        # Divide into groups of 5, find median of each
        medians = []
        for i in range(left, right + 1, 5):
            sub_right = min(i + 4, right)
            median = sorted(nums[i:sub_right + 1])[(sub_right - i) // 2]
            medians.append(median)

        # Recursively find median of medians
        return median_of_medians_list(medians)

    def partition(left, right, pivot_value):
        # Partition around pivot_value
        # ... implementation ...
        pass

    # Main quickselect with median of medians pivot
    # ... implementation ...
    pass

Note: Median of Medians is rarely implemented in interviews due to complexity. Randomized QuickSelect is preferred in practice.

1) General form

1-1) Basic OP

1-1-1 : Reverse Array

// java
void reverse(int[] nums){

    int left = 0;
    int right = nums.length - 1

    while (left < right){

        int tmp = nums(left);
        nums(left) = nums(right)
        nums(right) = tmp;
        
        left += 1;
        right -= 1;
    }
}

1-1-6: binary search

1-1-7: sliding window

2) LC Example

2-1) Remove Element

# python
# basic
class Solution(object):
    def removeElement(self, nums, val):
        length = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[length] = nums[i]
                length += 1
        return length

# LC 026 : Remove Duplicates from Sorted Array
# https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Array/remove-duplicates-from-sorted-array.py
# V0
# IDEA : 2 POINTERS: i, j
class Solution(object):
    def removeDuplicates(self, nums):
        # edge case
        if not nums:
            return
        i = 0
        for j in range(1, len(nums)):
            """
            NOTE !!!
             -> note this condition
             -> we HAVE to swap i+1, j once nums[i], nums[j] are different
             -> so we MAKE SURE there is no duplicate
            """
            if nums[j] != nums[i]:
                nums[i+1], nums[j] = nums[j], nums[i+1]
                i += 1

        #print ("nums = " + str(nums))
        return i+1

# V0'
# IDEA : 2 POINTERS
# HAVE A POINTER j STARTS FROM 0 AND THE OTHER POINTER i GO THROUGH nums
#  -> IF A[i] != A[j]
#     -> THEN SWITCH A[i] AND A[j+1]
#     -> and j += 1
# *** NOTE : it's swith A[j+1] (j+1) with A[i]
# DEMO 1 
# A = [1,1,1,2,3]
# s = Solution()
# s.removeDuplicates(A)
# [1, 1, 1, 2, 3]
# [1, 1, 1, 2, 3]
# [1, 1, 1, 2, 3]
# [1, 2, 1, 1, 3]
# [1, 2, 3, 1, 1]
#
# DEMO 2
# A = [1,2,2,3,4]
# s = Solution()
# s.removeDuplicates(A)
# A = [1, 2, 2, 3, 4]
# A = [1, 2, 2, 3, 4]
# A = [1, 2, 2, 3, 4]
# A = [1, 2, 2, 3, 4]
# A = [1, 2, 3, 2, 4]
# -> A = [1, 2, 3, 4, 2]
class Solution:
    def removeDuplicates(self, A):
        if len(A) == 0:
            return 0
        j = 0
        for i in range(0, len(A)):
            ###  NOTE : below condition
            if A[i] != A[j]:
                A[i], A[j+1] = A[j+1], A[i]
                j = j + 1
        return j+1

# LC 283 move-zeroes
# V0
class Solution(object):
    def moveZeroes(self, nums):
        y = 0
        for x in range(len(nums)):
            if nums[x] != 0:
                nums[x], nums[y] = nums[y], nums[x]
                y += 1
        return nums

# V0'
class Solution(object):
    def moveZeroes(self, nums):
        # edge case
        if not nums:
            return
        j = 0
        for i in range(1, len(nums)):
            # if nums[j] = 0, swap with nums[i]
            if nums[j] == 0:
                if nums[i] != 0:
                    nums[j], nums[i] = nums[i], nums[j]
                    j += 1
            # if nums[j] != 0, then move j (j+=1) for searching next 0
            else:
                j += 1
        return nums

# LC 080 : Remove Duplicates from Sorted Array II
# V0
# IDEA : 2 POINTERS
#### NOTE : THE nums already ordering
# DEMO
# example 1
# nums = [1,1,1,2,2,3]
#           i j
#           i   j
#        [1,1,2,1,2,3]
#             i   j
#        [1,1,2,2,1,3]
#               i   j
#
# example 2
# nums = [0,0,1,1,1,1,2,3,3] 
#           i j
#        [0,0,1,1,1,1,2,3,3]
#             i j
#        [0,0,1,1,1,1,2,3,3]
#               i j
#        [0,0,1,1,1,1,2,3,3]
#               i   j
#               i     j
#        [0,0,1,1,2,1,1,3,3]
#                 i     j  
#        [0,0,1,1,2,3,1,1,3]
#                   i     j
#        [0,0,1,1,2,3,3,1,1]
class Solution:
    def removeDuplicates(self, nums):
        if len(nums) < 3:
            return len(nums)

        ### NOTE : slow starts from 1
        slow = 1
        ### NOTE : fast starts from 2
        for fast in range(2, len(nums)):
            """
            NOTE : BELOW CONDITION

            1) nums[slow] != nums[fast]: for adding "1st" element
            2) nums[slow] != nums[slow-1] : for adding "2nd" element
            """
            if nums[slow] != nums[fast] or nums[slow] != nums[slow-1]:
                # both of below op are OK
                #nums[slow+1] = nums[fast]
                nums[slow+1], nums[fast] = nums[fast], nums[slow+1] 
                slow += 1
        return slow+1

2-2) Longest Palindromic Substring

# LC 005 Longest Palindromic Substring
# V0
# IDEA : TWO POINTERS
# -> DEAL WITH odd, even len cases
#  -> step 1) for loop on idx 
#  -> step 2) and start from "center" 
#  -> step 3) and do a while loop
#  -> step 4) check if len of sub str > 1
# https://leetcode.com/problems/longest-palindromic-substring/discuss/1025355/Easy-to-understand-solution-with-O(n2)-time-complexity
# Time complexity = best case O(n) to worse case O(n^2)
# Space complexity = O(1) if not considering the space complexity for result, as all the comparison happens in place.
class Solution:
    # The logic I have used is very simple, iterate over each character in the array and assming that its the center of a palindrome step in either direction to see how far you can go by keeping the property of palindrome true. The trick is that the palindrome can be of odd or even length and in each case the center will be different.
    # For odd length palindrome i am considering the index being iterating on is the center, thereby also catching the scenario of a palindrome with a length of 1.
    # For even length palindrome I am considering the index being iterating over and the next element on the left is the center.
    def longestPalindrome(self, s):

        if len(s) <= 1:
            return s

        res = []

        for idx in range(len(s)):
        
            """
            # CASE 1) : odd len
            # Check for odd length palindrome with idx at its center

            -> NOTE : the only difference (between odd, even len)
            
            -> NOTE !!!  : 2 idx : left = right = idx
            """
            left = right = idx
            # note the condition !!!
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > len(res):
                    res = s[left:right + 1]
                left -= 1
                right += 1
              
            """"
            # CASE 2) : even len  
            # Check for even length palindrome with idx and idx-1 as its center

            -> NOTE : the only difference (between odd, even len)

            -> NOTE !!!  : 2 idx : left = idx - 1,  right = idx
            """
            left = idx - 1
            right = idx
            # note the condition !!!
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > len(res):
                    res = s[left:right + 1]
                left -= 1
                right += 1

        return res

# V0'
# IDEA : TWO POINTER + RECURSION
# https://leetcode.com/problems/longest-palindromic-substring/discuss/1057629/Python.-Super-simple-and-easy-understanding-solution.-O(n2).
class Solution:
    def longestPalindrome(self, s):
        res = ""
        length = len(s)
        def helper(left, right):
            while left >= 0 and right < length and s[left] == s[right]:
                left -= 1
                right += 1      
            return s[left + 1 : right]
        
        for index in range(len(s)):
            res = max(helper(index, index), helper(index, index + 1), res, key = len)           
        return res

2-3) Container With Most Water

# LC 11 Container With Most Water
# V0 
# IDEA : TWO POINTERS 
class Solution(object):
    def maxArea(self, height):
        ans = 0
        l = 0
        r = len(height) - 1
        while l < r:
            ans = max(ans, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans

2-4) Longest Consecutive Sequence

# LC 128 Longest Consecutive Sequence

# V0
# IDEA : sliding window
class Solution(object):
    def longestConsecutive(self, nums):
        # edge case
        if not nums:
            return 0
        nums = list(set(nums))
        # if len(nums) == 1: # not necessary
        #     return 1
        # sort first
        nums.sort()
        res = 0
        l = 0
        r = 1
        """
        NOTE !!!

        Sliding window here :
            condition :  l, r are still in list (r < len(nums) and l < len(nums))

            2 cases

                case 1) nums[r] != nums[r-1] + 1
                    -> means not continous, 
                        -> so we need to move r to right (1 idx)
                        -> and MOVE l to r - 1, since it's NOT possible to have any continous subarray within [l, r] anymore
                case 2) nums[r] == nums[r-1] + 1
                        -> means there is continous subarray currently, so we keep moving r to right (r+=1) and get current max sub array length (res = max(res, r-l+1))
        """
        while r < len(nums) and l < len(nums):
            # case 1)
            if nums[r] != nums[r-1] + 1:
                r += 1
                l = (r-1)
            # case 2)
            else:
                res = max(res, r-l+1)
                r += 1
        # edge case : if res == 0, means no continous array (with len > 1), so we return 1 (a single alphabet can be recognized as a "continous assay", and its len = 1)
        return res if res > 1 else 1

# V0'
# IDEA : SORTING + 2 POINTERS
class Solution(object):
    def longestConsecutive(self, nums):
        # edge case
        if not nums:
            return 0

        nums.sort()
        cur_len = 1
        max_len = 1
        #print ("nums = " + str(nums))

        # NOTE : start from idx = 1
        for i in range(1, len(nums)):
            ### NOTE : start from nums[i] != nums[i-1] case
            if nums[i] != nums[i-1]:
                ### NOTE : if nums[i] == nums[i-1]+1 : cur_len += 1
                if nums[i] == nums[i-1]+1:
                    cur_len += 1
                ### NOTE : if nums[i] != nums[i-1]+1 : get max len, and reset cur_lent as 1
                else:
                    max_len = max(max_len, cur_len)
                    cur_len = 1
        # check max len again
        return max(max_len, cur_len)

2-6) Palindromic Substrings

# LC 647. Palindromic Substrings
# V0'
# IDEA : TWO POINTERS
# https://leetcode.com/problems/palindromic-substrings/discuss/1041760/Python-Easy-Solution-Beats-85
# https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/String/longest-palindromic-substring.py
class Solution:
    def countSubstrings(self, s):
        ans = 0    
        for i in range(len(s)):
            # odd
            ans += self.helper(s, i, i)
            # even
            ans += self.helper(s, i, i + 1)  
        return ans
        
    def helper(self, s, l, r):     
        ans = 0    
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
            ans += 1          
        return ans

# V0
# IDEA : BRUTE FORCE
class Solution(object):
    def countSubstrings(self, s):
        count = 0
        # NOTE: since i from 0 to len(s) - 1, so for j we need to "+1" then can get go throgh all elements in str
        for i in range(len(s)):
            # Note : for j we need to "+1"
            for j in range(i+1, len(s)+1):
                if s[i:j] == s[i:j][::-1]:
                    count += 1
        return count

# V0''
# IDEA : TWO POINTERS (similar as LC 005)
class Solution(object):
    def countSubstrings(self, s):
        count = 0
        for i in range(len(s)):
            # for every single character
            count += 1
            
            # case 1) palindromic substrings length is odd 
            left = i - 1
            right = i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1

            # case 2) palindromic substrings length is even 
            left = i - 1
            right = i
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1

        return count

2-7) Sum of Subarray Ranges

# LC 2104. Sum of Subarray Ranges
# V0
# IDEA : BRUTE FORCE
class Solution:
    def subArrayRanges(self, nums):
        res = 0
        for i in range(len(nums)):
            curMin = float("inf")
            curMax = -float("inf")
            for j in range(i, len(nums)):
                curMin = min(curMin, nums[j])
                curMax = max(curMax, nums[j])
                res += curMax - curMin
        return res

# V0'
# IDEA : INCREASING STACK
class Solution:
    def subArrayRanges(self, A0):
        res = 0
        inf = float('inf')
        A = [-inf] + A0 + [-inf]
        s = []
        for i, x in enumerate(A):
            while s and A[s[-1]] > x:
                j = s.pop()
                k = s[-1]
                res -= A[j] * (i - j) * (j - k)
            s.append(i)
            
        A = [inf] + A0 + [inf]
        s = []
        for i, x in enumerate(A):
            while s and A[s[-1]] < x:
                j = s.pop()
                k = s[-1]
                res += A[j] * (i - j) * (j - k)
            s.append(i)
        return res

2-8) Trapping Rain Water

# LC 42. Trapping Rain Water
# NOTE : there is also 2 scan, dp approaches
# V0'
# IDEA : TWO POINTERS 
# IDEA : CORE
#     -> step 1) use left_max, right_mex : record "highest" "wall" in left, right handside at current idx
#     -> step 2) 
#                case 2-1) if height[left] < height[right] : 
#                   -> all left passed idx's height is LOWER than height[right]
#                   -> so the "short" wall MUST on left
#                   -> and since we record left_max, so we can get trap amount based on left_max, height[left]
#                
#                case 2-2) if height[left] > height[right]
#                   -> .... (similar as above)
class Solution:
    def trap(self, height):
 
        if not height:
            return 0

        left_max = right_max = res = 0
        left, right = 0, len(height) - 1
 
        while left < right:
            if height[left] < height[right]:  # left pointer op
                if height[left] < left_max:
                    res += left_max - height[left]
                else:
                    left_max = height[left]
                left += 1  # move left pointer 
            else:
                if height[right] < right_max:  # right pointer op
                    res += right_max - height[right]
                else:
                    right_max = height[right]
                right -= 1  # move right pointer 
        return res

2-9) Next Permutation

# LC 31. Next Permutation
# V0
class Solution:
    def nextPermutation(self, nums):
        i = j = len(nums)-1
        while i > 0 and nums[i-1] >= nums[i]:
            i -= 1
        if i == 0:   # nums are in descending order
            nums.reverse()
            return 
        k = i - 1    # find the last "ascending" position
        while nums[j] <= nums[k]:
            j -= 1
        nums[k], nums[j] = nums[j], nums[k]  
        l, r = k+1, len(nums)-1  # reverse the second part
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l +=1
            r -= 1

# V0'
class Solution(object):
    def nextPermutation(self, num):
        k, l = -1, 0
        for i in range(len(num) - 1):
            if num[i] < num[i + 1]:
                k = i

        if k == -1:
            num.reverse()
            return

        for i in range(k + 1, len(num)):
            if num[i] > num[k]:
                l = i
        num[k], num[l] = num[l], num[k]
        num[k + 1:] = num[:k:-1] ### dounle check here ###

2-10) Valid Palindrome II (Palindrome with One Deletion)

Pattern: Two Pointers with Mismatch Handling

Check palindrome from both ends
On first mismatch, try TWO possibilities:
1. Skip left character (check s[l+1...r])
2. Skip right character (check s[l...r-1])
If EITHER works, return true
Use helper function to check palindrome in range

Key Insight:

Don’t remove character and create new string (O(N) space)
Instead, use pointers to check substring in-place (O(1) space)

// java
// LC 680. Valid Palindrome II
/**
 * Pattern: Palindrome with at most 1 deletion allowed
 *
 * Example:
 *   s = "abca"
 *
 *   [a b c a]    l=0, r=3, s[l]=a, s[r]=a, match! l++, r--
 *    l     r
 *
 *   [a b c a]    l=1, r=2, s[l]=b, s[r]=c, MISMATCH!
 *      l r       Try: skip b (check "ca") OR skip c (check "ba")
 *                     "ca" is NOT palindrome
 *                     "ba" is NOT palindrome
 *                BUT we need to check full substring!
 *
 *   Actually for "abca":
 *   - Try skip l: check "cba" -> isPali("abca", 2, 3) = true (just "a")
 *   - OR skip r: check "aba" -> isPali("abca", 1, 2) = true (just "b")
 *
 *   Either works -> return true
 *
 * Time: O(N), Space: O(1)
 */
public boolean validPalindrome(String s) {
    int l = 0;
    int r = s.length() - 1;

    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) {
            /** NOTE !!!
             *
             *  On mismatch, try BOTH possibilities:
             *    1. Skip left char  -> check s[l+1...r]
             *    2. Skip right char -> check s[l...r-1]
             *
             *  If EITHER is palindrome, we can make it work with 1 deletion
             */
            return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
        }
        l++;
        r--;
    }

    return true; // Already a perfect palindrome
}

/** NOTE !!!
 *
 *  Helper function with left, right pointers as parameters
 *  Checks if substring s[l...r] is palindrome
 *  NO new string created - check in place!
 */
private boolean isPalindrome(String s, int l, int r) {
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

# python
# LC 680. Valid Palindrome II
class Solution:
    def validPalindrome(self, s):

        l, r = 0, len(s) - 1

        while l < r:
            if s[l] != s[r]:
                """
                # NOTE this !!!!
                -> On mismatch, try skipping left OR right character
                -> Check if either resulting substring is palindrome
                """
                skip_left = s[l+1:r+1]   # skip s[l]
                skip_right = s[l:r]      # skip s[r]
                # NOTE this !!!!
                return skip_left == skip_left[::-1] or skip_right == skip_right[::-1]
            else:
                l += 1
                r -= 1

        return True

Common Mistakes:

❌ Creating new strings (O(N) space and time)
❌ Only trying to skip one side
✅ Use helper with pointers (O(1) space)
✅ Try BOTH skip possibilities

Similar Problems:

LC 680 Valid Palindrome II (this pattern)
LC 125 Valid Palindrome
LC 1216 Valid Palindrome III (k deletions allowed - DP)
LC 234 Palindrome Linked List

2-11) Merge Sorted Array

# LC 88. Merge Sorted Array
# V0
# IDEA : 2 pointers
### NOTE : we need to merge the sorted arrat to nums1 with IN PLACE (CAN'T USE EXTRA CACHE)
# -> SO WE START FROM RIGHT HAND SIDE (biggeest element) to LEFT HAND SIDE (smallest element)
# -> Then paste the remain elements
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        ### NOTE : we define 2 pointers (p, q) here
        p, q = m-1, n-1
        ### NOTE : the while loop conditions
        while p >= 0 and q >= 0:
            if nums1[p] > nums2[q]:
                #***** NOTE : WE START FROM p+q+1 index, since that's the count of non-zero elements in nums1, and nums2
                nums1[p+q+1] = nums1[p]
                p = p-1
            else:
                ### NOTE WE START FROM p+q+1 index, reason same as above
                nums1[p+q+1] = nums2[q]
                q = q-1
        # if there're still elements in nums2, we just replace the ones in nums1[:q+1] with them (nums2[:q+1])
        nums1[:q+1] = nums2[:q+1]

2-12) Interval List Intersections

// java
// LC 986
    public int[][] intervalIntersection_1(int[][] firstList, int[][] secondList) {
        if (firstList.length == 0 || secondList.length == 0)
            return new int[0][0];
    /**
     *  NOTE !!!!
     *   - i and j are pointers used to iterate through
     *      `firstList` and `secondList` respectively.
     *
     *   - `startMax` and `endMin` are used to compute
     *     the `intersection` of the current intervals
     *     from firstList and secondList.
     *
     *   - ans is a list to store the resulting intersection intervals.
     */
        int i = 0;
        int j = 0;
        int startMax = 0, endMin = 0;
        List<int[]> ans = new ArrayList<>();

    /**
     *
     *   - The loop continues as long as
     *      there are intervals remaining in `BOTH lists`.
     *
     *   - `startMax` is the maximum of the `START points` of the two
     *     intervals (firstList[i] and secondList[j]).
     *       -> This ensures the intersection starts no earlier than both intervals.
     *
     *   - `endMin` is the minimum of the `END points` of the two intervals.
     *
     *   - This ensures the intersection ends no later than the earlier of
     *     the two intervals.
     *
     */
    while (i < firstList.length && j < secondList.length) {
      startMax = Math.max(firstList[i][0], secondList[j][0]);
      endMin = Math.min(firstList[i][1], secondList[j][1]);

      // you have end greater than start and you already know that this interval is
      // surrounded with startMin and endMax so this must be the intersection
      /**
       *
       *  - If endMin >= startMax, it means there is an intersection between the two intervals.
       *    ->  Add the intersection [startMax, endMin] to the result list.
       */
      if (endMin >= startMax) {
        ans.add(new int[] {startMax, endMin});
      }

      // the interval with min end has been covered completely and have no chance to
      // intersect with any other interval so move that list's pointer
      /**
       * - Since the intervals are sorted and disjoint:
       *    - If the interval from firstList ends first (or at the same time), increment i.
       *    - If the interval from secondList ends first (or at the same time), increment j.
       *    -> This ensures that the interval which has been fully processed is skipped, moving to the next potential candidate for intersection.
       *
       */
      if (endMin == firstList[i][1]) i++;
      if (endMin == secondList[j][1]) j++;
        }

        return ans.toArray(new int[ans.size()][2]);
    }

2-13) Sort Colors (Dutch National Flag)

Pattern: Three-Way Partitioning with Two Pointers

Use three pointers: left (0s), mid (current), right (2s)
Partition array into three sections
Single pass solution

// java
// LC 75. Sort Colors
/**
 * Pattern: Dutch National Flag - Three-way partitioning
 *
 * Goal: Sort array with only 0, 1, 2 in one pass
 *
 * Pointers:
 *   - left: boundary for 0s (everything before left is 0)
 *   - mid: current element being examined
 *   - right: boundary for 2s (everything after right is 2)
 *
 * Example:
 *   nums = [2,0,2,1,1,0]
 *
 *   [2,0,2,1,1,0]    mid=0, nums[mid]=2, swap with right, right--
 *    l           r   [0,0,2,1,1,2]
 *    m
 *
 *   [0,0,2,1,1,2]    mid=0, nums[mid]=0, swap with left, left++, mid++
 *    l         r
 *    m
 *
 *   [0,0,2,1,1,2]    mid=1, nums[mid]=0, swap with left, left++, mid++
 *      l       r
 *      m
 *
 *   [0,0,2,1,1,2]    mid=2, nums[mid]=2, swap with right, right--
 *        l     r
 *        m
 *
 *   [0,0,1,1,2,2]    mid=2, nums[mid]=1, mid++
 *        l   r
 *        m
 *
 *   [0,0,1,1,2,2]    mid=3, nums[mid]=1, mid++
 *        l r
 *          m
 *
 *   mid > right, done!
 *
 * Time: O(N), Space: O(1)
 */
public void sortColors(int[] nums) {
    int left = 0;           // Next position for 0
    int mid = 0;            // Current examining position
    int right = nums.length - 1;  // Next position for 2

    while (mid <= right) {
        if (nums[mid] == 0) {
            // Found 0, swap to left
            swap(nums, left, mid);
            left++;
            mid++;
        } else if (nums[mid] == 2) {
            // Found 2, swap to right
            // NOTE: Don't increment mid yet, need to check swapped element
            swap(nums, mid, right);
            right--;
        } else {
            // Found 1, just move mid
            mid++;
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

Similar Problems:

LC 75 Sort Colors (this pattern)
LC 26 Remove Duplicates from Sorted Array
LC 80 Remove Duplicates from Sorted Array II
LC 283 Move Zeroes

2-14) 3Sum

Pattern: Two Pointers with Fixed First Element

Fix first element, use two pointers for remaining two
Avoid duplicates by skipping same values
Sort array first

// java
// LC 15. 3Sum
/**
 * Pattern: Fixed element + Two pointers
 *
 * Steps:
 *   1. Sort array
 *   2. Fix first element (i)
 *   3. Use two pointers (l, r) to find remaining two elements
 *   4. Skip duplicates
 *
 * Example:
 *   nums = [-1,0,1,2,-1,-4]
 *   After sort: [-4,-1,-1,0,1,2]
 *
 *   i=0, nums[i]=-4, l=1, r=5
 *   [-4,-1,-1,0,1,2]
 *     i  l       r    sum=-4+-1+2=-3 < 0, l++
 *
 *   i=1, nums[i]=-1, l=2, r=5
 *   [-4,-1,-1,0,1,2]
 *        i  l     r   sum=-1+-1+2=0, found! [-1,-1,2]
 *                     l++, r--, skip duplicates
 *
 *   [-4,-1,-1,0,1,2]
 *        i    l r     sum=-1+0+1=0, found! [-1,0,1]
 *
 * Time: O(N^2), Space: O(1) excluding result
 */
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);

    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;
        int right = nums.length - 1;
        int target = -nums[i];

        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                // Skip duplicates for second element
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                // Skip duplicates for third element
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }

                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

Similar Problems:

LC 15 3Sum (this pattern)
LC 16 3Sum Closest
LC 18 4Sum
LC 259 3Sum Smaller
LC 1 Two Sum

2-15) Reverse String / Reverse Words

Pattern: In-place Reversal with Two Pointers

// java
// LC 344. Reverse String
/**
 * Pattern: Swap from both ends moving toward center
 *
 * Example:
 *   s = ['h','e','l','l','o']
 *
 *   ['h','e','l','l','o']
 *     l           r       swap, l++, r--
 *
 *   ['o','e','l','l','h']
 *       l       r         swap, l++, r--
 *
 *   ['o','l','l','e','h']
 *           l r           l >= r, done!
 *
 * Time: O(N), Space: O(1)
 */
public void reverseString(char[] s) {
    int left = 0;
    int right = s.length - 1;

    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

Similar Problems:

LC 344 Reverse String
LC 345 Reverse Vowels of a String
LC 541 Reverse String II
LC 186 Reverse Words in a String II
LC 151 Reverse Words in a String

2-16) Shortest Palindrome (Find Longest Palindromic Prefix)

Pattern: Scan from right, track left pointer to find longest palindromic prefix

Core Idea:

Find the longest prefix of s that is already a palindrome
Reverse the remaining suffix and prepend it to s
Use two pointers: j anchored at 0 (left), i scans right-to-left
When s[i] == s[j], advance j — after the scan s[0..j-1] is the matched prefix
If j < n, recurse on s[0..j] and sandwich the non-palindrome suffix around it

Dry Run — s = "aacecaaa":

i scans right-to-left, j starts at 0

i=7 s[7]='a' == s[0]='a'  -> j=1
i=6 s[6]='a' == s[1]='a'  -> j=2
i=5 s[5]='a' != s[2]='c'  -> skip
i=4 s[4]='c' == s[2]='c'  -> j=3
i=3 s[3]='e' != s[3]='e'  -> j=4  (wait — equal!) -> j=4
i=2 s[2]='c' != s[4]='c'  -> j=5  -> j=5
i=1 s[1]='a' != s[5]='a'  -> j=6
i=0 s[0]='a' != s[6]='a'  -> j=7

j == n? No (j=7 < 8). suffix = s.substring(7) = "a"
reversed("a") + shortestPalindrome("aacecaa") + "a"

Key Insight — why does j track the prefix?

Scanning i from right to left acts like a "sieve":
- Every time s[i] matches s[j], j advances one step right
- After the full scan, s[0..j-1] is the longest possible palindromic prefix
  (not a strict palindrome proof, but works with the recursive structure)
- The characters NOT in the prefix (s[j..n-1]) form the suffix that
  must be reversed and prepended to make the whole string a palindrome

// java
// LC 214. Shortest Palindrome
/**
 * Pattern: Find longest palindromic prefix via right-to-left scan
 *
 * Step 1: Scan i from n-1 to 0, advance j when s[i] == s[j]
 * Step 2: j is now the length of the "matched" prefix
 * Step 3: suffix  = s.substring(j)        (non-palindrome tail)
 *         prefix  = reverse(suffix)        (chars to prepend)
 * Step 4: return prefix + shortestPalindrome(s[0..j]) + suffix
 *
 * Time: O(N^2) average (O(N) per recursion level, O(N) depth)
 * Space: O(N) recursion stack
 *
 * Example 1: s = "aacecaaa" -> "aaacecaaa"
 * Example 2: s = "abcd"     -> "dcbabcd"
 */
public String shortestPalindrome(String s) {
    if (s == null || s.length() <= 1) return s;

    int j = 0;

    /** NOTE !!!
     *  Scan from the RIGHT end toward left.
     *  j tracks how far into s we've "matched" from the front.
     */
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == s.charAt(j)) {
            j++;
        }
    }

    // Whole string is already a palindrome
    if (j == s.length()) return s;

    // suffix is the part NOT covered by the palindromic prefix
    String suffix = s.substring(j);
    String prefix = new StringBuilder(suffix).reverse().toString();

    /** NOTE !!!
     *  Recurse on s[0..j] to handle the inner part,
     *  then sandwich the current suffix around it.
     */
    return prefix + shortestPalindrome(s.substring(0, j)) + suffix;
}

// java
// LC 214. Shortest Palindrome — KMP approach (O(N) time)
/**
 * IDEA: KMP Prefix Table
 *
 * Combine s + "#" + reverse(s) into one string.
 * The KMP prefix table's last value gives the length of the
 * longest palindromic prefix of s.
 *
 * Time: O(N), Space: O(N)
 */
public String shortestPalindromeKMP(String s) {
    String rev = new StringBuilder(s).reverse().toString();
    String combined = s + "#" + rev;
    int[] table = buildPrefixTable(combined);

    int palindromeLen = table[combined.length() - 1];
    String suffix = new StringBuilder(s.substring(palindromeLen)).reverse().toString();
    return suffix + s;
}

private int[] buildPrefixTable(String s) {
    int[] table = new int[s.length()];
    int len = 0;
    for (int i = 1; i < s.length(); i++) {
        while (len > 0 && s.charAt(i) != s.charAt(len))
            len = table[len - 1];
        if (s.charAt(i) == s.charAt(len))
            len++;
        table[i] = len;
    }
    return table;
}

Brute-force version (TLE on large inputs):

// java — O(N^2) brute force
// Find largest i such that s[0..i] is a palindrome, then prepend reverse(s[i+1..n-1])
public String shortestPalindromeBrute(String s) {
    int n = s.length();
    if (n <= 1) return s;
    int end = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (isPalindrome(s, 0, i)) { end = i; break; }
    }
    String suffix = s.substring(end + 1);
    return new StringBuilder(suffix).reverse() + s;
}

private boolean isPalindrome(String s, int l, int r) {
    while (l < r) {
        if (s.charAt(l++) != s.charAt(r--)) return false;
    }
    return true;
}

Pointer Movement Comparison:

Approach	Left pointer `j`	Right pointer `i`	When `j` advances
Right-to-left scan	Anchored at 0, moves right	Scans n-1 → 0	`s[i] == s[j]`
Brute force isPalindrome	Expands from both ends	Starts at n-1, decrements	Always (matching chars)
KMP	N/A — uses prefix table	N/A	N/A

Similar Problems:

LC 214 Shortest Palindrome (this pattern)
LC 5 Longest Palindromic Substring (expand from center)
LC 647 Palindromic Substrings (expand from center)
LC 680 Valid Palindrome II (skip one char)
LC 516 Longest Palindromic Subsequence (DP)
LC 132 Palindrome Partitioning II (DP + palindrome check)
LC 336 Palindrome Pairs (hash map + palindrome prefix/suffix)

3) Classic LC Problems Summary

Easy:

LC 26 Remove Duplicates from Sorted Array
LC 27 Remove Element
LC 125 Valid Palindrome
LC 283 Move Zeroes
LC 344 Reverse String
LC 345 Reverse Vowels of a String
LC 349 Intersection of Two Arrays
LC 350 Intersection of Two Arrays II
LC 392 Is Subsequence
LC 680 Valid Palindrome II
LC 844 Backspace String Compare
LC 977 Squares of a Sorted Array

Medium:

LC 3 Longest Substring Without Repeating Characters (Sliding Window)
LC 5 Longest Palindromic Substring
LC 11 Container With Most Water
LC 15 3Sum
LC 16 3Sum Closest
LC 18 4Sum
LC 75 Sort Colors (Dutch National Flag)
LC 80 Remove Duplicates from Sorted Array II
LC 86 Partition List
LC 88 Merge Sorted Array
LC 142 Linked List Cycle II
LC 167 Two Sum II - Input Array Is Sorted
LC 209 Minimum Size Subarray Sum (Sliding Window)
LC 287 Find the Duplicate Number
LC 567 Permutation in String (Sliding Window)
LC 647 Palindromic Substrings
LC 713 Subarray Product Less Than K
LC 881 Boats to Save People
LC 986 Interval List Intersections
LC 1023 Camelcase Matching

Hard:

LC 42 Trapping Rain Water
LC 76 Minimum Window Substring (Sliding Window)
LC 214 Shortest Palindrome
LC 828 Count Unique Characters of All Substrings

4) Two Pointers Cheat Sheet

Pattern	When to Use	Example Problems
Opposite Direction	Sorted array, palindrome check	LC 167, LC 344, LC 125
Same Direction (Fast-Slow)	Remove duplicates, cycle detection	LC 26, LC 27, LC 142
Sliding Window	Subarray/substring problems	LC 3, LC 76, LC 209
Merge Two Lists	Merge sorted arrays/lists	LC 88, LC 21
Partition	Rearrange elements	LC 75, LC 86
Palindrome with Deletion	Allow k changes	LC 680, LC 1216
Fixed + Two Pointers	Sum problems (3Sum, 4Sum)	LC 15, LC 16, LC 18
Subsequence Matching	Check if one string is subsequence of another	LC 392, LC 524, LC 792
Pattern Match with Constraints	Subsequence + character type validation	LC 1023
Longest Palindromic Prefix	Find longest palindromic prefix, prepend reversed suffix	LC 214, LC 336

2 Pointers

Table of Contents