Longest Bounded Subarray with One Exclusion — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Cumulative sum for range queries
O(n)O(n)Problem Description
Given an array of positive integers nums and an integer limit, find the maximum length of a contiguous subarray such that the sum of its elements, after excluding exactly one occurrence of the maximum element in that subarray, is less than or equal to limit. If a subarray has a length of 1, its sum after excluding its only element is considered to be 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Longest Bounded Subarray with One Exclusion"
WHY DOES IT MATTER?
This pattern blends sliding‑window mechanics with a monotonic queue, a staple for problems that need real‑time extremum queries over a moving range. Mastery of this combination unlocks efficient solutions for a wide class of “window‑bounded” constraints, which appear frequently in performance‑critical code.
OPTIMIZATION CHALLENGE
The key insight is that the maximum of a sliding window can be maintained in O(1) amortized time by discarding elements that are smaller than the incoming element, because they can never become the maximum while they remain behind a larger element in the queue.
REAL-WORLD CONNECTION
Think of a network router that monitors a sliding time window of packet sizes and must drop the largest packet if the total bandwidth usage exceeds a threshold. The router continuously adds new packets, removes old ones, and instantly knows the current largest packet using a monotonic queue, mirroring the algorithm’s core idea.
When coding, keep the deque clean: always pop from the back while the new element is larger, and pop from the front when the left pointer moves past the deque’s front element. This tiny detail prevents stale values and guarantees correctness.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem asks for the longest contiguous segment whose total sum, after removing exactly one occurrence of the segment’s maximum value, does not exceed a given limit. A naïve solution would enumerate every possible subarray, compute its sum and maximum, adjust the sum, and compare to the limit – an O(n^2) or O(n^3) approach that quickly becomes infeasible for n up to 10^5. The optimal paradigm combines a sliding‑window (two‑pointer) technique with a data structure that can retrieve and update the current window’s maximum in O(1) amortized time. By keeping a running sum of the window and a monotonic decreasing deque that stores candidate maximums, we can test the condition sum‑max ≤ limit in constant time. When the condition is violated, we advance the left pointer, subtract the outgoing element from the sum, and purge it from the deque if it was the stored maximum. This yields a linear scan of the array while dynamically maintaining the required statistics, achieving O(n) time and O(n) auxiliary space.
Interview Questions on This Problem
Q1How would you modify the solution if the problem required excluding the *minimum* element instead of the maximum?
Replace the decreasing deque with an increasing deque to track the window’s minimum. The rest of the sliding‑window logic stays the same: maintain the sum, and ensure sum‑min ≤ limit while expanding or shrinking the window.
Q2Can the algorithm be adapted to handle negative numbers in the array while still excluding exactly one maximum?
Yes, but the monotonic deque must now handle the possibility that the maximum can be negative; the sliding‑window condition remains sum‑max ≤ limit. However, because negative numbers can increase the window length without violating the limit, we must be careful when shrinking: we only move the left pointer when the condition fails, not based on sign.
Q3What is the time‑space trade‑off if you replace the deque with a balanced binary search tree (e.g., multiset) to maintain the maximum?
A balanced BST gives O(log n) insert, delete, and max‑query operations, increasing the overall time to O(n log n) while still using O(n) space. The deque is preferable because it provides O(1) amortized operations for the monotonic property, yielding a linear solution.
Examples
Input
[1, 2, 3, 4, 5], 10
Output
4
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] and limit 10, we first find the maximum element in the subarray, which is 5. Then, we exclude 5 from the subarray and calculate the sum of the remaining elements, which is 1 + 2 + 3 + 4 = 10. Since the sum is less than or equal to the limit, we return the length of the subarray, which is 4.
Input
[1, 2, 3, 4, 5], 5
Output
3
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] and limit 5, we first find the maximum element in the subarray, which is 5. Then, we exclude 5 from the subarray and calculate the sum of the remaining elements, which is 1 + 2 + 3 + 4 = 10. Since the sum is greater than the limit, we try excluding the next maximum element, which is 4. The sum of the remaining elements is 1 + 2 + 3 = 6, which is still greater than the limit. We continue this process until we find a subarray with a sum less than or equal to the limit. In this case, we exclude 4 and get a sum of 1 + 2 + 3 = 6, which is still greater than the limit. We then exclude 3 and get a sum of 1 + 2 + 4 = 7, which is still greater than the limit. Finally, we exclude 2 and get a sum of 1 + 3 + 4 = 8, which is still greater than the limit. We then exclude 1 and get a sum of 3 + 4 = 7, which is still greater than the limit. We then exclude 3 and get a sum of 1 + 4 = 5, which is less than or equal to the limit. Therefore, we return the length of the subarray, which is 3.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 0 <= limit <= 10^15
Optimal Approach & Strategy
Use a sliding window with a running sum and a monotonic decreasing deque to obtain the current maximum in O(1), adjusting the left pointer only when the condition fails.
Brute Force Approach
Enumerate every subarray, compute its sum and maximum, subtract the maximum, and check against the limit, updating the best length.
Code Solutions
function solution(nums, limit) {
let max = -Infinity;
let sum = 0;
let maxLength = 0;
for (let i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
sum += nums[i];
if (sum > limit) {
sum -= max;
max = -Infinity;
} else {
maxLength = Math.max(maxLength, i + 1);
}
}
return maxLength;
}class Solution {
public:
int solution(vector<int>& nums, int limit) {
int max = INT_MIN;
int sum = 0;
int maxLength = 0;
for (int i = 0; i < nums.size(); i++) {
max = max(max, nums[i]);
sum += nums[i];
if (sum > limit) {
sum -= max;
max = INT_MIN;
} else {
maxLength = max(maxLength, i + 1);
}
}
return maxLength;
}
};class Solution {
public int solution(int[] nums, int limit) {
int max = Integer.MIN_VALUE;
int sum = 0;
int maxLength = 0;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
sum += nums[i];
if (sum > limit) {
sum -= max;
max = Integer.MIN_VALUE;
} else {
maxLength = Math.max(maxLength, i + 1);
}
}
return maxLength;
}
}def solution(nums, limit):
max_val = float('-inf')
current_sum = 0
max_length = 0
for num in nums:
max_val = max(max_val, num)
current_sum += num
if current_sum > limit:
current_sum -= max_val
max_val = float('-inf')
else:
max_length = max(max_length, len(nums[:nums.index(num) + 1]))
return max_lengthfunction solution(nums, limit) {
let max = -Infinity;
let sum = 0;
let maxLength = 0;
for (let i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
sum += nums[i];
if (sum > limit) {
sum -= max;
max = -Infinity;
} else {
maxLength = Math.max(maxLength, i + 1);
}
}
return maxLength;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.