[Leetcode] Problem 315 - Count of Smaller Numbers After Self

Posted on | In ,

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example

Input: nums = [5,2,6,1]

Output: [2,1,1,0]

Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Constraints

  • 0 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class BinaryIndexedTree {
    private int[] sum;

    public BinaryIndexedTree(int n) {
        sum = new int[n + 1];
    }

    public void update(int i, int delta) {
        while (i < sum.length) {
            sum[i] += delta;
            i += lowbit(i);
        }
    }

    public int query(int i) {
        int result = 0;

        while (i > 0) {
            result += sum[i];
            i -= lowbit(i);
        }

        return result;
    }

    private int lowbit(int x) {
        return x & (-x);
    }
}

public List<Integer> countSmaller(int[] nums) {
    List<Integer> result = new ArrayList<>();

    if (nums == null || nums.length < 1)
        return result;

    int[] sort = nums.clone();
    Arrays.sort(sort);
    Map<Integer, Integer> rank = new HashMap<>();
    int r = 0;

    for (int s : sort) {
        if (!rank.containsKey(s))
            rank.put(s, ++r);
    }

    BinaryIndexedTree tree = new BinaryIndexedTree(rank.size());

    for (int i = nums.length - 1; i >= 0; i--) {
        int cur = rank.get(nums[i]);
        tree.update(cur, 1);
        result.add(tree.query(cur - 1));
    }

    Collections.reverse(result);
    return result;
}