1. Problem Statement
Given an integer x and an integer array arr[], find the length of the smallest contiguous subarray whose sum is strictly greater than x.
If no such subarray exists, return 0.
Example 1:
Input:
x = 51
arr[] = [1, 4, 45, 6, 0, 19]Output:
3Explanation:
The subarray [4, 45, 6] has a sum of 55, which is greater than 51. Its length is 3, which is the smallest possible length.
Example 2:
Input:
x = 100
arr[] = [1, 10, 5, 2, 7]Output:
0Explanation:
No subarray in the given array has a sum greater than 100. Therefore, the result is 0.
2. Approach – Sliding Window (Two Pointers)
The problem can be solved efficiently using the Sliding Window technique. Instead of generating every possible subarray and calculating its sum separately, a window is maintained using two pointers.
The right pointer expands the window by adding elements, while the left pointer shrinks the window whenever its sum becomes greater than x.
Since all the array elements are non-negative, shrinking the window will never increase its sum. This property helps to find the smallest valid subarray efficiently.
Algorithm
- Initialize
left = 0,sum = 0, andminLength = int.MaxValue. - Traverse the array using the
rightpointer. - Add the current element
arr[right]tosum. - If
sum > x, the current window is a valid subarray. - Update
minLengthwith the minimum length of the current window. - Remove the element at
arr[left]from the sum and incrementleftto shrink the window. - Repeat the shrinking process as long as
sum > x. - After traversing the array, return
minLength. If no valid subarray is found, return0.
3. C# Implementation
class Solution {
public int smallestSubWithSum(int[] arr, int x) {
int left = 0;
int sum = 0;
int minLength = int.MaxValue;
for (int right = 0; right < arr.Length; right++) {
sum += arr[right];
while (sum > x) {
minLength = Math.Min(minLength, right - left + 1);
sum -= arr[left];
left++;
}
}
return minLength == int.MaxValue ? 0 : minLength;
}
}4. Code Explanation
Step 1: Initialize variables
int left = 0;
int sum = 0;
int minLength = int.MaxValue;left– represents the starting index of the current window.sum– stores the sum of elements inside the current window.minLength– stores the minimum valid subarray length found so far. It is initialized toint.MaxValuebecause no valid subarray has been found yet.
Step 2: Expand the sliding window
for (int right = 0; right < arr.Length; right++) {
sum += arr[right];The right pointer traverses the array from left to right. Each element is added to the current window sum.
Whenever a new element is added, the window becomes larger and its sum is updated.
Step 3: Check whether the sum is greater than X
while (sum > x) {Whenever the current window sum exceeds x, a valid subarray is found.

Join the conversation! Your thoughts help the community grow.