The shortest valid window
When validity survives growing rather than shrinking, the loop turns inside out: shrink while the window is valid, and record its length before every step in.
The loop, inside out
"Covers every letter" and "sum at least K with positive numbers" are the opposite kind of property: a run that contains a valid run is valid. Growing can only help, so the question is how short a valid window can be. Grow on the right until the window is valid; then, while it stays valid, record its length and drop an element from the left. The moment it stops being valid, go back to growing.
Two details differ from the longest window and both cause bugs. The answer is recorded inside the shrinking loop, before each removal, because after the loop the window is no longer valid. And the best starts at "none found", not at zero.
The shortest window of "aabcbcdbca" that holds a, b, c and d.
-
Step 1 / 11sa0a1b2c3b4c5d6b7c8a9need4
The string holds 4 kinds of letter: a, b, c, d. A window must contain all of them.
-
Step 2 / 11sa0lo/hia1b2c3b4c5d6b7c8a9have1best—
'a' enters; the window covers 1 of 4.
-
Step 3 / 11sa0loa1hib2c3b4c5d6b7c8a9have1best—
'a' enters; the window covers 1 of 4.
-
Step 4 / 11sa0loa1b2hic3b4c5d6b7c8a9have2best—
'b' enters; the window covers 2 of 4.
-
Step 5 / 11sa0loa1b2c3hib4c5d6b7c8a9have3best—
'c' enters; the window covers 3 of 4.
-
Step 6 / 11sa0loa1b2c3b4hic5d6b7c8a9have3best—
'b' enters; the window covers 3 of 4.
-
Step 7 / 11sa0loa1b2c3b4c5hid6b7c8a9have3best—
'c' enters; the window covers 3 of 4.
-
Step 8 / 11sa0a1b2loc3b4c5d6hib7c8a9have3best6
'd' enters; the window covers 4 of 4. It covers everything, so record 7, then 6 while dropping from the left; it stops covering when lo reaches 2. Best 6.
-
Step 9 / 11sa0a1b2loc3b4c5d6b7hic8a9have3best6
'b' enters; the window covers 3 of 4.
-
Step 10 / 11sa0a1b2loc3b4c5d6b7c8hia9have3best6
'c' enters; the window covers 3 of 4.
-
Step 11 / 11sa0a1b2c3b4c5d6b7loc8a9hihave3best4
'a' enters; the window covers 4 of 4. It covers everything, so record 8, then 7, then 6, then 5, then 4 while dropping from the left; it stops covering when lo reaches 7. Best 4.
The code
The positive-sum version, where the state is a running total and "valid" means the total has reached the target.
def shortest_subarray(nums, target):
n = len(nums)
best, lo, total = n + 1, 0, 0
for hi, value in enumerate(nums):
total += value
while total >= target: # shrink while it still qualifies
best = min(best, hi - lo + 1)
total -= nums[lo]
lo += 1
return 0 if best == n + 1 else best#include <vector>
#include <algorithm>
int solve(const std::vector<int>& nums, long long target) {
const int n = static_cast<int>(nums.size());
int best = n + 1, lo = 0;
long long total = 0; // 64-bit: the sum can reach 10^9
for (int hi = 0; hi < n; ++hi) {
total += nums[hi];
while (total >= target) { // shrink while it still qualifies
best = std::min(best, hi - lo + 1);
total -= nums[lo];
++lo;
}
}
return best == n + 1 ? 0 : best;
}class Solution {
public int shortestSubarray(int[] nums, long target) {
int n = nums.length, best = n + 1, lo = 0;
long total = 0; // 64-bit: the sum can reach 10^9
for (int hi = 0; hi < n; hi++) {
total += nums[hi];
while (total >= target) { // shrink while it still qualifies
best = Math.min(best, hi - lo + 1);
total -= nums[lo];
lo++;
}
}
return best == n + 1 ? 0 : best;
}
}function shortestSubarray(nums, target) {
const n = nums.length;
let best = n + 1, lo = 0, total = 0;
for (let hi = 0; hi < n; hi++) {
total += nums[hi];
while (total >= target) { // shrink while it still qualifies
best = Math.min(best, hi - lo + 1);
total -= nums[lo];
lo++;
}
}
return best === n + 1 ? 0 : best;
}fn solve(nums: &[i64], target: i64) -> usize {
let n = nums.len();
let (mut best, mut lo, mut total) = (n + 1, 0usize, 0i64);
for hi in 0..n {
total += nums[hi];
while total >= target { // shrink while it still qualifies
best = best.min(hi - lo + 1);
total -= nums[lo];
lo += 1;
}
}
if best == n + 1 { 0 } else { best }
}import Data.Array
-- An array rather than a list, so that dropping from the left stays O(1) and the
-- whole scan stays linear. go carries: right end, left end, running sum, best so far.
solve :: [Int] -> Int -> Int
solve nums target
| best > n = 0
| otherwise = best
where
n = length nums
arr = listArray (0, n - 1) nums
best = go 0 0 0 (n + 1)
go hi lo total acc
| hi >= n = acc
| otherwise = let (lo', total', acc') = shrink lo (total + arr ! hi) acc
in go (hi + 1) lo' total' acc'
where
shrink l t a -- shrink while it still qualifies
| t >= target = shrink (l + 1) (t - arr ! l) (min a (hi - l + 1))
| otherwise = (l, t, a)The same code is the reference solution to Shortest subarray with a sum at least the target, where it is compiled and run against the tests in all six languages.
Longest and shortest side by side
| Longest valid window | Shortest valid window | |
|---|---|---|
| Validity survives | shrinking | growing |
| Inner loop runs | while the window is invalid | while the window is valid |
| Record the answer | after the inner loop | inside the inner loop, before removing |
| Start the best at | 0 | none found (∞ or a flag) |
| Typical words | "longest", "at most" | "shortest", "at least", "contains all" |
For "cover the letters of t, with repeats", keep need[c] for each letter of t and the number of letters still short. It is the anagram counter of the fixed-window module, used here to decide when the window is valid.