2 Pointers

Last updated: Jul 7, 2026

0) Concept
0-1) Types
0-2) Pattern
0-2-0) Remove Duplicates from Sorted Array — LC 26
0-2-0b) Remove Duplicates from Sorted Array II (LC 80) — LC 80
0-2-1) Remove Element — LC 27
0-2-1b) Remove Element (Bidirectional Two Pointers) — LC 27
0-2-2) Move Zeros to End — LC 283
0-2-7) Group-by-Group String Comparison (Expressive Words) — LC 809
0-2-8) Next Permutation — LC 31
0-2-9) DI String Match (Converging Low/High Pointers) — LC 942
0-2-3) QuickSelect (Partition Algorithm for Kth Element) — LC 215
1) General form
1-1) Basic OP
2) LC Example
2-1) Remove Element — LC 27
2-2) Longest Palindromic Substring — LC 5
2-3) Container With Most Water — LC 11
2-4) Longest Consecutive Sequence — LC 128
2-6) Palindromic Substrings — LC 647
2-7) Sum of Subarray Ranges — LC 2104
2-8) Trapping Rain Water — LC 42
2-9) Next Permutation — LC 31
2-10) Valid Palindrome II (Palindrome with One Deletion) — LC 680
2-11) Merge Sorted Array — LC 88
2-12) Interval List Intersections — LC 986
2-13) Sort Colors (Dutch National Flag) — LC 75
2-14) 3Sum — LC 15
2-14b) 3Sum Closest (LC 16) — LC 16
2-15) Reverse String / Reverse Words — LC 344
2-16) Shortest Palindrome (Find Longest Palindromic Prefix) — LC 214
2-17) Encode and Decode Strings (Length-Prefixed Two Pointers) — LC 271
3) Classic LC Problems Summary
Easy:
Medium:
Hard:
4) Two Pointers Cheat Sheet
Missing Google Patterns
Dutch National Flag (3-Way Partition) — LC 75 Sort Colors
Tortoise and Hare (Cycle Detection) — LC 141, LC 142
Merge Two Sorted Arrays — LC 88
Container With Most Water — LC 11
Valid Palindrome (Two Pointers from Edges) — LC 125, LC 680
Google Interview Tips for Two Pointers

Two pointers

Ref
- fucking-algorithm : 2 pointers

Step	Action	Why
`nums[fast] == nums[slow]`	Only advance `fast`	Duplicate — skip it
`nums[fast] != nums[slow]`	`slow++`, then write/swap	New unique found — claim next slot
Return	`slow + 1`	`slow` is index, length = index + 1

Problem	LC#	Difference	Key Trick
Remove Duplicates from Sorted Array	26	Allow each value once	`nums[slow] = nums[fast]` when different
Remove Duplicates from Sorted Array II	80	Allow each value at most twice	Compare `nums[fast]` with `nums[slow-1]` (two back)
Remove Element	27	Remove all occurrences of `val`	Write when `nums[fast] != val`
Move Zeroes	283	Move zeros to end, preserve order	Swap when `nums[fast] != 0`
Remove Duplicates from Sorted List	83	Linked list version of LC 26	`node.next = node.next.next` on duplicate
Remove Duplicates from Sorted List II	82	Delete ALL nodes with duplicate values	Extra sentinel node + skip entire duplicate group

Aspect	LC 26 (at most 1)	LC 80 (at most 2)
Condition	`nums[fast] != nums[slow - 1]`	`nums[fast] != nums[slow - 2]`
Init	`slow = 1, fast = 1`	`slow = 2, fast = 2`
Returns	`slow`	`slow`
Generalized	`k = 1`	`k = 2`

Problem	LC#	Key Difference
Remove Duplicates I	26	At most 1 copy — compare `nums[slow-1]`
Remove Duplicates II	80	At most 2 copies — compare `nums[slow-2]`
Remove Element	27	Remove all of a specific value
Move Zeroes	283	Keep zeros, move to end

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

Find a valid peak (a local maximum where both neighbors are strictly smaller), then expand left and right from that peak to find the full mountain base. This is different from the “expand from center” palindrome pattern: here you first validate the peak, then walk outward along strictly monotone slopes.

Key Optimization — i = right skip:

After fully processing a mountain, jump i directly to right (the right base). Without this, the outer loop would re-examine every index on the descending slope — giving O(N²). With it, no index is ever revisited, so total work across all mountains is O(N).

Without skip: outer loop backtracks over already-visited slope indices → O(N²)
With i = right: outer loop only ever moves forward → amortized O(N)

Pattern (Java — find-peak + expand-left/right):

java

// LC 845 - Longest Mountain in Array
// IDEA: For each valid peak, expand left and right; skip i to right base
// time = O(N), space = O(1)
public int longestMountain(int[] arr) {
    if (arr == null || arr.length < 3) return 0;
    int maxLen = 0, n = arr.length;

    for (int i = 1; i < n - 1; i++) {
        // Step 1: Check for a valid peak (strictly greater than both neighbors)
        if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {

            // Step 2: Expand LEFT — walk back while strictly increasing
            int left = i - 1;
            while (left > 0 && arr[left] > arr[left - 1]) left--;

            // Step 3: Expand RIGHT — walk forward while strictly decreasing
            int right = i + 1;
            while (right < n - 1 && arr[right] > arr[right + 1]) right++;

            // Step 4: Record length
            maxLen = Math.max(maxLen, right - left + 1);

            /** NOTE !!!
             *  Skip i to the right base to avoid re-scanning the descending slope.
             *  Without this, time complexity degrades to O(N²).
             *  With this, each element is visited at most twice → O(N).
             */
            i = right;
        }
    }
    return maxLen;
}

Dry-run — arr = [2,1,4,7,3,2,5]:

i=1: arr[1]=1, 1 > 2? No → skip
i=2: arr[2]=4, 4 > 1 && 4 > 7? No → skip
i=3: arr[3]=7, 7 > 4 && 7 > 3? YES → peak found
       expand left:  left=2 → left=1 (arr[1]=1 < arr[2]=4, stop)
       expand right: right=4 → right=5 (arr[5]=2 < arr[4]=3, stop; arr[6]=5 > arr[5]=2, STOP)
       len = right(5) - left(1) + 1 = 5  → maxLen = 5
       i = right = 5  ← SKIP over the descending slope

i=6: arr[6]=5, 5 > arr[5]=2 but 5 > arr[7]? out of bounds → skip (i=6 = n-2, loop ends)

Result: 5  (mountain = [1,4,7,3,2])

Alternative — while loop (explicit base tracking, V1 pattern):

java

// Scan from base; find ascending slope, peak, then descending slope in one pass
// time = O(N), space = O(1)
public int longestMountain_v1(int[] A) {
    int N = A.length, ans = 0, base = 0;
    while (base < N) {
        int end = base;
        if (end + 1 < N && A[end] < A[end + 1]) {      // found left slope
            while (end + 1 < N && A[end] < A[end + 1]) end++;  // climb to peak
            if (end + 1 < N && A[end] > A[end + 1]) {  // confirmed peak
                while (end + 1 < N && A[end] > A[end + 1]) end++; // descend
                ans = Math.max(ans, end - base + 1);
            }
        }
        base = Math.max(end, base + 1);  // advance base past processed segment
    }
    return ans;
}

Comparison of approaches:

Approach	Core pointer	Skip trick	When to use
Peak + expand (V0)	`i` scans for peaks; `left`/`right` expand	`i = right` after each mountain	Clearest structure
Base + climb (V1)	`base` tracks mountain start	`base = max(end, base+1)`	Single-pass, no look-around

Invariant for a valid mountain:

Peak must not be at index 0 or n-1
At least one element strictly ascending on the left
At least one element strictly descending on the right
No flat segments (strict inequality required on both slopes)

Similar LC problems:

Problem	LC#	Key Pattern
Longest Mountain in Array	845	Find peak → expand left/right → skip to right base
Valid Mountain Array	941	Single pass: go up then down, verify full coverage
Peak Index in Mountain Array	852	Binary search for peak in guaranteed mountain
Find Peak Element	162	Binary search: always move toward higher neighbor
Trapping Rain Water	42	Left/right expansion + height tracking
Longest Palindromic Substring	5	Expand from center (symmetric version of this pattern)
Count of Subarrays with Score less than K	2302	Slope expansion with sum tracking

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

java

// 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

// 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-5b) One Edit Distance (Insert / Delete / Replace)

Core Idea: Check whether two strings differ by exactly one edit (insert, delete, or replace).

Key observations:

If |len(s) - len(t)| > 1 → impossible, return false
If s == t → zero edits, return false
Always work with s as the shorter string (swap if needed)
Scan left-to-right: on the first mismatch, try the only possible operation and verify the remainder in O(1) with substring.equals()

Three cases at first mismatch:

Lengths	Operation	Check
`len(s) == len(t)`	Replace `s[i]`	`s[i+1..] == t[i+1..]`
`len(s) < len(t)`	Insert into s (skip t[i])	`s[i..] == t[i+1..]`
`len(s) > len(t)`	Delete from s (skip s[i])	`s[i+1..] == t[i..]`

After the loop (no mismatch found): valid only if len(t) == len(s) + 1 (one trailing insert).

Pattern (Java):

java

// LC 161 - One Edit Distance
public boolean isOneEditDistance(String s, String t) {
    int ns = s.length(), nt = t.length();

    // Ensure s is always the shorter string
    if (ns > nt) return isOneEditDistance(t, s);

    // Length gap > 1 → impossible
    if (nt - ns > 1) return false;

    for (int i = 0; i < ns; i++) {
        if (s.charAt(i) != t.charAt(i)) {
            if (ns == nt) {
                // Replace: rest of both strings must match
                return s.substring(i + 1).equals(t.substring(i + 1));
            } else {
                // Insert into s (skip one char in t)
                return s.substring(i).equals(t.substring(i + 1));
            }
        }
    }

    // No mismatch in s — valid only if t has exactly one extra trailing char
    return ns + 1 == nt;
}

Why substring comparison instead of continuing the loop? Once we find the first mismatch, there is only ONE valid repair move. Checking the suffix via substring.equals() resolves this in O(n) without needing extra flags or pointer bookkeeping.

Pointer movement summary:

Both i and j advance together while chars match.
At FIRST mismatch:
  - Same length  → advance both (replace): check suffix
  - Diff length  → advance j only (insert): check suffix
No second chance — any further mismatch = false.

Similar LC problems:

Problem	LC#	Key Difference
One Edit Distance	161	Exactly 1 edit (insert/delete/replace)
Edit Distance	72	Minimum edits (DP)
Is Subsequence	392	Deletions only, any count
Longest Common Subsequence	1143	Max common chars (DP)
Valid Palindrome II	680	At most 1 delete to form palindrome

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

java

// 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

# 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-7) Group-by-Group String Comparison (Expressive Words) — LC 809

Core Idea

Compare two strings group by group, where a group is a maximal run of the same character. For each aligned group:

Characters must match
The source group count cntS must be ≥ query group count cntW (can only expand, not shrink)
If counts differ (cntS != cntW), cntS must be ≥ 3 — otherwise the source can’t have been “extended” from the query

Key invariant:
  cntS < cntW          → impossible (word has more chars than s)
  cntS != cntW && cntS < 3  → impossible (s has too few to be an extension)
  otherwise            → valid group match

Both pointers must reach the end of their strings simultaneously.

java

// java
// LC 809 - Expressive Words
// time: O(S + W) per word, O(N * (S + W)) total
// space: O(1)
/**
 * Example:
 *   s = "heeellooo", word = "hello"
 *
 *   Group 'h': cntS=1, cntW=1  → equal, OK
 *   Group 'e': cntS=3, cntW=1  → differ, but cntS=3 >= 3, OK (extended)
 *   Group 'l': cntS=2, cntW=2  → equal, OK
 *   Group 'o': cntS=3, cntW=1  → differ, but cntS=3 >= 3, OK (extended)
 *   Both exhausted → true (stretchy)
 *
 *   s = "heeellooo", word = "helo"
 *   Group 'l': cntS=2, cntW=1  → differ, but cntS=2 < 3, FAIL
 */
public int expressiveWords(String s, String[] words) {
    int cnt = 0;
    for (String word : words) {
        if (isStretchy(s, word)) cnt++;
    }
    return cnt;
}

private boolean isStretchy(String s, String word) {
    int i = 0, j = 0;

    while (i < s.length() && j < word.length()) {
        if (s.charAt(i) != word.charAt(j)) return false;

        char ch = s.charAt(i);

        // count group in s
        int cntS = 0;
        while (i < s.length() && s.charAt(i) == ch) { cntS++; i++; }

        // count group in word
        int cntW = 0;
        while (j < word.length() && word.charAt(j) == ch) { cntW++; j++; }

        if (cntS < cntW) return false;              // word has more than s → can't shrink
        if (cntS != cntW && cntS < 3) return false; // extension requires group size >= 3
    }

    return i == s.length() && j == word.length();
}

Decision Table Per Group

`cntS` vs `cntW`	`cntS >= 3`?	Result
`cntS == cntW`	—	Valid (exact match)
`cntS < cntW`	—	Invalid (s is shorter)
`cntS > cntW`	Yes (>= 3)	Valid (extended)
`cntS > cntW`	No (< 3)	Invalid (can’t extend a small group)

Problem	LC#	Key Difference
Expressive Words	809	Multi-word: count stretchy words
String Compression	443	Encode groups as `char + count` in-place
Count and Say	38	Generate next sequence by reading groups
Consecutive Characters	1446	Find longest single-char run
Run-Length Encoding	—	Encode/decode character groups

0-2-8) Next Permutation — LC 31

Core Idea

Find-Pivot → Find-Successor → Swap → Reverse-Suffix:

Find pivot — scan right-to-left for the first index i where nums[i] < nums[i+1]. The suffix nums[i+1:] is fully descending (by definition). If no such i exists, the whole array is descending → reverse it and return.
Find successor — scan right-to-left for the first index j where nums[j] > nums[i]. This is the smallest value in the suffix that beats the pivot.
Swap nums[i] and nums[j]. The suffix is still descending after the swap.
Reverse suffix nums[i+1:] — descending → ascending, giving the smallest possible tail.

Key invariant:
  suffix after pivot is ALWAYS descending when we find the pivot.
  After the swap it's still descending (we swapped the smallest-greater element in).
  Reversing descending → ascending gives the smallest suffix.

Why it works:

Pivot is the rightmost position where we can increment the number.
Picking the smallest successor ensures the minimum possible increase at position i.
Reversing the suffix ensures the tail is as small as possible.

Visual Trace

nums = [1, 2, 5, 4, 3]

Step 1 — Find pivot (right-to-left, first nums[i] < nums[i+1]):
  i=3: nums[3]=4, nums[4]=3  → 4 >= 3, skip
  i=2: nums[2]=5, nums[3]=4  → 5 >= 4, skip
  i=1: nums[1]=2, nums[2]=5  → 2 < 5  ✓ pivot = index 1, value 2

Step 2 — Find successor (right-to-left, first nums[j] > nums[pivot]):
  j=4: nums[4]=3 > 2  ✓ successor = index 4, value 3

Step 3 — Swap pivot and successor:
  [1, 2, 5, 4, 3]  →  [1, 3, 5, 4, 2]
      ^        ^
      i        j

Step 4 — Reverse suffix nums[2:]:
  [1, 3, 5, 4, 2]  →  [1, 3, 2, 4, 5]
         -------            -------

Result: [1, 3, 2, 4, 5]

Pattern (Python)

python

# python
# LC 31 - Next Permutation
# time = O(N), space = O(1)
def nextPermutation(nums):
    n = len(nums)
    i = n - 2

    # Step 1: find pivot
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    # Step 2 & 3: find successor and swap
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]

    # Step 4: reverse suffix
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Pattern (Java)

java

// java
// LC 31 - Next Permutation
// time = O(N), space = O(1)
public void nextPermutation(int[] nums) {
    int n = nums.length;
    int i = n - 2;

    // Step 1: find pivot (right-to-left, first ascending pair)
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;

    // Step 2 & 3: find successor and swap
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;
        int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
    }

    // Step 4: reverse suffix (descending → ascending)
    int l = i + 1, r = n - 1;
    while (l < r) {
        int tmp = nums[l]; nums[l] = nums[r]; nums[r] = tmp;
        l++; r--;
    }
}

Algorithm Steps Summary

Step	Action	Condition	Effect
Find pivot	Scan right-to-left	Stop at first `nums[i] < nums[i+1]`	Marks leftmost improvable position
No pivot found	`i == -1`	Whole array descending	Reverse entire array (wrap to first permutation)
Find successor	Scan right-to-left from end	First `nums[j] > nums[i]`	Smallest value that beats pivot
Swap	`nums[i], nums[j]`	—	Minimum increment at position `i`
Reverse suffix	`nums[i+1:]`	Always	Descending → ascending = smallest tail

Problem	LC#	Key Pattern
Next Permutation	31	Pivot + successor + reverse suffix
Previous Permutation with One Swap	1053	Scan left for first descending pair, swap with rightmost smaller
Next Greater Element III	556	Same algorithm on integer digits (with overflow check)
Permutation Sequence	60	Build Kth permutation directly using factorial number system
Permutations	46	Generate all permutations (backtracking)
Permutations II	47	All permutations with duplicates (backtracking + dedup)
Find the Next Palindrome	3348	Permutation-style digit manipulation

0-2-9) DI String Match (Converging Low/High Pointers) — LC 942

Core Idea

Reconstruct a permutation of [0, n] from a "I"/"D" string. Keep two pointers over the available value range:

low = 0 (smallest unused value), high = n (largest unused value)
On "I" (next must be larger) → append low, then low++
On "D" (next must be smaller) → append high, then high--
After the loop low == high → append that final survivor

Why it’s always valid: picking low for "I" guarantees whatever comes next is bigger (all remaining values are > low); picking high for "D" guarantees whatever comes next is smaller. We never “use up” a value we needed, so any greedy choice produces one valid answer.

Pointer roles:
  low  — smallest value not yet placed (consumed on "I")
  high — largest value not yet placed  (consumed on "D")

Invariant: after k chars processed, exactly (n+1) - k values remain,
           and they are the contiguous range [low, high].
           The final leftover (low == high) fills the last slot.

Visual Trace

s = "IDID"   →   n = 4,  low = 0, high = 4

| Step  | char | Action          | ans         | low | high |
| ----- | ---- | --------------- | ----------- | --- | ---- |
| start | -    | -               | []          | 0   | 4    |
| i=0   | I    | append low  (0) | [0]         | 1   | 4    |
| i=1   | D    | append high (4) | [0,4]       | 1   | 3    |
| i=2   | I    | append low  (1) | [0,4,1]     | 2   | 3    |
| i=3   | D    | append high (3) | [0,4,1,3]   | 2   | 2    |
| end   | -    | append low  (2) | [0,4,1,3,2] | 2   | 2    |

Result: [0, 4, 1, 3, 2]

Pattern (Python)

python

# python
# LC 942 - DI String Match
# IDEA: converging low/high pointers over range [0, n]
# time = O(N), space = O(N) for output (O(1) extra)
def diStringMatch(s):
    low, high = 0, len(s)
    ans = []
    for c in s:
        if c == "I":
            ans.append(low)   # next value will be larger
            low += 1
        else:                 # c == "D"
            ans.append(high)  # next value will be smaller
            high -= 1
    ans.append(low)           # low == high: last remaining value
    return ans

Pattern (Java)

java

// java
// LC 942 - DI String Match
// IDEA: converging low/high pointers over range [0, n]
// time = O(N), space = O(N) for output (O(1) extra)
public int[] diStringMatch(String s) {
    int n = s.length();
    int low = 0, high = n;
    int[] ans = new int[n + 1];
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == 'I') {
            ans[i] = low++;   // next value will be larger
        } else {              // 'D'
            ans[i] = high--;  // next value will be smaller
        }
    }
    ans[n] = low;             // low == high: last remaining value
    return ans;
}

Problem	LC#	Key Pattern
DI String Match	942	Greedy: `"I"`→low, `"D"`→high, converge inward
Next Permutation	31	Pivot + successor + reverse suffix
Valid Permutations for DI Sequence	903	Count (not construct) DI permutations via DP
Score After Flipping Matrix	861	Greedy per-position optimal choice

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

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

# 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

// 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

# 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

// 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

python

# 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):

python

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):

python

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)

python

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

// 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 — LC 27

python

# 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

python

# 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

python

# 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

python

# 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 slow < 2 or nums[fast] != nums[slow - 2]:
                nums[slow] = nums[fast]
                slow += 1
        return slow

2-2) Longest Palindromic Substring — LC 5

python

# 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

python

# 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

python

# 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

python

# 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

python

# 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

python

# 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

python

# 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) — LC 680

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

// 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

# 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

python

# 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 — LC 986

java

// 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) — LC 75

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

// 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 — LC 15

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

// 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-14b) 3Sum Closest (LC 16) — LC 16

Core Idea

Sort + Fix-One + Two-Pointer Squeeze:

Sort the array so the two-pointer direction is deterministic
Fix the first element at index i (outer loop i = 0..n-3)
For the remaining sub-array, set l = i+1, r = n-1 and squeeze inward
At each step compute sum = nums[i] + nums[l] + nums[r] and update closest when |sum - target| < |closest - target|
Exact match → return immediately (can’t do better)
sum > target → r-- (reduce sum, need smaller right value)
sum < target → l++ (increase sum, need larger left value)

Key invariant:
  closest always holds the best (minimum-distance) sum seen so far
  
Pointer movement:
  i   — fixed anchor, advances each outer iteration
  l   — moves right when sum is too small
  r   — moves left when sum is too large

java

// java
// LC 16 - 3Sum Closest
// time: O(N^2), space: O(1)
/**
 * Dry run: nums = [-1, 2, 1, -4], target = 1
 * After sort: [-4, -1, 1, 2]
 *
 * ==================================================================
 * | i | l | r | sum              | |sum-1| | closest | action      |
 * ==================================================================
 * | 0 | 1 | 3 | -4 + -1 + 2 = -3 |   4    |  -3     | l++         |
 * | 0 | 2 | 3 | -4 +  1 + 2 = -1 |   2    |  -1     | l++         |
 * | 0 | 3 | 3 | l >= r, inner loop ends                            |
 * | 1 | 2 | 3 | -1 +  1 + 2 =  2 |   1    |   2     | r-- (>1)    |
 * | 1 | 2 | 2 | l >= r, inner loop ends                            |
 * | 2 | 3 | 3 | l >= r, inner loop ends                            |
 * ==================================================================
 * return closest = 2
 */
public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);

    // initialise with first possible triplet
    int closest = nums[0] + nums[1] + nums[2];

    /** NOTE !!!
     *  outer loop ends at nums.length - 2
     *  (need at least 2 elements after i for l and r)
     */
    for (int i = 0; i < nums.length - 2; i++) {

        /** NOTE !!!
         *  l = i + 1
         *  r = last index
         */
        int l = i + 1;
        int r = nums.length - 1;

        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];

            // update closest if this sum is nearer to target
            if (Math.abs(sum - target) < Math.abs(closest - target)) {
                closest = sum;
            }

            if (sum == target) {
                return sum;           // exact match — can't improve
            } else if (sum > target) {
                r--;                  // need a smaller sum
            } else {
                l++;                  // need a larger sum
            }
        }
    }

    return closest;
}

Pattern vs 3Sum (LC 15)

Aspect	3Sum (LC 15)	3Sum Closest (LC 16)
Goal	All triplets summing to 0	Single triplet closest to `target`
Track	Result list	`closest` scalar
On exact match	Record & skip duplicates	Return immediately
Duplicate skip	Required (avoid repeated triplets)	Optional (problem guarantees unique answer)
Return	`List<List<Integer>>`	`int`

Problem	LC#	Key Difference
3Sum	15	Sum == 0 exactly; collect all triplets
3Sum Closest	16	Closest sum to arbitrary target
3Sum Smaller	259	Count triplets with sum < target
4Sum	18	Four elements; add one more fixed outer loop
Two Sum II	167	Two elements, sorted array
Two Sum (closest)	—	Two-pointer variant of this pattern

2-15) Reverse String / Reverse Words — LC 344

Pattern: In-place Reversal with Two Pointers

java

// 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) — LC 214

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

// 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

// 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

// 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)

2-17) Encode and Decode Strings (Length-Prefixed Two Pointers) — LC 271

Pattern: Parse a length header, then jump i forward by the declared length

The key idea: encode each string as len(s) + "#" + s. Decoding uses two pointers (i, j) where:

i points to the start of the length header at each iteration
j scans forward from i until it hits "#", revealing the word length
After extracting the word, i jumps directly to j + 1 + length (the next header)

This differs from normal two-pointer patterns because the jump distance is variable and encoded in the string itself — no fixed window size.

Pointer roles:
  i  — "header start": marks the beginning of each encoded block
  j  — "separator finder": scans forward until s[j] == "#"

Per-iteration flow:
  1. j starts at i, advances until s[j] == "#"
  2. length = int(s[i:j])         ← word length from header
  3. word   = s[j+1 : j+1+length] ← extract word
  4. i      = j + 1 + length      ← jump to next block's header

python

# python
# LC 271 - Encode and Decode Strings

class Codec:

    def encode(self, strs):
        # time: O(N), space: O(N)
        res = ""
        for s in strs:
            res += str(len(s)) + "#" + s
        return res

    def decode(self, s):
        # time: O(N), space: O(N)
        if not s:
            return []

        res = []
        i = 0

        while i < len(s):
            j = i

            # NOTE: j scans right until it hits "#"
            while s[j] != "#":
                j += 1

            # NOTE: everything between i and j is the length header
            length = int(s[i:j])

            # NOTE: extract exactly `length` chars after the "#"
            word = s[j + 1 : j + 1 + length]
            res.append(word)

            # NOTE: jump i to the start of the next block
            i = j + 1 + length

        return res

Dry Run — strs = ["Hello", "World"]:

encode → "5#Hello5#World"

decode:
  i=0: j scans → s[1]="#", length=5, word="Hello", i=7
  i=7: j scans → s[8]="#", length=5, word="World", i=14
  i=14: loop ends

result: ["Hello", "World"]

Why # as separator works safely:

The length header tells exactly how many bytes to read — so even if the word contains #, j+1+length jumps past it correctly
The only # that matters is the first one after i (which j finds by scanning)

Alternative: str.find("#", i) — same O(N), slightly cleaner:

python

def decode(self, s):
    res = []
    i = 0
    while i < len(s):
        sep = s.find("#", i)        # find first "#" from position i
        length = int(s[i:sep])
        res.append(s[sep + 1 : sep + 1 + length])
        i = sep + 1 + length
    return res

Similar Problems:

LC 271 Encode and Decode Strings (this pattern)
LC 297 Serialize and Deserialize Binary Tree (variable-length encoding of tree nodes)
LC 449 Serialize and Deserialize BST

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 942 DI String Match
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 (exact)	Sum == target; collect all	LC 15, LC 18
Fixed + Two Pointers (closest)	Sum nearest to target	LC 16, LC 259
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
Length-Prefixed (Encode/Decode)	Parse `len#word` blocks; `i` jumps by declared length	LC 271, LC 297
Converging Low/High (build permutation)	Greedy: consume smallest/largest available per signal	LC 942

Missing Google Patterns

Dutch National Flag (3-Way Partition) — LC 75 Sort Colors

Partition array into three groups in O(n) time, O(1) space using three pointers.

python

def sortColors(nums):
    lo, mid, hi = 0, 0, len(nums) - 1
    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1; mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1  # don't advance mid — new nums[mid] is unknown

Invariant: nums[0..lo-1]=0, nums[lo..mid-1]=1, nums[mid..hi]=unknown, nums[hi+1..n-1]=2.

Tortoise and Hare (Cycle Detection) — LC 141, LC 142

Fast pointer moves 2 steps, slow moves 1. They meet inside the cycle (if one exists).

python

# LC 141 — Detect cycle
def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# LC 142 — Find cycle entry point
def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    # Reset one pointer to head; advance both one step at a time
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow   # entry point of cycle

Merge Two Sorted Arrays — LC 88

Fill from the back to avoid shifting elements.

python

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] >= nums2[j]:
            nums1[k] = nums1[i]; i -= 1
        else:
            nums1[k] = nums2[j]; j -= 1
        k -= 1
    while j >= 0:           # remaining nums2 elements
        nums1[k] = nums2[j]; j -= 1; k -= 1

Container With Most Water — LC 11

Start with widest window, shrink the shorter side to maximize area.

python

def maxArea(height):
    l, r = 0, len(height) - 1
    ans = 0
    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

Why move the shorter side? Moving the taller side can only decrease width without increasing the min-height bottleneck — no gain possible.

Valid Palindrome (Two Pointers from Edges) — LC 125, LC 680

python

# LC 125 — ignore non-alphanumeric
def isPalindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum(): l += 1
        while l < r and not s[r].isalnum(): r -= 1
        if s[l].lower() != s[r].lower(): return False
        l += 1; r -= 1
    return True

# LC 680 — can delete at most one character
def validPalindrome(s):
    def is_pal(l, r):
        while l < r:
            if s[l] != s[r]: return False
            l += 1; r -= 1
        return True

    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:
            return is_pal(l+1, r) or is_pal(l, r-1)
        l += 1; r -= 1
    return True

Google Interview Tips for Two Pointers

Signal	Pattern
“sort + find pair”	Left-right pointers after sorting
“in-place remove/deduplicate”	Slow-fast write pointer
“cycle in linked list”	Tortoise and hare
“partition into 3 groups”	Dutch national flag
“merge sorted in-place”	Fill from back
“palindrome check”	Pointers from both ends
“maximum area / container”	Shrink shorter side
“encode/decode variable-length fields”	Length-prefixed two pointers (`len#word`)

2 Pointers

Table of Contents