Fixed-Size Subarray Sum

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given an array of integers arr of size N, an integer K, and a target value Sum. Your task is to determine if there exists a contiguous subarray of size exactly K whose elements sum up to the given Sum.

If such a subarray exists, you should report "YES". Otherwise, you should report "NO".

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single integer N, the size of the array.

The second line contains N space-separated integers, representing the elements of the array arr.

The third line contains two space-separated integers, K and Sum.

Output Format:

Print a single string, either "YES" or "NO".

Note:

A brute-force approach of checking every possible subarray of size K would be too slow. An efficient approach like the sliding window technique is required to solve this problem within the given time limits.

Sample Input 1:

9
1 4 2 10 2 3 1 0 20
4 18

Sample Output 1:

YES

Explanation for Sample 1:

The subarray starting at index 1: {4, 2, 10, 2} has a size of 4, and its sum is 4 + 2 + 10 + 2 = 18. Since a valid subarray was found, the output is "YES".

Sample Input 2:

9
1 4 2 10 2 3 1 0 20
3 6

Sample Output 2:

YES

Explanation for Sample 2:

The subarray starting at index 4: {2, 3, 1} has a size of 3, and its sum is 2 + 3 + 1 = 6. Since a valid subarray was found, the output is "YES".

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= K <= N <= 10^5
-10^9 <= arr[i] <= 10^9
-10^{14} <= Sum <= 10^{14} (The sum might exceed the capacity of a standard 32-bit integer)

Time Limit: 1 sec

Approaches (1)

Approach 1

Sliding window

Time Complexity

Space Complexity

(100% EXP penalty)

Fixed-Size Subarray Sum

Console