You are given a non-negative integer array nums and an integer k.
You must select a subarray of nums such that the difference between its maximum and minimum elements is at most k. The value of this subarray is the bitwise XOR of all elements in the subarray.
Return an integer denoting the maximum possible value of the selected subarray.
Example 1:
Input: nums = [5,4,5,6], k = 2
Output: 7
Explanation:
[5, 4, 5, 6].6 - 4 = 2 <= k.4 XOR 5 XOR 6 = 7.Example 2:
Input: nums = [5,4,5,6], k = 1
Output: 6
Explanation:
[5, 4, 5, 6].6 - 6 = 0 <= k.
Constraints:
1 <= nums.length <= 4 * 1040 <= nums[i] < 2150 <= k < 215Problem Overview: You are given an array and a valid subarray length range [L, R]. Among all subarrays whose length falls within this range, return the maximum XOR value. The constraint forces you to evaluate XOR values while maintaining a sliding set of candidate prefix values.
Approach 1: Brute Force Subarray Enumeration (O(n^2) time, O(1) space)
Iterate over every starting index and expand the subarray while tracking the running XOR. For each end index, check whether the subarray length lies within [L, R] and update the maximum XOR. This directly computes XOR values but requires examining up to O(n^2) subarrays. It works for small inputs but becomes impractical when n grows. Still useful as a baseline to verify correctness during implementation.
Approach 2: Prefix XOR + Bitwise Trie (O(n log A) time, O(n) space)
Use the classic trick for maximum subarray XOR: compute a prefixXor array where the XOR of subarray [l, r] equals prefixXor[r] ^ prefixXor[l-1]. Insert prefix values into a bitwise trie and greedily choose opposite bits during queries to maximize XOR. For each index r, query the trie to find the prefix that produces the largest XOR with prefixXor[r]. The trie stores numbers bit-by-bit, so each query takes O(log A) where A is the value range. This solves the unrestricted version of the problem efficiently.
Approach 3: Sliding Window Prefix Trie (Bounded Range) (O(n log A) time, O(R log A) space)
The bounded length requirement means the prefix index must satisfy r - l + 1 ∈ [L, R]. Maintain a sliding window of valid prefix indices using a sliding window. When processing position r, insert prefixXor[r-L] into the trie because it becomes a valid starting point. Remove prefixXor[r-R-1] when it leaves the window. Each step queries the trie to compute the best XOR with the current prefix. A queue or index tracking structure helps synchronize insertions and removals efficiently. The trie handles the bit manipulation logic while prefix arrays manage subarray XOR computation.
Recommended for interviews: Interviewers expect the prefix XOR + trie idea combined with a window constraint. Starting from brute force shows you understand subarray XOR properties, but the optimized solution demonstrates mastery of trie-based maximum XOR queries and sliding window constraints. The final solution runs in O(n log A) time and scales to large arrays.
Java
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray XOR | O(n^2) | O(1) | Small arrays or validating correctness during testing |
| Prefix XOR + Trie | O(n log A) | O(n) | Maximum subarray XOR without length constraints |
| Sliding Window Prefix Trie | O(n log A) | O(R log A) | General case with bounded subarray length range |
Leetcode 3845 | Maximum Subarray XOR with Bounded Range | Trie | Deque • CodeWithMeGuys • 689 views views
Watch 2 more video solutions →Practice Maximum Subarray XOR with Bounded Range with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor