Java O(n) Trie solution, beat 99.05% solutions. Easy to understand. 32 ms


  • 0
    Q
    public class Node{
    		Node left;
    		Node right;	
    	}
    	public int findMaximumXOR(int[] nums) {
    		if(nums.length<2) return 0;
    		Node head = new Node();
    		int maxxor = 0;
    		int mask = 1<<30;
    		for (int i = 0; i < nums.length; i++) {
    			Node tnode = head;
    			Node temp = tnode;
    			int num = nums[i];
    			int tm = mask;
    			int xor = 0;
    			while(tm!=0){
    				if((tm & num) == 0){
    					if(tnode.left==null) tnode.left = new Node();
    					tnode = tnode.left;
    					if(temp.right!=null){
    						xor += tm;
    						temp = temp.right;
    					}else{
    						temp = temp.left;
    					}
    				}else{
    					if(tnode.right==null) tnode.right = new Node();
    					tnode = tnode.right;
    					if(temp.left!=null){
    						xor += tm;
    						temp = temp.left;
    					}else{
    						temp = temp.right;
    					}
    				}
    				tm = tm>>1;
    			}
    			maxxor = Math.max(xor, maxxor);
    			
    		}
    		return maxxor;
    	        
    	    }
    

Log in to reply
 

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