Longest Subarray with Average ≥ k: O(n) Prefix-Sum Solution

Finding the longest subarray with average at least k reduces, after one algebraic transformation, to finding the longest subarray with non-negative sum.

That transformation is the core insight. Once you see it, the rest is a standard prefix-sum problem solvable in O(n) time with a monotonic stack. Miss it, and you’re stuck with O(n²) brute force.

Problem Statement and Examples

Given an array of integers and a threshold k, find the length of the longest contiguous subarray whose average is greater than or equal to k. If no such subarray exists, return 0.

Example 1

• Input: arr = [-2, 1, 6, -3], k = 3
• The subarray [1, 6] has average (1 + 6) / 2 = 3.5, which is >= 3
• Output: 2

Example 2

• Input: arr = [5, 5, 5, 5], k = 5
• Every element equals k, so the entire array qualifies
• Output: 4

Example 3

• Input: arr = [1, 2, 1], k = 10
• No subarray has average >= 10
• Output: 0

The Key Transformation: Average to Sum

The direct approach of computing averages for every subarray is slow. A cleaner path exists.

Start with the condition for a subarray a[l..r] (inclusive indices):

• Average condition: sum(a[l..r]) / (r - l + 1) >= k

Multiply both sides by (r - l + 1):

• sum(a[l..r]) >= k * (r - l + 1)

Rewrite the right side:

• sum(a[l..r]) >= sum of k repeated (r - l + 1) times

Rearrange:

• sum(a[l..r]) - k * (r - l + 1) >= 0
• sum(a[i] - k for i in l..r) >= 0

Define a transformed array b[i] = a[i] - k. The condition becomes:

• sum(b[l..r]) >= 0

The problem is now: find the longest subarray of b with non-negative sum. This formulation admits efficient solutions.

Brute-Force Approach: O(n²)

Check every subarray, compute its sum, verify the condition.

// C++ brute force O(n squared)
int longestSubarrayBruteForce(vector<int>& arr, int k) {
    int n = arr.size();
    int maxLen = 0;

    for (int l = 0; l < n; l++) {
        int sum = 0;
        for (int r = l; r < n; r++) {
            sum += arr[r];
            int len = r - l + 1;
            if (sum >= (long long)k * len) {
                maxLen = max(maxLen, len);
            }
        }
    }
    return maxLen;
}

# Python brute force O(n squared)
def longest_subarray_brute_force(arr, k):
    n = len(arr)
    max_len = 0

    for l in range(n):
        total = 0
        for r in range(l, n):
            total += arr[r]
            length = r - l + 1
            if total >= k * length:
                max_len = max(max_len, length)

    return max_len

• Time: O(n²) from nested loops
• Space: O(1)

This works for small inputs but does not scale to competitive-programming constraints (n up to 10⁵).

Efficient Approach: Prefix Sum and Monotonic Stack

The transformed problem (longest subarray with sum >= 0) has a well-known solution using prefix sums and a monotonic stack.

Step 1: Build the Transformed Array and Prefix Sums

Create b[i] = a[i] - k. Then compute prefix sums:

• P[0] = 0
• P[i] = P[i-1] + b[i-1] for i = 1..n

The sum of b[l..r] equals P[r+1] - P[l]. We need P[r+1] - P[l] >= 0, or equivalently P[r+1] >= P[l].

Step 2: Build a Monotonic Decreasing Stack

Traverse P[0..n] from left to right. Maintain a stack of indices where the prefix values are strictly decreasing. If P[i] is not smaller than the top of the stack, skip it. This stack contains all candidate left endpoints.

Why decreasing? For any valid right endpoint j, we want the smallest index i such that P[i] <= P[j]. A larger prefix sum at an earlier index is never useful as a left endpoint, because a later index with a smaller prefix value produces a longer subarray.

Step 3: Right-to-Left Traversal

Traverse from P[n] down to P[0]. For each j, while the stack is non-empty and P[stack.top()] <= P[j], we have a valid subarray from stack.top() to j-1. Record the length and pop. Continue popping while the condition holds.

Each index enters and exits the stack at most once, so the total work is O(n).

Implementation

// C++ O(n) using prefix sum + monotonic stack
#include <vector>
#include <algorithm>
using namespace std;

int longestSubarrayAverage(vector<int>& arr, int k) {
    int n = arr.size();
    if (n == 0) return 0;

    // Build prefix sums of (arr[i] - k)
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + (arr[i] - k);
    }

    // Build monotonic decreasing stack of indices (left to right)
    // Using vector for random access during traversal
    vector<int> stk;
    for (int i = 0; i <= n; i++) {
        if (stk.empty() || prefix[i] < prefix[stk.back()]) {
            stk.push_back(i);
        }
    }

    // Traverse prefix array from right to left
    int maxLen = 0;
    int idx = (int)stk.size() - 1;

    for (int j = n; j >= 0 && idx >= 0; j--) {
        while (idx >= 0 && prefix[stk[idx]] <= prefix[j]) {
            maxLen = max(maxLen, j - stk[idx]);
            idx--;
        }
    }

    return maxLen;
}

# Python O(n) using prefix sum + monotonic stack
def longest_subarray_average(arr, k):
    n = len(arr)
    if n == 0:
        return 0

    # Build prefix sums of (arr[i] - k)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + (arr[i] - k)

    # Build monotonic decreasing stack of indices
    stack = []
    for i in range(n + 1):
        if not stack or prefix[i] < prefix[stack[-1]]:
            stack.append(i)

    # Traverse from right to left
    max_len = 0
    idx = len(stack) - 1

    for j in range(n, -1, -1):
        while idx >= 0 and prefix[stack[idx]] <= prefix[j]:
            max_len = max(max_len, j - stack[idx])
            idx -= 1

    return max_len


# Test cases
print(longest_subarray_average([-2, 1, 6, -3], 3))  # Output: 2
print(longest_subarray_average([5, 5, 5, 5], 5))    # Output: 4
print(longest_subarray_average([1, 2, 1], 10))      # Output: 0

Dry Run on Example 1

Trace through arr = [-2, 1, 6, -3], k = 3:

• Transformed array b: [-5, -2, 3, -6]
• Prefix sums P: [0, -5, -7, -4, -10]
• Build stack (push only if prefix value is smaller than top):
  • i=0: push 0 (P=0). Stack: [0]
  • i=1: P=-5 < 0, push 1. Stack: [0, 1]
  • i=2: P=-7 < -5, push 2. Stack: [0, 1, 2]
  • i=3: P=-4, not < -7, skip
  • i=4: P=-10 < -7, push 4. Stack: [0, 1, 2, 4]
• Right-to-left traversal (idx starts at 3, pointing to stack[3]=4):
  • j=4: P[4]=-10 <= P[4]=-10, length 4-4=0. Pop, idx=2
  • j=3: P[2]=-7 <= P[3]=-4, length 3-2=1. Pop, idx=1. Then P[1]=-5 <= P[3]=-4, length 3-1=2. Pop, idx=0
  • j=2 down to 0: P[0]=0 is never <= P[j] for these j values
• Result: maxLen = 2 (subarray indices 1 to 2, which is [1, 6] in the original array)

Why the Stack Works

The monotonic stack pattern appears in many subarray problems. Here, it ensures that:

• Every potential left endpoint is considered exactly once
• Endpoints with larger prefix values at earlier indices are discarded, because they can never produce a longer valid subarray than a later index with a smaller prefix value
• The right-to-left traversal pairs each right endpoint with the best available left endpoint

Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute force	O(n²)	O(1)
Prefix sum + monotonic stack	O(n)	O(n)

• Brute force examines up to n²/2 subarrays
• Prefix-sum approach makes two linear passes (one to build the stack, one to traverse right-to-left), touching each index at most twice
• Stack operations are amortised O(1) because each index is pushed and popped at most once

Common Pitfalls and Edge Cases

Four mistakes show up repeatedly when candidates first attempt this problem in a coding round.

The first is forgetting to subtract k. Many submissions try to slide a window across the original array and compute averages on the fly. Sliding window does not work cleanly here because the transformed array can hold negative values, and shrinking from the left can break monotonicity. The transformation step is what unlocks the linear-time solution; skipping it forces you back to the O(n²) baseline.

The second is mixing up the direction of stack traversal. Some implementations build the stack right-to-left and traverse left-to-right. The result is the same in spirit, but the inequality direction flips and most candidates lose marks for off-by-one errors during the comparison. Pick one convention (build left-to-right with strictly decreasing prefix values, traverse right-to-left, pop while the top is at most the current prefix) and stay with it.

The third is integer overflow on large inputs. When n approaches 10^5 and elements approach 10^4 in magnitude, the prefix sum can exceed the range of a 32-bit signed integer. Use long long in C++ and Python’s arbitrary-precision integers handle this automatically. Forgetting the cast inside the brute-force comparison sum >= (long long)k * len is a classic silent failure on hidden test cases.

The fourth is mishandling the empty-result case. When every element is below k, the answer is 0, not -1 or some sentinel. The algorithm above returns 0 correctly because maxLen is initialised to 0 and never updated. If you change the initialisation, document the expected behaviour at the top of the function.

Practicing DSA for Placement Tests

Array problems with prefix sums and monotonic stacks appear frequently in placement coding assessments. TCS CodeVita, Infosys HackWithInfy, and Wipro Elite NTH all include problems that test these patterns. Recognising the transformation from a complex condition to a simpler equivalent is often the difference between a working solution and a time-out.

The transformation step in this problem (subtracting k from every element to convert an average condition into a sum condition) is the kind of reasoning that separates memorised templates from actual fluency. TinkerLLM lets you practice that decomposition step-by-step with AI feedback at ₹299 for the launch subscription. For a broader preparation plan, see recommended DSA preparation resources.