Skip to main content
Talentd

Frequency Balance Subarray - Solution & Explanation

MediumArrayHash TableCounting9 min readAsked at: Meta
Practice this problem

Problem Statement

You are given an integer array ​​​​​​​nums.

Define a frequency balance subarray as follows:

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

Return an integer denoting the length of the longest frequency balance subarray.

 

Example 1:

Input: nums = [1,2,2,1,2,3,3,3]

Output: 5

Explanation:

  • The longest frequency balance subarray is [2, 1, 2, 3, 3].
  • The elements that appear most frequently are 2 and 3, both appearing twice.
  • The remaining element 1 appears once, meeting the requirements.

Example 2:

Input: nums = [5,5,5,5]

Output: 4

Explanation:

  • The longest frequency balance subarray is [5, 5, 5, 5].
  • The element that appears most frequently is 5.
  • There are no other elements meeting the requirements.

Example 3:

Input: nums = [1,2,3,4]

Output: 1

Explanation:

Since all elements appear only once, the length of the longest frequency balance subarray is 1.

 

Constraints:

  • 1 <= nums.length <= 10​​​​​​​3
  • 1 <= nums[i] <= 10​​​​​​​9

Approach Overview

Problem Overview: Given an array, identify subarrays where the frequencies of the elements are balanced. A balanced subarray means every distinct value appears the same number of times inside that subarray. The task is to efficiently detect or count such segments.

Approach 1: Brute Force Enumeration (O(n^3) time, O(k) space)

Generate every possible subarray using two nested loops and recompute frequencies from scratch for each segment. For each candidate range [i, j], build a frequency map and check whether all values have the same count. The check requires iterating over the map to confirm that the minimum and maximum frequencies match. This approach is straightforward and demonstrates the definition of a balanced subarray clearly, but recomputing frequencies repeatedly makes it too slow for large inputs.

Approach 2: Incremental Frequency Map (O(n^2) time, O(k) space)

Fix the starting index and expand the right boundary one element at a time. Maintain a running hash map that tracks frequencies of elements in the current subarray. After each expansion, update the map and check if all frequencies are equal by comparing the smallest and largest counts. Because the map updates happen in constant time per step, the expensive recomputation disappears. This approach reduces the complexity significantly while keeping the implementation simple using hash map frequency tracking.

Approach 3: Frequency Pattern Hashing (Near O(n) average, O(n) space)

A more optimized strategy represents the frequency distribution as a normalized pattern. Maintain counts for each value and track a "frequency of frequencies" structure so you can determine when all active elements share the same count. By storing normalized prefix states in a hash map, repeated patterns indicate that the segment between them maintains balanced frequency growth. This idea is similar to prefix-difference techniques used in prefix sum problems and leverages constant-time hash lookups to detect matches quickly.

Recommended for interviews: The incremental hash map approach is the most practical explanation during interviews. Starting with brute force shows understanding of the definition, but moving to the O(n^2) expansion technique demonstrates control over frequency counting and hash-based optimization. Discussing prefix-state hashing shows deeper algorithmic insight and familiarity with advanced counting techniques.

Solution

We can enumerate the left endpoint l of the subarray in the range [0, n), then enumerate the right endpoint r from left to right starting from l. During the enumeration, we use two hash tables cnt and freq to record the frequency of each element in the subarray and the frequency of each frequency value, respectively.

When either of the following conditions is satisfied, update the answer ans = max(ans, r - l + 1):

  • There is only one distinct element in the hash table cnt, i.e., the length of cnt is 1;
  • There are only two distinct frequency values in the hash table freq, i.e., the length of freq is 2, and one frequency value is exactly twice the other;

After the enumeration ends, return the answer ans.

The time complexity is O(n^2) and the space complexity is O(n). Where n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^3)O(k)Useful for understanding the definition or verifying small inputs
Incremental Frequency MapO(n^2)O(k)General solution when constraints allow quadratic expansion
Frequency Pattern HashingO(n) averageO(n)Large inputs where repeated normalized frequency states can be hashed

Video Solution

Leetcode 3960 | Frequency Balance Subarray | Leetcode weekly contest 506 • CodeWithMeGuys • 1,239 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Frequency Balance Subarray easy or hard?
Frequency Balance Subarray is typically considered a medium difficulty problem. The brute force logic is simple, but optimizing the frequency checks and reducing repeated work requires careful use of hash maps and counting strategies.
Frequency Balance Subarray Python/Java solution
Most implementations rely on a dictionary (Python) or HashMap (Java) to track counts while expanding the subarray. Each step updates the frequency map and checks whether all values share the same frequency. The same algorithm translates cleanly between Python and Java using their respective hash map libraries.
How to solve Frequency Balance Subarray in O(n)?
Track element frequencies while maintaining a normalized representation of the frequency distribution. Store this representation in a hash map keyed by prefix state. When the same normalized state appears again, the subarray between the two positions preserves balanced frequency growth. Hash lookups allow constant-time detection, giving near O(n) average complexity.
What is the best approach for Frequency Balance Subarray?
The most practical approach uses a hash map to maintain element frequencies while expanding a subarray from each starting index. This reduces redundant recomputation and runs in O(n^2) time with O(k) extra space, where k is the number of distinct values. Advanced solutions use normalized frequency patterns with hashing to approach O(n) average time.
Is Frequency Balance Subarray asked at Google/Amazon/Meta?
Frequency-based subarray questions appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem title may differ, the underlying concepts—hash maps, prefix states, and frequency counting—are common interview patterns.
What data structure is used in Frequency Balance Subarray?
The core data structure is a hash map that stores element frequencies within the current subarray. Some optimized solutions also maintain a frequency-of-frequencies map or a hashed prefix pattern to quickly detect balanced distributions.
What is the time complexity of Frequency Balance Subarray?
Complexity depends on the method used. A brute force approach that recomputes frequencies for every subarray takes O(n^3). Maintaining an incremental frequency map reduces it to O(n^2). Optimized prefix-state hashing can achieve near O(n) average time with additional memory for stored states.

Ready to solve this problem?

Practice Frequency Balance Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays