Two Pointers – DSA Notes

Patterns for sorting + two-pointers, windows, and partitions.

---

📌 Summary Table

Problem	Pattern	Time	Space
3Sum	Sort + two pointers, skip dupes	O(n²)	O(1)
Trapping Rain Water	Two pointers with running max	O(n)	O(1)
Rotate Array (Reversal)	Triple-reversal trick	O(n)	O(1)
Remove Duplicates from Sorted Array	Slow/fast overwrite	O(n)	O(1)
Max Consecutive Ones	Linear scan counter	O(n)	O(1)

---

3Sum

Problem. Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0.

Idea.

• Sort the array.
• For each index i, find pairs with sum -nums[i] using two pointers (l, r).
• Skip duplicates at i, and while moving l and r.

Complexity. O(n²) time (outer loop × inner linear scan), O(1) extra space (ignoring output).

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // required for two-pointer + dedupe
        List<List<Integer>> ans = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip same anchor

            int l = i + 1, r = nums.length - 1;
            int target = -nums[i];

            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum == target) {
                    ans.add(Arrays.asList(nums[i], nums[l], nums[r]));

                    // skip duplicates on left and right
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;

                    l++; r--;
                } else if (sum < target) {
                    l++; // need bigger sum
                } else {
                    r--; // need smaller sum
                }
            }
        }
        return ans;
    }
}

Key Takeaway. Sort → fix i → two-pointer for -nums[i] → dedupe carefully.

---

Trapping Rain Water (Two Pointers)

Problem. Given bar heights, compute total trapped water.

Idea.

• Maintain two pointers l and r and running maxima lmax, rmax.
• At each step, process the lower side: water there is maxSoFar - height.

Complexity. O(n) time, O(1) space.

class Solution {
    public int trap(int[] h) {
        int n = h.length, l = 0, r = n - 1;
        int lmax = 0, rmax = 0, ans = 0;

        while (l <= r) {
            if (h[l] <= h[r]) {
                // left side bounded by lmax
                if (h[l] >= lmax) lmax = h[l];
                else ans += lmax - h[l];
                l++;
            } else {
                // right side bounded by rmax
                if (h[r] >= rmax) rmax = h[r];
                else ans += rmax - h[r];
                r--;
            }
        }
        return ans;
    }
}

Key Takeaway. Always move the smaller side inward; use running max to count water.

---

Rotate Array (Reversal)

Problem. Rotate an array to the right by k steps.

Idea. Use the triple-reversal trick:

1. reverse whole array, 2) reverse first k, 3) reverse remaining n-k.

Complexity. O(n) time, O(1) space.

class Solution {
    private void rev(int[] a, int l, int r) {
        while (l < r) {
            int t = a[l];
            a[l++] = a[r];
            a[r--] = t;
        }
    }
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; // normalize
        if (k == 0) return;

        rev(nums, 0, n - 1);   // reverse all
        rev(nums, 0, k - 1);   // reverse prefix
        rev(nums, k, n - 1);   // reverse suffix
    }
}

Key Takeaway. Rotation = reverse all → reverse parts.

---

Remove Duplicates from Sorted Array

Problem. In-place remove duplicates from a sorted array; return new length.

Idea. Two pointers: j scans, i writes next unique. Overwrite duplicates.

Complexity. O(n) time, O(1) space.

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 1; // write index for next unique
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[j - 1]) {
                nums[i++] = nums[j]; // place unique
            }
        }
        return i; // new length
    }
}

Key Takeaway. Slow/fast pointers with overwrite on sorted input.

---

Max Consecutive Ones

Problem. Given a binary array, find the maximum number of consecutive 1s.

Idea. Linear scan, keep running count of 1s, reset on 0.

Complexity. O(n) time, O(1) space.

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int best = 0, cur = 0;
        for (int x : nums) {
            if (x == 1) {
                cur++;
                if (cur > best) best = cur; // update max
            } else {
                cur = 0; // reset streak
            }
        }
        return best;
    }
}

Key Takeaway. Simple streak counter pattern.

---