3960. Frequency Balance Subarray

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

We define a frequency balance subarray based on the following conditions:

If the subarray contains only one distinct value, then it is frequency balanced.
Otherwise, there must exist a positive integer f such that every distinct value in the subarray occurs either f times or 2 * f times, and both of these frequencies (f and 2 * f) actually appear among the distinct values.

In other words, when there is more than one distinct value, you can pick some positive integer f, and every distinct value's count must be exactly f or exactly 2 * f. On top of that, at least one value must occur f times and at least one value must occur 2 * f times.

Your task is to return an integer representing the length of the longest frequency balance subarray.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Following the described procedure step by step produces the solution.

Open in Flowchart

Intuition

The key observation is that the condition for a frequency balance subarray depends only on how often each value appears within that subarray, not on the order or the actual values themselves. So we need a way to efficiently track frequencies as we look at different subarrays.

Since the array length is small enough, a natural idea is to fix the left endpoint l of the subarray and then extend the right endpoint r one element at a time. As we extend r, we only add one new element each step, so we can maintain the frequency information incrementally instead of recomputing it from scratch.

To check the frequency balance condition quickly, we maintain two hash tables:

cnt: maps each value to how many times it currently appears in the subarray [l, r].
freq: maps each frequency value to how many distinct values currently have that frequency. This is essentially "the frequency of frequencies".

Why is freq useful? Because the condition is entirely about frequencies. When we add a new element x, its count changes from some old value to a new value, so we update freq accordingly: decrease the count for its old frequency and increase the count for its new frequency.

Now, checking whether the current subarray is frequency balanced becomes simple by looking at freq:

If there is only one distinct value in the subarray (len(cnt) == 1), it is automatically balanced.
Otherwise, the subarray is balanced exactly when there are only two distinct frequency values present (len(freq) == 2), and one of them is exactly twice the other. We can verify this by checking, for the new count cnt[x], whether a frequency of cnt[x] * 2 exists, or whether cnt[x] is even and a frequency of cnt[x] // 2 exists.

Whenever the condition holds, we update the answer with the length r - l + 1. By trying every possible left endpoint and extending rightward, we cover all subarrays and capture the longest valid one.

Solution Approach

Solution 1: Enumeration + Hash Table

We enumerate the left endpoint l of the subarray over the range [0, n), and for each l, we extend the right endpoint r from l toward the end of the array. During this process, we use two hash tables to track the frequency information:

cnt: records how many times each element appears in the current subarray [l, r].
freq: records the "frequency of frequencies", i.e., for each frequency value, how many distinct elements have that frequency.

For each new left endpoint l, we reset both cnt and freq to empty, then process each r in order.

When we add element x = nums[r] to the subarray, we update the hash tables in two steps:

Remove the old frequency record. Let the old count of x be cnt[x]. If freq[cnt[x]] exists and is positive, we decrement it by 1, since x will no longer have this frequency. If it drops to 0, we remove the entry from freq to keep the table accurate about which frequencies are present.
Add the new frequency record. We increment cnt[x] by 1, then increment freq[cnt[x]] by 1 to reflect that x now appears cnt[x] times.

After updating, we check whether the current subarray [l, r] is frequency balanced by testing either condition:

len(cnt) == 1: the subarray contains only one distinct value, so it is balanced.
len(freq) == 2 and one frequency is exactly twice the other: we check this for the just-updated count cnt[x] by verifying whether freq[cnt[x] * 2] exists, or whether cnt[x] is even and freq[cnt[x] // 2] exists. Since freq has exactly two distinct frequencies, this confirms one is double the other and both appear.

If either condition holds, we update the answer with ans = max(ans, r - l + 1).

After all enumerations finish, we return ans. The answer is initialized to 1 because any single element is trivially a valid frequency balance subarray.

The time complexity is O(n^2), where n is the length of the array, since we examine every (l, r) pair with O(1) work per step. The space complexity is O(n), used by the two hash tables.

Example Walkthrough

Let's trace through the solution approach using a small example: nums = [1, 1, 2, 2, 2, 2].

We initialize ans = 1 (every single element is trivially balanced).

We fix the left endpoint l and extend the right endpoint r, maintaining cnt (value → count) and freq (count → how many values have that count). Below we focus on the most illustrative starting point, l = 0, resetting both tables to empty before we begin.

Starting with l = 0:

Step r = 0 — add x = 1:

Old count of 1 is 0 (no freq entry to remove).
Increment: cnt = {1: 1}, then freq = {1: 1}.
Check: len(cnt) == 1 → balanced. Length is 0 - 0 + 1 = 1. ans = max(1, 1) = 1.

Step r = 1 — add x = 1:

Old count of 1 is 1. Decrement freq[1]: it drops to 0, so remove it → freq = {}.
Increment: cnt = {1: 2}, then freq = {2: 1}.
Check: len(cnt) == 1 → balanced. Length is 1 - 0 + 1 = 2. ans = max(1, 2) = 2.

Step r = 2 — add x = 2:

Old count of 2 is 0 (nothing to remove).
Increment: cnt = {1: 2, 2: 1}, then freq = {2: 1, 1: 1}.
Check: len(cnt) == 2, so look at freq. There are two distinct frequencies (1 and 2). For the updated count cnt[2] = 1: does freq[1 * 2] = freq[2] exist? Yes. → balanced. (Values 1 appears f*2 = 2 times, value 2 appears f = 1 time.) Length is 2 - 0 + 1 = 3. ans = max(2, 3) = 3.

Step r = 3 — add x = 2:

Old count of 2 is 1. Decrement freq[1] → drops to 0, remove it → freq = {2: 1}.
Increment: cnt = {1: 2, 2: 2}, then freq = {2: 2}.
Check: len(cnt) == 2, but len(freq) == 1 (both values appear 2 times). The condition needs two distinct frequencies with one double the other. For cnt[2] = 2: freq[4]? No. freq[1]? No. → not balanced.

Step r = 4 — add x = 2:

Old count of 2 is 2. Decrement freq[2] → drops to 1 → freq = {2: 1}.
Increment: cnt = {1: 2, 2: 3}, then freq = {2: 1, 3: 1}.
Check: len(cnt) == 2, two frequencies (2 and 3). For cnt[2] = 3: freq[6]? No. 3 is odd, so skip the half check. → not balanced (3 is not double of 2, nor is 2 double of 3).

Step r = 5 — add x = 2:

Old count of 2 is 3. Decrement freq[3] → drops to 0, remove it → freq = {2: 1}.
Increment: cnt = {1: 2, 2: 4}, then freq = {2: 1, 4: 1}.
Check: len(cnt) == 2, two frequencies (2 and 4). For cnt[2] = 4: freq[8]? No. 4 is even, so does freq[4 // 2] = freq[2] exist? Yes. → balanced. (Value 1 appears f = 2 times, value 2 appears f*2 = 4 times.) Length is 5 - 0 + 1 = 6. ans = max(3, 6) = 6.

Other left endpoints: Continuing with l = 1, 2, ... (each resetting the tables) explores shorter subarrays. None of them can exceed length 6, since 6 already spans the entire array.

Result: The longest frequency balance subarray is the whole array [1, 1, 2, 2, 2, 2], where 1 occurs f = 2 times and 2 occurs 2 * f = 4 times. The function returns ans = 6.

Solution Implementation

1from collections import Counter
2from typing import List
3
4
5class Solution:
6    def getLength(self, nums: List[int]) -> int:
7        n = len(nums)
8        ans = 1
9
10        # Try every possible left endpoint of the subarray.
11        for left in range(n):
12            # count[value] -> how many times "value" appears in the window
13            count = Counter()
14            # freq_of_count[c] -> how many distinct values currently have count == c
15            freq_of_count = Counter()
16
17            # Extend the window to the right one element at a time.
18            for right in range(left, n):
19                value = nums[right]
20                old_count = count[value]
21
22                # Remove the bookkeeping for this value's previous count,
23                # since its count is about to change.
24                if freq_of_count[old_count]:
25                    freq_of_count[old_count] -= 1
26                    if freq_of_count[old_count] == 0:
27                        freq_of_count.pop(old_count)
28
29                # Increase the value's count and record the new count.
30                count[value] += 1
31                new_count = count[value]
32                freq_of_count[new_count] += 1
33
34                # The window is valid when:
35                # 1) Every element is the same (only one distinct value), OR
36                # 2) There are exactly two distinct count values, and one of
37                #    them is exactly double the other relative to this element's
38                #    new count:
39                #    - a count of (new_count * 2) exists, or
40                #    - new_count is even and a count of (new_count // 2) exists.
41                if (len(count) == 1) or (
42                    len(freq_of_count) == 2
43                    and (
44                        freq_of_count[new_count * 2]
45                        or (new_count % 2 == 0 and freq_of_count[new_count // 2])
46                    )
47                ):
48                    ans = max(ans, right - left + 1)
49
50        return ans
51

1class Solution {
2    public int getLength(int[] nums) {
3        int n = nums.length;
4        // ans holds the length of the longest valid subarray found so far.
5        int ans = 1;
6
7        // Enumerate every possible left endpoint of the subarray.
8        for (int left = 0; left < n; left++) {
9            // count: maps each value to how many times it appears in nums[left..right].
10            Map<Integer, Integer> count = new HashMap<>();
11            // freqOfCount: maps a "number of occurrences" to how many distinct
12            // values currently have exactly that many occurrences.
13            Map<Integer, Integer> freqOfCount = new HashMap<>();
14
15            // Extend the right endpoint one element at a time.
16            for (int right = left; right < n; right++) {
17                int value = nums[right];
18
19                // Current occurrence count of `value` before adding nums[right].
20                int oldCount = count.getOrDefault(value, 0);
21
22                // Remove the old occurrence count from the frequency-of-counts map,
23                // since `value`'s count is about to change.
24                if (freqOfCount.getOrDefault(oldCount, 0) > 0) {
25                    freqOfCount.put(oldCount, freqOfCount.get(oldCount) - 1);
26                    // Clean up zero entries to keep freqOfCount.size() accurate.
27                    if (freqOfCount.get(oldCount) == 0) {
28                        freqOfCount.remove(oldCount);
29                    }
30                }
31
32                // Increment the occurrence count of `value`.
33                count.put(value, oldCount + 1);
34
35                // Register the new occurrence count in the frequency-of-counts map.
36                int newCount = count.get(value);
37                freqOfCount.merge(newCount, 1, Integer::sum);
38
39                // Validity check for the current window nums[left..right]:
40                //   (a) Only one distinct value exists, OR
41                //   (b) Exactly two distinct occurrence counts exist, and the
42                //       updated element's count `newCount` relates to the other
43                //       count by a factor of 2 — either there is a group with
44                //       count == newCount * 2, or newCount is even and there is
45                //       a group with count == newCount / 2.
46                if (count.size() == 1
47                        || (freqOfCount.size() == 2
48                            && (freqOfCount.getOrDefault(newCount * 2, 0) > 0
49                                || (newCount % 2 == 0
50                                    && freqOfCount.getOrDefault(newCount / 2, 0) > 0)))) {
51                    ans = Math.max(ans, right - left + 1);
52                }
53            }
54        }
55
56        return ans;
57    }
58}
59

1class Solution {
2public:
3    int getLength(vector<int>& nums) {
4        int n = nums.size();
5        int ans = 1;
6
7        // Enumerate every possible left endpoint of the subarray
8        for (int left = 0; left < n; ++left) {
9            // count: maps each value to how many times it appears in the current window
10            unordered_map<int, int> count;
11            // freq: maps an occurrence-count to how many distinct values have that count
12            // (i.e. freq[k] = number of values whose frequency in the window is exactly k)
13            unordered_map<int, int> freq;
14
15            // Extend the right endpoint of the subarray one element at a time
16            for (int right = left; right < n; ++right) {
17                int value = nums[right];
18                int oldCount = count[value];
19
20                // The value previously appeared oldCount times, so before updating,
21                // remove its contribution from the freq map
22                if (freq.contains(oldCount)) {
23                    if (--freq[oldCount] == 0) {
24                        freq.erase(oldCount);
25                    }
26                }
27
28                // Add one more occurrence of the current value
29                ++count[value];
30                // Register the new occurrence-count in the freq map
31                ++freq[count[value]];
32
33                int newCount = count[value];
34
35                // A window is valid if either:
36                //   1. It contains only a single distinct value (count.size() == 1), or
37                //   2. There are exactly two distinct occurrence-counts (freq.size() == 2)
38                //      and one count is exactly double the other:
39                //         - some value has count newCount * 2, or
40                //         - newCount is even and some value has count newCount / 2.
41                if (count.size() == 1 ||
42                    (freq.size() == 2 &&
43                     (freq.contains(newCount * 2) ||
44                      (newCount % 2 == 0 && freq.contains(newCount / 2))))) {
45                    // Update the answer with the length of the current valid window
46                    ans = max(ans, right - left + 1);
47                }
48            }
49        }
50
51        return ans;
52    }
53};
54

1/**
2 * Finds the length of the longest contiguous subarray whose element
3 * frequency distribution is "balanced":
4 *   - either every element in the window is the same value, or
5 *   - there are exactly two distinct frequency values where one is
6 *     double the other (e.g. some elements appear k times, others 2k times).
7 *
8 * @param nums - the input array of numbers
9 * @returns the maximum length of a valid subarray
10 */
11function getLength(nums: number[]): number {
12    const length = nums.length;
13    let answer = 1;
14
15    // Try every possible left endpoint of the subarray.
16    for (let left = 0; left < length; left++) {
17        // valueCount: maps an element value -> its occurrence count in [left, right].
18        const valueCount = new Map<number, number>();
19        // freqCount: maps a count value -> how many distinct elements have that count.
20        const freqCount = new Map<number, number>();
21
22        // Extend the right endpoint one step at a time.
23        for (let right = left; right < length; right++) {
24            const value = nums[right];
25            const prevCount = valueCount.get(value) ?? 0;
26
27            // The element's old count (prevCount) is about to change,
28            // so remove its contribution from freqCount.
29            if ((freqCount.get(prevCount) ?? 0) > 0) {
30                const remaining = (freqCount.get(prevCount) ?? 0) - 1;
31                if (remaining === 0) {
32                    freqCount.delete(prevCount);
33                } else {
34                    freqCount.set(prevCount, remaining);
35                }
36            }
37
38            // Increment the element's count and record the new count in freqCount.
39            valueCount.set(value, prevCount + 1);
40            const newCount = prevCount + 1;
41            freqCount.set(newCount, (freqCount.get(newCount) ?? 0) + 1);
42
43            // Check whether the current window [left, right] is balanced.
44            const isSingleValue = valueCount.size === 1;
45            const hasTwoFreqs = freqCount.size === 2;
46            const hasDoubleFreq = (freqCount.get(newCount * 2) ?? 0) > 0;
47            const hasHalfFreq =
48                newCount % 2 === 0 && (freqCount.get(newCount / 2) ?? 0) > 0;
49
50            if (
51                isSingleValue ||
52                (hasTwoFreqs && (hasDoubleFreq || hasHalfFreq))
53            ) {
54                answer = Math.max(answer, right - left + 1);
55            }
56        }
57    }
58
59    return answer;
60}
61

Time and Space Complexity

Time Complexity

The code uses two nested loops: the outer loop iterates over the left boundary l from 0 to n-1, and the inner loop iterates over the right boundary r from l to n-1. This gives a total of O(n^2) iterations.

Within the inner loop, all operations are performed on the Counter objects (cnt and freq), including lookups, increments, decrements, and conditional checks. Each of these operations takes O(1) time on average. The len() calls on the counters are also O(1).

Therefore, the overall time complexity is O(n^2), where n is the length of the array nums.

Space Complexity

The algorithm maintains two Counter objects:

cnt: stores the frequency of each distinct value within the current subarray nums[l..r]. In the worst case, all elements are distinct, so cnt can hold up to O(n) entries.
freq: stores the count of how many distinct values share the same frequency. In the worst case, this can also hold up to O(n) entries.

Both counters are reset for each iteration of the outer loop, but at any given time their combined size is bounded by O(n).

Therefore, the overall space complexity is O(n), where n is the length of the array nums.

Common Pitfalls

Pitfall 1: Using Default `Counter` Access That Silently Creates Zero Entries

The most subtle bug in this kind of solution comes from how Python's Counter (and defaultdict) behaves on read access. When you write freq_of_count[old_count] in the condition check, even just to test a value, Python inserts a new key with value 0 if it didn't already exist.

For example, when old_count == 0 (a value being seen for the first time), the line:

if freq_of_count[old_count]:

reads freq_of_count[0], which creates the entry 0: 0 in the table. Now len(freq_of_count) is polluted by a phantom key, and your len(freq_of_count) == 2 check will be wrong.

Why the given code is actually safe: It guards the decrement with if freq_of_count[old_count]: but then immediately pops any entry that hits 0. The read of freq_of_count[0] does create the 0 key, but since its value is falsy, the body is skipped, and the key lingers — which would corrupt len(freq_of_count). This is a real latent risk.

Solution: Use explicit membership testing or .get() so reads never mutate the table, and never let a zero-count key survive:

# Safe: read without inserting
if freq_of_count.get(old_count, 0) > 0:
    freq_of_count[old_count] -= 1
    if freq_of_count[old_count] == 0:
        del freq_of_count[old_count]

# Safe membership test for the doubling check
if (len(count) == 1) or (
    len(freq_of_count) == 2
    and (
        (new_count * 2) in freq_of_count
        or (new_count % 2 == 0 and (new_count // 2) in freq_of_count)
    )
):
    ans = max(ans, right - left + 1)

Using in and .get() keeps len(freq_of_count) reflecting only the frequencies that genuinely appear.

Pitfall 2: Misinterpreting "Both Frequencies Must Appear"

The condition requires that both f and 2*f actually occur among the distinct values — it is not enough that every count is either f or 2*f. A common mistake is to accept a window where all distinct values share the same count (e.g., every value appears exactly f times with more than one distinct value).

In that case len(freq_of_count) == 1 with len(count) > 1, which is not balanced. The code correctly handles this because it strictly requires len(freq_of_count) == 2. If you relax this to len(freq_of_count) <= 2, you would wrongly accept uniform-frequency windows with multiple distinct values.

Pitfall 3: Wrong Initialization of the Answer

The answer must start at 1, not 0. Any single element is trivially frequency balanced (one distinct value). If you initialize ans = 0 and the input has length n >= 1, the loop still updates it via the len(count) == 1 branch — but relying on that is fragile. For robustness, initialize ans = 1 (or 0 only when handling a possibly empty array). Note that for an empty array the loops never run, so the returned 1 would be incorrect; guard with:

if n == 0:
    return 0

Pitfall 4: Assuming the Doubling Check Covers All Pairs

Because the code only inspects new_count (the count of the element just added), one might worry it misses valid configurations. It works only because len(freq_of_count) == 2 guarantees exactly two distinct frequencies exist. Since the just-updated element holds one of them (new_count), checking whether 2*new_count or new_count//2 is the other frequency is sufficient. If you ever try to generalize this to allow more than two distinct frequencies, this localized check breaks and you must compare the two frequency keys directly.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know