3960. Frequency Balance Subarray

Description

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³
1 <= nums[i] <= 10⁹

Solutions

Solution 1: Enumeration + Hash Table

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 $\textit{cnt}$ and $\textit{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 $\textit{ans} = \max(\textit{ans}, r - l + 1)$:

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

After the enumeration ends, return the answer $\textit{ans}$.

The time complexity is $O(n^2)$ and the space complexity is $O(n)$. Where $n$ is the length of the array $\textit{nums}$.

class 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;
    }
};

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 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
}

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;
}

3960 - Frequency Balance Subarray

3960. Frequency Balance Subarray

Description

Solutions

Solution 1: Enumeration + Hash Table

All Problems

All Solutions

Welcome to Subscribe On Youtube

3960. Frequency Balance Subarray

Description

Solutions

Solution 1: Enumeration + Hash Table

All Problems

All Solutions