3845. Maximum Subarray XOR with Bounded Range

HardBit ManipulationTrieQueueArrayPrefix SumSliding WindowMonotonic Queue

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a non-negative integer array nums and an integer k.

You must select a subarray of nums (a contiguous, non-empty portion of the array) such that the difference between its maximum and minimum elements is at most k. In other words, for the chosen subarray, the condition max(subarray) - min(subarray) <= k must hold.

For each valid subarray that satisfies this constraint, its value is defined as the bitwise XOR of all elements contained within that subarray.

Your task is to return an integer denoting the maximum possible value among all valid subarrays.

For example, if a subarray consists of the elements [a, b, c], then its value is a ^ b ^ c, and this subarray is only considered valid if the difference between its largest and smallest element does not exceed k. Among all such valid subarrays, you must find the one whose XOR value is the greatest.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Sliding Window?

This problem maps to Sliding Window through a short path in the full flowchart.

Sliding window with monotonic deques maintains the max-min constraint, while a binary Trie queries max XOR within the window.

Open in Flowchart

Intuition

The problem combines two seemingly different challenges: maintaining a constraint on a subarray's max - min, and computing the maximum XOR of a subarray. Let's break these down separately and then see how they fit together.

Handling the XOR of a subarray.

A classic trick for subarray XOR is the prefix XOR array. If we define prefixXor[i] as the XOR of all elements from index 0 up to i - 1, then the XOR of any subarray nums[l..r] can be written as:

nums[l] ^ nums[l+1] ^ ... ^ nums[r] = prefixXor[r + 1] ^ prefixXor[l]

This works because XOR is its own inverse, so the common prefix prefixXor[l] cancels out. This means that finding the maximum XOR of a subarray ending at position r reduces to: pick some earlier prefix prefixXor[l] and maximize prefixXor[r + 1] ^ prefixXor[l].

To maximize the XOR of a fixed value against a collection of stored values, we use a binary Trie. We insert prefix values bit by bit (from the highest bit to the lowest), and when querying we greedily try to go down the opposite bit at each step, since differing bits contribute 1 to the XOR. This greedy choice from the most significant bit guarantees the largest possible XOR result. Since the values are bounded, we only need a fixed number of bits (here, bits 14 down to 0).

Handling the max - min <= k constraint.

This part naturally suggests a sliding window. As we extend the window's right boundary, the maximum and minimum can only change in predictable ways. When the window's max - min exceeds k, we must shrink it from the left until the constraint holds again.

To efficiently track the maximum and minimum inside the window, we use two monotonic deques:

One decreasing deque whose front always gives the current window's maximum.
One increasing deque whose front always gives the current window's minimum.

This lets us check max - min in constant time and slide the window without rescanning elements.

Putting them together.

The key insight is that a valid subarray nums[l..r] corresponds to choosing two prefix indices l and r + 1, where the original index l must lie within the current valid window. So as the sliding window moves, the set of valid left endpoints l corresponds exactly to the set of prefix values we should keep available in the Trie.

This gives a clean strategy:

When the window shrinks and left advances, we remove prefixXor[left] from the Trie (decrement its count), since that left endpoint is no longer valid.
For each new right boundary right, after fixing the window, we query the Trie with prefixXor[right + 1] to find the best XOR achievable with any valid left endpoint.
We then insert prefixXor[right + 1] so it becomes available as a left endpoint for future positions.

Because each prefix value may be added and later removed, the Trie nodes carry a count field rather than a simple boolean flag. This count tells us how many active prefixes still pass through a node, so during a query we only follow branches with count > 0.

By combining the prefix XOR trick, the binary Trie for maximizing XOR, and the monotonic-deque sliding window for the max - min constraint, every element is processed a constant number of times, leading to an efficient overall solution.

Pattern Learn more about Trie, Queue, Prefix Sum, Sliding Window and Monotonic Queue patterns.

Solution Approach

The implementation weaves together three components: a binary Trie, a prefix XOR array, and two monotonic deques forming a sliding window. Let's walk through each piece and how the main loop coordinates them.

The Trie structure.

We define a TrieNode with:

children[2] — two pointers representing the 0 and 1 bit branches.
count — how many active prefix values currently pass through this node.

The count field is essential because prefixes get added and removed as the window slides, so a plain on/off flag would not suffice.

class TrieNode {
    TrieNode[] children = new TrieNode[2];
    int count = 0;
}

Inserting and removing prefixes.

The updateTrie(value, delta) method walks from bit 14 down to bit 0, creating child nodes as needed and adjusting count by delta. Passing delta = 1 inserts a value; passing delta = -1 removes it. We only need 15 bits because the prefix values stay within a bounded range.

void updateTrie(int value, int delta) {
    TrieNode current = root;
    for (int bit = 14; bit >= 0; bit--) {
        int currentBit = (value >> bit) & 1;
        if (current.children[currentBit] == null) {
            current.children[currentBit] = new TrieNode();
        }
        current = current.children[currentBit];
        current.count += delta;
    }
}

Querying for maximum XOR.

The getMaxXor(value) method greedily maximizes the XOR. At each bit, it prefers the opposite bit branch, since matching opposite bits sets that bit to 1 in the XOR. It only takes that branch if it exists and its count > 0 (meaning at least one active prefix uses it). If the bit is set, we add 1 << bit to the answer.

int getMaxXor(int value) {
    TrieNode current = root;
    int maxXor = 0;
    for (int bit = 14; bit >= 0; bit--) {
        int currentBit = (value >> bit) & 1;
        int oppositeBit = 1 - currentBit;
        if (current.children[oppositeBit] != null && current.children[oppositeBit].count > 0) {
            maxXor |= (1 << bit);
            current = current.children[oppositeBit];
        } else {
            current = current.children[currentBit];
        }
    }
    return maxXor;
}

Building the prefix XOR array.

We compute prefixXor[i + 1] = prefixXor[i] ^ nums[i], so the XOR of subarray nums[l..r] equals prefixXor[r + 1] ^ prefixXor[l].

int[] prefixXor = new int[length + 1];
for (int i = 0; i < length; i++) {
    prefixXor[i + 1] = prefixXor[i] ^ nums[i];
}

The sliding window with monotonic deques.

We maintain two deques storing indices into nums:

maxDeque is kept decreasing, so its front holds the index of the window's maximum.
minDeque is kept increasing, so its front holds the index of the window's minimum.

Before adding the new index right, we pop from the back of each deque any element that violates the monotonic order:

while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[right]) {
    maxDeque.pollLast();
}
while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[right]) {
    minDeque.pollLast();
}
maxDeque.addLast(right);
minDeque.addLast(right);

Shrinking the window.

After adding right, if nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit, the window is invalid. We advance left, popping the deque fronts when they equal left (they leave the window), and crucially we remove prefixXor[left] from the Trie because that left endpoint is no longer usable:

while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
    if (maxDeque.peekFirst() == left) maxDeque.pollFirst();
    if (minDeque.peekFirst() == left) minDeque.pollFirst();
    updateTrie(prefixXor[left], -1);
    left++;
}

Tying it together in the main loop.

Before the loop, we seed the Trie with prefixXor[0], since the prefix at index 0 is a valid left endpoint for subarrays starting at index 0.

updateTrie(prefixXor[0], 1);

Then for each right:

Update the deques and shrink the window so the max - min <= limit constraint holds. After shrinking, the Trie contains exactly the prefixes prefixXor[left..right] that correspond to valid left endpoints.
Query getMaxXor(prefixXor[right + 1]) to get the best subarray XOR ending at right, and update result.
Insert prefixXor[right + 1] into the Trie so it becomes an available left endpoint for future right boundaries.

result = Math.max(result, getMaxXor(prefixXor[right + 1]));
updateTrie(prefixXor[right + 1], 1);

Why this is correct and efficient.

The window guarantees that only valid left endpoints (those satisfying the max - min constraint) remain in the Trie at the moment of each query. The Trie then finds, in O(15) per query, the prefix that maximizes the XOR against prefixXor[right + 1]. Each index enters and leaves the deques and the Trie at most once, so the time complexity is O(n * B) where B = 15 is the number of bits, effectively linear in n. The space is dominated by the Trie, bounded by O(n * B) nodes.

Example Walkthrough

Let's trace through a small example to see how the three components — prefix XOR, the binary Trie, and the sliding window — work together.

**Input:** `nums = [1, 2, 3, 1]`, `k = 2`

**Step 0: Build the prefix XOR array.**

We compute `prefixXor[i + 1] = prefixXor[i] ^ nums[i]`:

| index i      | 0 | 1 | 2 | 3 | 4 |
|--------------|---|---|---|---|---|
| prefixXor[i] | 0 | 1 | 3 | 0 | 1 |

- `prefixXor[0] = 0`
- `prefixXor[1] = 0 ^ 1 = 1`
- `prefixXor[2] = 1 ^ 2 = 3`
- `prefixXor[3] = 3 ^ 3 = 0`
- `prefixXor[4] = 0 ^ 1 = 1`

Recall the XOR of subarray `nums[l..r]` equals `prefixXor[r + 1] ^ prefixXor[l]`.

**Seeding the Trie.**

Before the loop, insert `prefixXor[0] = 0`. The Trie now holds `{0}`, marking index `0` as a valid left endpoint.

`left = 0`, `result = 0`.

---

**right = 0** (element `nums[0] = 1`)

- Update deques. Both deques become `[0]`.
  - `maxDeque` front → `nums[0] = 1`, `minDeque` front → `nums[0] = 1`.
- Check constraint: `1 - 1 = 0 <= 2` ✓. No shrinking. Trie still holds `{0}`.
- Query `getMaxXor(prefixXor[1]) = getMaxXor(1)`. Best stored prefix is `0`, giving `1 ^ 0 = 1`.
  - This corresponds to subarray `nums[0..0] = [1]`, XOR = `1`. ✓
- `result = max(0, 1) = 1`.
- Insert `prefixXor[1] = 1`. Trie holds `{0, 1}`.

---

**right = 1** (element `nums[1] = 2`)

- Update deques.
  - `maxDeque`: pop `0` since `nums[0]=1 <= nums[1]=2`, then add `1` → `[1]`. Front max = `2`.
  - `minDeque`: `nums[0]=1` is not `>= nums[1]=2`, so keep `0`, add `1` → `[0, 1]`. Front min = `1`.
- Check constraint: `2 - 1 = 1 <= 2` ✓. No shrinking. Trie holds `{0, 1}`.
- Query `getMaxXor(prefixXor[2]) = getMaxXor(3)`.
  - vs `0`: `3 ^ 0 = 3`; vs `1`: `3 ^ 1 = 2`. Best = `3`.
  - This corresponds to subarray `nums[0..1] = [1, 2]`, XOR = `3`. ✓ (window valid since max-min = 1)
- `result = max(1, 3) = 3`.
- Insert `prefixXor[2] = 3`. Trie holds `{0, 1, 3}`.

---

**right = 2** (element `nums[2] = 3`)

- Update deques.
  - `maxDeque`: pop `1` since `nums[1]=2 <= nums[2]=3`, add `2` → `[2]`. Front max = `3`.
  - `minDeque`: `nums[0]=1`, `nums[1]=2` both `< 3`, add `2` → `[0, 1, 2]`. Front min = `1`.
- Check constraint: `3 - 1 = 2 <= 2` ✓. No shrinking. Trie holds `{0, 1, 3}`.
- Query `getMaxXor(prefixXor[3]) = getMaxXor(0)`.
  - vs `0`: `0`; vs `1`: `1`; vs `3`: `3`. Best = `3`.
  - This corresponds to subarray `nums[2..2] = [3]`, XOR = `3` (left endpoint = prefix `3`). ✓
- `result = max(3, 3) = 3`.
- Insert `prefixXor[3] = 0`. Trie holds `{0, 0, 1, 3}` (the value `0` now has count 2).

---

**right = 3** (element `nums[3] = 1`)

- Update deques.
  - `maxDeque`: `nums[2]=3 > nums[3]=1`, keep, add `3` → `[2, 3]`. Front max = `3`.
  - `minDeque`: pop `2`(`3>=1`), pop `1`(`2>=1`), pop `0`(`1>=1`), then add `3` → `[3]`. Front min = `1`.
- Check constraint: `3 - 1 = 2 <= 2` ✓. No shrinking. Trie still holds `{0, 0, 1, 3}`.

  *(Note: although `left` has not advanced, all the prefixes still represent valid left endpoints for subarrays ending at index 3, since the window `[0..3]` would have max-min = 3-1 = 2 ≤ 2.)*
- Query `getMaxXor(prefixXor[4]) = getMaxXor(1)`.
  - vs `0`: `1`; vs `1`: `0`; vs `3`: `2`. Best = `2`.
  - This corresponds to subarray `nums[2..3] = [3, 1]` (left = prefix `3`), XOR = `3 ^ 1 = 2`. ✓
- `result = max(3, 2) = 3`.
- Insert `prefixXor[4] = 1`.

---

**Final answer:** `result = 3`.

The maximum-XOR valid subarray is `[1, 2]` (or `[3]`), both yielding XOR `3` while satisfying `max - min <= 2`.

**Illustrating the shrink path.** Had `k` been smaller, say `k = 1`, then at `right = 2` the window `[1,2,3]` would violate `3 - 1 = 2 > 1`. We'd advance `left` from `0`: pop `minDeque` front `0`, call `updateTrie(prefixXor[0], -1)` to remove `0` from the Trie, and recheck. This shows how invalid left endpoints are purged from the Trie precisely as the window shrinks.

Solution Implementation

1from collections import deque
2
3
4class Solution:
5
6    class TrieNode:
7        """
8        Trie node for storing prefix-XOR values in their binary representation.
9        Each node has two branches (bit 0 and bit 1) and a count of how many
10        active prefix values currently pass through this node.
11        """
12
13        def __init__(self):
14            self.children = [None, None]  # index 0 -> bit 0, index 1 -> bit 1
15            self.count = 0                # number of active values through this node
16
17    # Number of bits to consider. nums[i] up to ~2^15, so 15 bits (indices 14..0) suffice.
18    MAX_BIT = 14
19
20    def __init__(self):
21        self.root = self.TrieNode()
22
23    def update_trie(self, value: int, delta: int) -> None:
24        """
25        Insert (delta = +1) or remove (delta = -1) a prefix-XOR value in the trie.
26        The count along each visited path is adjusted by delta, which lets us
27        "delete" values logically without rebuilding the structure.
28
29        :param value: the prefix-XOR value to insert or remove
30        :param delta: +1 to insert, -1 to remove
31        """
32        current = self.root
33        for bit in range(self.MAX_BIT, -1, -1):
34            current_bit = (value >> bit) & 1
35            if current.children[current_bit] is None:
36                current.children[current_bit] = self.TrieNode()
37            current = current.children[current_bit]
38            current.count += delta
39
40    def get_max_xor(self, value: int) -> int:
41        """
42        Compute the maximum XOR achievable between the given value and any value
43        currently active in the trie. At each bit we greedily try to take the
44        opposite bit (which sets that bit in the XOR result) if such a branch
45        still has active values.
46
47        :param value: the value to XOR against the active trie entries
48        :return: the maximum XOR result
49        """
50        current = self.root
51        max_xor = 0
52
53        for bit in range(self.MAX_BIT, -1, -1):
54            current_bit = (value >> bit) & 1
55            opposite_bit = 1 - current_bit
56
57            # Prefer the opposite branch to maximize the XOR at this bit.
58            if current.children[opposite_bit] is not None and current.children[opposite_bit].count > 0:
59                max_xor |= (1 << bit)
60                current = current.children[opposite_bit]
61            else:
62                # Otherwise we must follow the same-bit branch (no XOR gain here).
63                current = current.children[current_bit]
64
65        return max_xor
66
67    def maxXor(self, nums: list[int], limit: int) -> int:
68        """
69        Find the maximum subarray XOR such that within the subarray
70        (max element - min element) <= limit.
71
72        :param nums: the input array
73        :param limit: the maximum allowed difference between max and min in a window
74        :return: the maximum subarray XOR satisfying the constraint
75        """
76        length = len(nums)
77
78        # prefix_xor[i] = XOR of nums[0..i-1]; prefix_xor[0] = 0.
79        # XOR of subarray nums[l..r] = prefix_xor[r + 1] ^ prefix_xor[l].
80        prefix_xor = [0] * (length + 1)
81        for i in range(length):
82            prefix_xor[i + 1] = prefix_xor[i] ^ nums[i]
83
84        # Monotonic deques over indices:
85        #   max_deque: decreasing values -> front is the window maximum.
86        #   min_deque: increasing values -> front is the window minimum.
87        max_deque = deque()
88        min_deque = deque()
89
90        left = 0     # left boundary of the current valid window
91        result = 0   # best XOR found so far
92
93        # The trie holds active prefix_xor values for indices in [left, right + 1].
94        # Seed it with prefix_xor[0] so single-element subarrays are considered.
95        self.update_trie(prefix_xor[0], 1)
96
97        for right in range(length):
98
99            # Maintain a decreasing deque so its front always holds the max value's index.
100            while max_deque and nums[max_deque[-1]] <= nums[right]:
101                max_deque.pop()
102
103            # Maintain an increasing deque so its front always holds the min value's index.
104            while min_deque and nums[min_deque[-1]] >= nums[right]:
105                min_deque.pop()
106
107            max_deque.append(right)
108            min_deque.append(right)
109
110            # Shrink the window from the left while the max-min spread exceeds limit.
111            while nums[max_deque[0]] - nums[min_deque[0]] > limit:
112
113                # Drop the left index from the deques if it is at their front.
114                if max_deque[0] == left:
115                    max_deque.popleft()
116                if min_deque[0] == left:
117                    min_deque.popleft()
118
119                # Remove the prefix value that leaves the window.
120                self.update_trie(prefix_xor[left], -1)
121                left += 1
122
123            # Best XOR ending at 'right' = prefix_xor[right + 1] XOR some active prefix.
124            result = max(result, self.get_max_xor(prefix_xor[right + 1]))
125
126            # Add the current prefix so future windows can pair with it.
127            self.update_trie(prefix_xor[right + 1], 1)
128
129        return result
130

1class Solution {
2
3    /**
4     * Trie node for storing prefix-XOR values in their binary representation.
5     * Each node has two branches (bit 0 and bit 1) and a count of how many
6     * active prefix values currently pass through this node.
7     */
8    private class TrieNode {
9        TrieNode[] children = new TrieNode[2]; // index 0 -> bit 0, index 1 -> bit 1
10        int count = 0;                         // number of active values through this node
11    }
12
13    private final TrieNode root = new TrieNode();
14
15    // Number of bits to consider. nums[i] up to ~2^15, so 15 bits (indices 14..0) suffice.
16    private static final int MAX_BIT = 14;
17
18    /**
19     * Insert (delta = +1) or remove (delta = -1) a prefix-XOR value in the trie.
20     * The count along each visited path is adjusted by delta, which lets us
21     * "delete" values logically without rebuilding the structure.
22     *
23     * @param value the prefix-XOR value to insert or remove
24     * @param delta +1 to insert, -1 to remove
25     */
26    private void updateTrie(int value, int delta) {
27        TrieNode current = root;
28        for (int bit = MAX_BIT; bit >= 0; bit--) {
29            int currentBit = (value >> bit) & 1;
30            if (current.children[currentBit] == null) {
31                current.children[currentBit] = new TrieNode();
32            }
33            current = current.children[currentBit];
34            current.count += delta;
35        }
36    }
37
38    /**
39     * Compute the maximum XOR achievable between the given value and any value
40     * currently active in the trie. At each bit we greedily try to take the
41     * opposite bit (which sets that bit in the XOR result) if such a branch
42     * still has active values.
43     *
44     * @param value the value to XOR against the active trie entries
45     * @return the maximum XOR result
46     */
47    private int getMaxXor(int value) {
48        TrieNode current = root;
49        int maxXor = 0;
50
51        for (int bit = MAX_BIT; bit >= 0; bit--) {
52            int currentBit = (value >> bit) & 1;
53            int oppositeBit = 1 - currentBit;
54
55            // Prefer the opposite branch to maximize the XOR at this bit.
56            if (current.children[oppositeBit] != null && current.children[oppositeBit].count > 0) {
57                maxXor |= (1 << bit);
58                current = current.children[oppositeBit];
59            } else {
60                // Otherwise we must follow the same-bit branch (no XOR gain here).
61                current = current.children[currentBit];
62            }
63        }
64
65        return maxXor;
66    }
67
68    /**
69     * Find the maximum subarray XOR such that within the subarray
70     * (max element - min element) <= limit.
71     *
72     * @param nums  the input array
73     * @param limit the maximum allowed difference between max and min in a window
74     * @return the maximum subarray XOR satisfying the constraint
75     */
76    public int maxXor(int[] nums, int limit) {
77        int length = nums.length;
78
79        // prefixXor[i] = XOR of nums[0..i-1]; prefixXor[0] = 0.
80        // XOR of subarray nums[l..r] = prefixXor[r + 1] ^ prefixXor[l].
81        int[] prefixXor = new int[length + 1];
82        for (int i = 0; i < length; i++) {
83            prefixXor[i + 1] = prefixXor[i] ^ nums[i];
84        }
85
86        // Monotonic deques over indices:
87        //   maxDeque: decreasing values -> front is the window maximum.
88        //   minDeque: increasing values -> front is the window minimum.
89        Deque<Integer> maxDeque = new ArrayDeque<>();
90        Deque<Integer> minDeque = new ArrayDeque<>();
91
92        int left = 0;     // left boundary of the current valid window
93        int result = 0;   // best XOR found so far
94
95        // The trie holds active prefixXor values for indices in [left, right + 1].
96        // Seed it with prefixXor[0] so single-element subarrays are considered.
97        updateTrie(prefixXor[0], 1);
98
99        for (int right = 0; right < length; right++) {
100
101            // Maintain a decreasing deque so its front always holds the max value's index.
102            while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[right]) {
103                maxDeque.pollLast();
104            }
105
106            // Maintain an increasing deque so its front always holds the min value's index.
107            while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[right]) {
108                minDeque.pollLast();
109            }
110
111            maxDeque.addLast(right);
112            minDeque.addLast(right);
113
114            // Shrink the window from the left while the max-min spread exceeds limit.
115            while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
116
117                // Drop the left index from the deques if it is at their front.
118                if (maxDeque.peekFirst() == left) {
119                    maxDeque.pollFirst();
120                }
121                if (minDeque.peekFirst() == left) {
122                    minDeque.pollFirst();
123                }
124
125                // Remove the prefix value that leaves the window.
126                updateTrie(prefixXor[left], -1);
127                left++;
128            }
129
130            // Best XOR ending at 'right' = prefixXor[right + 1] XOR some active prefix.
131            result = Math.max(result, getMaxXor(prefixXor[right + 1]));
132
133            // Add the current prefix so future windows can pair with it.
134            updateTrie(prefixXor[right + 1], 1);
135        }
136
137        return result;
138    }
139}
140

1class Solution {
2private:
3    /**
4     * Trie node for storing prefix-XOR values in their binary representation.
5     * Each node has two branches (bit 0 and bit 1) and a count of how many
6     * active prefix values currently pass through this node.
7     */
8    struct TrieNode {
9        TrieNode* children[2] = {nullptr, nullptr}; // index 0 -> bit 0, index 1 -> bit 1
10        int count = 0;                              // number of active values through this node
11    };
12
13    TrieNode* root = new TrieNode();
14
15    // Number of bits to consider. nums[i] up to ~2^15, so 15 bits (indices 14..0) suffice.
16    static constexpr int MAX_BIT = 14;
17
18    /**
19     * Insert (delta = +1) or remove (delta = -1) a prefix-XOR value in the trie.
20     * The count along each visited path is adjusted by delta, which lets us
21     * "delete" values logically without rebuilding the structure.
22     *
23     * @param value the prefix-XOR value to insert or remove
24     * @param delta +1 to insert, -1 to remove
25     */
26    void updateTrie(int value, int delta) {
27        TrieNode* current = root;
28        for (int bit = MAX_BIT; bit >= 0; bit--) {
29            int currentBit = (value >> bit) & 1;
30            if (current->children[currentBit] == nullptr) {
31                current->children[currentBit] = new TrieNode();
32            }
33            current = current->children[currentBit];
34            current->count += delta;
35        }
36    }
37
38    /**
39     * Compute the maximum XOR achievable between the given value and any value
40     * currently active in the trie. At each bit we greedily try to take the
41     * opposite bit (which sets that bit in the XOR result) if such a branch
42     * still has active values.
43     *
44     * @param value the value to XOR against the active trie entries
45     * @return the maximum XOR result
46     */
47    int getMaxXor(int value) {
48        TrieNode* current = root;
49        int maxXor = 0;
50
51        for (int bit = MAX_BIT; bit >= 0; bit--) {
52            int currentBit = (value >> bit) & 1;
53            int oppositeBit = 1 - currentBit;
54
55            // Prefer the opposite branch to maximize the XOR at this bit.
56            if (current->children[oppositeBit] != nullptr && current->children[oppositeBit]->count > 0) {
57                maxXor |= (1 << bit);
58                current = current->children[oppositeBit];
59            } else {
60                // Otherwise we must follow the same-bit branch (no XOR gain here).
61                current = current->children[currentBit];
62            }
63        }
64
65        return maxXor;
66    }
67
68public:
69    /**
70     * Find the maximum subarray XOR such that within the subarray
71     * (max element - min element) <= limit.
72     *
73     * @param nums  the input array
74     * @param limit the maximum allowed difference between max and min in a window
75     * @return the maximum subarray XOR satisfying the constraint
76     */
77    int maxXor(vector<int>& nums, int limit) {
78        int length = nums.size();
79
80        // prefixXor[i] = XOR of nums[0..i-1]; prefixXor[0] = 0.
81        // XOR of subarray nums[l..r] = prefixXor[r + 1] ^ prefixXor[l].
82        vector<int> prefixXor(length + 1, 0);
83        for (int i = 0; i < length; i++) {
84            prefixXor[i + 1] = prefixXor[i] ^ nums[i];
85        }
86
87        // Monotonic deques over indices:
88        //   maxDeque: decreasing values -> front is the window maximum.
89        //   minDeque: increasing values -> front is the window minimum.
90        deque<int> maxDeque;
91        deque<int> minDeque;
92
93        int left = 0;     // left boundary of the current valid window
94        int result = 0;   // best XOR found so far
95
96        // The trie holds active prefixXor values for indices in [left, right + 1].
97        // Seed it with prefixXor[0] so single-element subarrays are considered.
98        updateTrie(prefixXor[0], 1);
99
100        for (int right = 0; right < length; right++) {
101
102            // Maintain a decreasing deque so its front always holds the max value's index.
103            while (!maxDeque.empty() && nums[maxDeque.back()] <= nums[right]) {
104                maxDeque.pop_back();
105            }
106
107            // Maintain an increasing deque so its front always holds the min value's index.
108            while (!minDeque.empty() && nums[minDeque.back()] >= nums[right]) {
109                minDeque.pop_back();
110            }
111
112            maxDeque.push_back(right);
113            minDeque.push_back(right);
114
115            // Shrink the window from the left while the max-min spread exceeds limit.
116            while (nums[maxDeque.front()] - nums[minDeque.front()] > limit) {
117
118                // Drop the left index from the deques if it is at their front.
119                if (maxDeque.front() == left) {
120                    maxDeque.pop_front();
121                }
122                if (minDeque.front() == left) {
123                    minDeque.pop_front();
124                }
125
126                // Remove the prefix value that leaves the window.
127                updateTrie(prefixXor[left], -1);
128                left++;
129            }
130
131            // Best XOR ending at 'right' = prefixXor[right + 1] XOR some active prefix.
132            result = max(result, getMaxXor(prefixXor[right + 1]));
133
134            // Add the current prefix so future windows can pair with it.
135            updateTrie(prefixXor[right + 1], 1);
136        }
137
138        return result;
139    }
140};
141

1/**
2 * Trie node for storing prefix-XOR values in their binary representation.
3 * Each node has two branches (bit 0 and bit 1) and a count of how many
4 * active prefix values currently pass through this node.
5 */
6interface TrieNode {
7    children: (TrieNode | null)[]; // index 0 -> bit 0, index 1 -> bit 1
8    count: number;                 // number of active values through this node
9}
10
11/**
12 * Factory helper to create an empty trie node with no children
13 * and a zero active count.
14 */
15function createTrieNode(): TrieNode {
16    return { children: [null, null], count: 0 };
17}
18
19// Root of the trie holding all active prefix-XOR values.
20let root: TrieNode = createTrieNode();
21
22// Number of bits to consider. nums[i] up to ~2^15, so 15 bits (indices 14..0) suffice.
23const MAX_BIT = 14;
24
25/**
26 * Insert (delta = +1) or remove (delta = -1) a prefix-XOR value in the trie.
27 * The count along each visited path is adjusted by delta, which lets us
28 * "delete" values logically without rebuilding the structure.
29 *
30 * @param value the prefix-XOR value to insert or remove
31 * @param delta +1 to insert, -1 to remove
32 */
33function updateTrie(value: number, delta: number): void {
34    let current: TrieNode = root;
35    for (let bit = MAX_BIT; bit >= 0; bit--) {
36        const currentBit = (value >> bit) & 1;
37        if (current.children[currentBit] === null) {
38            current.children[currentBit] = createTrieNode();
39        }
40        current = current.children[currentBit]!;
41        current.count += delta;
42    }
43}
44
45/**
46 * Compute the maximum XOR achievable between the given value and any value
47 * currently active in the trie. At each bit we greedily try to take the
48 * opposite bit (which sets that bit in the XOR result) if such a branch
49 * still has active values.
50 *
51 * @param value the value to XOR against the active trie entries
52 * @return the maximum XOR result
53 */
54function getMaxXor(value: number): number {
55    let current: TrieNode = root;
56    let maxXorValue = 0;
57
58    for (let bit = MAX_BIT; bit >= 0; bit--) {
59        const currentBit = (value >> bit) & 1;
60        const oppositeBit = 1 - currentBit;
61
62        // Prefer the opposite branch to maximize the XOR at this bit.
63        const oppositeChild = current.children[oppositeBit];
64        if (oppositeChild !== null && oppositeChild.count > 0) {
65            maxXorValue |= (1 << bit);
66            current = oppositeChild;
67        } else {
68            // Otherwise we must follow the same-bit branch (no XOR gain here).
69            current = current.children[currentBit]!;
70        }
71    }
72
73    return maxXorValue;
74}
75
76/**
77 * Find the maximum subarray XOR such that within the subarray
78 * (max element - min element) <= limit.
79 *
80 * @param nums  the input array
81 * @param limit the maximum allowed difference between max and min in a window
82 * @return the maximum subarray XOR satisfying the constraint
83 */
84function maxXor(nums: number[], limit: number): number {
85    // Reset the shared trie so repeated calls start from a clean state.
86    root = createTrieNode();
87
88    const length = nums.length;
89
90    // prefixXor[i] = XOR of nums[0..i-1]; prefixXor[0] = 0.
91    // XOR of subarray nums[l..r] = prefixXor[r + 1] ^ prefixXor[l].
92    const prefixXor = new Array<number>(length + 1).fill(0);
93    for (let i = 0; i < length; i++) {
94        prefixXor[i + 1] = prefixXor[i] ^ nums[i];
95    }
96
97    // Monotonic deques over indices (implemented as arrays):
98    //   maxDeque: decreasing values -> front is the window maximum.
99    //   minDeque: increasing values -> front is the window minimum.
100    const maxDeque: number[] = [];
101    const minDeque: number[] = [];
102
103    let left = 0;     // left boundary of the current valid window
104    let result = 0;   // best XOR found so far
105
106    // The trie holds active prefixXor values for indices in [left, right + 1].
107    // Seed it with prefixXor[0] so single-element subarrays are considered.
108    updateTrie(prefixXor[0], 1);
109
110    for (let right = 0; right < length; right++) {
111
112        // Maintain a decreasing deque so its front always holds the max value's index.
113        while (maxDeque.length > 0 && nums[maxDeque[maxDeque.length - 1]] <= nums[right]) {
114            maxDeque.pop();
115        }
116
117        // Maintain an increasing deque so its front always holds the min value's index.
118        while (minDeque.length > 0 && nums[minDeque[minDeque.length - 1]] >= nums[right]) {
119            minDeque.pop();
120        }
121
122        maxDeque.push(right);
123        minDeque.push(right);
124
125        // Shrink the window from the left while the max-min spread exceeds limit.
126        while (nums[maxDeque[0]] - nums[minDeque[0]] > limit) {
127
128            // Drop the left index from the deques if it is at their front.
129            if (maxDeque[0] === left) {
130                maxDeque.shift();
131            }
132            if (minDeque[0] === left) {
133                minDeque.shift();
134            }
135
136            // Remove the prefix value that leaves the window.
137            updateTrie(prefixXor[left], -1);
138            left++;
139        }
140
141        // Best XOR ending at 'right' = prefixXor[right + 1] XOR some active prefix.
142        result = Math.max(result, getMaxXor(prefixXor[right + 1]));
143
144        // Add the current prefix so future windows can pair with it.
145        updateTrie(prefixXor[right + 1], 1);
146    }
147
148    return result;
149}
150

Time and Space Complexity

Time Complexity: O(n * B)

Let n be the length of nums and B be the number of bits processed in the trie (here B = 15, since the loop runs bit = 14 down to 0).

The analysis proceeds as follows:

Prefix XOR construction: A single pass over nums builds the prefixXor array in O(n).
Main loop: The right pointer iterates n times. Within each iteration:
- Monotonic deque maintenance: Each index is added to and removed from maxDeque and minDeque at most once across the entire run. Amortized, this contributes O(1) per iteration, so O(n) total.
- Window shrinking (left pointer): The left pointer only moves forward and never resets, so the total number of left advances across all iterations is at most n. Each advance calls updateTrie(prefixXor[left], -1), which costs O(B). This gives O(n * B) amortized for all removals.
- getMaxXor call: Each call traverses the trie from the highest bit to the lowest, costing O(B). Called once per iteration → O(n * B).
- updateTrie insertion: Each call costs O(B). Called once per iteration → O(n * B).

Combining all parts: O(n) + O(n * B) = O(n * B). Since B = 15 is a constant bound (values fit within 15 bits), this can also be viewed as O(n), but the precise expression is O(n * B).

Space Complexity: O(n + n * B) = O(n * B)

The space usage breaks down as:

Prefix XOR array: O(n) for storing n + 1 prefix values.
Monotonic deques: At most n indices stored across both deques → O(n).
Trie: At most n + 1 prefix values are inserted, and each insertion creates up to B new nodes along its path. The total number of trie nodes is bounded by O(n * B).

The dominant term is the trie, giving an overall space complexity of O(n * B). Treating B = 15 as a constant, this simplifies to O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using `MAX_BIT` Too Small for the Prefix-XOR Range

The most subtle and dangerous mistake is choosing too few bits for the Trie. A natural but incorrect intuition is: "the values in nums are at most 2^15, so 15 bits is enough." The catch is that we are not storing nums[i] in the Trie — we are storing prefix-XOR values.

The XOR of values, each below 2^15, is still bounded by 2^15 - 1 (XOR never produces a bit higher than the highest bit present in any operand). So MAX_BIT = 14 works only if the individual elements truly fit in 15 bits. If the constraints allow nums[i] up to, say, 10^9, then MAX_BIT = 14 silently drops the high bits, producing wrong answers without any crash.

Why it's hard to spot: the code runs fine and returns a number — just the wrong one. Small test cases where all values fit in 15 bits will pass, masking the bug.

Solution: Derive MAX_BIT from the actual maximum value rather than hard-coding it.

def maxXor(self, nums: list[int], limit: int) -> int:
    # Compute the highest bit position needed from the data itself.
    max_val = max(nums) if nums else 0
    self.MAX_BIT = max(max_val.bit_length() - 1, 0)
    # ... rest of the algorithm unchanged

This makes the Trie depth adapt to the input, eliminating silent truncation while keeping queries fast.

Pitfall 2: Querying the Trie When It Is Empty

After the shrink step, it is theoretically possible to reason that the Trie is never empty — because prefix_xor[right + 1] itself has not yet been inserted, but prefix_xor[left] always remains as a valid endpoint (the window [left, right] is non-empty since a single element trivially satisfies max - min = 0 <= limit).

However, if someone modifies the shrink loop or the insertion order (a common refactor), the Trie can become empty, and get_max_xor will then dereference a None child:

current = current.children[current_bit]  # current_bit branch may be None -> crash

Solution: Make get_max_xor defensive by tracking whether a valid path exists, and guard against missing branches:

def get_max_xor(self, value: int) -> int:
    if self.root.children[0] is None and self.root.children[1] is None:
        return 0  # trie is empty, no valid pairing

    current = self.root
    max_xor = 0
    for bit in range(self.MAX_BIT, -1, -1):
        current_bit = (value >> bit) & 1
        opposite_bit = 1 - current_bit
        if current.children[opposite_bit] is not None and current.children[opposite_bit].count > 0:
            max_xor |= (1 << bit)
            current = current.children[opposite_bit]
        elif current.children[current_bit] is not None and current.children[current_bit].count > 0:
            current = current.children[current_bit]
        else:
            break  # no active path remains
    return max_xor

The added count > 0 check on the same-bit branch (plus the break) ensures we never follow a logically deleted path. Without it, the original code follows children[current_bit] even when its count is 0, walking into stale nodes whose count is zero — which can yield an inflated XOR by treating removed prefixes as still present.

This second issue (following same-bit branches without checking their count) is itself a genuine latent bug: a node can have count == 0 yet still exist as an object, and the original else branch trusts it blindly.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering