Watch 2 video solutions for Count Good Subarrays, a hard level problem involving Array, Stack, Bit Manipulation. This walkthrough by CodeWithMeGuys has 837 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |