Longest Subarray with Proportional Sum — Problem Statement & Solution Guide

ArraysMediumPrefix Sums & Monotonic Stack

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Prefix Sums, Monotonic Stack, Coordinate Transformation

TopicArrays

PatternPrefix Sums & Monotonic Stack

TimeO(n)

SpaceO(n)

Problem Description

You are provided with an integer array nums of length n and a positive integer k. Your task is to identify the maximum length L of a contiguous subarray such that the sum of its elements is at least k times its length. Formally, for a subarray nums[i...j] of length L = j - i + 1, the condition is sum(nums[i...j]) >= k * L. If no such subarray exists, return 0.

The input consists of two lines. The first line contains two space-separated integers n and k, where n is the size of the array and k is the proportionality factor. The second line contains n space-separated integers representing the elements of nums.

The output must be a single integer representing the maximum length of a subarray satisfying the condition.

DSA Pattern Breakdown

"Longest Subarray with Proportional Sum"

medium

WHY DOES IT MATTER?

The prefix‑sum + monotonic‑stack pattern transforms a seemingly quadratic subarray problem into a linear one by exploiting order relationships between cumulative sums. It is essential because it guarantees optimal time complexity while keeping the logic intuitive and implementable.

OPTIMIZATION CHALLENGE

The bottleneck in naive solutions is the O(n²) pairwise comparison. The insight that a subarray’s sum can be expressed as a difference of two prefix sums, and that we only need to find the earliest smaller prefix for each position, reduces the problem to a single pass with a monotonic stack.

REAL-WORLD CONNECTION

Consider a server monitoring system that tracks CPU usage per minute. To detect the longest period where average usage stays above a safety threshold, you subtract the threshold from each reading and look for the longest stretch with a non‑negative cumulative deviation—exactly the same algorithmic pattern.

When explaining this to an interviewer, emphasize the transformation step first, then describe the stack construction as a way to keep only promising start indices. Mention that the stack is strictly decreasing in prefix values, which guarantees that popping yields the longest possible subarray ending at the current index.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem reduces to finding the longest subarray whose average is at least a given threshold k. By subtracting k from every element, the condition sum(nums[i…j]) ≥ k·L becomes sum((nums[i] – k) + … + (nums[j] – k)) ≥ 0. Thus we only need the longest subarray with a non‑negative sum in the transformed array. A naive O(n²) scan of all subarrays is infeasible for large n. The optimal solution uses prefix sums and a monotonic stack (or deque). Compute prefix[i] = sum of first i transformed elements. For any pair i < j, the subarray i+1…j has non‑negative sum iff prefix[j] ≥ prefix[i]. We want the maximum j – i satisfying this. By first building a decreasing stack of prefix indices (keeping indices where prefix value is strictly smaller than the previous), we guarantee that for each j we can binary‑search or pop from the stack to find the earliest i with prefix[i] ≤ prefix[j], yielding the longest valid subarray ending at j. This linear‑time, linear‑space algorithm is optimal because any algorithm must at least read all n elements and maintain prefix information.

The key insight is that the problem transforms into a classic “longest subarray with non‑negative sum” which can be solved in O(n) by exploiting the monotonicity of prefix sums. The monotonic stack ensures we only consider candidate start indices that could potentially yield a longer subarray, eliminating redundant comparisons. This pattern is widely applicable in problems involving subarray sums, averages, or differences, making it a valuable tool in a candidate’s algorithmic toolkit.

Interview Questions on This Problem

Q1How would you modify the algorithm if the requirement changed to find the longest subarray with an average strictly greater than k instead of at least k?

Subtract k+ε from each element, where ε is an infinitesimally small positive number, or equivalently, transform the array by subtracting k and then look for a strictly positive sum. In practice, you can treat the condition as sum > 0 and adjust the monotonic stack to require prefix[j] > prefix[i] instead of ≥. The rest of the algorithm remains identical.

Q2A fintech platform needs to detect the longest period where the average transaction amount exceeds a threshold. Which data structure would you use to support real‑time updates to the array while still answering the query efficiently?

Use a segment tree or binary indexed tree to maintain prefix sums dynamically. Each update modifies a single element, and you can query the maximum subarray length by performing a binary search on the segment tree while maintaining a monotonic stack of prefix indices. This allows O(log n) updates and O(n) query time, which is acceptable for moderate n.

Q3During a coding interview at a high‑growth startup, the interviewer asks: "Can you explain why a two‑pointer sliding window approach fails for this problem?"

A sliding window works when the condition is monotonic with respect to window expansion, e.g., sum ≤ k. Here the condition is sum ≥ k·len, which is not monotonic: expanding the window can decrease the average if new elements are below k. Therefore, a simple two‑pointer approach cannot guarantee that once the condition fails it will never hold again, leading to incorrect results.

Examples

Example 1

Input

5 3
1 2 3 4 5

Output

Explanation: The entire array [1, 2, 3, 4, 5] has a sum of 15 and a length of 5. The condition requires sum >= 3 * 5 = 15. Since 15 >= 15, the condition holds. No longer subarray exists, so the answer is 5.

Example 2

Input

4 2
1 1 1 1

Output

Explanation: For any subarray of length L, the sum is L. The condition requires L >= 2 * L, which simplifies to L >= 2L, or 0 >= L. This is only true if L=0. Since we are looking for a non-empty subarray (implied by 'subarray' in standard contexts, but even if empty allowed, max length is 0), no valid non-empty subarray exists. Thus, the answer is 0.

Example 3

Input

6 4
10 1 1 1 1 10

Output

Explanation: The full array [10, 1, 1, 1, 1, 10] has a sum of 24 and a length of 6. The condition requires sum >= 4 * 6 = 24. Since 24 >= 24, the condition holds. The answer is 6.

Example 4

Input

3 5
1 2 3

Output

Explanation: Check all subarrays: - [1]: sum=1, len=1, 1 >= 5*1? No. - [2]: sum=2, len=1, 2 >= 5*1? No. - [3]: sum=3, len=1, 3 >= 5*1? No. - [1,2]: sum=3, len=2, 3 >= 5*2=10? No. - [2,3]: sum=5, len=2, 5 >= 5*2=10? No. - [1,2,3]: sum=6, len=3, 6 >= 5*3=15? No. No subarray satisfies the condition, so the answer is 0.

Constraints

1 <= n <= 10^5
1 <= k <= 10^9
-10^9 <= nums[i] <= 10^9

Optimal Approach & Strategy

Transform the array by subtracting k from each element, compute prefix sums, and use a monotonic decreasing stack to find the longest subarray with non‑negative sum in O(n) time and O(n) space.

Brute Force Approach

Check every possible subarray by nested loops, compute its sum and length, and keep the maximum length where sum ≥ k·len. This takes O(n²) time and O(1) extra space.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

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_len

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;
   }

Asked in Top Tech Interviews

Adobe

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.