Frequency Balance Subarray solution and explanation
8 more videos on this problem
Leetcode 3960 | Frequency Balance Subarray | Leetcode weekly contest 506CodeWithMeGuys · 26:04 · 1K views
Leetcode 3960 Weekly Contest 506 Q2 | Frequency Balance Subarray | Frequency of Frequency 🔥CodeSprint · 14:07 · 650 views
Frequency Balance Subarray | LeetCode Weekly Contest 506 | Problem 2Prince Gupta Study · 36:51 · 255 views
3960. Frequency Balance Subarray (Leetcode Medium)Programming Live with Larry · 14:37 · 207 views
3960. Frequency Balance Subarray | Leetcode | Medium | Array | MapLeet's Code · 21:29 · 173 views
Weekly Contest 506 | Leetcode 3960 | Frequency Balance SubarrayCode Like Him · 5:31 · 142 views
3960. Frequency Balance Subarray | LeetCode Weekly 506 | Maps with in depth Dry Run C++ codeBEASTCODES · 30:14 · 51 views
LeetCode Weekly Contest 506 | Problem 3959 & 3960 Explained in JavaProof2Code · 14:22 · 50 views
Frequency Balance Subarray | Leetcode weekly contest 506 | #3960UMANG AGRAWAL · 17:12 · 23 views
The problem
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
fsuch that every distinct value in the subarray occurs eitherfor2 * ftimes, 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 <= 1031 <= nums[i] <= 109
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 ofcntis1; - There are only two distinct frequency values in the hash table
freq, i.e., the length offreqis2, 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.
class Solution:
def getLength(self, nums: List[int]) -> int:
n = len(nums)
ans = 1
for l in range(n):
cnt = Counter()
freq = Counter()
for r in range(l, n):
x = nums[r]
if freq[cnt[x]]:
freq[cnt[x]] -= 1
if freq[cnt[x]] == 0:
freq.pop(cnt[x])
cnt[x] += 1
freq[cnt[x]] += 1
if (len(cnt) == 1) or (len(freq) == 2 and (freq[cnt[x] * 2] or (cnt[x] % 2 == 0 and freq[cnt[x] // 2]))):
ans = max(ans, r - l + 1)
return ansclass Solution {
public int getLength(int[] nums) {
int n = nums.length;
int ans = 1;
for (int l = 0; l < n; l++) {
Map<Integer, Integer> cnt = new HashMap<>();
Map<Integer, Integer> freq = new HashMap<>();
for (int r = l; r < n; r++) {
int x = nums[r];
int c = cnt.getOrDefault(x, 0);
if (freq.getOrDefault(c, 0) > 0) {
freq.put(c, freq.get(c) - 1);
if (freq.get(c) == 0) {
freq.remove(c);
}
}
cnt.put(x, c + 1);
freq.merge(cnt.get(x), 1, Integer::sum);
int cx = cnt.get(x);
if (cnt.size() == 1
|| (freq.size() == 2
&& (freq.getOrDefault(cx * 2, 0) > 0
|| (cx % 2 == 0 && freq.getOrDefault(cx / 2, 0) > 0)))) {
ans = Math.max(ans, r - l + 1);
}
}
}
return ans;
}
}class Solution {
public:
int getLength(vector<int>& nums) {
int n = nums.size();
int ans = 1;
for (int l = 0; l < n; ++l) {
unordered_map<int, int> cnt;
unordered_map<int, int> freq;
for (int r = l; r < n; ++r) {
int x = nums[r];
int c = cnt[x];
if (freq.contains(c)) {
if (--freq[c] == 0) {
freq.erase(c);
}
}
++cnt[x];
++freq[cnt[x]];
if (cnt.size() == 1 || (freq.size() == 2 && (freq.contains(cnt[x] * 2) || (cnt[x] % 2 == 0 && freq.contains(cnt[x] / 2))))) {
ans = max(ans, r - l + 1);
}
}
}
return ans;
}
};function getLength(nums: number[]): number {
const n = nums.length;
let ans = 1;
for (let l = 0; l < n; l++) {
const cnt = new Map<number, number>();
const freq = new Map<number, number>();
for (let r = l; r < n; r++) {
const x = nums[r];
const c = cnt.get(x) ?? 0;
if ((freq.get(c) ?? 0) > 0) {
const f = (freq.get(c) ?? 0) - 1;
if (f === 0) {
freq.delete(c);
} else {
freq.set(c, f);
}
}
cnt.set(x, c + 1);
freq.set(c + 1, (freq.get(c + 1) ?? 0) + 1);
const cur = c + 1;
if (
cnt.size === 1 ||
(freq.size === 2 &&
((freq.get(cur * 2) ?? 0) > 0 ||
(cur % 2 === 0 && (freq.get(cur / 2) ?? 0) > 0)))
) {
ans = Math.max(ans, r - l + 1);
}
}
}
return ans;
}func getLength(nums []int) int {
n := len(nums)
ans := 1
for l := 0; l < n; l++ {
cnt := make(map[int]int)
freq := make(map[int]int)
for r := l; r < n; r++ {
x := nums[r]
c := cnt[x]
if freq[c] > 0 {
freq[c]--
if freq[c] == 0 {
delete(freq, c)
}
}
cnt[x] = c + 1
freq[cnt[x]]++
cx := cnt[x]
if len(cnt) == 1 || (len(freq) == 2 && (freq[cx*2] > 0 || (cx%2 == 0 && freq[cx/2] > 0))) {
ans = max(ans, r-l+1)
}
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(k) | Useful for understanding the definition or verifying small inputs |
| Incremental Frequency Map | O(n^2) | O(k) | General solution when constraints allow quadratic expansion |
| Frequency Pattern Hashing | O(n) average | O(n) | Large inputs where repeated normalized frequency states can be hashed |
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.