Review the fundamentals: Arrays guide and time complexities.

Alternating Equilibrium Subarrays — Problem Statement & Solution Guide

Q: How can you transform the original problem into a standard subarray‑sum‑zero problem?

Assign +a[i] to even indices and -a[i] to odd indices, then look for subarrays whose signed sum is zero.

Q: Why does counting equal prefix sums give the number of equilibrium subarrays?

If two prefix sums are equal, the elements between them sum to zero, satisfying the equilibrium condition.

Q: What is the time and space complexity of the optimal solution and why?

Both are O(n) because we scan the array once and store at most n+1 distinct prefix sums in a hash map.

ArraysMediumcumulative-array-sum

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Alternating Equilibrium Subarrays problem optimally.

TopicArrays

Patterncumulative-array-sum

TimeO(n)

SpaceO(n)

Problem Description

You are analyzing a sequence of altitude changes recorded by a drone. An interval [l, r] (0-indexed) is considered in 'equilibrium' if the sum of elements at even indices of the original array altitudes within this range (i.e., indices i where l <= i <= r and i is even) is equal to the sum of elements at odd indices of the original array altitudes within this range (i.e., indices i where l <= i <= r and i is odd). Given an integer array altitudes, find the total number of non-empty contiguous subarrays that are in equilibrium.

DSA Pattern Breakdown

"Alternating Equilibrium Subarrays"

medium

WHY DOES IT MATTER?

Detecting balance between two alternating groups appears in many parity‑based analytics.

OPTIMIZATION CHALLENGE

Turning a quadratic scan into a linear hash‑map counting problem cuts runtime dramatically.

REAL-WORLD CONNECTION

It mirrors load‑balancing where even‑indexed servers and odd‑indexed servers must handle equal traffic.

Always pre‑process the array into a signed version; it simplifies reasoning and avoids index‑parity bugs.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The equilibrium condition can be rewritten by assigning a sign to each element based on its original index parity: +a[i] for even i and -a[i] for odd i. The sum of even‑indexed elements equals the sum of odd‑indexed elements inside [l, r] exactly when the signed sum of this transformed array over the same interval is zero. A naive double loop would recompute these sums for every subarray, leading to O(n^2) time, which is prohibitive for n up to 10^5 or more. By computing prefix sums of the signed array and counting how many times each prefix value appears, we reduce the problem to counting pairs of equal prefix sums, which can be done in linear time using a hash map.

This approach follows the classic “subarray sum equals K” paradigm, where K=0. Each prefix sum acts as a state; identical states imply a zero‑sum segment between them. The hash map stores frequencies of each prefix sum encountered so far, allowing us to increment the answer by the current frequency before updating it. The overall algorithm runs in O(n) time and O(n) auxiliary space, handling large inputs efficiently while preserving exact integer arithmetic.

Interview Questions on This Problem

Q1How can you transform the original problem into a standard subarray‑sum‑zero problem?

Assign +a[i] to even indices and -a[i] to odd indices, then look for subarrays whose signed sum is zero.

Q2Why does counting equal prefix sums give the number of equilibrium subarrays?

If two prefix sums are equal, the elements between them sum to zero, satisfying the equilibrium condition.

Q3What is the time and space complexity of the optimal solution and why?

Both are O(n) because we scan the array once and store at most n+1 distinct prefix sums in a hash map.

Examples

Example 1

Input

altitudes = [3, 2, 2, 3]

Output

Explanation: The equilibrium subarrays are: 1. altitudes[0...3] -> [3, 2, 2, 3]: Sum of even indices (0, 2) is 3 + 2 = 5. Sum of odd indices (1, 3) is 2 + 3 = 5. 2. altitudes[1...2] -> [2, 2]: Sum of even indices (2) is 2. Sum of odd indices (1) is 2.

Example 2

Input

altitudes = [1, 1, 1]

Output

Explanation: The equilibrium subarrays are: 1. altitudes[0...1] -> [1, 1]: Sum of even indices (0) is 1. Sum of odd indices (1) is 1. 2. altitudes[1...2] -> [1, 1]: Sum of even indices (2) is 1. Sum of odd indices (1) is 1.

Constraints

1 <= altitudes.length <= 10^5
-10^4 <= altitudes[i] <= 10^4

Optimal Approach & Strategy

Create a signed array, track prefix sums, and use a hash map to count equal prefix values, yielding O(n) time.

Brute Force Approach

Iterate over all O(n^2) subarrays, compute even and odd sums separately, and compare them.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function countEquilibriumSubarrays(altitudes) {
    const freq = new Map();
    let diff = 0; // prefixEven - prefixOdd
    let ans = 0;
    freq.set(0, 1); // empty prefix
    for (let i = 0; i < altitudes.length; ++i) {
        if (i % 2 === 0) diff += altitudes[i];
        else diff -= altitudes[i];
        const prev = freq.get(diff) || 0;
        ans += prev;
        freq.set(diff, prev + 1);
    }
    return ans;
}

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

class Solution {
public:
    long long countEquilibriumSubarrays(const vector<int>& altitudes) {
        unordered_map<long long, long long> freq;
        long long diff = 0; // prefixEven - prefixOdd
        long long ans = 0;
        freq[0] = 1; // empty prefix
        for (size_t i = 0; i < altitudes.size(); ++i) {
            if (i % 2 == 0) diff += altitudes[i];
            else diff -= altitudes[i];
            if (freq.find(diff) != freq.end()) ans += freq[diff];
            ++freq[diff];
        }
        return ans;
    }
};

import java.util.*;

class Solution {
    public long countEquilibriumSubarrays(int[] altitudes) {
        Map<Long, Long> freq = new HashMap<>();
        long diff = 0L; // prefixEven - prefixOdd
        long ans = 0L;
        freq.put(0L, 1L); // empty prefix
        for (int i = 0; i < altitudes.length; ++i) {
            if ((i & 1) == 0) diff += altitudes[i];
            else diff -= altitudes[i];
            long prev = freq.getOrDefault(diff, 0L);
            ans += prev;
            freq.put(diff, prev + 1);
        }
        return ans;
    }
}

from collections import defaultdict

def count_equilibrium_subarrays(altitudes):
    """Return the number of subarrays where the sum of elements at even original indices equals the sum at odd original indices.
    Uses prefix difference technique: diff = sum_even - sum_odd.
    """
    freq = defaultdict(int)
    diff = 0
    ans = 0
    freq[0] = 1  # empty prefix
    for i, val in enumerate(altitudes):
        if i % 2 == 0:
            diff += val
        else:
            diff -= val
        ans += freq[diff]
        freq[diff] += 1
    return ans

function countEquilibriumSubarrays(altitudes) {
    const freq = new Map();
    let diff = 0; // prefixEven - prefixOdd
    let ans = 0;
    freq.set(0, 1); // empty prefix
    for (let i = 0; i < altitudes.length; ++i) {
        if (i % 2 === 0) diff += altitudes[i];
        else diff -= altitudes[i];
        const prev = freq.get(diff) || 0;
        ans += prev;
        freq.set(diff, prev + 1);
    }
    return ans;
}

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.