Maximum XOR With an Element From Array LeetCode solution in Java

1
class Solution {
2
  class QueryComparator implements Comparator<int[]> {
3
    public int compare(int[] a, int[] b) {
4
      return Integer.compare(a[1], b[1]);
5
    }
6
  }
7

8
  class Node {
9
    Node zero;
10
    Node one;
11

12
    public Node() {
13
      this.zero = null;
14
      this.one = null;
15
    }
16
  }
17

18
  public int[] maximizeXor(int[] nums, int[][] queries) {
19
    Arrays.sort(nums);
20

21
    int len = queries.length;
22
    int[][] queryWithIndex = new int[len][3];
23
    for (int i = 0; i < len; i++) {
24
      queryWithIndex[i][0] = queries[i][0];
25
      queryWithIndex[i][1] = queries[i][1];
26
      queryWithIndex[i][2] = i;
27
    }
28
    Arrays.sort(queryWithIndex, new QueryComparator());
29

30
    int numId = 0;
31
    int[] ans = new int[len];
32

33
    Node root = new Node();
34
    for (int i = 0; i < len; i++) {
35
      while (numId < nums.length && nums[numId] <= queryWithIndex[i][1]) {
36
        addNumToTree(nums[numId], root);
37
        numId++;
38
      }
39

40
      ans[queryWithIndex[i][2]] = maxXOR(queryWithIndex[i][0], root);
41
    }
42

43
    return ans;
44
  }
45

46
  private void addNumToTree(int num, Node node) {
47
    for (int i = 31; i >= 0; i--) {
48
      int digit = (num >> i) & 1;
49
      if (digit == 1) {
50
        if (node.one == null) {
51
          node.one = new Node();
52
        }
53
        node = node.one;
54
      } else {
55
        if (node.zero == null) {
56
          node.zero = new Node();
57
        }
58
        node = node.zero;
59
      }
60
    }
61
  }
62

63
  private int maxXOR(int num, Node node) {
64
    if (node.one == null && node.zero == null) {
65
      return -1;
66
    }
67

68
    int ans = 0;
69
    for (int i = 31; i >= 0 && node != null; i--) {
70
      int digit = (num >> i) & 1;
71
      if (digit == 1) {
72
        if (node.zero != null) {
73
          ans += (1 << i);
74
          node = node.zero;
75
        } else {
76
          node = node.one;
77
        }
78
      } else {
79
        if (node.one != null) {
80
          ans += (1 << i);
81
          node = node.one;
82
        } else {
83
          node = node.zero;
84
        }
85
      }
86
    }
87

88
    return ans;
89
  }
90
}