Longest Subarray with Exact Average — Problem Statement & Solution Guide

ArraysMediumPrefix Sum and Hash Map

TimeO(n)

SpaceO(n)

Problem Description

You are provided with a sequence of integers, nums, and a target integer k. Your task is to identify the maximum length of a contiguous subarray such that the arithmetic mean of the elements within that subarray is exactly equal to k. If no such subarray exists, return 0.

The arithmetic mean of a subarray is calculated by dividing the sum of its elements by the number of elements in the subarray. For a subarray of length L with sum S, the condition is S / L == k, which can be algebraically rearranged to S == k * L.

Input consists of the array nums and the integer k. Output is a single integer representing the maximum length of the valid subarray.

DSA Pattern Breakdown

"Longest Subarray with Exact Average"

medium

WHY DOES IT MATTER?

Finding longest subarrays with a specific sum is a foundational pattern that appears in load balancing, financial time‑series analysis, and error‑correction codes. Mastering the prefix‑sum + hashmap technique equips engineers to turn quadratic sliding‑window problems into linear‑time solutions.

OPTIMIZATION CHALLENGE

The key insight is algebraic transformation: converting an average constraint into a zero‑sum condition by subtracting k from every element. This eliminates the need to track lengths explicitly and enables a single pass with a hash map to capture the earliest occurrence of each cumulative sum.

REAL-WORLD CONNECTION

Imagine a distributed logging system where each log entry adds (+1) or subtracts (-1) from a global counter. Detecting the longest period where the counter returns to its original value mirrors the zero‑sum subarray problem, helping identify stable intervals in system metrics.

During an interview, compute the transformed array on the fly (no extra array needed) and update the prefix sum and hashmap in the same loop. Remember to initialize the map with sum 0 at index -1 to handle subarrays that start at index 0.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The condition "average of subarray equals k" can be rewritten as sum(subarray) = k * length(subarray). By subtracting k from every element, we obtain a transformed array where each element is nums[i] - k. In this new array the problem reduces to finding the longest contiguous segment whose sum is exactly zero. The classic solution uses prefix sums: for each index we compute the cumulative sum up to that point and store the earliest index where each distinct sum appears in a hash map. When the same prefix sum reappears at a later index, the elements between those two indices sum to zero, giving a candidate subarray. The longest such distance yields the answer. A naive O(n²) scan enumerates all start‑end pairs and checks the average, which quickly blows up for n up to 10⁵, whereas the prefix‑sum + hashmap technique runs in linear time, making it optimal for large inputs.

Interview Questions on This Problem

Q1How would you modify the solution if the problem asked for the longest subarray whose average is greater than or equal to k?

Transform each element to nums[i] - k and look for the longest subarray with non‑negative sum. This can be solved by maintaining a monotonic decreasing stack of prefix sums to query the farthest earlier prefix that is ≤ current prefix, achieving O(n) time.

Q2Explain why storing only the first occurrence of each prefix sum is sufficient for finding the longest zero‑sum subarray.

The distance between two equal prefix sums equals the length of a zero‑sum subarray. Using the earliest index maximizes this distance for any later occurrence, so later repeats automatically give the longest possible subarray ending at that point.

Q3Can the algorithm be adapted to work with streaming data where the array is not fully known in advance?

Yes. As each new element arrives, update the running prefix sum and check the hashmap for a previous occurrence. The hashmap can be maintained incrementally, allowing O(1) amortized update per element and constant‑time query for the longest subarray seen so far.

Examples

Example 1

Input

nums = [1, 2, 3, 4, 5], k = 3

Output

Explanation: The entire array [1, 2, 3, 4, 5] has a sum of 15 and a length of 5. The average is 15 / 5 = 3, which matches k. Since the whole array is valid, the maximum length is 5.

Example 2

Input

nums = [1, 1, 1, 1], k = 2

Output

Explanation: The sum of any subarray of length L is L (since all elements are 1). The average is L / L = 1. Since 1 != 2 for any L > 0, no valid subarray exists. Return 0.

Example 3

Input

nums = [2, 4, 6, 8], k = 5

Output

Explanation: Check subarrays: - Length 1: Averages are 2, 4, 6, 8. None equal 5. - Length 2: [2,4] avg=3, [4,6] avg=5 (Valid), [6,8] avg=7. - Length 3: [2,4,6] avg=4, [4,6,8] avg=6. - Length 4: [2,4,6,8] avg=5 (Valid). Wait, let's re-evaluate. Sum of [2,4,6,8] is 20. 20/4 = 5. So length 4 is valid. Let's pick a better example where max is not full length. Revised Example 3: Input: nums = [1, 3, 2, 4], k = 2 Output: 2 Explanation: - Subarray [1, 3]: Sum=4, Len=2, Avg=2. Valid. - Subarray [3, 2]: Sum=5, Len=2, Avg=2.5. Invalid. - Subarray [2, 4]: Sum=6, Len=2, Avg=3. Invalid. - Subarray [1, 3, 2]: Sum=6, Len=3, Avg=2. Valid. - Subarray [3, 2, 4]: Sum=9, Len=3, Avg=3. Invalid. - Subarray [1, 3, 2, 4]: Sum=10, Len=4, Avg=2.5. Invalid. Max length is 3.

Example 4

Input

nums = [5, 5, 5, 5], k = 5

Output

Explanation: Every element is 5. Any subarray of length L has sum 5*L and average 5. The longest contiguous subarray is the entire array of length 4.

Example 5

Input

nums = [1, 2, 3, 1, 2, 3], k = 2

Output

Explanation: Sum of entire array = 1+2+3+1+2+3 = 12. Length = 6. Average = 12/6 = 2. This matches k. Thus, the maximum length is 6.

Constraints

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

Optimal Approach & Strategy

Transform the array by subtracting k from each element, then use a hash map to record the earliest index of each prefix sum while scanning once. When a prefix sum repeats, the distance between indices yields a zero‑sum subarray, and we keep the maximum length.

Brute Force Approach

Enumerate every possible start and end index, compute the sum of the subarray, and check if sum/length equals k. This requires O(n²) time and O(1) extra space.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function longestSubarrayWithExactAverage(nums, k) {
    const map = new Map();
    map.set(0, -1); // prefix sum 0 before start
    let prefix = 0;
    let maxLen = 0;
    for (let i = 0; i < nums.length; ++i) {
        prefix += nums[i] - k; // transformed value
        if (map.has(prefix)) {
            maxLen = Math.max(maxLen, i - map.get(prefix));
        } else {
            map.set(prefix, i);
        }
    }
    return maxLen;
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Returns the maximum length of a contiguous subarray with average exactly k.
    int longestSubarrayWithExactAverage(vector<int>& nums, int k) {
        unordered_map<long long, int> firstIdx;
        long long prefix = 0;
        int maxLen = 0;
        firstIdx[0] = -1; // prefix sum 0 occurs before the array starts
        for (int i = 0; i < (int)nums.size(); ++i) {
            prefix += (long long)nums[i] - k; // transform element
            auto it = firstIdx.find(prefix);
            if (it != firstIdx.end()) {
                maxLen = max(maxLen, i - it->second);
            } else {
                firstIdx[prefix] = i;
            }
        }
        return maxLen;
    }
};

import java.util.*;

public class Solution {
    // Returns the maximum length of a contiguous subarray with average exactly k.
    public int longestSubarrayWithExactAverage(int[] nums, int k) {
        Map<Long, Integer> firstIdx = new HashMap<>();
        firstIdx.put(0L, -1); // prefix sum 0 before the array starts
        long prefix = 0;
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix += (long) nums[i] - k; // transformed value
            if (firstIdx.containsKey(prefix)) {
                maxLen = Math.max(maxLen, i - firstIdx.get(prefix));
            } else {
                firstIdx.put(prefix, i);
            }
        }
        return maxLen;
    }
}

class Solution:
    def longestSubarrayWithExactAverage(self, nums: List[int], k: int) -> int:
        """Return the maximum length of a contiguous subarray whose average equals k.
        The problem reduces to finding the longest subarray with sum 0 after
        subtracting k from each element.
        """
        first_idx = {0: -1}  # prefix sum -> earliest index
        prefix = 0
        max_len = 0
        for i, val in enumerate(nums):
            prefix += val - k
            if prefix in first_idx:
                max_len = max(max_len, i - first_idx[prefix])
            else:
                first_idx[prefix] = i
        return max_len

function longestSubarrayWithExactAverage(nums, k) {
    const map = new Map();
    map.set(0, -1); // prefix sum 0 before start
    let prefix = 0;
    let maxLen = 0;
    for (let i = 0; i < nums.length; ++i) {
        prefix += nums[i] - k; // transformed value
        if (map.has(prefix)) {
            maxLen = Math.max(maxLen, i - map.get(prefix));
        } else {
            map.set(prefix, i);
        }
    }
    return maxLen;
}

Asked in Top Tech Interviews

CredSwiggy

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.

Longest Subarray with Exact Average Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Longest Subarray with Exact Average — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor