Getting everything ready for you…

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

0s

Practice › Sliding Window

Longest Subarray with Sum K

Medium · Sliding Window · Asked at Amazon, Microsoft, TCS, Infosys

All numbers are positive. Find the length of the longest contiguous subarray whose sum is exactly k, or 0 if none exists.

Input

First line: n. Second line: n integers. Third line: k.

Output

The maximum length, or 0.

Constraints

Example 1

Input

7
1 2 3 1 1 1 1
3

Output

3

Example 2

Input

2
5 6
4

Output

0

Hints

  1. With only positive numbers, a window whose sum is too big can only be fixed by shrinking it from the left.
  2. Expand right, shrink left while sum > k, and record the length whenever the sum equals k.

Approach

Sliding window: add a[r] to the sum, and while the sum exceeds k remove a[l] and move l forward. If the sum is now exactly k, update the best length with r − l + 1. This works only because all values are positive. With negatives you'd need the prefix-sum + hash-map method instead.

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 k, sum = 0;
    cin >> k;
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum > k) sum -= a[l++];
        if (sum == k) best = max(best, r - l + 1);
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
best = total = l = 0
for r in range(n):
    total += a[r]
    while total > k:
        total -= a[l]
        l += 1
    if total == k:
        best = max(best, r - l + 1)
print(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 k = sc.nextLong(), sum = 0;
        int best = 0, l = 0;
        for (int r = 0; r < n; r++) {
            sum += a[r];
            while (sum > k) sum -= a[l++];
            if (sum == k) best = Math.max(best, r - l + 1);
        }
        System.out.println(best);
    }
}

Solve Longest Subarray with Sum K online · All practice problems