Bitwise ORs of Subarrays: Tracking Distinct OR Values Efficiently

LeetCode Bitwise ORs of Subarrays (Problem 898) asks you to find how many distinct values you can get by taking the bitwise OR of every possible contiguous subarray of an integer array. Given an array arr, you compute arr[i] | arr[i+1] | ... | arr[j] for every valid pair i, j where i is at most j, and return the count of distinct results.

The problem

You are given an integer array arr. For every contiguous subarray, compute the bitwise OR of its elements. Return the number of distinct OR values across all subarrays.

For example, given arr = [1, 1, 2], the subarrays and their ORs are: [1] gives 1, [1] gives 1, [2] gives 2, [1,1] gives 1, [1,2] gives 3, [1,1,2] gives 3. The distinct values are , so the answer is 3.

The brute force approach

The most direct approach is to enumerate every subarray and compute its OR. You could use two nested loops to pick the start and end indices, then OR the elements together. That gives O(n^2) subarrays, and computing each OR from scratch takes up to O(n), resulting in O(n^3) time. You can optimize the inner loop by extending the OR incrementally (instead of recomputing from scratch), bringing it down to O(n^2). But even O(n^2) is too slow when n can reach 50,000.

The key insight

Bitwise OR is monotonic: once a bit is set, it stays set. If you fix the right endpoint at index j and slide the left endpoint from j back to 0, the OR value can only increase or stay the same. It never decreases.

More importantly, the number of distinct OR values ending at any position j is bounded by the number of bits in the integers. For 32-bit integers, that is at most 30 distinct values. Each time you extend the OR to the left, you either set at least one new bit (creating a new distinct value) or change nothing. Since there are only about 30 bits to set, the set of reachable OR values ending at position j has at most 30 elements.

This means you can track a small set of "currently reachable" OR values and propagate it forward through the array. At each new element, you OR it with every value in the previous set and also start a fresh subarray with just that element. The resulting set replaces the old one, and you add all its values to a global result set.

Step-by-step walkthrough

Let's trace through the algorithm on arr = [1, 1, 2]. We maintain a set prev of all distinct OR values of subarrays ending at the previous index. At each step, we build a new set from prev and the current element, then merge it into the global result.

After processing all three elements, the result set contains . The answer is 3.

The code

def subarrayBitwiseORs(arr):
    result = set()
    prev = set()
    for x in arr:
        prev = {v | x for v in prev} | {x}
        result |= prev
    return len(result)

The variable prev holds all distinct OR values of subarrays ending at the previous position. For each new element x, you OR it with every value in prev to extend those subarrays by one element, and you also add x itself for the single-element subarray starting at this position. The new set becomes prev for the next iteration. Every value from prev is also added to result, which tracks all distinct OR values seen across the entire array.

Complexity analysis

The set propagation approach processes each element once. For each element, the inner set has at most 30 entries (bounded by bit width), so each step does at most 30 OR operations and 30 set insertions. The total work is O(30n), which simplifies to O(n). The result set can hold at most O(n * 30) values in the worst case, though in practice it is much smaller.

The building blocks

Set propagation with bounded state

The core technique here is maintaining a set of "reachable values" that gets updated at each position. The key property that makes this efficient is that the set size is bounded by the bit width of the integers. This same pattern appears whenever you propagate a state forward through an array and the number of possible states is inherently limited. Recognizing that the state space is small (even when the array is large) is the critical observation.

Bitwise OR monotonicity

OR only adds bits, never removes them. Once a bit is turned on, extending the subarray further to the left or right cannot turn it off. This monotonicity property means the number of distinct values you can form by extending a subarray is bounded by the number of bits. You will see similar monotonicity arguments in problems involving AND (which only clears bits) and other bitwise operations.

Edge cases

Single element array. When arr has one element, there is exactly one subarray, and the answer is 1. The algorithm handles this naturally: prev becomes a set with one element, and result has size 1.

All elements are the same. If every element is identical, say arr = [5, 5, 5], then every subarray has the same OR value (5). The answer is 1. The prev set always contains just , and result stays at element.

Elements are powers of two. When each element is a distinct power of two, like [1, 2, 4], every subset of bits can be reached. The number of distinct OR values grows combinatorially, but is still bounded. For [1, 2, 4], you get , giving 7 distinct values.

Zero in the array. Zero OR-ed with anything is that thing. If the array contains 0, it adds 0 as a possible OR value (from the subarray [0]) but does not affect other OR computations. The algorithm handles this correctly since {v | 0 for v in prev} just returns prev, plus for the new single-element subarray.

From understanding to recall

The tricky part of this problem is not the code itself, which is only a few lines. The tricky part is recognizing that the set of reachable OR values at each position is bounded by the bit width. Without that insight, you might dismiss the set-based approach as potentially quadratic and never reach the efficient solution.

When drilling this problem, pay attention to the moment you realize why prev stays small. That is the conceptual leap. If you can articulate "OR only sets bits, so each new distinct value in prev must have at least one more bit set, limiting the set to at most 30 entries" without looking at notes, you own the insight.

Also watch for the pattern of building a new set from the old one at each step. This forward propagation of bounded state is a reusable technique. You will see it again in problems that track reachable sums, reachable remainders, or other accumulated values where the state space is naturally limited.

Related posts

• Bitwise AND of Numbers Range - Another bitwise problem over ranges. AND strips bits across a range while OR accumulates them, but both exploit the bounded bit width for efficient solutions.
• Number of 1 Bits - Fundamental bit manipulation that builds fluency with bitwise operations. Understanding how bits are set and cleared is the foundation for the OR monotonicity insight here.
• Subarray Sum Equals K - A different subarray accumulation problem. Instead of OR values, you track prefix sums. Both problems share the pattern of propagating state across subarrays to count distinct or matching results.