Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Sliding Window

Minimum Size Subarray Sum

Medium · Sliding Window · Asked at Amazon, Google, Goldman Sachs

All numbers are positive. Find the length of the shortest contiguous subarray whose sum is at least s. Print 0 if there is none.

Input

First line: n. Second line: n positive integers. Third line: s.

Output

The minimal length, or 0.

Constraints

Example 1

Input

6
2 3 1 2 4 3
7

Output

2

Example 2

Input

3
1 1 1
10

Output

0

Hints

  1. All numbers are positive, so growing a window only increases its sum and shrinking only decreases it.
  2. Expand the right end; while the sum is ≥ s, record the length and shrink from the left.

Approach

A variable-size window. Move r forward, adding a[r]. While the window sum is at least s, the window qualifies: record r − l + 1, then remove a[l] and advance l to look for something shorter. Each index enters and leaves the window once. If no window ever qualifies, print 0.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    long long s;
    cin >> s;
    long long sum = 0;
    int best = INT_MAX, l = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum >= s) {
            best = min(best, r - l + 1);
            sum -= a[l++];
        }
    }
    cout << (best == INT_MAX ? 0 : best) << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, s = data[1 : n + 1], data[n + 1]
best, total, l = n + 1, 0, 0
for r in range(n):
    total += a[r]
    while total >= s:
        best = min(best, r - l + 1)
        total -= a[l]
        l += 1
print(0 if best == n + 1 else best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        long s = sc.nextLong(), sum = 0;
        int best = Integer.MAX_VALUE, l = 0;
        for (int r = 0; r < n; r++) {
            sum += a[r];
            while (sum >= s) {
                best = Math.min(best, r - l + 1);
                sum -= a[l++];
            }
        }
        System.out.println(best == Integer.MAX_VALUE ? 0 : best);
    }
}

Solve Minimum Size Subarray Sum online · All practice problems