Two Pointers & Sliding Window: Deriving the Optimal Solution for 6 Problems (LC 1/167/15/11/3/76)

The worst way to grind LeetCode is to memorize solutions without understanding them. This post doesn't just hand you answers — it walks the full derivation for each problem:

Break down the problem → write the brute force → find the bottleneck → spot the key insight → arrive at the optimum → code.

These 6 problems (LC 1, 167, 15, 11, 3, 76) form one evolution line — from hashing, to two pointers, to the sliding window. Understand the derivation and you can re-derive any variant on the spot.

Three Core Patterns

1. HashMap — trade space for time, turning "find the other number" from O(n) into O(1).
2. Two Pointers — requires a sorted array; converge via monotonic moves of the left/right pointers.
3. Sliding Window — expand the right pointer, shrink the left, maintaining one valid interval.

💡 How they relate: hashing handles "find a pair in unsorted data"; once sorted, two pointers drop the hash map's space; when the problem becomes a contiguous interval, two pointers evolve into a sliding window.

① LC 1 — Two Sum

📋 Problem: Given an integer array nums and a target, return the indices of the two numbers that add up to target. Assume exactly one solution, and you may not use the same element twice.

Example: nums = [2,7,11,15], target = 9 → [0,1] (2 + 7 = 9)

🧭 From reading the problem to the solution

1. Break it down: input is an unsorted array + target; output is two indices.
2. Brute force: a double loop — for each i, scan ahead for a j with nums[i]+nums[j]==target. O(n²).
3. The bottleneck: the inner loop keeps doing the same thing — linearly searching for the other half target - nums[i]. That search is O(n).
4. Key insight: if we could check in O(1) whether the other half has appeared before, the inner loop disappears → keep a HashMap of "value seen → its index".
5. Derive the optimum: iterate once, and each step ask "is target - current in the map?" If yes → return both indices; if no → store the current number and continue.

def twoSum(nums, target):
    seen = {}                       # value -> index
    for i, n in enumerate(nums):
        if target - n in seen:      # check before insert
            return [seen[target - n], i]
        seen[n] = i
    return []

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;               // value -> index
    for (int i = 0; i < (int)nums.size(); ++i) {
        auto it = seen.find(target - nums[i]);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {};
}

• Complexity: O(n) time, O(n) space.
• Pitfall: always check before inserting, or you'll pair a number with itself.

② LC 167 — Two Sum II

📋 Problem: Given a 1-indexed, ascending-sorted array numbers and a target, find two numbers that add up to target and return their 1-based indices [index1, index2]. Exactly one solution.

Example: numbers = [2,7,11,15], target = 9 → [1,2] (2 + 7 = 9)

🧭 From reading the problem to the solution

1. Break it down: almost identical to LC1, but with one key extra condition — it's sorted.
2. Recall LC1: the HashMap solution still works (O(n) time, O(n) space). But it ignores the "sorted" condition entirely — in interviews, a given condition is usually a hint.
3. Key insight: after sorting, look at the sum of the smallest (leftmost) + largest (rightmost):
   • Sum too big → to shrink it, move the right pointer left (to a smaller value).
   • Sum too small → to grow it, move the left pointer right.
   • Each step safely eliminates one element; the pointers close in monotonically.
4. Derive the optimum: two pointers moving toward each other, deciding who moves by comparing sum to target. Space drops to O(1).

def twoSum(numbers, target):
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s == target:
            return [lo + 1, hi + 1]   # 1-indexed
        elif s < target:
            lo += 1                   # need a bigger sum
        else:
            hi -= 1                   # need a smaller sum
    return []

vector<int> twoSum(vector<int>& numbers, int target) {
    int lo = 0, hi = (int)numbers.size() - 1;
    while (lo < hi) {
        int s = numbers[lo] + numbers[hi];
        if (s == target) return {lo + 1, hi + 1};
        else if (s < target) ++lo;
        else --hi;
    }
    return {};
}

• Complexity: O(n) time, O(1) space.
• Pitfall: the answer is 1-indexed; two pointers only work because moving in a sorted array is monotonic.

🔑 Interview comparison: LC1 vs LC167 — "Why HashMap for one and two pointers for the other?" Answer: whether the input is already sorted.

③ LC 15 — 3Sum

📋 Problem: Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] (with distinct indices) that sum to 0. The result must not contain duplicate triplets.

Example: nums = [-1,0,1,2,-1,-4] → [[-1,-1,2], [-1,0,1]]

🧭 From reading the problem to the solution

1. Break it down: three numbers summing to 0, and no duplicate triplets in the result.
2. Start from 2Sum: three numbers summing to 0 ⟺ fix one number a, and the other two must sum to -a — that's Two Sum!
3. Key insight: since the remainder is a Two Sum, and LC167 taught us "sorted + two pointers is cheapest", sort first, fix nums[i], and run left/right pointers to its right looking for -nums[i].
4. Handle dedup (the real difficulty here): after sorting, duplicates are adjacent, so —
   • Skip a fixed nums[i] if it equals the previous one (else the same triplet is counted again).
   • After finding a hit, also skip adjacent duplicate values on both lo and hi.
5. Pruning: after sorting, if nums[i] > 0, nothing ahead can sum to 0 — stop early.

def threeSum(nums):
    nums.sort()
    res, n = [], len(nums)
    for i in range(n - 2):
        if nums[i] > 0:                      # smallest already > 0
            break
        if i > 0 and nums[i] == nums[i - 1]: # skip duplicate anchor
            continue
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:  # skip dups
                    lo += 1
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
    return res

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i < n - 2; ++i) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] == nums[i - 1]) continue;   // skip anchor dup
        int lo = i + 1, hi = n - 1;
        while (lo < hi) {
            int s = nums[i] + nums[lo] + nums[hi];
            if (s < 0) ++lo;
            else if (s > 0) --hi;
            else {
                res.push_back({nums[i], nums[lo], nums[hi]});
                ++lo; --hi;
                while (lo < hi && nums[lo] == nums[lo - 1]) ++lo;
                while (lo < hi && nums[hi] == nums[hi + 1]) --hi;
            }
        }
    }
    return res;
}

• Complexity: O(n²) time, O(1) space (excluding sort and output).
• Pitfall: three layers of dedup — skip duplicate anchors i, and after a hit, skip duplicate lo/hi. Miss any layer and duplicate triplets leak through.

④ LC 11 — Container With Most Water

📋 Problem: Given n non-negative integers height, each a vertical line, pick two lines that together with the x-axis form a container holding the most water, and return that amount. Water = min(height[i], height[j]) × (j - i).

Example: height = [1,8,6,2,5,4,8,3,7] → 49 (lines of height 8 and 7, width 7, area 7 × 7 = 49)

🧭 From reading the problem to the solution

1. Break it down: area = min(left height, right height) × distance, to be maximized.
2. Brute force: try every pair, take the max area. O(n²).
3. Key insight (greedy): start from the widest pair — the two ends, maximum width. Now the only free variable is height. Which side do we move?
   • Area is capped by the shorter line. If you move the taller side: width shrinks and the height is still stuck at that short line → area can't grow.
   • Only moving the shorter side gives any chance of a taller line and a bigger area.
4. Derive the optimum: two pointers from both ends, each step move the shorter side, recording the max area along the way. Each element is visited once → O(n).

def maxArea(height):
    lo, hi, best = 0, len(height) - 1, 0
    while lo < hi:
        h = min(height[lo], height[hi])
        best = max(best, h * (hi - lo))
        if height[lo] < height[hi]:   # move the shorter side
            lo += 1
        else:
            hi -= 1
    return best

int maxArea(vector<int>& height) {
    int lo = 0, hi = (int)height.size() - 1, best = 0;
    while (lo < hi) {
        int h = min(height[lo], height[hi]);
        best = max(best, h * (hi - lo));
        if (height[lo] < height[hi]) ++lo;
        else --hi;
    }
    return best;
}

• Complexity: O(n) time, O(1) space.
• Pitfall (the classic follow-up): point 3 above — "why move the shorter side" — is the greedy correctness argument; be ready to say it out loud.

🔑 Interview comparison: LC11 vs LC167 — both use left/right pointers, but 167 decides direction by "sum vs target", while 11 decides by "which side is shorter".

⑤ LC 3 — Longest Substring Without Repeating Characters

📋 Problem: Given a string s, find the length of the longest substring without repeating characters.

Example: s = "abcabcbb" → 3 ("abc"); s = "pwwkew" → 3 ("wke")

🧭 From reading the problem to the solution

1. Break it down: the keyword "substring" means a contiguous range (not a subsequence); we want the longest with no repeats.
2. Brute force: enumerate every start/end and check for repeats. O(n²) or even O(n³).
3. Key insight: maintain a window [left, right] representing "the current repeat-free stretch". Keep expanding right; the moment you hit a character already inside the window, jump left to "one past that character's previous position" to make the window valid again.
4. Derive the optimum: keep a map of "each character's last index". As right advances, if the current char's last index is >= left (i.e. inside the window), push left forward. Update the max length each step. Each pointer only moves forward → O(n).

def lengthOfLongestSubstring(s):
    last = {}            # char -> last index seen
    left = best = 0
    for right, c in enumerate(s):
        if c in last and last[c] >= left:
            left = last[c] + 1        # jump past the duplicate
        last[c] = right
        best = max(best, right - left + 1)
    return best

int lengthOfLongestSubstring(string s) {
    vector<int> last(128, -1);        // char -> last index
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        if (last[s[right]] >= left)
            left = last[s[right]] + 1;
        last[s[right]] = right;
        best = max(best, right - left + 1);
    }
    return best;
}

• Complexity: O(n) time, O(min(n, charset)) space.
• Pitfall: the check must be last[c] >= left. If the duplicate sits outside the window (left of left), you should NOT shrink — missing this condition is the most common bug.

⑥ LC 76 — Minimum Window Substring

📋 Problem: Given strings s and t, return the shortest substring of s that contains all characters of t (including duplicates). If none exists, return "".

Example: s = "ADOBECODEBANC", t = "ABC" → "BANC"

🧭 From reading the problem to the solution

1. Break it down: again a "contiguous substring", but now we want the shortest, and the condition is upgraded to "cover an entire set of character requirements from t (with counts)".
2. Start from LC3: LC3 was a variable window for the longest; this is also a variable window, but for the shortest with a more complex condition. Same frame: expand right, shrink left.
3. Key insight (when to expand vs shrink):
   • Keep expanding right until the window covers t.
   • Once it covers, shrink left as far as possible — until one more step would stop covering — recording the shortest length along the way.
   • Then resume expanding right, and repeat.
4. How to check "covers" in O(1): keep need[char] counts (how many more of a char we need, allowed to go negative for surplus) plus an integer missing (total chars still needed). missing == 0 means covered — no need to re-scan the whole table each step.
5. Derive the optimum:
   • Expand: need[c] -= 1; if c was "needed" (need[c] > 0 before decrementing), missing -= 1.
   • When missing == 0: enter the shrink loop, record the shortest; on shrinking, need[left] += 1, and if we just dropped a "needed" char (need[left] > 0), missing += 1.

from collections import Counter

def minWindow(s, t):
    if not s or not t:
        return ""
    need = Counter(t)
    missing = len(t)                  # how many chars still needed
    left = 0
    best = (float('inf'), 0, 0)       # (length, start, end)
    for right, c in enumerate(s):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1                  # may go negative (surplus)
        while missing == 0:           # window covers t -> try to shrink
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right + 1)
            need[s[left]] += 1
            if need[s[left]] > 0:     # we just dropped a needed char
                missing += 1
            left += 1
    return "" if best[0] == float('inf') else s[best[1]:best[2]]

string minWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";
    vector<int> need(128, 0);
    for (char c : t) need[c]++;
    int missing = t.size(), left = 0;
    int bestLen = INT_MAX, bestStart = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        if (need[s[right]] > 0) --missing;
        need[s[right]]--;                       // may go negative
        while (missing == 0) {                  // covers t -> shrink
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            need[s[left]]++;
            if (need[s[left]] > 0) ++missing;    // dropped a needed char
            ++left;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}

• Complexity: O(|s| + |t|) time, O(charset) space.
• Pitfall: need counts can go negative (surplus of a char); a single missing integer is far faster than re-comparing the whole map each step; only shrink left while missing == 0.

🔑 Interview comparison: LC3 vs LC76 — both are variable-size windows, but LC3 wants the longest (record on expansion) and LC76 wants the shortest (record on shrink).

One Table to Remember It All

Pattern-Recognition Cheats

• "Two numbers to a fixed sum" → unsorted: HashMap; sorted: two pointers.
• "Multiple numbers to a fixed sum + dedup" → sort + fixed anchor + two pointers.
• "Maximize across both ends" → greedy two pointers, move the shorter side.
• "Contiguous substring/subarray + longest or shortest" → sliding window; longest records on expansion, shortest records on shrink.

The derivation matters more than memorization: in an interview, narrate "brute force → bottleneck → insight → optimum" and even if you stall, the interviewer still sees how you think.