Sliding Window and Two Pointers in Java: 12 Interview Problems Solved
Learn sliding window and two pointers in Java through 12 classic interview problems: fixed vs variable windows, step-by-step dry runs, brute-force cross-checks and operation counts, all from real JDK 25 runs.
You read a problem that says subarray, substring or contiguous, and your first instinct is two nested loops: pick every start, extend to every end, check each slice. It is correct, it is easy to explain, and it is O(n²) — which is exactly when the interviewer says “can you do it in one pass?”
This post teaches the two patterns that answer that question, sliding window and two pointers, from the ground up. It starts with the single idea underneath both, then solves twelve classic interview problems in order of difficulty. Every solution was compiled and run on JDK 25, checked against a deliberately slow brute-force version on thousands of random inputs, and every number and console line below is quoted from a file in the companion module; each code block and output block links to the file it came from.
You do not need to know either pattern. The sections are in difficulty order, and the collapsible “going deeper” panels hold the intermediate and reference-level material, so read straight through the first time and open the panels later.
Versions this was built and run against. JDK 25.0.5+8 (Temurin, LTS), JUnit 6.1.3 (the latest GA on Maven Central, taken from maven-metadata.xml for junit-bom; the only newer-looking entries were 6.1.0-RC1) and Maven 3.9.x. No other dependencies: everything is plain java.util. The module is sliding-window in the asmhatre/java-interview-lab repository.
A window is a running summary you update instead of recompute
A window is the slice of an array or string between two indices, left and right, both included. The trick behind the whole family is to keep a summary of what is inside the window — its sum, or a count of each character — and to update that summary when the window moves, instead of recomputing it from scratch.
Take the array [2, 1, 5, 1, 3, 2] and ask for the largest sum of any 3 consecutive elements. The nested-loop answer adds up 3 numbers for every position. The window answer adds up 3 numbers once, then slides.
The picture shows two consecutive windows. Moving from window 1 to window 2 removes the leftmost value (a red, dashed box) and adds one new value on the right (green); the two values in the middle never need to be looked at again. So each slide is one addition and one subtraction, however large the window is.
Here is the whole solution, FixedWindow.maxSumSubarray:
public static long maxSumSubarray(int[] a, int k) {
if (k <= 0 || k > a.length) {
throw new IllegalArgumentException("k must be in 1.." + a.length + " but was " + k);
}
long sum = 0;
for (int i = 0; i < k; i++) {
sum += a[i]; // build the first window
}
long best = sum;
for (int right = k; right < a.length; right++) {
sum += a[right] - a[right - k]; // slide: one element in, one element out
best = Math.max(best, sum);
}
return best;
}
Running it on that array, traced step by step by an instrumented copy that the tests prove returns the same answer (output/01-fixed-window-trace.txt):
The saving is easy to state and easy to measure. Rather than timing the code — JVM timings are noisy, as the JMH tutorial on this blog shows at length — the module counts element reads, which gives the same answer on every machine. For a window of 100 elements (from output/08-operation-counts.txt):
Max sum of k=100 consecutive elements: element reads
n brute force sliding window ratio
1000 90,100 1,900 47.4x
2000 190,100 3,900 48.7x
4000 390,100 7,900 49.4x
8000 790,100 15,900 49.7x
The brute-force count grows with n × k; the window count grows with n alone, and the ratio settles near k / 2 (about 50 for a window of 100).
Going deeper: where the numbers come from, and what a window cannot do
The window version reads k elements to build the first window and then 2 per slide, so k + 2(n − k) reads in total; the brute-force version reads (n − k + 1) × k. Both formulas are asserted against the real counters in ComplexityTest, so they are not just algebra. The brute-force reference that the randomized tests use is BruteForce.java; the counters are in Complexity.java.
The sliding trick only works when the summary can be undone. A sum can: subtract the value that left. A set of character counts can: decrement the one that left. A maximum cannot, because if the maximum is the value that just left, nothing in the summary says what the new maximum is. Problem 3 below needs a different structure for exactly that reason.
Going deeper
Complexity.java — the operation counters behind the table above
Java’s stream API also ships a built-in sliding window, Gatherers.windowSliding, covered in Java Stream Gatherers (JEP 485) — useful when the data is already a stream.
Fixed windows: when the problem tells you the length
When the length k is given, the left edge needs no thinking: it is always right − k + 1. Two of the twelve problems live here, and they show the two ways a fixed window keeps its summary.
Problem 2 — permutation in string. Does s contain some rearrangement of p as a substring? A rearrangement has the same letter counts as p, so slide a window of length p.length() across s and compare its letter counts with p’s. The summary is a 26-slot count array; a slide increments one slot and decrements another (lowercase a–z only in this version):
public static boolean permutationInString(String p, String s) {
if (p.length() > s.length()) {
return false;
}
int k = p.length();
int[] need = new int[26];
int[] have = new int[26];
for (int i = 0; i < k; i++) {
need[p.charAt(i) - 'a']++;
have[s.charAt(i) - 'a']++;
}
if (Arrays.equals(need, have)) {
return true;
}
for (int right = k; right < s.length(); right++) {
have[s.charAt(right) - 'a']++; // character enters
have[s.charAt(right - k) - 'a']--; // character leaves
if (Arrays.equals(need, have)) {
return true;
}
}
return false;
}
Problem 3 — sliding window maximum. Report the maximum of every window of size k. This is where the “undo” problem from the panel above bites: when the maximum leaves the window you would have to rescan. The fix is a monotonic deque of indices whose values are kept in decreasing order, so the front is always the current maximum.
The diagram freezes the moment the value 5 arrives. Everything already in the deque is smaller and older, so none of it can ever be a maximum again while the 5 is around, and it is popped from the back. The front index is dropped only when it slides out of the window.
public static int[] slidingWindowMaximum(int[] a, int k) {
if (k <= 0 || k > a.length) {
throw new IllegalArgumentException("k must be in 1.." + a.length + " but was " + k);
}
int[] out = new int[a.length - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // indices, values decreasing
for (int right = 0; right < a.length; right++) {
while (!dq.isEmpty() && a[dq.peekLast()] <= a[right]) {
dq.pollLast(); // smaller-or-equal values can never be a maximum again
}
dq.addLast(right);
if (dq.peekFirst() <= right - k) {
dq.pollFirst(); // the front index slid out of the window
}
if (right >= k - 1) {
out[right - k + 1] = a[dq.peekFirst()];
}
}
return out;
}
right=0 a[right]=1 deque(value@index)=[1@0]
right=1 a[right]=3 deque(value@index)=[3@1]
right=2 a[right]=-1 deque(value@index)=[3@1, -1@2] -> window max 3
right=3 a[right]=-3 deque(value@index)=[3@1, -1@2, -3@3] -> window max 3
right=4 a[right]=5 deque(value@index)=[5@4] -> window max 5
right=5 a[right]=3 deque(value@index)=[5@4, 3@5] -> window max 5
right=6 a[right]=6 deque(value@index)=[6@6] -> window max 6
right=7 a[right]=7 deque(value@index)=[7@7] -> window max 7
answer = [3, 3, 5, 5, 6, 7]
Going deeper: why the deque is O(n) and why it stores indices
Every index is pushed once and popped at most once, so the loop does at most 2n deque operations even though it contains a while. The same “each element enters once, leaves once” argument returns in section 4.
The deque stores indices rather than values because it needs to know when an entry has expired (index ≤ right − k), and a value alone cannot tell you that. The <= in the pop condition (rather than <) discards older entries equal to the new one: the newer equal value outlives them, so keeping both would only make the deque longer.
A PriorityQueue also solves this problem, in O(n log k) with lazy deletion of expired entries. I reasoned about that alternative but did not benchmark it for this post, so the claim above is about growth, not about measured speed.
Going deeper
Variable windows: grow on the right, shrink on the left, only when a rule breaks
Most window problems do not give you the length. They give you a rule — no repeated characters, at most two distinct letters, at most one zero — and ask for the longest window that obeys it. The window now breathes: right always steps forward and adds a character; if that breaks the rule, left steps forward and removes characters until the rule holds again.
Read the diagram as a loop: box 1 always runs, box 3 runs zero or more times, and the right edge only moves forward. The window size is recorded after the rule has been repaired, so it is always a valid window. Every problem in this section is that loop with a different summary and a different rule.
Problem 4 — longest substring without repeating characters. The summary is the last index at which each character was seen, so when a duplicate arrives left can jump straight past its previous occurrence. The code, from VariableWindow.java:
public static int longestUniqueSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
Integer prev = lastSeen.get(c);
if (prev != null) {
left = Math.max(left, prev + 1); // never move left backwards
}
lastSeen.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
input "abcabcbb"
right=0 'a' left=0 window="a" best=1
right=1 'b' left=0 window="ab" best=2
right=2 'c' left=0 window="abc" best=3
right=3 'a' left=1 window="bca" best=3 seen at 0 inside the window, left 0 -> 1
right=4 'b' left=2 window="cab" best=3 seen at 1 inside the window, left 1 -> 2
right=5 'c' left=3 window="abc" best=3 seen at 2 inside the window, left 2 -> 3
right=6 'b' left=5 window="cb" best=3 seen at 4 inside the window, left 3 -> 5
right=7 'b' left=7 window="b" best=3 seen at 6 inside the window, left 5 -> 7
answer = 3
input "abba"
right=0 'a' left=0 window="a" best=1
right=1 'b' left=0 window="ab" best=2
right=2 'b' left=2 window="b" best=2 seen at 1 inside the window, left 0 -> 2
right=3 'a' left=2 window="ba" best=2 seen at 0 but that is left of the window, left stays 2
answer = 2
Look at the last line of the "abba" trace: the final a was last seen at index 0, but the window already starts at 2, so left stays put. That is what Math.max is for, and section 7 shows what happens without it.
Problems 5, 6 and 7 reuse the same loop with different summaries:
#
Problem
Summary kept
Rule that must hold
5
Longest substring with at most K distinct characters
public static int longestKDistinct(String s, int k) {
if (k <= 0) {
return 0;
}
Map<Character, Integer> count = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
count.merge(s.charAt(right), 1, Integer::sum);
while (count.size() > k) { // rule broken: shrink from the left
char out = s.charAt(left++);
if (count.merge(out, -1, Integer::sum) == 0) {
count.remove(out);
}
}
best = Math.max(best, right - left + 1);
}
return best;
}
public static int characterReplacement(String s, int k) {
int[] count = new int[128];
int left = 0;
int maxFreq = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
maxFreq = Math.max(maxFreq, ++count[s.charAt(right)]);
if ((right - left + 1) - maxFreq > k) { // more than k characters need replacing
count[s.charAt(left++)]--; // slide (window size stays the same)
}
best = Math.max(best, right - left + 1);
}
return best;
}
public static int longestOnes(int[] a, int k) {
int left = 0;
int zeros = 0;
int best = 0;
for (int right = 0; right < a.length; right++) {
if (a[right] == 0) {
zeros++;
}
while (zeros > k) {
if (a[left++] == 0) {
zeros--;
}
}
best = Math.max(best, right - left + 1);
}
return best;
}
Going deeper: the maxFreq that is never decreased
Problem 6 has one line that looks like a bug: maxFreq only ever goes up, even after the character that set it has left the window. So the check (windowSize − maxFreq) > k can use a stale, too-large maxFreq and wrongly say the window is fine.
It does not matter, because of how the loop reacts. A broken check slides the window by one (an if, not a while), so the window never shrinks below its best size so far. The window can only grow past the record when a genuinely larger maxFreq appears, and that has to be a real count in the current window. A stale value therefore can keep the window the same size but cannot inflate the answer.
That is an argument, and the argument is what justifies the line. The randomized test (2,000 inputs against brute force, in output/07-random-agreement.txt) is evidence consistent with it, not a proof.
Going deeper
Shortest valid window: shrink while it is still valid
Flip the question from “longest window that obeys a rule” to “shortest window that reaches a goal” and the shrinking changes purpose. Before, left moved to repair a broken window. Now it moves to improve a valid one: grow until the goal is met, then shrink for as long as the goal is still met, recording the best size at every step.
Problem 8 — minimum size subarray sum. Shortest subarray whose sum is at least target (VariableWindow.minSubArrayLen):
public static int minSubArrayLen(int target, int[] a) {
if (target <= 0) {
throw new IllegalArgumentException("target must be positive but was " + target);
}
int left = 0;
long sum = 0;
int best = 0;
for (int right = 0; right < a.length; right++) {
sum += a[right];
while (sum >= target) { // valid: record it, then try a smaller one
int len = right - left + 1;
best = (best == 0) ? len : Math.min(best, len);
sum -= a[left++];
}
}
return best;
}
One precondition is easy to miss, and the method guards the cheap half of it (target must be positive): every element must be positive. Shrinking from the left is only safe if removing a value can never raise the sum.
Fingerprint of the negative-number bug. Give the window version [-2, -2, 3] and target 3 and it answers 0 (“no such subarray”), while the subarray [3] obviously qualifies — the running sum is −1 when the 3 arrives, so the window never looks valid. The real output is in section 7 (output/09-pitfalls.txt).
Problem 9 — minimum window substring. The hardest problem here and the most asked: the smallest substring of s containing every character of t, counting repeats. The summary is a need-count per character plus a single number, missing, of characters the window still owes. When missing reaches 0 the window is valid; shrink until it is not.
public static String minWindow(String s, String t) {
if (t.isEmpty() || t.length() > s.length()) {
return "";
}
int[] need = new int[128];
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
int missing = t.length(); // characters still owed to the window
int left = 0;
int bestStart = 0;
int bestLen = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
if (need[s.charAt(right)]-- > 0) {
missing--; // this character was genuinely needed
}
while (missing == 0) { // valid: shrink as far as possible
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
if (++need[s.charAt(left++)] > 0) {
missing++; // we just gave back a needed character
}
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
right=5 'C' window="ADOBEC" is VALID
new best "ADOBEC" (length 6)
drop 'A' -> window="DOBEC" no longer valid, missing=1
right=10 'A' window="DOBECODEBA" is VALID
drop 'D' -> window="OBECODEBA" still valid
drop 'O' -> window="BECODEBA" still valid
drop 'B' -> window="ECODEBA" still valid
drop 'E' -> window="CODEBA" still valid
drop 'C' -> window="ODEBA" no longer valid, missing=1
right=12 'C' window="ODEBANC" is VALID
drop 'O' -> window="DEBANC" still valid
drop 'D' -> window="EBANC" still valid
new best "EBANC" (length 5)
drop 'E' -> window="BANC" still valid
new best "BANC" (length 4)
drop 'B' -> window="ANC" no longer valid, missing=1
answer = "BANC"
The window becomes valid three times and the answer, BANC, is found on the third. Notice that the shrink loop sometimes drops a character and the window stays valid (a surplus O, D, E), and sometimes drops one and it breaks (the needed A, C, B); the missing counter is what tells those two cases apart in constant time.
A fair worry: there is a while inside a for. Is this not quadratic again?
No, and the diagram says why: left and right each walk the string once and neither steps backwards, so together they make at most about 2n moves. The module counts them on random strings; the numbers (from output/08-operation-counts.txt) are:
minWindow on random strings over A-D, t="ABCD" (seed 42): pointer moves
The loop is nested but each pointer only moves forward, so total moves stay linear.
n right moves left moves valid windows
1000 1,000 996 996
2000 2,000 1,996 1,996
4000 4,000 3,996 3,996
8000 8,000 7,993 7,993
Going deeper: why “a loop inside a loop” is not always quadratic
Count moves, not loop levels. The outer loop moves right exactly n times. The inner loop moves left, and left can never pass right, so across the entire run it moves at most n times as well. The inner loop is cheap on average even if one particular pass is long. This is called amortized analysis, and it is the same argument as for the deque in section 2.
In the table, “left moves” and “valid windows” are equal on every row by construction: each pass through the inner loop body moves left once and counts one valid window. They are two names for the same loop count, not two independent measurements.
The counts are a model of work (pointer moves), not a timing, so they say the algorithm is linear in operations, not how many nanoseconds it takes on your machine.
Going deeper
Two pointers from both ends: sorted data lets you throw half the answers away
The window patterns above move both edges the same way. The third pattern starts the pointers at opposite ends and walks them toward each other. It needs a reason to discard something at every step, and sorted order provides one.
Problem 10 — Two Sum II. In a sorted array, find two values that add up to target. Look at the smallest and the largest. If their sum is too small, the smallest value cannot be part of any answer: pairing it with anything smaller than the current largest only makes the sum smaller still. So drop it. If the sum is too big, drop the largest by the mirror argument.
Each row of the diagram is one step; the faded boxes are values already ruled out. One value disappears at every step, so a search over 6 values needs at most 5 steps rather than 15 pair checks.
public static int[] twoSumSorted(int[] a, int target) {
int lo = 0;
int hi = a.length - 1;
while (lo < hi) {
long sum = (long) a[lo] + a[hi];
if (sum == target) {
return new int[] {lo, hi};
} else if (sum < target) {
lo++; // need a bigger sum: only moving lo up can help
} else {
hi--; // need a smaller sum: only moving hi down can help
}
}
return new int[0];
}
The same argument scales. In the worst case (the target is not present) a sorted array of 8,000 values needs 31,996,000 pair checks by brute force and 7,999 two-pointer steps (from output/08-operation-counts.txt):
Pair search, target absent (worst case) in a sorted array 0..n-1: checks / steps
n all pairs two pointers
1000 499,500 999
2000 1,999,000 1,999
4000 7,998,000 3,999
8000 31,996,000 7,999
Problem 11 — 3Sum. Find all unique triplets that sum to zero. Sort once, fix the first value, and run Two Sum II on the rest. The only new difficulty is duplicates: equal values must be skipped at all three positions or the same triplet is reported several times.
3Sum in TwoPointers.threeSum:
public static List<List<Integer>> threeSum(int[] input) {
int[] a = input.clone();
Arrays.sort(a);
List<List<Integer>> out = new ArrayList<>();
for (int i = 0; i < a.length - 2; i++) {
if (a[i] > 0) {
break; // sorted: everything to the right is positive too
}
if (i > 0 && a[i] == a[i - 1]) {
continue; // skip duplicate first elements
}
int lo = i + 1;
int hi = a.length - 1;
while (lo < hi) {
int sum = a[i] + a[lo] + a[hi];
if (sum == 0) {
out.add(List.of(a[i], a[lo], a[hi]));
lo++;
hi--;
while (lo < hi && a[lo] == a[lo - 1]) {
lo++; // skip duplicate second elements
}
while (lo < hi && a[hi] == a[hi + 1]) {
hi--; // skip duplicate third elements
}
} else if (sum < 0) {
lo++;
} else {
hi--;
}
}
}
return out;
}
Problem 12 — container with most water. Given line heights, pick two lines that hold the most water between them. The area is min(height) × distance. Start with the widest pair. To do better the pair must get narrower, so the only hope is a taller limiting line: move the shorter pointer, because moving the taller one can only lower or keep the limiting height while the width shrinks.
public static long maxArea(int[] height) {
int lo = 0;
int hi = height.length - 1;
long best = 0;
while (lo < hi) {
long area = (long) Math.min(height[lo], height[hi]) * (hi - lo);
best = Math.max(best, area);
if (height[lo] < height[hi]) {
lo++; // the shorter line limits the area: discard it
} else {
hi--;
}
}
return best;
}
Container With Most Water: heights [1, 8, 6, 2, 5, 4, 8, 3, 7]
lo=0 hi=8 min(1,7) x 8 = 8 best=8 lo++ (left line is shorter)
lo=1 hi=8 min(8,7) x 7 = 49 best=49 hi-- (right line is not taller)
lo=1 hi=7 min(8,3) x 6 = 18 best=49 hi-- (right line is not taller)
lo=1 hi=6 min(8,8) x 5 = 40 best=49 hi-- (right line is not taller)
lo=1 hi=5 min(8,4) x 4 = 16 best=49 hi-- (right line is not taller)
lo=1 hi=4 min(8,5) x 3 = 15 best=49 hi-- (right line is not taller)
lo=1 hi=3 min(8,2) x 2 = 4 best=49 hi-- (right line is not taller)
lo=1 hi=2 min(8,6) x 1 = 6 best=49 hi-- (right line is not taller)
answer = 49
Going deeper: the 3Sum loop details, and the container greedy rule3Sum. Three details are worth knowing. if (a[i] > 0) break; is valid because the array is sorted: once the first value is positive, every sum to its right is positive. After finding a triplet the code advances both pointers and then skips equal neighbours with a[lo] == a[lo - 1] and a[hi] == a[hi + 1]; the second comparison reads one index to the right of hi, which is always in bounds because hi has just been decremented. And the input is cloned before sorting, so the caller’s array is not reordered — at the cost of O(n) extra space.
Container. The discard rule is a safe-elimination argument, the same shape as Two Sum II: when the left line is the shorter one, every pair that keeps it and uses a closer right line is both narrower and no taller, so none of them can beat the area just computed. That justifies dropping the left line for good. When the heights are equal the code moves hi; either choice is safe.
Going deeper
“O(1)” for problems 6 and 9 means a fixed 128-slot array, because these versions accept ASCII input only.
Going deeper: a quick recognition checklist for interviews
Ask three questions in order. Is the answer a contiguous slice? If it can skip elements, a window is the wrong tool (section 9). Can I undo the summary when an element leaves? Sums and counts yes, maximum no (use a deque, problem 3). For a variable window, does removing an element always move me toward the rule being satisfied? That is the monotonicity that makes shrinking safe, and it is exactly what fails for negative numbers in problem 8.
Going deeper
Window code is short, and short code hides bugs that pass every example in the problem statement. The module reproduces four of the most common as real wrong versions (in Pitfalls.java) and shows each failing, with the output committed in output/09-pitfalls.txt:
1. longest substring without repeats, left = lastSeen + 1 WITHOUT Math.max
input "abba": buggy = 3 correct = 2
at the final 'a', lastSeen('a') = 0, so the buggy code moves left from 2 back to 1
2. minimum-size subarray window used on input that contains negatives
target 3, input [-2, -2, 3]: window = 0 ("none") brute force = 1 ([3])
the running sum is -1 when the 3 arrives, so the window never looks valid
3. 3Sum without skipping duplicates
input [-1, 0, 1, 2, -1, -4]
buggy = [[-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]
correct = [[-1, -1, 2], [-1, 0, 1]]
4. two pointers on an array that is NOT sorted
input [3, 2, 4], target 6: twoSumSorted = [] but 2 + 4 = 6 exists (brute force: true)
The first one is the instructive one, so here is its source. The only difference from problem 4 is one missing Math.max (Pitfalls.longestUniqueNoMax):
public static int longestUniqueNoMax(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen.containsKey(c)) {
left = lastSeen.get(c) + 1;
}
lastSeen.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
The fingerprint of the first bug. The answer comes out too large, and only on inputs where a character’s previous occurrence sits to the left of the current window. Short examples from the problem statement rarely contain that shape; "abba" does. When you test a variable window, always include one input where the earlier duplicate is already outside the window.
The other three, in one line each: the minimum-subarray window silently assumes positive numbers (answers 0 for [-2, -2, 3] with target 3); 3Sum without skipping duplicates reports [-1, 0, 1] twice; and Two Sum II run on an unsorted array returns nothing for [3, 2, 4] and target 6 even though 2 + 4 is there. The common thread is that each pattern carries a precondition (a monotone rule, positive values, sorted input) that the code never checks, so the only defence is to know it.
Going deeper: edge cases worth running every time
From the four failures above and the guard clauses in the module: an empty string; k = 0 (problem 5 returns 0 immediately); k larger than the array (the fixed-window methods throw IllegalArgumentException); a target no subarray reaches (problem 8 returns 0); an array of all-equal values (3Sum must report [0, 0, 0] exactly once). All of these are asserted in SolutionsTest.edgeCases and invalidArgumentsAreRejected (SolutionsTest.java).
Going deeper
Reading a window solution and believing it is how the bugs above get shipped. The module does two things instead. First, every solution has a deliberately slow, obviously correct twin in BruteForce.java. Second, RandomAgreementTest feeds both the same seeded random inputs and fails the build on the first disagreement. The result file:
Going deeper: tests that double as the transcripts, and what the checks do not cover
Each output/NN-*.txt file is written by a JUnit test that asserts the same numbers it prints, through a tiny Transcript helper. A figure quoted in this post is therefore an assertion: if the code changes and the number stops being true, the build fails rather than the post quietly going stale. scripts/run-all.sh regenerates all nine files.
The limits are worth stating. The random inputs use short lengths and small alphabets, which is very good at finding edge-case bugs and says nothing about behaviour at scale; the operation counts model work rather than time; and problems 2, 6 and 9 accept restricted alphabets (lowercase letters for problem 2, ASCII for 6 and 9), so unusual Unicode input is out of scope.
Going deeper
Windows and two pointers are fast because they throw information away safely. When the information cannot be thrown away safely, they quietly give wrong answers (section 7), so it is worth knowing where the boundary is.
Should you reach for a window here? Often no, if the slice is not contiguous (then it is a dynamic-programming or subset problem), if the numbers can be negative and the rule is a sum threshold (shrinking is no longer safe; prefix sums with a hash map or a monotonic deque are the usual alternatives, which this module does not implement), or if the input is unsorted and you need a pair (sort first at O(n log n), or use a hash set at O(n) time and O(n) space). A window is the right tool when the answer is a contiguous slice and each element leaving the window has a predictable effect on your summary.
Further reading
sliding-window module in asmhatre/java-interview-lab — every file referenced above, plus all nine transcripts in output/
LRU Cache in Java — another interview staple built from a map plus a linked structure, with the same verify-against-brute-force habit
No Comments yet!