Finding the Smallest Subarray with Sum ≥ X Using Sliding Window in C
C
Hard
4 views
Problem Description
Find the smallest subarray whose sum is greater than or equal to the given value - Two pointer sliding window expansion/shrink decision logic?
Official Solution
#include <stdio.h>
#include <limits.h>
int main() {
int arr[100], n, x;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter array elements:n");
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
printf("Enter target sum x: ");
scanf("%d", &x);
int minLength = INT_MAX;
int start = 0, currentSum = 0;
for (int end = 0; end < n; end++) {
currentSum += arr[end];
// Shrink the window as much as possible while sum >= x
while (currentSum >= x) {
if (end - start + 1 < minLength)
minLength = end - start + 1;
currentSum -= arr[start];
start++;
}
}
if (minLength == INT_MAX)
printf("No subarray found with sum >= %dn", x);
else
printf("Length of smallest subarray with sum >= %d = %dn", x, minLength);
return 0;
}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!