Kadane, sliding window and two pointers, step by step

Pick a technique, then type or paste an array of integers separated by commas or spaces, along with the window size or target the technique needs. Step makes one decision at a time; Play runs them all. The tinted cells are the current window (for two pointers, the part of the array still in play) and the green cells are the best answer found so far. The panel on the right shows the running values and the full trace.

• Each technique opens with a standard example; Load the example brings it back after you edit.
• Copy answer gives the numbered trace and the result as plain text; Copy link saves the technique, array, target and step in the address.

Many array problems ask about contiguous subarrays (the largest sum, the shortest run reaching a total, how many add up to k) or about pairs of elements. The direct solution tries them all. An array of n elements has n(n + 1)/2 non-empty subarrays and n(n − 1)/2 pairs, so brute force grows with the square of n:

The maximum subarray problem asks for the contiguous run with the largest sum. In Programming Pearls, Jon Bentley tells its history: Ulf Grenander of Brown University posed it as a simplified, one-dimensional version of a pattern-matching problem on digitised images; Michael Shamos found a faster divide-and-conquer solution and described the problem at a Carnegie Mellon seminar, where the statistician Jay Kadane came up with the linear algorithm within a minute.

The idea is to ask, for each position i, what the best subarray ending at i is. It is either a[i] alone or a[i] added to the best subarray ending at i − 1, whichever is larger: cur = max(a[i], cur + a[i]). Put another way, a run with a negative sum is never worth extending, so the algorithm drops it and starts again. The overall answer is the largest cur seen. On [-2, 1, -3, 4, -1, 2, 1, -5, 4], the run restarts at 1 and again at 4, then grows to 6 over [4, -1, 2, 1] and never beats that. Kadane takes 9 steps; brute force computes 45 subarray sums.

Starting with best = a[0], as here, makes an all-negative array return its largest element: [-3, -1, -2] gives -1. Many write-ups start from 0 instead, which silently allows an empty subarray with sum 0. Which is right depends on how the problem is worded. Kadane's algorithm is also a small example of dynamic programming: cur is the answer to a subproblem, and each answer is built from the previous one.

A sliding window keeps a contiguous range [lo, hi] and a summary of it, usually its sum, and updates the summary as the ends move instead of recomputing it. With a fixed size k, sliding one place right adds the element entering and subtracts the one leaving, so each window costs two operations instead of k − 1 additions. On [1, 4, 2, 10, 23, 3, 1, 0, 20] with k = 4 the best window sums to 39, found with 13 additions and subtractions against 18 for summing every window from scratch. The saving grows with k: with k = 100 on 10,000 numbers it is 19,899 against 980,199.

A variable window grows and shrinks. For the shortest subarray with sum at least a target, move hi right, adding elements, until the sum reaches the target; then move lo right, removing elements, while it still does, recording the length each time. Each pointer only moves forward, so there are at most 2n moves. On [2, 3, 1, 2, 4, 3] with target 7 the answer is 2, the pair [4, 3], after 11 pointer moves.

The variable window depends on every number being positive: then growing the window always raises the sum and shrinking always lowers it, so once a window is too small, no window starting further left and ending at the same place can be shorter and still qualify. With a negative number that reasoning breaks. On [1, -2, 4] with target 3, the window method reports length 3, but [4] on its own reaches the target, so the answer is 1. The visualizer refuses to run the variable window on arrays with zero or negative numbers for this reason; prefix sums are the tool for those.

To find two numbers that add up to a target, sort the array and put one pointer at each end. If the two numbers add up to too little, the left one is too small to pair with anything that remains, because it is already paired with the largest remaining number; move it right. If the sum is too big, the right one is too large for anything that remains; move it left. Each comparison rules out every remaining pair that uses one of the two elements, which is why at most n − 1 comparisons are needed. For [2, 7, 11, 15] and target 9 that is 3 comparisons out of 6 pairs; on 10,000 numbers, 722 against 49,995,000.

Sorting costs O(n log n), so the whole method is O(n log n). If the array is unsorted and the original positions matter, a hash map of the numbers seen so far finds the pair in one O(n) pass instead. The same converging-pointer idea appears in reversing an array, checking a palindrome and the three-sum problem, which fixes one number and runs two pointers over the rest.

The prefix sum P[j] is the sum of the first j elements, with P[0] = 0. Any subarray sum is then a difference of two prefix sums: a[i] + … + a[j] = P[j + 1] − P[i]. A subarray ending at j sums to k exactly when some earlier prefix equals P[j + 1] − k. Keeping a hash map from each prefix sum to the number of times it has appeared turns the question "how many subarrays end here and sum to k" into one lookup.

The map starts as {0: 1}, for the empty prefix, so subarrays that start at index 0 are counted. On [1, 2, 1, -1, 2, 3] with k = 3, the run finds 4 subarrays in 6 lookups, where brute force checks 21 subarrays. Unlike the sliding window this does not care about signs, because it never assumes that a longer subarray has a larger sum. The cost is O(n) extra memory for the map.