mediumArraysPattern: Prefix Sum
Longest Bounded Subarray with One Exclusion Solution
Problem Statement
You are 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.
Examples
Example 1:
Input:nums = [2, 8, 4, 3, 5], limit = 8
Output:3
Explanation: The subarray [8, 4, 3] has a maximum of 8. Excluding it, the sum of the remaining elements is 4 + 3 = 7, which is <= 8. This subarray has length 3.
Example 2:
Input:nums = [10, 2, 10, 5, 1], limit = 6
Output:3
Explanation: The subarray [10, 5, 1] has a maximum of 10. Excluding it, the sum is 5 + 1 = 6, which is <= 6. No longer subarray satisfies the condition.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 0 <= limit <= 10^15
Time: O(N) Space: O(N)
Utilize a sliding window (two-pointer approach) combined with a monotonic deque to track the maximum value within the active window. As the 'right' pointer expands, we push the current index to the deque, maintaining descending order, and add the element to the running sum. If the current sum minus the maximum element (found at the front of the deque) exceeds the limit, we incrementally shrink the window from the 'left' until the constraint is satisfied, updating the maximum valid window size found.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import List
from collections import deque
class Solution:
def longestBoundedSubarray(self, nums: List[int], limit: int) -> int:
left = 0
current_sum = 0
max_deque = deque()
max_len = 0
for right in range(len(nums)):
current_sum += nums[right]
while max_deque and nums[max_deque[-1]] <= nums[right]:
max_deque.pop()
max_deque.append(right)
while max_deque and current_sum - nums[max_deque[0]] > limit:
current_sum -= nums[left]
if max_deque[0] == left:
max_deque.popleft()
left += 1
max_len = max(max_len, right - left + 1)
return max_len