Reversing Order

Not Started

Place two pointers at different positions and move them based on conditions. Typically one at each end walking inward, or both from the left at different speeds.

When to Use

Opposite-end swap: Skip elements that don't match a condition, swap the ones that do - e.g. reversing only the vowels in a string while leaving consonants in place

Pair sum on sorted data: Move inward based on whether the current sum is too small or too large

Palindrome check: Compare characters from both ends, moving inward until they meet

Partitioning: Slow pointer marks the write position, fast pointer scans ahead - useful for removing duplicates or filtering in place

Implementation

def two_sum(arr, target):  # arr must be sorted
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1  # need larger sum
        else:
            right -= 1  # need smaller sum
    return []

vector<int> twoSum(vector<int>& arr, int target) {  // arr must be sorted
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        int s = arr[l] + arr[r];
        if (s == target) return {l, r};
        else if (s < target) l++;  // need larger sum
        else r--;  // need smaller sum
    }
    return {};
}

int[] TwoSum(int[] arr, int target) {  // arr must be sorted
    int l = 0, r = arr.Length - 1;
    while (l < r) {
        int s = arr[l] + arr[r];
        if (s == target) return new[] {l, r};
        else if (s < target) l++;  // need larger sum
        else r--;  // need smaller sum
    }
    return new int[0];
}

int[] twoSum(int[] arr, int target) {  // arr must be sorted
    int l = 0, r = arr.length - 1;
    while (l < r) {
        int s = arr[l] + arr[r];
        if (s == target) return new int[]{l, r};
        else if (s < target) l++;  // need larger sum
        else r--;  // need smaller sum
    }
    return new int[0];
}