🧠 Data Structures & Algorithms · Advanced

Common techniques in Java

Two pointers, sliding window, prefix sums, greedy.

🧩 The mysteryChecking every pair in an array is O(n²): fine for 1,000 items, hopeless for a million. Four small tricks get most of these problems down to a single pass.

Two pointers

To find a pair with a target sum in a sorted array, start one pointer at each end. Sum too small? Move lo right to get bigger. Too big? Move hi left. Sorted order is what guarantees no pair is skipped. One pass: O(n).

int lo = 0, hi = a.length - 1;
while (lo < hi) {
    int s = a[lo] + a[hi];
    if (s == target) return true;
    if (s < target) lo++; else hi--;
}
return false;

🔮 Predict it

Squeeze from both ends

What does this print?

int[] a = {1, 3, 4, 6, 9};
int lo = 0, hi = a.length - 1, target = 13;
while (lo < hi) {
    int s = a[lo] + a[hi];
    if (s == target) break;
    if (s < target) lo++;
    else hi--;
}
System.out.println(a[lo] + "+" + a[hi]);

4+9
3+9
1+9

Show the answer

Round 1: 1 + 9 = 10, too small, lo moves right. Round 2: 3 + 9 = 12, still too small. Round 3: 4 + 9 = 13, found. Three steps instead of checking all 10 pairs.

Sliding window

For questions about contiguous ranges, keep a running total for a window and slide it: add the element that enters, subtract the one that leaves. Each slide is O(1), so the whole scan is O(n). Like a train window: one view enters as one leaves.

🔮 Predict it

Best window of 2

What does this print?

int[] a = {4, 2, 1, 7, 3};
int k = 2, 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);
}
System.out.println(best);

10
8
11
17

Show the answer

Window sums of size 2: [4, 2] = 6, [2, 1] = 3, [1, 7] = 8, [7, 3] = 10. Each step adds the new element and subtracts the one that left, never re-adding the whole window.

Prefix sums

Precompute p[i + 1] = p[i] + a[i] once in O(n). Then the sum of a[i..j] is **p[j + 1] - p[i]: one subtraction, O(1) per query. For a = {2, 4, 6, 8}, p = {0, 2, 6, 12, 20}, and a[1] + a[2] = p[3] - p[1] = 12 - 2 = 10**.

int[] p = new int[a.length + 1];
for (int i = 0; i < a.length; i++)
    p[i + 1] = p[i] + a[i];
int rangeSum = p[j + 1] - p[i];

⚠️ The trap

Greedy isn't always right

Greedy takes the best-looking choice at each step. With coins {4, 3, 1} and amount 6, largest-first takes 4, then 1, then 1: 3 coins. The optimum is 3 + 3: 2 coins. Greedy is fast, but each problem needs a proof; otherwise reach for DP. It *is* proven for picking the most non-overlapping meetings by earliest end time.

int[] coins = {4, 3, 1};
int amount = 6, used = 0;
for (int c : coins) {
    used += amount / c;
    amount %= c;
}
// used == 3, but 3 + 3 needs only 2

🤔 Think first

Pick the technique

"Find the longest substring without repeating characters." Which technique fits, and how do you spot the others?

Think about it, then reveal the answer

A contiguous range that grows and shrinks: sliding window. A pair with a target sum in sorted data: two pointers. Many range-sum queries on fixed data: prefix sums. Most non-overlapping meetings: greedy by earliest end time.

💼 In the real world

From interviews to production

These four patterns solve a large share of coding-interview problems. In production, sliding windows power rolling averages and rate limiters, and prefix sums make range queries on dashboards instant.

Key takeaways

Two pointers: pair sums in sorted arrays, palindromes
Sliding window: add the new element, drop the old one
Prefix sums: sum of a[i..j] = p[j + 1] - p[i]
Greedy needs proof: it fails for coins {4, 3, 1} making 6

💡 A sliding window is a train window: as the train moves, one view enters and one leaves.

🤯 Did you know?

The Viola-Jones face detector (2001) relied on an "integral image", a 2D prefix sum that gives the sum of any rectangle with just four lookups.

Practice questions

What does this print?

int[] a = {2, 1, 5, 1, 3, 2};
int k = 3, 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);
}
System.out.println(best);

Check your answer

9. Window sums of size 3 are 8, 7, 9 and 6, so the best is 9 (5 + 1 + 3). Each slide is O(1), so the whole scan is O(n).

What does this print?

int[] a = {3, 1, 4, 1, 5};
int[] p = new int[a.length + 1];
for (int i = 0; i < a.length; i++)
    p[i + 1] = p[i] + a[i];
System.out.println(p[4] - p[1]);

Check your answer

6. p[4] = 3 + 1 + 4 + 1 = 9 and p[1] = 3, so the difference is a[1] + a[2] + a[3] = 1 + 4 + 1 = 6. Any range sum is one subtraction.

New world: Testing, Tools & Ecosystem. How do you prove all this clever code actually works? Meet JUnit 5.