LeetCode 3845 - Maximum Subarray XOR with Bounded Range

LeetCode Problem 3845

Difficulty: 🔴 Hard
Topics: Array, Bit Manipulation, Trie, Queue, Sliding Window, Prefix Sum, Monotonic Queue

Solution

Problem Understanding

The problem asks us to find a subarray of a given non-negative integer array nums such that the difference between the maximum and minimum elements of the subarray does not exceed a given integer k. Once such a subarray is chosen, we compute the XOR of all its elements, and our goal is to maximize this XOR value over all possible valid subarrays.

In simpler terms, we are balancing two requirements: the subarray must have a bounded range (maximum minus minimum ≤ k), and among all such subarrays, we want the one whose XOR of elements is largest. The input array can have up to 40,000 elements, and each element is at most 2^15, so brute force enumeration of all subarrays is infeasible. Constraints guarantee that the array is non-empty, all numbers are non-negative, and the range k is also non-negative.

Important edge cases include arrays where all elements are identical, arrays with only one element, or when k is very small (0 or 1), as these affect which subarrays are valid.

Approaches

The naive brute-force approach is to iterate over every possible subarray, compute its maximum and minimum to check the k constraint, and then calculate the XOR of all its elements. This approach is correct but extremely slow: it requires O(n^3) time if implemented directly (O(n^2) subarrays and O(n) to compute max/min/XOR). This is impractical for n ≈ 40,000.

The optimal approach uses two key observations: first, we can maintain a sliding window of valid subarrays by keeping track of maximum and minimum elements efficiently using monotonic deques. Second, we can compute the maximum XOR of subarrays ending at each position efficiently using a prefix XOR array and a binary trie. The prefix XOR allows us to compute the XOR of any subarray in constant time using prefixXOR[j] ^ prefixXOR[i], and the trie helps us find the maximum XOR value for a given prefix efficiently.

Algorithm Walkthrough

1. Initialize two monotonic deques to maintain the maximum and minimum elements of the current window. One deque stores indices in decreasing order for the maximum, and another stores indices in increasing order for the minimum.
2. Use a sliding window approach with left and right pointers. Expand the window by incrementing right, updating the deques with the new element.
3. Whenever the difference between the current maximum and minimum exceeds k, move the left pointer forward, removing elements from the deques that fall out of the window.
4. Maintain a prefix XOR array such that prefixXOR[i] is the XOR of all elements from the beginning up to index i-1. This allows subarray XORs to be computed as prefixXOR[right + 1] ^ prefixXOR[left].
5. Use a binary trie to store prefix XORs of valid subarrays and query for the maximum XOR efficiently. Each trie node represents a binary bit of the XOR value.
6. At each step, compute the XOR of the current subarray with previous prefixes in the trie, updating the maximum XOR found.

Why it works: The monotonic deques ensure that the window always satisfies the k constraint. The prefix XOR and trie efficiently find the maximum XOR for all valid subarrays ending at the current position. This guarantees that no valid subarray is missed, and the XOR is maximized.

Python Solution

class TrieNode:
    def __init__(self):
        self.children = [None, None]

class Solution:
    def maxXor(self, nums: list[int], k: int) -> int:
        from collections import deque
        
        def insert(trie: TrieNode, num: int):
            node = trie
            for i in range(14, -1, -1):
                bit = (num >> i) & 1
                if not node.children[bit]:
                    node.children[bit] = TrieNode()
                node = node.children[bit]

        def query(trie: TrieNode, num: int) -> int:
            node = trie
            res = 0
            for i in range(14, -1, -1):
                bit = (num >> i) & 1
                toggled = 1 - bit
                if node.children[toggled]:
                    res |= (1 << i)
                    node = node.children[toggled]
                else:
                    node = node.children[bit]
            return res

        n = len(nums)
        max_deque, min_deque = deque(), deque()
        prefixXOR = [0] * (n + 1)
        for i in range(n):
            prefixXOR[i + 1] = prefixXOR[i] ^ nums[i]
        
        trie = TrieNode()
        insert(trie, 0)
        max_xor = 0
        left = 0
        
        for right in range(n):
            while max_deque and nums[right] > nums[max_deque[-1]]:
                max_deque.pop()
            max_deque.append(right)
            
            while min_deque and nums[right] < nums[min_deque[-1]]:
                min_deque.pop()
            min_deque.append(right)
            
            while nums[max_deque[0]] - nums[min_deque[0]] > k:
                left += 1
                if max_deque[0] < left:
                    max_deque.popleft()
                if min_deque[0] < left:
                    min_deque.popleft()
            
            max_xor = max(max_xor, query(trie, prefixXOR[right + 1]))
            insert(trie, prefixXOR[right + 1])
        
        return max_xor

This implementation initializes monotonic deques for tracking the min and max efficiently and computes prefix XORs. The trie allows querying the maximum XOR with previous prefixes efficiently. The sliding window ensures only valid subarrays satisfying the k constraint are considered.

Go Solution

type TrieNode struct {
    children [2]*TrieNode
}

func insert(trie *TrieNode, num int) {
    node := trie
    for i := 14; i >= 0; i-- {
        bit := (num >> i) & 1
        if node.children[bit] == nil {
            node.children[bit] = &TrieNode{}
        }
        node = node.children[bit]
    }
}

func query(trie *TrieNode, num int) int {
    node := trie
    res := 0
    for i := 14; i >= 0; i-- {
        bit := (num >> i) & 1
        toggled := 1 - bit
        if node.children[toggled] != nil {
            res |= (1 << i)
            node = node.children[toggled]
        } else {
            node = node.children[bit]
        }
    }
    return res
}

func maxXor(nums []int, k int) int {
    n := len(nums)
    prefixXOR := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefixXOR[i+1] = prefixXOR[i] ^ nums[i]
    }

    maxDeque, minDeque := []int{}, []int{}
    trie := &TrieNode{}
    insert(trie, 0)
    maxXor := 0
    left := 0

    for right := 0; right < n; right++ {
        for len(maxDeque) > 0 && nums[right] > nums[maxDeque[len(maxDeque)-1]] {
            maxDeque = maxDeque[:len(maxDeque)-1]
        }
        maxDeque = append(maxDeque, right)

        for len(minDeque) > 0 && nums[right] < nums[minDeque[len(minDeque)-1]] {
            minDeque = minDeque[:len(minDeque)-1]
        }
        minDeque = append(minDeque, right)

        for nums[maxDeque[0]]-nums[minDeque[0]] > k {
            left++
            if maxDeque[0] < left {
                maxDeque = maxDeque[1:]
            }
            if minDeque[0] < left {
                minDeque = minDeque[1:]
            }
        }

        maxXor = max(maxXor, query(trie, prefixXOR[right+1]))
        insert(trie, prefixXOR[right+1])
    }

    return maxXor
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go version mirrors the Python logic with slices instead of deques. The main difference is handling slice resizing for popleft operations and explicit helper functions like max.

Worked Examples

Example 1: nums = [5, 4, 5, 6], k = 2