Two Pointers

Pointer movement rules:
  - fast: moves EVERY iteration (scans all elements)
  - slow: moves ONLY when a new unique value is found (after nums[fast] != nums[slow])
  - Both start at 0 (or slow=0, fast=1 in while-loop variants)

// 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
 *
 */
// Variant A: OVERWRITE (cleaner, preferred for sorted arrays)
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;                  // open next write slot
                nums[slow] = nums[fast]; // overwrite with new unique value
            }
            // if equal: fast keeps moving, slow stays
        }
        return slow + 1;
    }
}

// Variant B: SWAP (preserves all values, same time/space)
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                // swap: move the new unique value to slow position
                int tmp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = tmp;
            }
            fast++;
        }
        return slow + 1;
    }
}

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

# 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

l = 0, r = n - 1
while l < r:
    evaluate the pair (l, r)
    move the pointer that cannot improve the answer
      -> the shorter wall (LC 11), the non-alphanumeric char (LC 125),
         the side whose sum is too small / too large (LC 167)

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

# 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

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

# LC 005  Longest Palindromic Substring
# LC 647 Palindromic Substrings
# python
# pseudo code
# ...
for i in range(len(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 `even`, 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
# ...

// 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();
}

Key invariant (why backward is always safe):

  write pointer  p  = m + n - 1
  read pointers  p1 = m - 1  (nums1),  p2 = n - 1  (nums2)

  p >= p1  ALWAYS holds, because p - p1 = n - 1 - p2 >= 0
  -> the slot we write to is never a slot we still need to read

  nums1 = [1, 2, 3, 0, 0, 0]
           ^        ^     ^
           |        |     p (write, from the END)
           |        first empty slot
           p1 (read nums1, from the END of valid part)

nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6],          n = 3

| Step | p1 | p2 | p | Compare                | Action  | nums1              |
|------|----|----|---|------------------------|---------|--------------------|
| init |  2 |  2 | 5 | —                      | setup   | [1,2,3,0,0,0]      |
|  1   |  2 |  2 | 5 | nums1[2]=3 < nums2[2]=6| write 6 | [1,2,3,0,0,6]      |
|  2   |  2 |  1 | 4 | nums1[2]=3 < nums2[1]=5| write 5 | [1,2,3,0,5,6]      |
|  3   |  2 |  0 | 3 | nums1[2]=3 > nums2[0]=2| write 3 | [1,2,3,3,5,6]      |
|  4   |  1 |  0 | 2 | nums1[1]=2 == nums2[0]=2| write 2 | [1,2,2,3,5,6]     |
|  5   |  1 | -1 | 1 | p2 < 0                 | STOP    | [1,2,2,3,5,6]      |

Step 5: nums1[0..1] = [1,2] is already correct -> no extra work needed

# python
# LC 88 - Merge Sorted Array
# IDEA : 2 POINTERS, MERGE FROM RIGHT -> LEFT (in-place)
# time = O(m + n), space = O(1)
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        # read pointers: END of the valid parts
        p1 = m - 1
        p2 = n - 1

        # write pointer: END of the whole nums1 array
        p = m + n - 1

        """
        NOTE !!!
         1) loop on `p2 >= 0` only
            -> if nums2 runs out, remaining nums1 is ALREADY in place
         2) all pointer conditions are `>= 0` (not `> 0`)
        """
        while p2 >= 0:
            # NOTE !!! must check `p1 >= 0` before reading nums1[p1]
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                # nums2[p2] is bigger (or equal), or nums1 is exhausted
                nums1[p] = nums2[p2]
                p2 -= 1

            p -= 1

// java
// LC 88 - Merge Sorted Array
// time = O(m + n), space = O(1)
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;          // read nums1
    int p2 = n - 1;          // read nums2
    int p = m + n - 1;       // write

    /** NOTE !!! loop on p2 only */
    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p--] = nums1[p1--];
        } else {
            nums1[p--] = nums2[p2--];
        }
    }
}

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

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

# 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

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


// ...

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