Skip to main content
Talentd

Maximum Subarray XOR with Bounded Range - Solution & Explanation

HardArrayBit ManipulationTrieQueue4 min read
Practice this problem

Problem Statement

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:

  • Select the subarray [5, 4, 5, 6].
  • The difference between its maximum and minimum elements is 6 - 4 = 2 <= k.
  • The value is 4 XOR 5 XOR 6 = 7.

Example 2:

Input: nums = [5,4,5,6], k = 1

Output: 6

Explanation:

  • Select the subarray [5, 4, 5, 6].
  • The difference between its maximum and minimum elements is 6 - 6 = 0 <= k.
  • The value is 6.

 

Constraints:

  • 1 <= nums.length <= 4 * 104
  • 0 <= nums[i] < 215
  • 0 <= k < 215

Approach Overview

Problem 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.

Solution

Code

Java

Java

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray XORO(n^2)O(1)Small arrays or validating correctness during testing
Prefix XOR + TrieO(n log A)O(n)Maximum subarray XOR without length constraints
Sliding Window Prefix TrieO(n log A)O(R log A)General case with bounded subarray length range

Video Solution

Leetcode 3845 | Maximum Subarray XOR with Bounded Range | Trie | Deque • CodeWithMeGuys • 781 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Maximum Subarray XOR with Bounded Range easy or hard?
This problem is considered hard because it combines several advanced techniques: prefix XOR transformation, maximum XOR queries with a trie, and sliding window constraints. Implementing insertion and deletion in the trie correctly is the main challenge.
Maximum Subarray XOR with Bounded Range Python/Java solution
Typical implementations compute prefix XOR values, maintain a binary trie for candidate prefixes, and update the trie as the sliding window moves. The same logic works across Python, Java, C++, and Go with O(n log A) complexity.
How to solve Maximum Subarray XOR with Bounded Range in O(n)?
A true O(n) solution is uncommon because maximizing XOR typically requires bit-level traversal. Using a prefix XOR array with a bitwise trie gives O(n log A), which is effectively linear for fixed integer sizes such as 32-bit values.
What is the best approach for Maximum Subarray XOR with Bounded Range?
The most efficient approach combines prefix XOR with a bitwise trie while maintaining a sliding window of valid prefix indices. Each step inserts and removes prefix values so the subarray length stays within [L, R]. Trie queries maximize XOR in O(log A) time, giving an overall complexity of O(n log A).
Is Maximum Subarray XOR with Bounded Range asked at Google/Amazon/Meta?
Problems involving maximum XOR, prefix XOR arrays, and trie-based bit optimization frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often include constraints such as subarray length limits or sliding window conditions.
What data structure is used in Maximum Subarray XOR with Bounded Range?
The key data structure is a bitwise trie (binary trie) used to compute maximum XOR pairs efficiently. The algorithm also relies on prefix XOR arrays and a sliding window or queue to maintain valid indices for the bounded range.
What is the time complexity of Maximum Subarray XOR with Bounded Range?
The optimal solution runs in O(n log A) time, where n is the array length and A is the maximum integer value range (typically up to 2^31). Each element performs one trie insertion, one removal, and one maximum-XOR query.

Ready to solve this problem?

Practice Maximum Subarray XOR with Bounded Range with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays