Create Sorted Array through Instructions LeetCode solution in Java

1
class Fenwick {
2
  public int[] tree; // Binary indexed Tree array
3

4
  // initialize a new Fenwick tree of size length
5
  public Fenwick(int length) {
6
    tree = new int[length];
7
  }
8

9
  // Returns the sum of values in an array from range [0, i]
10
  public int sum(int i) {
11
    int sum = 0;
12
    while (i > 0) {
13
      sum += tree[i];
14
      i = i - (i & -i); // flip the last set bit using 2's compliment
15
    }
16
    return sum;
17
  }
18

19
  // Returns sum of values in the given range [start, end]
20
  public int sumRange(int start, int end) {
21
    return sum(end) - sum(start - 1);
22
  }
23

24
  // updates the value at index i by "k" in tree
25
  public void update(int i, int k) {
26
    while (i < tree.length) {
27
      tree[i] += k;
28
      i = i + (i & -i); // add last set bit
29
    }
30
  }
31
}
32

33
class Solution {
34
  public int createSortedArray(int[] instructions) {
35
    // check for valid instructions
36
    if (instructions.length == 0) {
37
      return 0;
38
    }
39

40
    /*
41
             to check for values strictly greater than any ith value in the instructions, we
42
             need to find the largest value in the instructions, this will denote the range
43
    of values in the Fenwick tree
44
         */
45
    int max = 0;
46
    for (int value : instructions) {
47
      if (value > max) {
48
        max = value;
49
      }
50
    }
51

52
    /*
53
        initialize a Fenwick Tree structure to allow for the search of all values strictly less than and
54
        strictly greater than instructions[i].
55

56
        since we need the tree to be 1 indexed, we add 1 to max
57
    */
58
    Fenwick tree = new Fenwick(max + 1);
59
    int cost = 0;
60

61
    for (int i = 0; i < instructions.length; i++) {
62
      int current_value = instructions[i];
63

64
      // get all the values less and greater than current_value
65
      int strictly_less = tree.sumRange(0, current_value - 1);
66
      int strictly_greater = tree.sumRange(current_value + 1, max);
67

68
      // update cost
69
      cost += Math.min(strictly_less, strictly_greater);
70

71
      // cost may be large so we mod it with 10^9 + 7
72
      cost = cost % ((int) 1e9 + 7);
73

74
      // update the current_value's count in the FW tree
75
      tree.update(current_value, 1);
76
    }
77

78
    return cost;
79
  }
80
}