Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

Sliding window for nonnegative values

A sliding window maintains one contiguous array range and moves its boundaries without recomputing every sum. The shrinking variant relies on nonnegative input values.

Version: C23; repository compiler flag, production runtime not attested

Syntax

Use this shrinking-window rule only when all input values are nonnegative and the target is strictly positive. Use a running-sum type that can represent every intermediate sum without overflow, including the sum immediately after adding an element and before shrinking the window. Maintain left and right window boundaries and add each entering value to the running sum. While the current sum is at least the target, compare the current window length with the shortest found so far and update it if needed. Then subtract the leftmost value and advance the left boundary, even if that removal drops the sum below the target. An empty window has sum zero, so the positive target ensures that the loop stops before attempting to remove another element.

A sliding window is represented by left and right boundaries. The right boundary adds the next value to the running sum. Once the sum reaches the target, the left boundary advances and removed values are subtracted. Every element enters and leaves the window at most once, so the traversal takes linear time.

The nonnegative input precondition is essential. Adding a nonnegative number cannot reduce the sum, and removing one from the left cannot increase it. This monotonic behavior makes shrinking the window safe. Negative values break that reasoning and require a different algorithm.

The example implements a sliding window that finds the shortest contiguous range whose sum is at least 7. For 2, 1, 5, 2, 3, 2, it prints 2 because the range 5, 2 satisfies the condition.

Examples

#include <stddef.h>
#include <stdio.h>

int main(void) {
    const int values[] = {2, 1, 5, 2, 3, 2};
    const size_t count = sizeof values / sizeof values[0];
    const int target = 7;
    size_t left = 0;
    size_t best = count + 1;
    int sum = 0;

    for (size_t right = 0; right < count; ++right) {
        sum += values[right];
        while (sum >= target) {
            const size_t length = right - left + 1;
            if (length < best) best = length;
            sum -= values[left++];
        }
    }

    if (best == count + 1) printf("none\n");
    else printf("%zu\n", best);
    return 0;
}

Result

2

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources