java-interview-lab/sliding-window/README.md

sliding-window

Companion code for the ankurm.com article Sliding Window and Two Pointers in Java: 12 Interview Problems Solved.

Twelve classic interview problems solved with the two patterns, each cross-checked against an obviously-correct brute-force version on seeded random inputs. Every figure and console line in the article is quoted from a file in output/, which the JUnit tests write while asserting the same numbers. There is no docs/ folder: the explanations live in the article itself.

Versions

Component	Version	Verified against
JDK	Temurin 25.0.5+8 (LTS)	java -version
JUnit	6.1.3	junit-bom maven-metadata.xml on Maven Central (latest GA)
Maven	3.9.x	mvn -version

Quickstart

cd sliding-window
export JAVA_HOME=/path/to/jdk-25 PATH="$JAVA_HOME/bin:$PATH"
./scripts/run-all.sh      # runs 11 tests and regenerates output/*.txt

The first Maven run must be online so the plugins land in the local cache.

The twelve problems

#	Problem	Pattern	Method
1	Maximum sum of k consecutive elements	fixed window	FixedWindow.maxSumSubarray
2	Permutation in string	fixed window + counts	FixedWindow.permutationInString
3	Sliding window maximum	fixed window + monotonic deque	FixedWindow.slidingWindowMaximum
4	Longest substring without repeating characters	variable window	VariableWindow.longestUniqueSubstring
5	Longest substring with at most K distinct characters	variable window	VariableWindow.longestKDistinct
6	Longest repeating character replacement	variable window	VariableWindow.characterReplacement
7	Max consecutive ones III	variable window	VariableWindow.longestOnes
8	Minimum size subarray sum	shrinking window	VariableWindow.minSubArrayLen
9	Minimum window substring	shrinking window	VariableWindow.minWindow
10	Two Sum II (sorted input)	opposite-end pointers	TwoPointers.twoSumSorted
11	3Sum	sort + pointers	TwoPointers.threeSum
12	Container with most water	opposite-end pointers	TwoPointers.maxArea

Source layout

sliding-window/
├── pom.xml
├── scripts/run-all.sh
├── src/main/java/com/ankurm/interviewlab/slidingwindow/
│   ├── FixedWindow.java       problems 1-3
│   ├── VariableWindow.java    problems 4-9
│   ├── TwoPointers.java       problems 10-12
│   ├── BruteForce.java        slow, obviously-correct references
│   ├── DryRuns.java           instrumented copies that record every step
│   ├── Complexity.java        operation counters (counted, not timed)
│   └── Pitfalls.java          four plausible-looking wrong versions
├── src/test/java/.../         SolutionsTest, RandomAgreementTest, DryRunTest, ComplexityTest, PitfallsTest
└── output/*.txt               captured real output

Captured output (output/)

File	What it shows
01-fixed-window-trace.txt	max-sum window sliding over [2,1,5,1,3,2]
02-longest-unique-trace.txt	left pointer jumps on abcabcbb and the abba case
03-min-window-trace.txt	grow until valid, shrink until invalid on ADOBECODEBANC
04-sliding-max-deque-trace.txt	the monotonic deque contents at every step
05-two-pointers-trace.txt	Two Sum II and Container With Most Water
06-all-twelve-results.txt	one example per problem beside the brute-force answer
07-random-agreement.txt	24,000 seeded comparisons, 0 disagreements
08-operation-counts.txt	brute force vs window operation counts at n = 1k..8k
09-pitfalls.txt	four classic mistakes, each reproduced