Longest Subarray with Proportional Sum — Problem Statement & Solution Guide
Problem Description
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.
Examples
Input
[1, 2, 3, 4, 5], 5
Output
3
Explanation: Step-by-step: with input [1, 2, 3, 4, 5], k = 5, we initialize a variable to store the maximum length and a variable to store the current sum. We iterate through the array, updating the current sum and checking if it's at least k times the current length. If it is, we update the maximum length. Finally, we return the maximum length.
Input
[1, 1, 1, 1, 1], 3
Output
3
Explanation: Step-by-step: with input [1, 1, 1, 1, 1], k = 3, we initialize a variable to store the maximum length and a variable to store the current sum. We iterate through the array, updating the current sum and checking if it's at least k times the current length. If it is, we update the maximum length. Finally, we return the maximum length.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- -10^4 <= k <= 10^4
Optimal Approach & Strategy
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.
Brute Force Approach
Generate all possible contiguous subarrays of the given array. For each subarray, compute its sum and check if it is at least k times its length. Track the maximum length of any subarray that satisfies this condition. Since there are O(N^2) subarrays and calculating each takes O(1) time using prefix sums, the total time complexity is O(N^2).
Verified Code Solutions
function solution(nums, k) {
let maxLen = 0;
let currSum = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum >= k * (right - left + 1)) {
maxLen = Math.max(maxLen, right - left + 1);
currSum -= nums[left++];
}
}
return maxLen;
}class Solution {
public:
int solution(vector<int>& nums, int k) {
int maxLen = 0;
int currSum = 0;
int left = 0;
for (int right = 0; right < nums.size(); right++) {
currSum += nums[right];
while (currSum >= k * (right - left + 1)) {
maxLen = max(maxLen, right - left + 1);
currSum -= nums[left++];
}
}
return maxLen;
}
};class Solution {
public int solution(int[] nums, int k) {
int maxLen = 0;
int currSum = 0;
int left = 0;
for (int right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum >= k * (right - left + 1)) {
maxLen = Math.max(maxLen, right - left + 1);
currSum -= nums[left++];
}
}
return maxLen;
}
}def solution(nums, k):
max_len = 0
curr_sum = 0
left = 0
for right in range(len(nums)):
curr_sum += nums[right]
while curr_sum >= k * (right - left + 1):
max_len = max(max_len, right - left + 1)
curr_sum -= nums[left]
left += 1
return max_lenfunction solution(nums, k) {
let maxLen = 0;
let currSum = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum >= k * (right - left + 1)) {
maxLen = Math.max(maxLen, right - left + 1);
currSum -= nums[left++];
}
}
return maxLen;
}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.