mediumArraysPattern: Prefix Sums & Monotonic Stack
Longest Subarray with Proportional Sum Solution
Problem Statement
Given an integer array `nums` and an integer `k`, find the maximum length of a contiguous subarray such that the sum of its elements is at least `k` times its length. Formally, find the maximum value of `j - i + 1` such that: $$\sum_{x=i}^{j} nums[x] \ge k \times (j - i + 1)$$ If no such subarray exists, return `0`.
Examples
Example 1:
Input:nums = [2, 1, 4, 0, 2], k = 2
Output:3
Explanation: The contiguous subarray [4, 0, 2] has a sum of 6 and length of 3. Here, 6 >= 2 * 3 (6 >= 6) is satisfied. Another valid subarray of length 3 is [2, 1, 4] with sum 7 (7 >= 6). No valid subarray of length 4 or 5 exists.
Example 2:
Input:nums = [0, 1, 2], k = 3
Output:0
Explanation: No contiguous subarray satisfies the condition. For example, the subarray [2] has a sum of 2 and length of 1, but 2 < 3 * 1.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- -10^4 <= k <= 10^4
Time: O(N) Space: O(N)
Subtract k from each element of nums to transform the requirement into finding the longest subarray with a sum >= 0. Compute the prefix sums of this transformed array. Build a strictly decreasing monotonic stack of indices of these prefix sums from left to right. Then, iterate from the end of the prefix sum array back to the beginning, greedily popping elements from the stack whenever the current prefix sum is greater than or equal to the prefix sum at the stack's top index to find the maximum width.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
class Solution:
def longestSubarrayProportionalSum(self, nums: list[int], k: int) -> int:
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + (nums[i] - k)
stack = []
for i in range(n + 1):
if not stack or prefix[i] < prefix[stack[-1]]:
stack.append(i)
max_len = 0
for j in range(n, -1, -1):
while stack and prefix[j] >= prefix[stack[-1]]:
max_len = max(max_len, j - stack.pop())
return max_len