Greedy Algorithms, Two Pointers and Sliding Windows

These three patterns turn brute-force O(n²) solutions into O(n) or O(n log n). Greedy makes the locally best choice when you can prove it leads to the global best; two pointers walk a sorted array from both ends; sliding windows track a contiguous range as it moves.

1. When does a greedy algorithm work?

When a problem has the greedy-choice property (a locally optimal choice is part of some optimal solution) and optimal substructure. Always sanity-check with a counterexample: greedy coin change works for Indian currency denominations but fails for {1, 3, 4} and amount 6. If greedy fails, think dynamic programming.

2. Activity selection: the maximum number of non-overlapping meetings.

Sort by end time and always pick the meeting that ends earliest among those that start after the last chosen one. Finishing early leaves the most room. O(n log n).

int maxMeetings(int[][] meetings) {
    Arrays.sort(meetings, Comparator.comparingInt(m -> m[1]));   // by end time
    int count = 0, lastEnd = Integer.MIN_VALUE;
    for (int[] m : meetings) {
        if (m[0] >= lastEnd) { count++; lastEnd = m[1]; }
    }
    return count;
}

3. Jump game: can you reach the last index?

Track the farthest index reachable so far; if the current index is beyond it, you are stuck. One pass, O(n).

boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}

4. Container with most water.

Two pointers at both ends. The area is limited by the shorter line, so moving the taller line can never help — always move the shorter one inward. O(n).

int maxArea(int[] h) {
    int i = 0, j = h.length - 1, best = 0;
    while (i < j) {
        best = Math.max(best, Math.min(h[i], h[j]) * (j - i));
        if (h[i] < h[j]) i++; else j--;
    }
    return best;
}

5. 3Sum: all unique triplets that sum to zero.

Sort, fix one number, then run two pointers on the rest; skip duplicates at every level. O(n²), which beats the O(n³) brute force.

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int lo = i + 1, hi = nums.length - 1;
        while (lo < hi) {
            int sum = nums[i] + nums[lo] + nums[hi];
            if (sum < 0) lo++;
            else if (sum > 0) hi--;
            else {
                res.add(List.of(nums[i], nums[lo], nums[hi]));
                while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                lo++; hi--;
            }
        }
    }
    return res;
}

6. Fixed-size sliding window: maximum sum of k consecutive elements.

Compute the first window, then slide: add the entering element and subtract the leaving one. O(n) instead of O(n·k).

int maxSumWindow(int[] a, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];
    int best = sum;
    for (int i = k; i < a.length; i++) {
        sum += a[i] - a[i - k];
        best = Math.max(best, sum);
    }
    return best;
}

7. Variable sliding window: the smallest subarray with sum ≥ target.

Expand the right edge to grow the sum; while the condition holds, record the length and shrink from the left. Each element enters and leaves once — O(n). Works because all numbers are positive.

int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, best = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            best = Math.min(best, right - left + 1);
            sum -= nums[left++];
        }
    }
    return best == Integer.MAX_VALUE ? 0 : best;
}

8. Gas station: where can you start to complete the circuit?

If the total gas is less than the total cost, no start works. Otherwise walk once keeping a running tank; whenever it goes negative, the next station becomes the candidate start. O(n).

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        total += gas[i] - cost[i];
        tank += gas[i] - cost[i];
        if (tank < 0) { start = i + 1; tank = 0; }
    }
    return total < 0 ? -1 : start;
}