Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode solution in Java

1
class Solution {
2
  public String minInteger(String num, int k) {
3
    // pqs stores the location of each digit.
4
    List<Queue<Integer>> pqs = new ArrayList<>();
5
    for (int i = 0; i <= 9; ++i) {
6
      pqs.add(new LinkedList<>());
7
    }
8

9
    for (int i = 0; i < num.length(); ++i) {
10
      pqs.get(num.charAt(i) - '0').add(i);
11
    }
12
    String ans = "";
13
    SegmentTree seg = new SegmentTree(num.length());
14

15
    for (int i = 0; i < num.length(); ++i) {
16
      // At each location, try to place 0....9
17
      for (int digit = 0; digit <= 9; ++digit) {
18
        // is there any occurrence of digit left?
19
        if (pqs.get(digit).size() != 0) {
20
          // yes, there is a occurrence of digit at pos
21
          Integer pos = pqs.get(digit).peek();
22
          // Since few numbers already shifted to left, this `pos` might be outdated.
23
          // we try to find how many number already got shifted that were to the left of pos.
24
          int shift = seg.getCountLessThan(pos);
25
          // (pos - shift) is number of steps to make digit move from pos to i.
26
          if (pos - shift <= k) {
27
            k -= pos - shift;
28
            seg.add(pos); // Add pos to our segment tree.
29
            pqs.get(digit).remove();
30
            ans += digit;
31
            break;
32
          }
33
        }
34
      }
35
    }
36
    return ans;
37
  }
38

39
  class SegmentTree {
40
    int[] nodes;
41
    int n;
42

43
    public SegmentTree(int max) {
44
      nodes = new int[4 * (max)];
45
      n = max;
46
    }
47

48
    public void add(int num) {
49
      addUtil(num, 0, n, 0);
50
    }
51

52
    private void addUtil(int num, int l, int r, int node) {
53
      if (num < l || num > r) {
54
        return;
55
      }
56
      if (l == r) {
57
        nodes[node]++;
58
        return;
59
      }
60
      int mid = (l + r) / 2;
61
      addUtil(num, l, mid, 2 * node + 1);
62
      addUtil(num, mid + 1, r, 2 * node + 2);
63
      nodes[node] = nodes[2 * node + 1] + nodes[2 * node + 2];
64
    }
65

66
    // Essentialy it tells count of numbers < num.
67
    public int getCountLessThan(int num) {
68
      return getUtil(0, num, 0, n, 0);
69
    }
70

71
    private int getUtil(int ql, int qr, int l, int r, int node) {
72
      if (qr < l || ql > r) return 0;
73
      if (ql <= l && qr >= r) {
74
        return nodes[node];
75
      }
76

77
      int mid = (l + r) / 2;
78
      return getUtil(ql, qr, l, mid, 2 * node + 1) + getUtil(ql, qr, mid + 1, r, 2 * node + 2);
79
    }
80
  }
81
}