.png)
Smallest Subarray with Sum Greater Than X
Problem Statement
You are given an integer array arr of positive integers and an integer X.
Your task is to find the minimum length of a contiguous subarray whose sum is strictly greater than X.
If no such subarray exists, return 0.
Example 1
Input
arr = [1, 4, 45, 6, 10, 19]
X = 51
Output
3
Explanation
Subarray [4, 45, 6] → sum = 55
Example 2
Input
arr = [1, 10, 5, 2, 7]
X = 9
Output
1
Example 3
Input
arr = [1, 1, 1]
X = 10
Output
0
Why This Problem Is Important
- Classic sliding window interview problem
- Tests two-pointer optimization
- Frequently asked in Amazon, Google, Microsoft
- Only works with positive integers
- Foundation for minimum window problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Prefix Sum + Binary Search | O(n log n) | O(n) |
| Approach 3 | Sliding Window (Optimal) | O(n) | O(1) |
Approach 1: Brute Force
Idea
Check all possible subarrays, calculate sum, and track minimum length whose sum > X.
Time & Space
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
#include
int main() {
int arr[] = {1,4,45,6,10,19};
int n = 6, X = 51;
int ans = INT_MAX;
for(int i=0;i X) {
if(j - i + 1 < ans)
ans = j - i + 1;
break;
}
}
}
printf("%d", ans == INT_MAX ? 0 : ans);
}
C++
#include
using namespace std;
int main() {
int arr[] = {1,4,45,6,10,19};
int n = 6, X = 51;
int ans = INT_MAX;
for(int i=0;i X) {
ans = min(ans, j - i + 1);
break;
}
}
}
cout << (ans == INT_MAX ? 0 : ans);
}
Java
class SmallestSubarray {
public static void main(String[] args) {
int[] arr = {1,4,45,6,10,19};
int X = 51;
int ans = Integer.MAX_VALUE;
for(int i=0;i X) {
ans = Math.min(ans, j - i + 1);
break;
}
}
}
System.out.println(ans == Integer.MAX_VALUE ? 0 : ans);
}
}
Python
arr = [1,4,45,6,10,19]
X = 51
n = len(arr)
ans = float('inf')
for i in range(n):
s = 0
for j in range(i,n):
s += arr[j]
if s > X:
ans = min(ans, j-i+1)
break
print(0 if ans == float('inf') else ans)
JavaScript
let arr = [1,4,45,6,10,19];
let X = 51;
let ans = Infinity;
for(let i=0;i X){
ans = Math.min(ans, j-i+1);
break;
}
}
}
console.log(ans === Infinity ? 0 : ans);
C#
using System;
class Program {
static void Main() {
int[] arr = {1,4,45,6,10,19};
int X = 51;
int ans = int.MaxValue;
for(int i=0;i X) {
ans = Math.Min(ans, j-i+1);
break;
}
}
}
Console.WriteLine(ans == int.MaxValue ? 0 : ans);
}
}
Approach 2: Prefix Sum + Binary Search
Idea
Build prefix sum array.
For each index i, find the smallest j such that:
prefix[j] - prefix[i] > X
Time & Space
- Time: O(n log n)
- Space: O(n)
Implementations
C++
#include
using namespace std;
int main() {
vector arr = {1,4,45,6,10,19};
int X = 51, n = arr.size();
vector prefix(n+1,0);
for(int i=0;iJava
import java.util.*;
class SmallestSubarray {
public static void main(String[] args) {
int[] arr = {1,4,45,6,10,19};
int X = 51;
int n = arr.length;
int[] prefix = new int[n+1];
for(int i=0;iPython
import bisect
arr = [1,4,45,6,10,19]
X = 51
prefix = [0]
for x in arr:
prefix.append(prefix[-1] + x)
ans = float('inf')
for i in range(len(arr)):
target = prefix[i] + X + 1
j = bisect.bisect_left(prefix, target)
if j < len(prefix):
ans = min(ans, j - i)
print(0 if ans == float('inf') else ans)
Approach 3: Sliding Window (Optimal)
Idea
Use two pointers because all elements are positive.
Algorithm
- Expand right pointer and add to sum
- While sum > X, shrink from left
- Update minimum length
Time & Space
- Time: O(n)
- Space: O(1)
Implementations (Optimal)
C
#include
#include
int main() {
int arr[] = {1,4,45,6,10,19};
int n = 6, X = 51;
int sum = 0, left = 0, ans = INT_MAX;
for(int right=0;right X) {
ans = ans < right-left+1 ? ans : right-left+1;
sum -= arr[left++];
}
}
printf("%d", ans == INT_MAX ? 0 : ans);
}
C++
#include
using namespace std;
int main() {
int arr[] = {1,4,45,6,10,19};
int n = 6, X = 51;
int sum = 0, l = 0, ans = INT_MAX;
for(int r=0;r X) {
ans = min(ans, r - l + 1);
sum -= arr[l++];
}
}
cout << (ans == INT_MAX ? 0 : ans);
}
Java
class SmallestSubarray {
public static void main(String[] args) {
int[] arr = {1,4,45,6,10,19};
int X = 51;
int sum = 0, left = 0;
int ans = Integer.MAX_VALUE;
for(int right=0;right X) {
ans = Math.min(ans, right - left + 1);
sum -= arr[left++];
}
}
System.out.println(ans == Integer.MAX_VALUE ? 0 : ans);
}
}
Python
arr = [1,4,45,6,10,19]
X = 51
sum = 0
left = 0
ans = float('inf')
for right in range(len(arr)):
sum += arr[right]
while sum > X:
ans = min(ans, right-left+1)
sum -= arr[left]
left += 1
print(0 if ans == float('inf') else ans)
JavaScript
let arr = [1,4,45,6,10,19];
let X = 51;
let sum = 0, left = 0, ans = Infinity;
for(let right=0; right X){
ans = Math.min(ans, right-left+1);
sum -= arr[left++];
}
}
console.log(ans === Infinity ? 0 : ans);
C#
using System;
class Program {
static void Main() {
int[] arr = {1,4,45,6,10,19};
int X = 51;
int sum = 0, left = 0;
int ans = int.MaxValue;
for(int right=0; right X) {
ans = Math.Min(ans, right-left+1);
sum -= arr[left++];
}
}
Console.WriteLine(ans == int.MaxValue ? 0 : ans);
}
}
Summary
- Brute Force: Concept clarity
- Prefix + Binary Search: Mid optimization
- Sliding Window: BEST & INTERVIEW-FAVORITE
- Works only for positive integers
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
