LeetCode Problem 3878

Difficulty: 🔴 Hard
Topics: Array, Stack, Bit Manipulation, Monotonic Stack

Solution

LeetCode 3878 - Count Good Subarrays

Problem Understanding

We are given an integer array nums, and we must count how many subarrays are good.

A subarray is considered good if the bitwise OR of all elements in that subarray is equal to at least one element that appears inside the same subarray.

Suppose a subarray contains values:

[a1, a2, a3, ..., ak]

Let:

OR = a1 | a2 | a3 | ... | ak

The subarray is good if there exists some element inside the subarray whose value is exactly OR.

The input consists of:

• An array nums
• 1 <= nums.length <= 100000
• 0 <= nums[i] <= 10^9

The output is the number of good subarrays.

The constraints are large. Since there can be up to 100000 elements, there are approximately 5 * 10^9 possible subarrays in the worst case. Any algorithm that explicitly examines every subarray is far too slow.

A useful observation about bitwise OR is that the OR of a set of numbers always contains every bit that appears in any element. Therefore, if the OR is equal to some element x inside the subarray, then x must already contain every bit appearing anywhere in the subarray.

Important edge cases include arrays containing only zeros, arrays where all elements are identical, arrays where every element contributes new bits to the OR, and arrays containing multiple elements that could serve as the OR value for the same subarray.

Approaches

Brute Force

The most direct approach is to enumerate every subarray.

For each starting position, extend the subarray one element at a time while maintaining its OR value. After computing the OR for a subarray, scan the subarray to determine whether that OR value appears among its elements.

This approach is correct because it directly checks the definition of a good subarray.

Unfortunately, there are O(n²) subarrays, and checking whether the OR value appears in the subarray can require another O(n) scan. Even with optimizations, the complexity remains far too large for n = 100000.

Key Insight

Consider an element nums[i] = v.

A subarray is good because of position i if:

OR(subarray) = v

Since the OR contains every bit appearing in the subarray, this condition means:

every element in the subarray must have all of its set bits contained in v

Equivalently:

(x | v) = v

for every element x in the subarray.

Therefore, for each position i, there is a maximal interval around i where every element's bits are a subset of nums[i].

Any subarray that:

• contains i
• stays entirely inside that maximal interval

is automatically good.

This transforms the problem into a geometric counting problem involving intervals and sweep-line processing.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Enumerate every subarray and verify directly
Optimal	O(n log n + 31n)	O(n)	Compute valid intervals and count them using a sweep line and segment tree

Algorithm Walkthrough

Step 1: Compute the maximal valid interval for every position

Let:

nums[i] = v

A position j is incompatible with i if it contains some bit that does not exist in v.

Formally:

nums[j] & ~v != 0

If an incompatible element appears in the subarray, then the OR becomes larger than v, making v unable to be the OR.

For each position i, compute:

• A[i] = leftmost valid boundary
• B[i] = rightmost valid boundary

such that every element in:

[A[i], B[i]]

has all bits contained in nums[i].

Step 2: Compute A[i]

Scan from left to right.

For each bit position, store the most recent index where that bit appeared.

If bit b is absent from nums[i], then any previous occurrence of bit b is incompatible with i.

The nearest incompatible position on the left is therefore:

max(previous occurrence of every forbidden bit)

and:

A[i] = leftIncompatible + 1

Step 3: Compute B[i]

Perform the symmetric computation from right to left.

For each bit position, store the next index where that bit appears.

The nearest incompatible position on the right is:

min(next occurrence of every forbidden bit)

and:

B[i] = rightIncompatible - 1

Step 4: Interpret each position as an interval generator

Position i generates all good subarrays satisfying:

A[i] <= l <= i <= r <= B[i]

For a fixed start index l, position i contributes the interval:

r ∈ [i, B[i]]

whenever:

A[i] <= l <= i

Step 5: Sweep over all starting positions

Process l from left to right.

A position i becomes active when:

l = A[i]

and stops being active when:

l = i + 1

While active, it contributes the interval:

[i, B[i]]

on the r axis.

Step 6: Maintain the union of active intervals

At each sweep position l, we need the number of ending positions r covered by at least one active interval.

This is exactly the size of the union of active intervals.

Use a segment tree supporting:

• range add
• range remove
• query number of covered positions

The number of covered r values is exactly the number of good subarrays starting at l.

Add this value to the answer.

Why it works

For a subarray [l, r] to be good, there must exist a position i inside it whose value equals the subarray OR. This is possible exactly when every element of the subarray has all its bits contained in nums[i].

The interval [A[i], B[i]] is precisely the maximal region where this property holds. Therefore:

[l, r] is good
⇔
∃ i such that A[i] ≤ l ≤ i ≤ r ≤ B[i]

The sweep line counts exactly these pairs (l, r), and the segment tree computes the union of all valid ending positions for each start position. Thus every good subarray is counted once, and no invalid subarray is counted.

Python Solution

class Solution:
    def countGoodSubarrays(self, nums: list[int]) -> int:
        n = len(nums)
        BITS = 31

        left_bound = [0] * n
        right_bound = [0] * n

        prev = [-1] * BITS

        for i, value in enumerate(nums):
            left_incompatible = -1

            for bit in range(BITS):
                if ((value >> bit) & 1) == 0:
                    left_incompatible = max(left_incompatible, prev[bit])

            left_bound[i] = left_incompatible + 1

            for bit in range(BITS):
                if (value >> bit) & 1:
                    prev[bit] = i

        nxt = [n] * BITS

        for i in range(n - 1, -1, -1):
            value = nums[i]
            right_incompatible = n

            for bit in range(BITS):
                if ((value >> bit) & 1) == 0:
                    right_incompatible = min(right_incompatible, nxt[bit])

            right_bound[i] = right_incompatible - 1

            for bit in range(BITS):
                if (value >> bit) & 1:
                    nxt[bit] = i

        add_events = [[] for _ in range(n + 1)]
        remove_events = [[] for _ in range(n + 1)]

        for i in range(n):
            add_events[left_bound[i]].append((i, right_bound[i]))
            remove_events[i + 1].append((i, right_bound[i]))

        size = 1
        while size < n:
            size <<= 1

        cover = [0] * (size * 2)
        covered_count = [0] * (size * 2)

        def update(
            ql: int,
            qr: int,
            delta: int,
            node: int,
            left: int,
            right: int,
        ) -> None:
            if ql > right or qr < left:
                return

            if ql <= left and right <= qr:
                cover[node] += delta
            else:
                mid = (left + right) // 2
                update(ql, qr, delta, node * 2, left, mid)
                update(ql, qr, delta, node * 2 + 1, mid + 1, right)

            if cover[node] > 0:
                covered_count[node] = right - left + 1
            elif left == right:
                covered_count[node] = 0
            else:
                covered_count[node] = (
                    covered_count[node * 2]
                    + covered_count[node * 2 + 1]
                )

        answer = 0

        for start in range(n):
            for left, right in add_events[start]:
                update(left, right, 1, 1, 0, size - 1)

            for left, right in remove_events[start]:
                update(left, right, -1, 1, 0, size - 1)

            answer += covered_count[1]

        return answer

The first phase computes the maximal valid interval for every position. The left-to-right scan determines how far each interval can extend to the left, while the right-to-left scan determines how far it can extend to the right.

The second phase converts each position into a sweep-line event. A position becomes active when the current start index reaches A[i], and it becomes inactive after passing i.

The segment tree maintains the union of all active intervals [i, B[i]]. Its root always stores the number of ending positions currently covered. Summing that value over all start indices yields the total number of good subarrays.

Go Solution

func countGoodSubarrays(nums []int) int64 {
	n := len(nums)
	const BITS = 31

	leftBound := make([]int, n)
	rightBound := make([]int, n)

	prev := make([]int, BITS)
	for i := 0; i < BITS; i++ {
		prev[i] = -1
	}

	for i, v := range nums {
		leftIncompatible := -1

		for b := 0; b < BITS; b++ {
			if ((v >> b) & 1) == 0 {
				if prev[b] > leftIncompatible {
					leftIncompatible = prev[b]
				}
			}
		}

		leftBound[i] = leftIncompatible + 1

		for b := 0; b < BITS; b++ {
			if ((v>>b)&1) == 1 {
				prev[b] = i
			}
		}
	}

	next := make([]int, BITS)
	for i := 0; i < BITS; i++ {
		next[i] = n
	}

	for i := n - 1; i >= 0; i-- {
		v := nums[i]
		rightIncompatible := n

		for b := 0; b < BITS; b++ {
			if ((v >> b) & 1) == 0 {
				if next[b] < rightIncompatible {
					rightIncompatible = next[b]
				}
			}
		}

		rightBound[i] = rightIncompatible - 1

		for b := 0; b < BITS; b++ {
			if ((v>>b)&1) == 1 {
				next[b] = i
			}
		}
	}

	addEvents := make([][][2]int, n+1)
	removeEvents := make([][][2]int, n+1)

	for i := 0; i < n; i++ {
		addEvents[leftBound[i]] = append(
			addEvents[leftBound[i]],
			[2]int{i, rightBound[i]},
		)

		removeEvents[i+1] = append(
			removeEvents[i+1],
			[2]int{i, rightBound[i]},
		)
	}

	size := 1
	for size < n {
		size <<= 1
	}

	cover := make([]int, size*2)
	covered := make([]int, size*2)

	var update func(int, int, int, int, int, int)

	update = func(
		ql int,
		qr int,
		delta int,
		node int,
		left int,
		right int,
	) {
		if ql > right || qr < left {
			return
		}

		if ql <= left && right <= qr {
			cover[node] += delta
		} else {
			mid := (left + right) / 2

			update(ql, qr, delta, node*2, left, mid)
			update(ql, qr, delta, node*2+1, mid+1, right)
		}

		if cover[node] > 0 {
			covered[node] = right - left + 1
		} else if left == right {
			covered[node] = 0
		} else {
			covered[node] =
				covered[node*2] +
					covered[node*2+1]
		}
	}

	var answer int64 = 0

	for start := 0; start < n; start++ {
		for _, interval := range addEvents[start] {
			update(
				interval[0],
				interval[1],
				1,
				1,
				0,
				size-1,
			)
		}

		for _, interval := range removeEvents[start] {
			update(
				interval[0],
				interval[1],
				-1,
				1,
				0,
				size-1,
			)
		}

		answer += int64(covered[1])
	}

	return answer
}

The Go implementation follows the same logic as the Python version. The only notable difference is that the answer is stored as int64, since the number of subarrays can be as large as approximately n(n+1)/2, which exceeds the range of a 32-bit integer.

Worked Examples

Example 1

nums = [4, 2, 3]

First compute valid intervals.

i	nums[i]	A[i]	B[i]
0	4	0	0
1	2	1	1
2	3	1	2

Generated intervals:

Position	Active for l	Interval on r
0	l = 0	[0,0]
1	l = 1	[1,1]
2	l = 1..2	[2,2]

Sweep:

l	Active intervals	Covered r values	Count
0	[0,0]	{0}	1
1	[1,1], [2,2]	{1,2}	2
2	[2,2]	{2}	1

Total:

1 + 2 + 1 = 4

Answer:

4

Example 2

nums = [1, 3, 1]

Intervals:

i	nums[i]	A[i]	B[i]
0	1	0	0
1	3	0	2
2	1	2	2

Generated intervals:

Position	Active for l	Interval on r
0	0	[0,0]
1	0..1	[1,2]
2	2	[2,2]

Sweep:

l	Covered r values	Count
0	{0,1,2}	3
1	{1,2}	2
2	{2}	1

Total:

3 + 2 + 1 = 6

Answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + 31n)	Interval construction is O(31n), sweep-line updates use O(log n) each
Space	O(n)	Event lists and segment tree

The interval computation examines 31 bit positions for every element, which is effectively linear. Each position generates one insertion and one removal event, and each event performs a segment tree range update. Therefore the dominant cost is O(n log n).

Test Cases

sol = Solution().countGoodSubarrays

assert sol([4, 2, 3]) == 4      # example 1
assert sol([1, 3, 1]) == 6      # example 2

assert sol([0]) == 1            # single element zero
assert sol([7]) == 1            # single element non-zero

assert sol([0, 0]) == 3         # every subarray has OR = 0
assert sol([1, 1]) == 3         # identical values

assert sol([1, 2]) == 2         # only singleton subarrays
assert sol([1, 2, 4]) == 3      # every longer subarray invalid

assert sol([3, 1]) == 3         # OR equals first element
assert sol([1, 3]) == 3         # OR equals second element

assert sol([7, 7, 7]) == 6      # every subarray good
assert sol([0, 7, 0]) == 6      # dominant middle element

assert sol([1, 3, 7, 3, 1]) == 15  # every subarray contains a dominating value

assert sol([8, 4, 2, 1]) == 4   # disjoint bits, only singletons

Test	Why
[4,2,3]	Official example
[1,3,1]	Official example
[0]	Smallest input
[7]	Single non-zero element
[0,0]	All zeros
[1,1]	Repeated identical values
[1,2]	No multi-element good subarray
[1,2,4]	OR continually grows
[3,1]	Left element dominates
[1,3]	Right element dominates
[7,7,7]	Every subarray good
[0,7,0]	One element contains all bits
[1,3,7,3,1]	Multiple possible dominators
[8,4,2,1]	Pairwise incompatible bits

Edge Cases

All Elements Are Zero

Consider:

[0, 0, 0]

The OR of any collection of zeros is still zero. Since zero is present in every subarray, every subarray is good.

This case can expose bugs in interval construction because every bit is absent. The implementation handles it correctly because no incompatible bit occurrences exist, so each interval expands across the entire array.

Every Element Uses Disjoint Bits

Consider:

[1, 2, 4, 8]

Any multi-element subarray has an OR strictly larger than every element inside it.

Only singleton subarrays are good.

The interval computation immediately detects incompatibilities caused by forbidden bits, causing every interval to collapse to a single position.

Multiple Dominating Elements

Consider:

[7, 7, 7]

Every subarray contains several valid dominators.

A naive counting strategy based on summing contributions from each position would overcount the same subarray many times.

The sweep-line formulation avoids this problem by counting the union of valid ending positions rather than summing individual position contributions. Each subarray is counted exactly once regardless of how many dominating elements it contains.