LeetCode 3209 - Number of Subarrays With AND Value of K

LeetCode Problem 3209

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Bit Manipulation, Segment Tree

Solution

Problem Understanding

The problem asks us to count how many contiguous subarrays of nums have a bitwise AND equal to k.

A subarray is any contiguous segment of the array. For every possible subarray, we compute the bitwise AND of all elements inside it. If the result equals k, that subarray contributes to the final answer.

For example, if:

nums = [1,1,2]
k = 1

then the valid subarrays are:

[1]          -> 1
[1]          -> 1
[1,1]        -> 1

so the answer is 3.

The input constraints are large:

1 <= nums.length <= 100000
0 <= nums[i], k <= 10^9

A length of 100000 immediately tells us that any quadratic solution will likely time out. Since there are O(n^2) subarrays, explicitly computing the AND for every subarray is too expensive.

The important property of bitwise AND is that it is monotonic in one direction:

a & b <= a

As we extend a subarray by adding more elements, the AND value can only stay the same or lose bits. It never increases. This observation is the key to the optimal solution.

Some important edge cases:

• Arrays containing many repeated values, because many subarrays may share the same AND.
• Cases where k = 0, since AND operations frequently collapse to zero.
• Arrays where no subarray can possibly equal k.
• Large arrays with many distinct numbers, where brute force becomes impossible.
• Single element arrays, where the answer depends entirely on whether nums[0] == k.

Approaches

Brute Force Approach

The most direct solution is to enumerate every subarray.

For each starting index i, we extend the subarray one element at a time:

AND = nums[i]
AND &= nums[i+1]
AND &= nums[i+2]
...

Whenever the running AND equals k, we increment the answer.

This approach is correct because it explicitly checks every possible subarray. However, there are O(n^2) subarrays, and each extension performs an AND operation.

With n = 100000, this becomes far too slow.

Key Insight

The critical observation is that bitwise AND values collapse very quickly.

Suppose we fix an ending position i. Consider all subarrays ending at i.

For each subarray ending at i, we can compute:

previous_and & nums[i]

A surprising but crucial fact is that the number of distinct AND values for subarrays ending at any position is very small.

Why?

Every AND operation can only turn bits off. Since integers have at most about 30 bits here, the number of distinct AND transitions is bounded.

This allows us to maintain:

AND value -> number of subarrays producing it

for all subarrays ending at the current index.

Instead of tracking all subarrays individually, we compress them by AND value.

This transforms the solution into nearly linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Enumerates every subarray explicitly
Optimal	O(n * B)	O(B)	Tracks compressed AND states, where B is the number of distinct AND values, typically at most 30

Algorithm Walkthrough

Optimal Algorithm

1. Initialize a variable answer = 0.
2. Maintain a hash map called previous:

AND value -> count of subarrays ending at previous index

This map stores all distinct AND results for subarrays ending at the previous position. 3. Iterate through each number num in nums. 4. Create a new hash map current. 5. Every subarray ending at the current index falls into one of two categories:

• A new subarray consisting only of num
• An extension of a previous subarray

6. Start the single-element subarray:

current[num] += 1

7. For every (and_value, count) in previous:

• Compute:

new_and = and_value & num

• Add the count:

current[new_and] += count

This represents extending all previous subarrays by the current element. 8. After constructing current, check:

current[k]

If it exists, add its count to the answer. 9. Replace:

previous = current

10. Continue until the array is fully processed.
11. Return answer.

Why it works

For every index i, the algorithm stores exactly all possible AND values for subarrays ending at i, along with how many subarrays produce each value.

When moving to index i + 1, every previous subarray can only be extended by ANDing with the new number. Since AND is associative:

(a & b) & c = a & (b & c)

the new AND values are computed correctly.

Because every subarray ending at each position is represented exactly once, and every occurrence of AND value k is counted, the final answer is correct.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        answer = 0
        
        previous = {}
        
        for num in nums:
            current = defaultdict(int)
            
            # Start a new subarray with only num
            current[num] += 1
            
            # Extend all previous subarrays
            for and_value, count in previous.items():
                new_and = and_value & num
                current[new_and] += count
            
            answer += current[k]
            
            previous = current
        
        return answer

The implementation follows the algorithm directly.

The previous dictionary stores all AND values for subarrays ending at the previous index. The value associated with each key is the number of subarrays producing that AND result.

For every new number, we build a fresh current dictionary.

The line:

current[num] += 1

creates the single-element subarray.

Then we extend every previous subarray by ANDing its result with the current number:

new_and = and_value & num

Multiple subarrays may collapse into the same AND value, so we accumulate counts.

Finally, we add:

current[k]

to the answer, because these are exactly the subarrays ending at the current position whose AND equals k.

Go Solution

func countSubarrays(nums []int, k int) int64 {
    var answer int64 = 0

    previous := map[int]int64{}

    for _, num := range nums {
        current := map[int]int64{}

        // Single-element subarray
        current[num]++

        // Extend previous subarrays
        for andValue, count := range previous {
            newAnd := andValue & num
            current[newAnd] += count
        }

        answer += current[k]

        previous = current
    }

    return answer
}

The Go implementation mirrors the Python version closely.

The main difference is that the answer uses int64, because the number of subarrays can be as large as:

n * (n + 1) / 2

which exceeds 32-bit integer range when n = 100000.

Go maps are used instead of Python dictionaries, and missing keys automatically return zero values.

Worked Examples

Example 1

nums = [1,1,1]
k = 1

Iteration Details

Index	num	current map	current[1]	answer
0	1	{1:1}	1	1
1	1	{1:2}	2	3
2	1	{1:3}	3	6

Final answer:

6

All subarrays have AND equal to 1.

Example 2

nums = [1,1,2]
k = 1

Iteration Details

Index	num	current map	current[1]	answer
0	1	{1:1}	1	1
1	1	{1:2}	2	3
2	2	{2:3}	0	3

Final answer:

3

The valid subarrays are:

[1]
[1]
[1,1]

Example 3

nums = [1,2,3]
k = 2

Iteration Details

Index	num	current map	current[2]	answer
0	1	{1:1}	0	0
1	2	{2:1, 0:1}	1	1
2	3	{3:1, 2:1, 0:1}	1	2

Final answer:

2

The valid subarrays are:

[2]
[2,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * B)	Each position processes only a small number of distinct AND values
Space	O(B)	Stores compressed AND states for one index

Here, B represents the number of distinct AND values for subarrays ending at a position.

Although the theoretical bound could appear larger, in practice and in analysis, B is bounded by the number of bits in the integers, roughly 30 for this problem.

Each AND operation can only remove bits, so the number of distinct values remains small.

Therefore, the solution behaves very close to linear time.

Test Cases

from typing import List

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        
        answer = 0
        previous = {}
        
        for num in nums:
            current = defaultdict(int)
            
            current[num] += 1
            
            for and_value, count in previous.items():
                current[and_value & num] += count
            
            answer += current[k]
            previous = current
        
        return answer

sol = Solution()

assert sol.countSubarrays([1,1,1], 1) == 6  # all subarrays valid
assert sol.countSubarrays([1,1,2], 1) == 3  # repeated ones
assert sol.countSubarrays([1,2,3], 2) == 2  # mixed values

assert sol.countSubarrays([5], 5) == 1  # single element valid
assert sol.countSubarrays([5], 1) == 0  # single element invalid

assert sol.countSubarrays([0,0,0], 0) == 6  # all AND values become zero

assert sol.countSubarrays([7,7,7], 7) == 6  # identical numbers

assert sol.countSubarrays([8,4,2,1], 0) == 6  # AND collapses to zero frequently

assert sol.countSubarrays([1,2,4,8], 16) == 0  # impossible target

assert sol.countSubarrays([3,3,3,3], 3) == 10  # every subarray valid

assert sol.countSubarrays([1,0,1,0], 0) == 8  # many zero-producing subarrays

print("All tests passed.")

Test	Why
[1,1,1], k=1	Every subarray is valid
[1,1,2], k=1	Tests repeated AND accumulation
[1,2,3], k=2	Tests mixed transitions
[5], k=5	Single valid element
[5], k=1	Single invalid element
[0,0,0], k=0	AND collapses immediately
[7,7,7], k=7	Constant AND value
[8,4,2,1], k=0	Frequent bit elimination
[1,2,4,8], k=16	No valid subarray
[3,3,3,3], k=3	Large number of valid subarrays
[1,0,1,0], k=0	Alternating zero behavior

Edge Cases

Edge Case 1, k = 0

Zero is special for bitwise AND because once a bit becomes zero, it never comes back.

Many subarrays quickly collapse to zero, especially when numbers share few common bits. A naive implementation might repeatedly recompute these ANDs inefficiently.

The optimized solution handles this naturally because many different subarrays compress into the same AND value 0 inside the hash map.

Edge Case 2, Single Element Arrays

When the array contains only one number, there is exactly one subarray.

This case is easy to mishandle if the implementation assumes subarrays must have length greater than one.

The algorithm explicitly creates the single-element subarray at every iteration:

current[num] += 1

so single-element cases work automatically.

Edge Case 3, Many Duplicate Numbers

Consider:

[7,7,7,7,7]

Every subarray has the same AND value.

A brute force solution still processes all O(n²) subarrays individually.

The optimized solution compresses all of them into a single dictionary entry:

7 -> count

This demonstrates why the hash map compression is so effective.

Edge Case 4, No Valid Subarray

Sometimes no subarray AND can equal k.

For example:

nums = [1,2,4,8]
k = 16

Since AND can never create new bits, reaching 16 is impossible.

The algorithm simply never finds current[k], and the answer remains zero.