Skip to content

Beyond Inequality — Bitmask Chaining

The Comparison Doesn't Have to Be < or >

Everything we've done so far uses simple numerical comparison. Is the new element bigger? Smaller? But the chaining framework from the Maths course told us something more general: a chain is any sequence where each element maintains some relation with the next.

So here's the question: can we run a monotonic stack with a relation other than < or >?

Yes. And this is where things get interesting.

The Eclipse Condition

Let's define what actually makes a monotonic stack work. Forget less-than and greater-than for a moment.

A monotonic stack works whenever you have an eclipse condition: a new element makes an old element permanently irrelevant for all future queries.

In NGE, when a[i] > a[top], the top element is "eclipsed" — no future element will ever be the next greater for a[top], because a[i] already is. So we pop.

The eclipse condition is the core mechanism. And it applies to far more than numerical comparisons.

Bitmask OR Chaining

OR chain on array showing bits turning on

Here's our first non-standard chain.

When you OR two values together, the result can only grow or stay the same. Bits only turn on, never off. So x | y >= x always holds.

Now think about it from the chain's perspective. If you have a value on the stack, and a new element comes along, and nums[top] | nums[i] > nums[top]... that means the new element has bits that the old one doesn't. The old value is no longer the "OR representative" for its range — ORing with the new element changes the result.

That's an eclipse. The old value's contribution is now incomplete. Pop it.

Let's trace this on a small array before looking at code. Take [3, 1, 6, 2]:

Index 0: value 3 = 011 in binary
Index 1: value 1 = 001
Index 2: value 6 = 110
Index 3: value 2 = 010
i nums[i] Binary Stack before Check Action Stack after
0 3 011 [] — Push 0 [0]
1 1 001 [0] 3|1=3=3. No new bits. Extends. Push 1 [0, 1]
2 6 110 [0, 1] 1|6=7>1. New bits! Pop 1. 3|6=7>3. New bits! Pop 0. Push 2 [2]
3 2 010 [2] 6|2=6=6. No new bits. Extends. Push 3 [2, 3]

See what happened at index 2? The value 6 (110) introduced bit patterns that neither 3 (011) nor 1 (001) had in their "high" position. Both got eclipsed — ORing them with 6 changes their value, so they can't represent a stable OR range anymore.

At index 3, value 2 (010) is already a subset of 6's bits (110). No new bits turn on. The chain extends peacefully.

Now let's see this in code:

// OR chain — forward pass
stack<int> st;
vector<int> rightBound(n, n);
for (int i = 0; i < n; i++) {
    while (!st.empty() && (nums[st.top()] | nums[i]) > nums[st.top()]) {
        rightBound[st.top()] = i;
        st.pop();
    }
    st.push(i);
}

If nums[top] | nums[i] == nums[top], the new element adds no new bits. The old value already "contains" the new one in terms of OR. The chain extends — push without popping.

A Real Problem: Counting Good Subarrays

Let's see this in action. The problem: given an array nums, count the number of subarrays where the OR of the entire subarray exists as an actual element in the subarray.

Think about what that means. Take a subarray [3, 5]. The OR is 3 | 5 = 7. Is 7 in the subarray? No. So it's not "good."

Take [3, 7]. The OR is 3 | 7 = 7. Is 7 in the subarray? Yes. Good subarray.

The trick is this: a subarray's OR equals one of its elements if and only if that element already has all the bits that every other element contributes. In other words, there's an element that "dominates" the OR — the OR doesn't add anything new.

For each element nums[i], we want to count how many subarrays containing nums[i] have their OR equal to nums[i]. That element must be the maximum-OR element in the subarray, and every other element in that subarray must be a "subset" of nums[i]'s bits.

We can find the left and right boundaries — how far can we extend from position i before we hit an element that introduces new bits (one that would change the OR beyond nums[i])?

class Solution {
public:
    long long countGoodSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> rightBoundary(n, n), leftBoundary(n, -1);
        stack<int> forwardStack, backwardStack;

        for (int i = 0, j = n - 1; i < n; i++, j--) {
            // Forward pass: find right boundary
            while (!forwardStack.empty() &&
                   (nums[forwardStack.top()] | nums[i]) > nums[forwardStack.top()]) {
                rightBoundary[forwardStack.top()] = i;
                forwardStack.pop();
            }
            forwardStack.push(i);

            // Backward pass: find left boundary
            while (!backwardStack.empty() &&
                   ((nums[backwardStack.top()] | nums[j]) > nums[backwardStack.top()] ||
                    nums[j] == nums[backwardStack.top()])) {
                leftBoundary[backwardStack.top()] = j;
                backwardStack.pop();
            }
            backwardStack.push(j);
        }

        long long totalGood = 0;
        for (int i = 0; i < n; i++) {
            totalGood += 1LL * (rightBoundary[i] - i) * (i - leftBoundary[i]);
        }
        return totalGood;
    }
};

Let's break down what's happening.

Forward stack (left to right): For each element, find the first position to the right where the OR would change. That's the right boundary. This is a standard OR-chain — pop when nums[top] | nums[i] > nums[top].

Backward stack (right to left): Same idea, but finding the left boundary. The extra condition nums[j] == nums[backwardStack.top()] handles duplicates — when two elements are equal, we want the leftmost one to "own" the range to avoid double-counting.

Contribution counting: For each element i, the number of subarrays where nums[i] is the OR-dominator is (rightBoundary[i] - i) * (i - leftBoundary[i]). This is the standard left-right boundary multiplication trick. The element can be paired with any left endpoint in (leftBoundary[i], i] and any right endpoint in [i, rightBoundary[i]).

The Left-Right Boundary Technique

This is worth its own callout because it shows up constantly.

When you have a monotonic stack that computes left and right boundaries for each element, the number of subarrays where element i is the "answer" (the max, the min, the OR-dominator, whatever) is:

count_i = (i - leftBound[i]) * (rightBound[i] - i)

Why? Because: - There are (i - leftBound[i]) choices for the left endpoint (from leftBound[i] + 1 to i) - There are (rightBound[i] - i) choices for the right endpoint (from i to rightBound[i] - 1) - Each combination gives a valid subarray where element i plays the role we care about

This is the same technique used in "sum of subarray minimums," "sum of subarray maximums," and many other contribution-counting problems.

GCD Chaining

Bitwise OR can only grow. GCD has the opposite behavior — it can only shrink (or stay the same).

When gcd(nums[top], nums[i]) < nums[top], the top element's GCD contribution has changed. It's been eclipsed. Pop it.

stack<int> st;
vector<int> rightBound(n, n);
for (int i = 0; i < n; i++) {
    while (!st.empty() && __gcd(nums[st.top()], nums[i]) < nums[st.top()]) {
        rightBound[st.top()] = i;
        st.pop();
    }
    st.push(i);
}

If gcd(nums[top], nums[i]) == nums[top], that means nums[top] divides nums[i]. The new element doesn't change the GCD — the chain extends.

GCD chains are useful for problems like "count subarrays where GCD equals 1" or "find the longest subarray with GCD > 1."

The General Pattern

Here's what to take away from this lesson.

The monotonic stack is not really about "increasing" or "decreasing." It's about maintaining a chain where each element is still "relevant." The eclipse condition determines what makes an element irrelevant:

Relation Eclipse Condition Chain Extends When
< / > New element is bigger/smaller Ordering maintained
Bitwise OR New element adds new bits New element is a subset
GCD New element reduces GCD New element is a multiple
LCM New element increases LCM New element is a divisor

The structure is always the same: scan, pop eclipsed elements, push, repeat. O(N) amortized. The only thing that changes is the condition inside the while loop.

When you encounter a problem and you notice that some property of a range can only change in one direction (only grow, only shrink, only gain bits), think about whether a stack-based chain can track it. Chances are good that it can.

Try It

The starter code tackles a problem that combines stacks with bitwise AND: count subarrays where the bitwise AND equals the minimum element. It uses PSE and NSE to find boundaries where each element is the minimum, then checks the AND condition within those boundaries.

Test it with:

5
7 3 3 7 5

Then try to think about why AND and MIN work together here — both operations can only decrease as the subarray grows. When do they decrease at the same rate?

Problems

Problem Link Difficulty
LC 2537 — Count Good Subarrays leetcode.com/problems/count-good-subarrays Medium
LC 496 — Next Greater Element I leetcode.com/problems/next-greater-element-i Easy
LC 503 — Next Greater Element II leetcode.com/problems/next-greater-element-ii Medium
LC 739 — Daily Temperatures leetcode.com/problems/daily-temperatures Medium
CSES 1645 — Nearest Smaller Values cses.fi/problemset/task/1645 Medium
LC 1944 — Visible People in Queue leetcode.com/problems/number-of-visible-people-in-a-queue Hard