315. Count of Smaller Numbers After Self

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].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
Example 1:

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.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

Constraints:

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

Solution

 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
class Solution {
    
    /*
    
    -1 -1 5 2 1
    
             0 1 2 3 4 5  
    .. 0...2 0 1 1 0 0 1
    
    
    */
    public List<Integer> countSmaller(int[] nums) {
        int offset = 10_000;
        int size = 2 * 10_000 + 1;
        int[] tree = new int[size * 2];

        List<Integer> res = new ArrayList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            int smallerCount = query(0, nums[i] + offset, tree, size);
            res.add(0, smallerCount);
            update(nums[i] + offset, 1, tree, size);
        }
        
        return res;
    }
    
    void update(int index, int value, int[] tree, int size) {
        index += size;
        tree[index] += value;
        while (index > 1) {
            index /= 2;
            tree[index] = tree[index * 2] + tree[index * 2 + 1];
        }
    }
    
    int query(int left, int right, int[] tree, int size) {
        int result = 0;
        left += size;
        right += size;
        
        while (left < right) {
            if (left % 2 == 1) {
                result += tree[left];
                left++;
            }
            if (right % 2 == 1) {
                right--;
                result += tree[right];
            }
            
            left /= 2;
            right /= 2;
        }
        
        return result;
    }
}

Solution#

Solution