315. Count of Smaller Numbers After Self

Posted on Edited on In

315. Count of Smaller Numbers After Self

Description

Difficulty: Hard

Related Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

1
2
3
4
5
6
7
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:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Hints/Notes

  • Merge sort
  • Compare tmp array with doing the merge

Solution

Language: C++

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
class Solution {
public:
    vector<int> res;
    vector<pair<int, int>> tmp;

    vector<int> countSmaller(vector<int>& nums) {
       vector<pair<int, int>> arr;
       int size = nums.size();
       for (int i = 0; i < size; i++) {
           arr.push_back({nums[i], i});
       }
       res = vector<int>(size, 0);
       tmp = vector<pair<int, int>>(size, {0, 0});
       sort(arr, 0, nums.size() - 1);
       return res;
    }

    void sort(vector<pair<int, int>>& arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort(arr, low, mid);
        sort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }

    void merge(vector<pair<int, int>>& arr, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            tmp[i] = arr[i];
        }

        int index = low, p1 = low, p2 = mid + 1;
        while (index <= high) {
            if (p1 == mid + 1) {
                arr[index++] = tmp[p2++];
            } else if (p2 == high + 1) {
                res[tmp[p1].second] += p2 - mid - 1;
                arr[index++] = tmp[p1++];
            } else if (tmp[p1].first > tmp[p2].first) {
                arr[index++] = tmp[p2++];
            } else {
                res[tmp[p1].second] += p2 - mid - 1;
                arr[index++] = tmp[p1++];
            }
        }
    }
};