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] <= 109Problem 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.
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.
Python
Java
C++
Go
TypeScript
| 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 |
Leetcode 3878 | Count Good Subarrays | Very Interesting | Leetcode weekly contest 494 • CodeWithMeGuys • 837 views views
Watch 1 more video solutions →Practice Count Good Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor