315

315. Count of Smaller Numbers After Self (Hard)

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:

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 <= 105
• -104 <= nums[i] <= 104

Companies: Amazon, Google, Apple

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

Similar Questions:

• Count of Range Sum (Hard)
• Queue Reconstruction by Height (Medium)
• Reverse Pairs (Hard)
• How Many Numbers Are Smaller Than the Current Number (Easy)
• Count Good Triplets in an Array (Hard)
• Count the Number of K-Big Indices (Hard)

Solution 1. Divide and Conquer (Merge Sort)

The idea is similar to Merge Sort.

// OJ: https://leetcode.com/problems/count-of-smaller-numbers-after-self/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
    vector<int> id, tmp, ans;
    void solve(vector<int> &A, int begin, int end) {
        if (begin + 1 >= end) return;
        int mid = (begin + end) / 2, i = begin, j = mid, k = begin;
        solve(A, begin, mid);
        solve(A, mid, end);
        for (; i < mid; ++i) {
            while (j < end && A[id[j]] < A[id[i]]) {
                tmp[k++] = id[j++];
            }
            ans[id[i]] += j - mid;
            tmp[k++] = id[i];
        }
        for (; j < end; ++j) tmp[k++] = id[j];
        for (int i = begin; i < end; ++i) id[i] = tmp[i];
    }
public:
    vector<int> countSmaller(vector<int>& A) {
        int N = A.size();
        id.assign(N, 0);
        tmp.assign(N, 0);
        ans.assign(N, 0);
        iota(begin(id), end(id), 0);
        solve(A, 0, N);
        return ans;
    }
};

Solution 2. Binary Indexed Tree

// OJ: https://leetcode.com/problems/count-of-smaller-numbers-after-self
// Author: github.com/lzl124631x
// Time: O(NlogM) where M is the range of A[i]
// Space: O(M)
class BIT {
    vector<int> node;
    static inline int lb(int x) { return x & -x; }
public:
    BIT(int N) : node(N + 1) {}
    int query(int i) { // query range is [-1, N-1]. [0,N-1] are valid external indices. -1 is a special index meaning 
empty set
        int ans = 0;
        for (++i; i; i -= lb(i)) ans += node[i];
        return ans;
    }
    void update(int i, int delta) {
        for (++i; i < node.size(); i += lb(i)) node[i] += delta;
    }
};
class Solution {
public:
    vector<int> countSmaller(vector<int>& A) {
        long N = A.size(), offset = 1e4; 
        vector<int> ans(N);
        BIT bit(2 * 1e4 + 1); // query(i) is the number of elements <= i
        for (int i = N - 1; i >= 0; --i) {
            ans[i] = bit.query(offset + A[i] - 1);
            bit.update(offset + A[i], 1);
        }
        return ans;
    }
};