LeetCode 898 - Bitwise ORs of Subarrays

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Bit Manipulation

Solution

Problem Understanding

The problem asks us to compute every possible bitwise OR value that can be formed from all non-empty contiguous subarrays of the given array arr, then return how many distinct values exist.

A subarray is any contiguous slice of the array. For example, if arr = [1,2,4], the valid subarrays are:

[1]
[2]
[4]
[1,2]
[2,4]
[1,2,4]

For each subarray, we compute the bitwise OR of all its elements. The bitwise OR operator combines bits such that a bit becomes 1 if it is set in at least one operand.

For example:

1 | 2 = 3
2 | 4 = 6
1 | 2 | 4 = 7

The goal is not to count subarrays, but to count how many unique OR results appear.

The input is an integer array:

1 <= arr.length <= 5 * 10^4
0 <= arr[i] <= 10^9

These constraints are extremely important. A naive solution that explicitly computes the OR for every subarray would involve roughly O(n^2) subarrays, which becomes infeasible when n = 50,000.

The problem guarantees:

The array is non-empty.
Values are non-negative.
Values fit comfortably within standard 32-bit integer operations.

Several edge cases are important:

Arrays containing only zeros, because repeated OR operations never change the value.
Arrays with repeated values, because many subarrays can produce identical OR results.
Arrays where OR values quickly saturate into large masks such as 7, 15, or 31.
Single-element arrays, because the answer must still include that element’s value.

Approaches

Brute Force Approach

The most direct approach is to generate every possible subarray and compute its bitwise OR.

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

Start with current_or = 0
For each ending index j >= i
Update current_or |= arr[j]
Insert the result into a set

Using a set guarantees uniqueness automatically.

This approach is correct because it explicitly enumerates every valid subarray and computes its OR exactly once.

However, there are O(n^2) subarrays. With n = 50,000, this becomes far too slow. Even though OR computation itself is constant time, iterating over billions of subarrays is not practical.

Key Insight for the Optimal Solution

The critical observation is that the number of distinct OR values generated from subarrays ending at a fixed index is actually very small.

Suppose we process the array from left to right. At position i, consider all subarrays ending at i.

Every such subarray can be formed by:

Taking a subarray ending at i - 1
OR-ing it with arr[i]

Or:

Starting a brand new subarray containing only arr[i]

The key property of bitwise OR is monotonicity:

Once a bit becomes 1, it never becomes 0

This means OR values can only increase as subarrays grow.

Because integers contain at most around 30 meaningful bits here, the number of distinct OR values for subarrays ending at a given position is bounded by approximately 30 to 32 unique states.

Instead of storing all subarrays, we only store the distinct OR values obtainable from subarrays ending at the current index.

This dramatically reduces the complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n²)	Enumerates every subarray explicitly
Optimal	O(n * B)	O(B + answer)	Uses rolling OR states, where B is number of bits, about 30

Algorithm Walkthrough

Initialize a global set called all_results.

This set stores every distinct OR value seen across all subarrays in the entire array. 2. Initialize another set called previous.

This set represents all distinct OR values of subarrays ending at the previous index. 3. Iterate through each number num in the array.

At each step, we want to compute all distinct OR values for subarrays ending at the current position. 4. Create a new set called current.

Start it with {num} because a subarray consisting only of the current element is always valid. 5. Extend every previous subarray.

For each value value in previous:

Compute value | num
Insert the result into current

This simulates extending every subarray ending at the previous position by one additional element. 6. Merge the newly generated OR values into all_results.

This accumulates all unique OR values globally. 7. Update previous = current.

The current set now becomes the set of OR values for subarrays ending at this position. 8. After processing the entire array, return the size of all_results.

Why it works

The invariant is:

previous always contains exactly the set of distinct OR values produced by all subarrays ending at the previous index.

When processing arr[i], every subarray ending at i is either:

The single-element subarray [arr[i]]
An extension of a subarray ending at i - 1

By OR-ing arr[i] with every value in previous, we generate every possible OR value for subarrays ending at i.

Because we store values in sets, duplicates are automatically removed.

Since every subarray ends somewhere, collecting all intermediate sets guarantees we capture every distinct OR value.

Python Solution

from typing import List

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        all_results = set()
        previous = set()

        for num in arr:
            current = {num}

            for value in previous:
                current.add(value | num)

            all_results.update(current)
            previous = current

        return len(all_results)

The implementation closely follows the algorithm described earlier.

all_results stores every distinct OR value discovered so far. This is the final collection whose size we return.

previous tracks all OR values for subarrays ending at the previous index. For each new element num, we build a fresh set called current.

The line:

current = {num}

handles the single-element subarray beginning and ending at the current index.

Next, we extend all prior subarrays:

for value in previous:
    current.add(value | num)

Each OR result corresponds to appending num to an earlier subarray.

After generating all possible OR values ending at this position, we merge them into the global answer set:

all_results.update(current)

Finally:

previous = current

moves the sliding state forward for the next iteration.

The implementation is concise because Python sets naturally handle uniqueness.

Go Solution

func subarrayBitwiseORs(arr []int) int {
    allResults := make(map[int]bool)
    previous := make(map[int]bool)

    for _, num := range arr {
        current := make(map[int]bool)
        current[num] = true

        for value := range previous {
            current[value|num] = true
        }

        for value := range current {
            allResults[value] = true
        }

        previous = current
    }

    return len(allResults)
}

The Go solution uses map[int]bool to simulate sets because Go does not provide a built-in set type.

The overall logic is identical to the Python implementation.

A new current map is created during each iteration to store OR values for subarrays ending at the current index.

Go integers safely handle the constraint range since arr[i] <= 10^9, well within 32-bit signed integer limits.

Unlike Python, Go requires explicit iteration over map keys:

for value := range previous

The final answer is simply:

len(allResults)

because the map stores only unique keys.

Worked Examples

Example 1

Input:

arr = [0]

Processing steps:

Index	num	previous before	current after processing	all_results
0	0	{}	{0}	{0}

Final answer:

Example 2

Input:

arr = [1,1,2]

Step 1

Current number is 1.

Subarrays ending here:

[1] -> 1

Variable	Value
previous	{}
current	{1}
all_results	{1}

Step 2

Current number is 1.

Existing OR values from previous step:

Extend them:

1 | 1 = 1

Also include:

[1] -> 1

Variable	Value
previous	{1}
current	{1}
all_results	{1}

Step 3

Current number is 2.

Extend previous values:

1 | 2 = 3

Single-element subarray:

[2] -> 2

Variable	Value
previous	{1}
current	{2, 3}
all_results	{1, 2, 3}

Final answer:

Example 3

Input:

arr = [1,2,4]

Index	num	previous	current	all_results
0	1	{}	{1}	{1}
1	2	{1}	{2,3}	{1,2,3}
2	4	{2,3}	{4,6,7}	{1,2,3,4,6,7}

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * B)	Each iteration processes at most about B distinct OR states
Space	O(B + answer)	Stores rolling OR states and all unique answers

Here, B represents the number of bits in the integers. Since arr[i] <= 10^9, we only need about 30 bits.

The important insight is that the set of distinct OR values for subarrays ending at any index remains small. OR operations only add bits, never remove them, so the number of transitions is bounded.

In practice, the algorithm behaves very efficiently even for the maximum input size.

Test Cases

from typing import List

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        all_results = set()
        previous = set()

        for num in arr:
            current = {num}

            for value in previous:
                current.add(value | num)

            all_results.update(current)
            previous = current

        return len(all_results)

sol = Solution()

assert sol.subarrayBitwiseORs([0]) == 1  # single zero
assert sol.subarrayBitwiseORs([1]) == 1  # single non-zero element
assert sol.subarrayBitwiseORs([1,1,2]) == 3  # repeated values
assert sol.subarrayBitwiseORs([1,2,4]) == 6  # increasing powers of two
assert sol.subarrayBitwiseORs([0,0,0]) == 1  # all zeros
assert sol.subarrayBitwiseORs([1,1,1]) == 1  # identical elements
assert sol.subarrayBitwiseORs([1,2,3]) == 3  # overlapping OR results
assert sol.subarrayBitwiseORs([5,1,2]) == 6  # mixed bit patterns
assert sol.subarrayBitwiseORs([8,4,2,1]) == 10  # descending powers of two
assert sol.subarrayBitwiseORs([7,7,7]) == 1  # saturated OR values
assert sol.subarrayBitwiseORs([1,3,7,15]) == 4  # cumulative saturation

Test	Why
`[0]`	Smallest valid input
`[1]`	Single non-zero element
`[1,1,2]`	Duplicate OR values
`[1,2,4]`	Produces many distinct ORs
`[0,0,0]`	OR never changes from zero
`[1,1,1]`	Repeated identical values
`[1,2,3]`	Multiple subarrays collapsing to same OR
`[5,1,2]`	Mixed binary combinations
`[8,4,2,1]`	Distinct bit accumulation
`[7,7,7]`	Fully saturated bitmask
`[1,3,7,15]`	Rapid OR saturation

Edge Cases

Arrays Containing Only Zeros

If the array is something like [0,0,0], every subarray OR evaluates to 0.

A buggy implementation might repeatedly count duplicates or fail to deduplicate properly.

This implementation handles the case naturally because all OR results are inserted into sets. Regardless of how many times 0 appears, the final set contains only one value.

Repeated Values

Arrays like [1,1,1] can generate many duplicate subarray ORs.

For example:

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

A naive algorithm may waste time recomputing identical states repeatedly.

The optimized approach avoids this issue because previous only stores distinct OR values, not every subarray individually.

Rapid Bit Saturation

Consider an array like [1,3,7,15].

Once many bits become set, extending subarrays often stops producing new OR values.

A brute-force solution still processes every subarray explicitly.

The optimized solution benefits from the fact that OR values stabilize quickly. The rolling set size remains small, which keeps the algorithm efficient even for large inputs.