C++, 22 ms, beats 99.5%, array partitioning similar to quick sort


  • 2
    Z

    I have put detailed comments in the code. Here I just highlight the logic of the method.

    1. working from most significant bit on the left towards right. Obviously, if the more significant bit is 1, the xor value is greater than those with this bit = 0.
    2. Similar to quick sort, we partition a certain range of the array nums in place. The left subrange has current bit = 1, and the right subrange has current bit = 0. Let's name them as A and B.
    3. In order to find the greatest XOR value, we have to take 1 number from A, and 1 number from B. And to set next bit to 1, there must be a subrange in A and a subrange in B having opposite bit; otherwise, next bit will be 0. So we partition range A and B recursively.
    4. When partitioning range A and B, there are 3 cases. (1) A has both bit 1 and 0 ranges. We check whether B has bit 0 or bit 1 range or both. (2) A has only bit 1. We check whether B has bit 0. (3) A has only bit 0. We check whether B has bit 1.

    For every recursive call, the runtime is O(n). There are totally 31 levels of calls, so the runtime is O(n). And extra space is O(1) because the code works in place. The code with comments is as below.

    class Solution {
    public:
        int findMaximumXOR(vector<int>& nums) {
            int n = nums.size();
            return helper(nums, 0, n-1, 0, n-1, 0, 30);
        }
    private:
        // (ls, le) and (rs, re) are two ranges of nums, which gives max xor value to current bit;
        // bit decreases from 30 to 0, i.e., working from most significant bit on the left towards right;
        // Similar to quicksort, partition (ls, le) to two ranges (ls, j-1) and (j, le) by swapping elements
        // the range on the left with current bit = 1, and the range on right is 0; We do the same to (rs, re)
        // In order to set the current bit in the answer, i.e. val, to be 1, the left (ls, le) and right (rs,re) ranges must have subranges with opposite bit. If so, val = (val << 1) + 1; otherwise, val = val << 1.
        int helper(vector<int>& nums, int ls, int le, int rs, int re, int val, int bit) {
            if (bit == -1) return val;
            int mask = 1<<bit, j = ls, k = rs;
            for (int i = ls; i <= le; i++) 
                if (nums[i]&mask) swap(nums[i], nums[j++]);
            for (int i = rs; i <= re; i++) 
                if (nums[i]&mask) swap(nums[i], nums[k++]);
            // the left range has two subranges, the answer is max of (bit 1 subrange on the left and bit 0 subrange on the right) or (bit 0 subrange on the left and bit 1 subrange on the right)
            if (j > ls && j <= le) {
                int ans = 0;
                if (k > rs) 
                    ans = helper(nums, j, le, rs, k-1, val*2+1, bit-1);
                if (k <= re) 
                    ans = max(ans, helper(nums, ls, j-1, k, re, val*2+1, bit-1));
                return ans;
            }
            // the left range has only bit 0 subrange
            else if (j <= ls) {
                // check whether the right range has bit 1 subrange
                if (k > rs) 
                    return helper(nums, ls, le, rs, k-1, val*2+1, bit-1);
                else 
                    return helper(nums, ls, le, rs, re, val*2, bit-1);
            }
            // the left range has only bit 1 subrange
            else {
                // check whether the right range has bit 0 subrange
                if (k <= re) 
                    return helper(nums, ls, le, k, re, val*2+1, bit-1);
                else 
                    return helper(nums, ls, le, rs, re, val*2, bit-1);
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.