Day 2 of 60 Days of DSA: Subarray with Given Sum & Subarray with Least Average

Learn how to calculate subarray sums problems — from brute force to prefix sums.

Problem Description- 1

Given an array A of length N. Also given are integers B and C. Return 1 if there exists a subarray with length B having sum C and 0 otherwise

Problem Constraints

1 <= N <= 105
1 <= A[i] <= 104
1 <= B <= N
1 <= C <= 109

Input Format

First argument A is an array of integers.
The remaining arguments B and C are integers

Output Format

Return 1 if such a subarray exist and 0 otherwise

Example Input

Input 1:
A = [4, 3, 2, 6, 1]
B = 3
C = 11
Input 2:
A = [4, 2, 2, 5, 1]
B = 4
C = 6

Example Output

Output 1:
1
Output 2:
0

Example Explanation

Explanation 1:
The subarray [3, 2, 6] is of length 3 and sum 11.
Explanation 2:
There are no such subarray.

Solution:

Solution Approach:

Intuition

If we try to check every subarray of length B by summing elements each time,
it would take O(N × B) time — too slow when N is large (up to 10^5).

Instead, we use a sliding window technique to efficiently calculate subarray sums in O(N) time.

Sliding Window Concept

A sliding window is a subarray that “slides” across the array while maintaining a fixed size.

  1. Start by summing the first B elements.
  2. As you move the window forward by one position:
  • Subtract the element that is going out of the window (leftmost).
  • Add the element that is coming into the window (next right element).

3. This way, each update takes O(1) time instead of recomputing the entire sum.

Example:

A = [4, 3, 2, 6, 1], B = 3
  • Window 1: [4, 3, 2] → sum = 9
  • Window 2: [3, 2, 6] → sum = 11 (add 6, remove 4)
  • Window 3: [2, 6, 1] → sum = 9 (add 1, remove 3)

Now, check if any sum = C (here, 11) → Yes → return 1 ✅

Code Walkthrough

Step 1: findSumOfSubArraySizeB()

This function returns an array of all subarray sums of size B.

Step 2: subArrayWithGivenSum()

Now we simply check if any of those subarray sums equals C.

function subArrayWithGivenSum(A, B, C){
 let arr = findSumOfSubArraySizeB(A, B);
 for(let i=0; i< arr.length; i++){
 if(arr[i] == C){
 return 1;
 }
 }
 return 0;
}

function findSumOfSubArraySizeB(arr, window){
 let opArray = [];
 let sum = 0;
 for(let i = 0; i< arr.length; i++){
 if(i<window-1){
 sum += arr[i]
 }else{
 sum += arr[i];
 if(i-window<0){
 opArray.push(sum);
 }else{
 sum -= arr[i-window];
 opArray.push(sum);
 }
 }
 }
 return opArray;
}

Time and Space Complexity

  • Time Complexity:
    O(N) — We traverse the array once and do O(1) work per element.
  • Space Complexity:
    O(K) — We store all window sums in an array (opArray) of size roughly N - B + 1.
    This can be optimized to O(1) if we check the condition inside the same loop instead of storing sums.

Problem Description- 2

Given an array A of size N, find the subarray of size B with the least average.

Problem Constraints

1 <= B <= N <= 105
-105 <= A[i] <= 105

Input Format

First argument contains an array A of integers of size N.
Second argument contains integer B.

Output Format

Return the index of the first element of the subarray of size B that has least average.
Array indexing starts from 0.

Example Input

Input 1:
A = [3, 7, 90, 20, 10, 50, 40]
B = 3
Input 2:
A = [3, 7, 5, 20, -10, 0, 12]
B = 2

Example Output

Output 1:
3
Output 2:
4

Example Explanation

Explanation 1:
Subarray between indexes 3 and 5
The subarray {20, 10, 50} has the least average
among all subarrays of size 3.
Explanation 2:
Subarray between [4, 5] has minimum average

Solution Approach:

Intuition

A subarray’s average is directly proportional to its sum when the length B is constant.
So instead of comparing averages, we can just compare sums — the subarray with the smallest sum will also have the smallest average.

Example:

A = [3, 7, 90, 20, 10, 50, 40]
B = 3

We check every 3-length subarray:

  • [3, 7, 90] → sum = 100
  • [7, 90, 20] → sum = 117
  • [90, 20, 10] → sum = 120
  • [20, 10, 50] → sum = 80 ✅ smallest sum
  • [10, 50, 40] → sum = 100

So, the subarray [20, 10, 50] has the least average, and its starting index is 3.

Sliding Window Approach

A naive approach would compute the sum of every possible subarray of size B —
which takes O(N × B) time.

Instead, we use a sliding window technique to achieve O(N) time complexity.

Steps:

  1. Calculate the sum of the first B elements (first window).
  2. As we move forward:
  • Add the new element entering the window.
  • Subtract the element that is leaving the window.

3. Track the minimum sum and its starting index as we slide.

Code Walkthrough

Step 1: findSumOfSubArraySizeB()

This helper function computes the sum of all subarrays of size B using a sliding window.

Step 2: leastAverage()

Once we have all subarray sums, we simply find the index of the smallest sum.


function leastAverage(A, B){
 let arr = findSumOfSubArraySizeB(A, B);
 let min = Number.MAX_SAFE_INTEGER;
 let index = -1;
 for(let i=0; i< arr.length; i++){
 if(min > arr[i]){
 min = arr[i];
 index = i;
 }
 }
 return index;
}

function findSumOfSubArraySizeB(arr, window){
 let opArray = [];
 let sum = 0;
 for(let i = 0; i< arr.length; i++){
 if(i<window-1){
 sum += arr[i]
 }else{
 sum += arr[i];
 if(i-window<0){
 opArray.push(sum);
 }else{
 sum -= arr[i-window];
 opArray.push(sum);
 }
 }
 }
 return opArray;
}

Time and Space Complexity

Time: O(N)

Reason- Single traversal for sliding window

Space: O(K)

Reason- Storing all window sums (can be optimised to O(1))

At Dev Simplified, We Value Your Feedback 📊

👉 Follow us to not miss any updates.

👉 Have any suggestions? Let us know in the comments!

👉 Subscribe for free and join our growing community!