Java O(n) recursion solution 36ms


  • 2

    This solution only supports an input array with unique elements. You can easily achieve that by filtering the input array with hashset.

    public class Solution {
        public int findMaximumXOR(int[] nums) {
            List<Integer> left = new ArrayList<>();
            List<Integer> right = new ArrayList<>();
            for(int i=0; i<nums.length; i++) {
                left.add(nums[i]);
                right.add(nums[i]);
            }
            return helper(left, right, 1<<30);
            
        }
        public int helper(List<Integer> left, List<Integer> right, int bit) {
            if(left.size()==0||right.size()==0) return 0;
            if(left.size()==1||right.size()==1) {
                int max = 0;
                for(Integer l: left) {
                    for(Integer r: right) {
                        max = Math.max(max, l^r);
                    }
                }
                return max;
            }
            List<Integer> oneLeft = new ArrayList<>();
            List<Integer> zeroLeft = new ArrayList<>();
            List<Integer> oneRight = new ArrayList<>();
            List<Integer> zeroRight = new ArrayList<>();
            while((oneLeft.size()==0||zeroRight.size()==0)&&(oneRight.size()==0||zeroLeft.size()==0)&&bit!=0) {
                oneLeft = new ArrayList<>();
                zeroLeft = new ArrayList<>();
                oneRight = new ArrayList<>();
                zeroRight = new ArrayList<>();
                for(Integer i:left) {
                    if((i&bit)==0) zeroLeft.add(i);
                    else oneLeft.add(i);
                }
                for(Integer i:right) {
                    if((i&bit)==0) zeroRight.add(i);
                    else oneRight.add(i);
                }
                bit >>= 1;
            }
            return Math.max(helper(oneLeft, zeroRight, bit), helper(zeroLeft, oneRight, bit));
        }
    }
    

  • 2
    Y

    would you like to explain


Log in to reply
 

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