Count Good Subarrays solution and explanation
3 more videos on this problem
Leetcode 3878 | Count Good Subarrays | Very Interesting | Leetcode weekly contest 494CodeWithMeGuys · 39:57 · 1K views
3878. Count Good Subarrays || SPARSE TABLE + BINARY SEARCH || LC HARD || WEEKLY CONTEST 494Pizza vs HiddenTestCases · 28:08 · 172 views
3878. Count Good Subarrays (Leetcode Hard)Programming Live with Larry · 1:07:09 · 169 views
LC3878 Count Good Subarrays (LeetCode Hard) (C++)WYCode · 9:36 · 10 views
The problem
You are given an integer array nums.
A subarray is called good if the bitwise OR of all its elements is equal to at least one element present in that subarray.
Return the number of good subarrays in nums.
Here, the bitwise OR of two integers a and b is denoted by a | b.
Example 1:
Input: nums = [4,2,3]
Output: 4
Explanation:
The subarrays of nums are:
| Subarray | Bitwise OR | Present in Subarray |
|---|---|---|
[4] |
4 = 4 |
Yes |
[2] |
2 = 2 |
Yes |
[3] |
3 = 3 |
Yes |
[4, 2] |
4 | 2 = 6 |
No |
[2, 3] |
2 | 3 = 3 |
Yes |
[4, 2, 3] |
4 | 2 | 3 = 7 |
No |
Thus, the good subarrays of nums are [4], [2], [3] and [2, 3]. Thus, the answer is 4.
Example 2:
Input: nums = [1,3,1]
Output: 6
Explanation:
Any subarray of nums containing 3 has bitwise OR equal to 3, and subarrays containing only 1 have bitwise OR equal to 1.
In both cases, the result is present in the subarray, so all subarrays are good, and the answer is 6.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an integer array and a value k. A subarray is considered good if it contains at least k pairs of equal elements. The task is to count how many subarrays satisfy this condition.
Approach 1: Brute Force with Frequency Counting (O(n²) time, O(n) space)
Enumerate every possible subarray using two nested loops. For each starting index, extend the subarray one element at a time and maintain a frequency map of values seen so far. Every time you add an element x, the number of new equal pairs increases by the current frequency of x. If the running pair count reaches k, the subarray qualifies as good. This approach directly simulates the definition of the problem and is useful for understanding how pairs accumulate.
Approach 2: Sliding Window with Pair Tracking (O(n) time, O(n) space)
The optimal solution uses a two-pointer sliding window combined with a hash map that stores the frequency of each value. As the right pointer expands the window, update the pair count by adding the current frequency of the new element before incrementing it. Once the window contains at least k equal pairs, every extension to the right will also remain valid, so you can count multiple subarrays at once. Move the left pointer forward while maintaining frequencies and reducing the pair count accordingly. This transforms a quadratic enumeration into a linear scan.
The key insight is that the number of equal pairs contributed by a value x depends on how many times it has already appeared in the window. Maintaining this incrementally avoids recomputing pair counts for each subarray. The technique is closely related to classic sliding window problems and relies on constant-time updates using a hash map. Understanding how pair counts grow with frequency is also useful for problems involving two pointers and frequency-based counting.
Recommended for interviews: Interviewers typically expect the sliding window solution. Starting with the brute force approach demonstrates that you understand how equal pairs are formed inside a subarray. The optimized window technique shows stronger algorithmic thinking by reducing the complexity from O(n²) to O(n) while maintaining accurate pair counts.
Solution
We can enumerate each element nums[i] as the bitwise OR result of a subarray, and count how many subarrays have a bitwise OR exactly equal to nums[i].
If the bitwise OR of a subarray is nums[i], then every element in the subarray must satisfy:
$
nums[k] \mid nums[i] = nums[i]
That is, every element in the subarray must be a subset of nums[i] (in terms of bits). We can use a monotonic stack to find the left boundary l[i] and right boundary r[i] for each element nums[i], such that all elements in the interval (l[i], r[i]) satisfy the above condition, while nums[l[i]] and nums[r[i]] do not. The number of subarrays with nums[i] as the bitwise OR result is then (i - l[i]) cdot (r[i] - i).
The time complexity is O(n) and the space complexity is O(n), where n$ is the length of the array.
class Solution:
def countGoodSubarrays(self, nums: list[int]) -> int:
n = len(nums)
l = [-1] * n
stk = []
for i, x in enumerate(nums):
while stk and nums[stk[-1]] < x and (nums[stk[-1]] | x) == x:
stk.pop()
l[i] = stk[-1] if stk else -1
stk.append(i)
r = [n] * n
stk = []
for i in range(n - 1, -1, -1):
while stk and (nums[stk[-1]] | nums[i]) == nums[i]:
stk.pop()
r[i] = stk[-1] if stk else n
stk.append(i)
return sum((i - l[i]) * (r[i] - i) for i in range(n))class Solution {
public long countGoodSubarrays(int[] nums) {
int n = nums.length;
int[] l = new int[n];
Arrays.fill(l, -1);
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
int x = nums[i];
while (!stk.isEmpty() && nums[stk.peek()] < x && (nums[stk.peek()] | x) == x) {
stk.pop();
}
l[i] = stk.isEmpty() ? -1 : stk.peek();
stk.push(i);
}
int[] r = new int[n];
Arrays.fill(r, n);
stk.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stk.isEmpty() && (nums[stk.peek()] | nums[i]) == nums[i]) {
stk.pop();
}
r[i] = stk.isEmpty() ? n : stk.peek();
stk.push(i);
}
long ans = 0;
for (int i = 0; i < n; i++) {
ans += (long) (i - l[i]) * (r[i] - i);
}
return ans;
}
}class Solution {
public:
long long countGoodSubarrays(vector<int>& nums) {
int n = nums.size();
vector<int> l(n, -1);
vector<int> stk;
for (int i = 0; i < n; i++) {
int x = nums[i];
while (!stk.empty() && nums[stk.back()] < x && (nums[stk.back()] | x) == x) {
stk.pop_back();
}
l[i] = stk.empty() ? -1 : stk.back();
stk.push_back(i);
}
vector<int> r(n, n);
stk.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stk.empty() && (nums[stk.back()] | nums[i]) == nums[i]) {
stk.pop_back();
}
r[i] = stk.empty() ? n : stk.back();
stk.push_back(i);
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += 1LL * (i - l[i]) * (r[i] - i);
}
return ans;
}
};function countGoodSubarrays(nums: number[]): number {
const n = nums.length;
const l = new Array(n).fill(-1);
const stk: number[] = [];
for (let i = 0; i < n; i++) {
const x = nums[i];
while (
stk.length &&
nums[stk[stk.length - 1]] < x &&
(nums[stk[stk.length - 1]] | x) === x
) {
stk.pop();
}
l[i] = stk.length ? stk[stk.length - 1] : -1;
stk.push(i);
}
const r = new Array(n).fill(n);
stk.length = 0;
for (let i = n - 1; i >= 0; i--) {
while (stk.length && (nums[stk[stk.length - 1]] | nums[i]) === nums[i]) {
stk.pop();
}
r[i] = stk.length ? stk[stk.length - 1] : n;
stk.push(i);
}
let ans = 0;
for (let i = 0; i < n; i++) {
ans += (i - l[i]) * (r[i] - i);
}
return ans;
}func countGoodSubarrays(nums []int) int64 {
n := len(nums)
l := make([]int, n)
for i := range l {
l[i] = -1
}
stk := []int{}
for i, x := range nums {
for len(stk) > 0 && nums[stk[len(stk)-1]] < x &&
(nums[stk[len(stk)-1]]|x) == x {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
l[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
r := make([]int, n)
for i := range r {
r[i] = n
}
stk = stk[:0]
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 &&
(nums[stk[len(stk)-1]]|nums[i]) == nums[i] {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
r[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
var ans int64
for i := 0; i < n; i++ {
ans += int64(i-l[i]) * int64(r[i]-i)
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Frequency Map | O(n²) | O(n) | Understanding how pair counts form in subarrays or when input size is small |
| Sliding Window with Pair Counting | O(n) | O(n) | General case and optimal interview solution for large arrays |
Frequently asked questions
Is Count Good Subarrays easy or hard?
Count Good Subarrays is typically considered a hard problem because it requires recognizing that pair counts can be updated incrementally inside a sliding window. The brute force idea is simple, but converting it into an O(n) solution requires deeper understanding of frequency-based counting.
Count Good Subarrays Python/Java solution
Most implementations use the same sliding window logic across languages. Python uses a dictionary or Counter for frequencies, while Java uses HashMap. The algorithm maintains a running pair count and adjusts it as the window expands or shrinks, achieving O(n) time complexity.
How to solve Count Good Subarrays in O(n)?
Maintain a sliding window with two pointers and a frequency map. When adding a new element at the right pointer, increase the pair count by its current frequency. If the pair count becomes at least k, move the left pointer while counting all valid subarrays formed by the current window. This avoids recomputing pair counts for every subarray and keeps the runtime linear.
What is the best approach for Count Good Subarrays?
The best approach uses a sliding window with a hash map that tracks element frequencies and the number of equal pairs inside the window. As the window expands, each new element contributes additional pairs equal to its previous frequency. Once the window reaches at least k pairs, all larger windows starting at the same left index are also valid. This method runs in O(n) time.
Is Count Good Subarrays asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Amazon, Google, and Meta because it combines sliding window logic with frequency counting. Interviewers often test whether candidates can track pair relationships efficiently instead of recomputing counts for each subarray.
What data structure is used in Count Good Subarrays?
The main data structure is a hash map (or dictionary) that stores the frequency of each value currently inside the sliding window. This allows constant-time updates and enables quick calculation of how many new equal pairs are formed when an element is added or removed.
What is the time complexity of Count Good Subarrays?
The optimal sliding window solution runs in O(n) time because each element is processed at most twice by the two pointers. Frequency updates and pair calculations are constant-time hash map operations. Space complexity is O(n) in the worst case when all elements in the window are distinct.