Chess Study Contrast Partners
Earliest prior indices maximizing XOR within a given array index distance
A chess club records study cards in chronological order. Each card has a 16-bit motif mask: a set bit indicates that the card features a particular tactical motif.
For each card, the coach wants to choose a recently recorded card with the most contrasting motif mask. The contrast between masks a and b is the integer value of their bitwise XOR, a ^ b.
You are given the masks in recording order as masks, and a nonnegative integer window. For the card at index i, an eligible partner has index j satisfying:
j < i, andi - j <= window.
Choose the eligible partner with the largest contrast. If several partners have the same contrast, choose the one with the smallest index.
Return an integer array of the same length as masks, where each entry is the chosen partner's zero-based index, or -1 if no partner is eligible. Cards with identical masks are separate records and may be chosen as partners.
Examples
Example 1
Input: masks = [3,5,6,1], window = 2 Output: [-1,0,0,2]
The first card has no earlier partner. For the card at index 2, only indices 0 and 1 are eligible, and index 0 gives greater contrast. For the card at index 3, index 0 has expired, so only indices 1 and 2 are considered.
Example 2
Input: masks = [9,9,9,9], window = 2 Output: [-1,0,0,1]
Every mask is identical, so all eligible partners give equal contrast. Each card therefore chooses the earliest index still inside its window.
Example 3
Input: masks = [0,65535,12], window = 0 Output: [-1,-1,-1]
A window of zero excludes every earlier card, so no card has an eligible partner.
Constraints
- 0 <= masks.length <= 100000
- 0 <= masks[i] <= 65535
- 0 <= window <= 100000
No chess knowledge is required. The intended solution takes O(n * B) time and O(n * B) space, where B = 16. Expired branches may remain allocated, but their active counts must be zero.
Hints
Show hint 1Hint 1
Maintain exactly the eligible earlier cards while moving from left to right. Can a binary trie support both adding and expiring a mask?
Show hint 2Hint 2
To maximize XOR, prefer the opposite bit at each trie level, but only if that branch contains an active card. Keep active indices for identical masks in chronological order to resolve ties.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the solution change if ties had to choose the most recent eligible card?
- How would you support an online stream of cards without retaining expired trie branches?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem