Review the fundamentals: Arrays guide and time complexities.

The Balanced Emission Period — Problem Statement & Solution Guide

ArraysMediumcumulative-array-sum

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the The Balanced Emission Period problem optimally.

TopicArrays

Patterncumulative-array-sum

TimeO(n)

SpaceO(n)

Problem Description

Given an integer array emissions representing the net carbon units processed by a facility over a sequence of days, and an integer target, determine the length of the longest contiguous subarray where the arithmetic mean of the elements is exactly equal to target.

The arithmetic mean of a subarray emissions[i..j] is defined as the sum of elements in that range divided by the number of elements (j - i + 1). You must find the maximum length L such that there exists a subarray of length L with a sum equal to L * target.

Return the length of this longest subarray. If no such subarray exists, return 0.

DSA Pattern Breakdown

"The Balanced Emission Period"

medium

WHY DOES IT MATTER?

Zero‑sum subarray detection is a core pattern for average‑based and ratio problems.

OPTIMIZATION CHALLENGE

Replacing O(n²) enumeration with a hashmap reduces complexity from quadratic to linear.

REAL-WORLD CONNECTION

It mirrors balancing energy input vs. output over time in smart‑grid monitoring.

Initialize the hashmap with sum 0 at index -1 to correctly handle subarrays starting at index 0.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The average of a subarray equals the target if and only if the sum of the subarray equals target multiplied by its length. By subtracting target from each element we reduce the problem to finding the longest contiguous segment whose transformed sum is zero, which is a classic prefix‑sum + hashmap problem. Naïve enumeration of all O(n²) subarrays quickly exceeds time limits for large n because each sum recomputation is linear. The optimal paradigm leverages prefix sums: as we scan the array we record the first index where each cumulative sum appears; when the same sum reappears, the segment between those indices has zero net sum, giving a candidate length. This yields a linear‑time solution while preserving correctness.

Interview Questions on This Problem

Q1How does subtracting the target from each array element simplify the problem?

It converts the average condition into a zero‑sum condition. The longest subarray with average = target becomes the longest subarray with sum = 0.

Q2Why do we store the earliest index of each prefix sum in a hashmap?

The earliest occurrence maximizes the distance when the same sum reappears later. This distance directly gives the longest possible zero‑sum subarray ending at the current index.

Q3Can this technique be extended to find subarrays with a specific average other than an integer?

Yes, by using rational arithmetic or scaling to avoid floating‑point errors. The same prefix‑sum logic applies after transforming each element by (value * denominator - numerator).

Examples

Example 1

Input

emissions = [1, 2, 3, 4, 5], target = 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 the target. No longer subarray exists. Thus, the answer is 5.

Example 2

Input

emissions = [1, 1, 1, 1, 1], target = 2

Output

Explanation: The sum of any subarray of length L is L. The average is L / L = 1. Since the target is 2, no subarray has an average of 2. Thus, the answer is 0.

Example 3

Input

emissions = [2, 4, 6, 8, 10], target = 6

Output

Explanation: Check subarrays: - Length 1: Averages are 2, 4, 6, 8, 10. [6] matches. - Length 2: Averages are 3, 5, 7, 9. None match. - Length 3: Averages are 4, 6, 8. [4, 6, 8] has sum 18, avg 6. Matches. - Length 4: Averages are 5, 7. None match. - Length 5: Average is 6. [2, 4, 6, 8, 10] has sum 30, avg 6. Matches. Wait, let's re-evaluate. Sum of [2,4,6,8,10] is 30. 30/5 = 6. So length 5 is valid. Let's pick a better example where the full array doesn't work. Revised Input: emissions = [2, 4, 6, 8, 12], target = 6. - Length 5: Sum = 32. Avg = 6.4. No. - Length 4: [2,4,6,8] Sum=20, Avg=5. [4,6,8,12] Sum=30, Avg=7.5. No. - Length 3: [2,4,6] Sum=12, Avg=4. [4,6,8] Sum=18, Avg=6. Match. [6,8,12] Sum=26, Avg=8.66. No. - Length 2: [2,4] Avg=3. [4,6] Avg=5. [6,8] Avg=7. [8,12] Avg=10. No. - Length 1: [6] Avg=6. Match. Longest is 3.

Example 4

Input

emissions = [5, 5, 5, 5], target = 5

Output

Explanation: Every subarray has an average of 5. The longest contiguous subarray is the entire array of length 4.

Constraints

1 <= emissions.length <= 10^5
-10^9 <= emissions[i] <= 10^9
-10^9 <= target <= 10^9

Optimal Approach & Strategy

Transform the array by subtracting target, then use a prefix‑sum hashmap to find the longest zero‑sum subarray in O(n) time.

Brute Force Approach

Check every possible subarray, compute its sum, and verify if sum equals target × length. This requires O(n³) time if sums are recomputed each time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * Returns the length of the longest contiguous subarray whose average equals target.
 * @param {number[]} emissions - array of integers representing daily net carbon units
 * @param {number} target - desired average value
 * @return {number} maximum length of such subarray
 */
function longestBalancedEmissionPeriod(emissions, target) {
    const firstIdx = new Map(); // prefix sum -> earliest index
    firstIdx.set(0, -1);
    let prefix = 0;
    let maxLen = 0;
    for (let i = 0; i < emissions.length; ++i) {
        prefix += emissions[i] - target;
        if (firstIdx.has(prefix)) {
            maxLen = Math.max(maxLen, i - firstIdx.get(prefix));
        } else {
            firstIdx.set(prefix, i);
        }
    }
    return maxLen;
}

module.exports = { longestBalancedEmissionPeriod };

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

class Solution {
public:
    int longestBalancedEmissionPeriod(vector<int>& emissions, int target) {
        unordered_map<long long, int> firstIdx; // prefix sum -> earliest index
        firstIdx.reserve(emissions.size() * 2);
        long long prefix = 0;
        int maxLen = 0;
        firstIdx[0] = -1; // sum of zero before array starts
        for (int i = 0; i < (int)emissions.size(); ++i) {
            // Transform each element by subtracting target
            prefix += (long long)emissions[i] - target;
            if (firstIdx.find(prefix) != firstIdx.end()) {
                maxLen = max(maxLen, i - firstIdx[prefix]);
            } else {
                firstIdx[prefix] = i;
            }
        }
        return maxLen;
    }
};

import java.util.*;

public class Solution {
    /**
     * Returns the length of the longest contiguous subarray whose arithmetic mean equals target.
     * The approach transforms each element by subtracting target and then finds the longest
     * subarray with sum zero using a prefix‑sum hashmap.
     */
    public int longestBalancedEmissionPeriod(int[] emissions, int target) {
        Map<Long, Integer> firstIdx = new HashMap<>();
        firstIdx.put(0L, -1); // prefix sum 0 occurs before the array starts
        long prefix = 0L;
        int maxLen = 0;
        for (int i = 0; i < emissions.length; i++) {
            prefix += (long) emissions[i] - target;
            if (firstIdx.containsKey(prefix)) {
                maxLen = Math.max(maxLen, i - firstIdx.get(prefix));
            } else {
                firstIdx.put(prefix, i);
            }
        }
        return maxLen;
    }
}

def longest_balanced_emission_period(emissions, target):
    """Return the length of the longest contiguous subarray whose average equals target.

    The problem reduces to finding the longest subarray with sum zero after
    subtracting `target` from each element.
    """
    first_idx = {0: -1}  # prefix sum -> earliest index
    prefix = 0
    max_len = 0
    for i, val in enumerate(emissions):
        prefix += val - target
        if prefix in first_idx:
            max_len = max(max_len, i - first_idx[prefix])
        else:
            first_idx[prefix] = i
    return max_len

/**
 * Returns the length of the longest contiguous subarray whose average equals target.
 * @param {number[]} emissions - array of integers representing daily net carbon units
 * @param {number} target - desired average value
 * @return {number} maximum length of such subarray
 */
function longestBalancedEmissionPeriod(emissions, target) {
    const firstIdx = new Map(); // prefix sum -> earliest index
    firstIdx.set(0, -1);
    let prefix = 0;
    let maxLen = 0;
    for (let i = 0; i < emissions.length; ++i) {
        prefix += emissions[i] - target;
        if (firstIdx.has(prefix)) {
            maxLen = Math.max(maxLen, i - firstIdx.get(prefix));
        } else {
            firstIdx.set(prefix, i);
        }
    }
    return maxLen;
}

module.exports = { longestBalancedEmissionPeriod };

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.