Question

Formatted question description: https://leetcode.ca/all/315.html

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Algorithm

You can start traversing from the right, and keep putting the traversed numbers into another sort array, and store this sort array in ascending order, So, if you are looking for a few smaller numbers to the right of the current value, then you have to find the position where the current value should be placed in the sort array (In order to improve efficiency, use the binary search method to determine where the current value should be placed), that is, there are several smaller numbers on the right.

example:

nums: [5,2,6,1] When i = 3, nums[i] =1, sort[0]=nums[i];

0 1 2 3     <= sort[] index
1           <= sort[] value

When i = 2, nums[i] = 6, by using the dichotomy search in sort (currently only element 1), it is found that 6 should be inserted after 1, [1,6], ie index=1, sort[index] =nums[i]; So the number of numbers smaller than it on the right of the current value 6 is index=1

0 1 2 3
1 6

When i = 1, nums[i] = 2, by using the dichotomy search in sort (currently only elements 1, 6), it is found that 2 should be inserted after 1, [1,2,6], ie index=1, sort[index]=nums[i]; So the number of numbers smaller than it on the right side of the current value 2 is index=1

0 1 2 3
1 2 6

When i = 0 and nums[i] = 5, by using the dichotomy search in sort (currently only elements 1, 2, 6), it is found that 5 should be inserted after 2, [1,2,5,6], that is index=2, sort[index]=nums[i]; So the number of numbers smaller than it on the right of the current value of 5 is index=2

0 1 2 3
1 2 5 6

Then, the result is Output: [2,1,1,0].

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Count_of_Smaller_Numbers_After_Self {

    public static void main(String[] args) {
        Count_of_Smaller_Numbers_After_Self out = new Count_of_Smaller_Numbers_After_Self();
        Solution s = out.new Solution();

        System.out.println(s.countSmaller(new int[]{5,2,6,1}));
    }

    class Solution {
        public List<Integer> countSmaller(int[] nums) {

            List<Integer> result = new ArrayList<>();
            List<Integer> sorted = new ArrayList<>();

            if (nums == null || nums.length == 0) {
                return result;
            }

            for (int i = nums.length - 1; i >= 0; i--) {

                // binary search for current pos, reference: Arrays.binarySearch()
                int left = 0;
                int right = sorted.size();
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (nums[i] <= sorted.get(mid)) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }

                // now nums[i] should be placed at index left
                sorted.add(left, nums[i]); // @note: equal to .insert()
                result.add(0, left); // @note: insert to 1st node，因为是倒序scan array
            }

            return result;
        }
    }
}

############

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int v : nums) {
            s.add(v);
        }
        List<Integer> alls = new ArrayList<>(s);
        alls.sort(Comparator.comparingInt(a -> a));
        int n = alls.size();
        Map<Integer, Integer> m = new HashMap<>(n);
        for (int i = 0; i < n; ++i) {
            m.put(alls.get(i), i + 1);
        }
        BinaryIndexedTree tree = new BinaryIndexedTree(n);
        LinkedList<Integer> ans = new LinkedList<>();
        for (int i = nums.length - 1; i >= 0; --i) {
            int x = m.get(nums[i]);
            tree.update(x, 1);
            ans.addFirst(tree.query(x - 1));
        }
        return ans;
    }
}

class BinaryIndexedTree {
    private int n;
    private int[] c;

    public BinaryIndexedTree(int n) {
        this.n = n;
        c = new int[n + 1];
    }

    public void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += lowbit(x);
        }
    }

    public int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= lowbit(x);
        }
        return s;
    }

    public static int lowbit(int x) {
        return x & -x;
    }
}

// OJ: https://leetcode.com/problems/count-of-smaller-numbers-after-self/
// 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;
    }
};

'''
bisect: maintaining a list in sorted order without having to sort the list after each insertion.
https://docs.python.org/3/library/bisect.html

bisect.bisect_left()
Locate the insertion point for x in a to maintain sorted order.

bisect.bisect_right() or bisect.bisect()
Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.


bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
Insert x in a in sorted order.
Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.


bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort(a, x, lo=0, hi=len(a), *, key=None)
Similar to insort_left(), but inserting x in a after any existing entries of x.


>>> import bisect
>>> bisect.bisect_left([1,2,3], 2)
1
>>> bisect.bisect_right([1,2,3], 2)
2

>>> a = [1, 1, 1, 2, 3]
>>> bisect.insort_left(a, 1.0)
>>> a
[1.0, 1, 1, 1, 2, 3]

>>> a = [1, 1, 1, 2, 3]
>>> bisect.insort_right(a, 1.0)
>>> a
[1, 1, 1, 1.0, 2, 3]

>>> a = [1, 1, 1, 2, 3]
>>> bisect.insort(a, 1.0)
>>> a
[1, 1, 1, 1.0, 2, 3]
'''

import bisect

class Solution(object):
  def countSmaller(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    ans = []
    bst = []
    for num in reversed(nums):
      idx = bisect.bisect_left(bst, num)
      ans.append(idx)
      bisect.insort(bst, num)
    return ans[::-1]

############

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x):
        s = 0
        while x > 0:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        alls = sorted(set(nums))
        m = {v: i for i, v in enumerate(alls, 1)}
        tree = BinaryIndexedTree(len(m))
        ans = []
        for v in nums[::-1]:
            x = m[v]
            tree.update(x, 1)
            ans.append(tree.query(x - 1))
        return ans[::-1]

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
	return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += this.lowbit(x)
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= this.lowbit(x)
	}
	return s
}

func countSmaller(nums []int) []int {
	s := make(map[int]bool)
	for _, v := range nums {
		s[v] = true
	}
	var alls []int
	for v := range s {
		alls = append(alls, v)
	}
	sort.Ints(alls)
	m := make(map[int]int)
	for i, v := range alls {
		m[v] = i + 1
	}
	ans := make([]int, len(nums))
	tree := newBinaryIndexedTree(len(alls))
	for i := len(nums) - 1; i >= 0; i-- {
		x := m[nums[i]]
		tree.update(x, 1)
		ans[i] = tree.query(x - 1)
	}
	return ans
}

315 - Count of Smaller Numbers After Self

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions