Card 03/ 08
The Variable Window Template in Python, Java and TypeScript
One loop that takes in the next element, one inner loop that shrinks while the rule is broken, and one line that records the best.
The variable window template is one loop that moves end over every element and an inner loop that moves start forward while the window breaks its rule. Three lines change between problems, and the highlighted lines mark them: the update when an element enters, the rule the inner loop tests, and the line that records the best window. Each listing finds the longest run of costs within a budget of 6, on 2 1 3 1 1 1 4, on costs that all fit, on costs that are each over budget and on an empty list.
The variable window template in three languages
def longest_within_budget(costs: list[int], budget: int) -> int:
start = 0
total = 0
best = 0
for end in range(len(costs)):
total += costs[end]
while total > budget:
total -= costs[start]
start += 1
best = max(best, end - start + 1)
return best
for costs, budget in [([2, 1, 3, 1, 1, 1, 4], 6), ([1, 1, 1], 6), ([7, 8], 6), ([], 6)]:
print(f"{costs} budget {budget}: longest run {longest_within_budget(costs, budget)}")[2, 1, 3, 1, 1, 1, 4] budget 6: longest run 4
[1, 1, 1] budget 6: longest run 3
[7, 8] budget 6: longest run 0
[] budget 6: longest run 0import java.util.Arrays;
public class LongestWithinBudget {
static int longestWithinBudget(int[] costs, int budget) {
int start = 0;
int total = 0;
int best = 0;
for (int end = 0; end < costs.length; end++) {
total += costs[end];
while (total > budget) {
total -= costs[start];
start++;
}
best = Math.max(best, end - start + 1);
}
return best;
}
public static void main(String[] args) {
int[][] inputs = {{2, 1, 3, 1, 1, 1, 4}, {1, 1, 1}, {7, 8}, {}};
for (int[] costs : inputs) {
System.out.println(Arrays.toString(costs) + " budget 6: longest run " + longestWithinBudget(costs, 6));
}
}
}[2, 1, 3, 1, 1, 1, 4] budget 6: longest run 4
[1, 1, 1] budget 6: longest run 3
[7, 8] budget 6: longest run 0
[] budget 6: longest run 0function longestWithinBudget(costs: number[], budget: number): number {
let start = 0;
let total = 0;
let best = 0;
for (let end = 0; end < costs.length; end++) {
total += costs[end];
while (total > budget) {
total -= costs[start];
start++;
}
best = Math.max(best, end - start + 1);
}
return best;
}
const inputs: number[][] = [[2, 1, 3, 1, 1, 1, 4], [1, 1, 1], [7, 8], []];
for (const costs of inputs) {
console.log(`[${costs.join(", ")}] budget 6: longest run ${longestWithinBudget(costs, 6)}`);
}[2, 1, 3, 1, 1, 1, 4] budget 6: longest run 4
[1, 1, 1] budget 6: longest run 3
[7, 8] budget 6: longest run 0
[] budget 6: longest run 0The three listings print the same lengths. When every cost is over budget, the inner loop empties the window each time, start passes end, and the recorded length is 0, so no special case is needed. The pass is O(n) time and O(1) extra space for n costs, because start and end each move at most n times.
A fixed window is the case where the window shrinks by exactly one element every step once it reaches its size, so the inner loop becomes a single subtraction. A problem that asks for the shortest valid window moves the record line inside the inner loop, so it records each valid window before shrinking it.
← → move through sections and cards