315. Count of Smaller Numbers After Self LeetCode Solution

In this guide, you will get 315. Count of Smaller Numbers After Self LeetCode Solution with the best time and space complexity. The solution to Count of Smaller Numbers After Self problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Count of Smaller Numbers After Self solution in C++
4. Count of Smaller Numbers After Self solution in Java
5. Count of Smaller Numbers After Self solution in Python
6. Additional Resources

Problem Statement of Count of Smaller Numbers After Self

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

Complexity Analysis

• Time Complexity: O(n\log n)
• Space Complexity: O(n)

315. Count of Smaller Numbers After Self LeetCode Solution in C++

class FenwickTree {
 public:
  FenwickTree(int n) : sums(n + 1) {}

  void add(int i, int delta) {
    while (i < sums.size()) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  int get(int i) const {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

 private:
  vector<int> sums;

  static inline int lowbit(int i) {
    return i & -i;
  }
};

class Solution {
 public:
  vector<int> countSmaller(vector<int>& nums) {
    vector<int> ans(nums.size());
    const unordered_map<int, int> ranks = getRanks(nums);
    FenwickTree tree(ranks.size());

    for (int i = nums.size() - 1; i >= 0; --i) {
      const int num = nums[i];
      ans[i] = tree.get(ranks.at(num) - 1);
      tree.add(ranks.at(num), 1);
    }

    return ans;
  }

 private:
  unordered_map<int, int> getRanks(const vector<int>& nums) {
    unordered_map<int, int> ranks;
    set<int> sorted(nums.begin(), nums.end());
    int rank = 0;
    for (const int num : sorted)
      ranks[num] = ++rank;
    return ranks;
  }
};
/* code provided by PROGIEZ */

315. Count of Smaller Numbers After Self LeetCode Solution in Java

class FenwickTree {
  public FenwickTree(int n) {
    sums = new int[n + 1];
  }

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

  public int get(int i) {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

  private int[] sums;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class Solution {
  public List<Integer> countSmaller(int[] nums) {
    List<Integer> ans = new ArrayList<>();
    Map<Integer, Integer> ranks = getRanks(nums);
    FenwickTree tree = new FenwickTree(ranks.size());

    for (int i = nums.length - 1; i >= 0; --i) {
      final int num = nums[i];
      ans.add(tree.get(ranks.get(num) - 1));
      tree.add(ranks.get(num), 1);
    }

    Collections.reverse(ans);
    return ans;
  }

  private Map<Integer, Integer> getRanks(int[] nums) {
    Map<Integer, Integer> ranks = new HashMap<>();
    SortedSet<Integer> sorted = new TreeSet<>();
    for (final int num : nums)
      sorted.add(num);
    int rank = 0;
    for (Iterator<Integer> it = sorted.iterator(); it.hasNext();)
      ranks.put(it.next(), ++rank);
    return ranks;
  }
}
// code provided by PROGIEZ

315. Count of Smaller Numbers After Self LeetCode Solution in Python

class FenwickTree:
  def __init__(self, n: int):
    self.sums = [0] * (n + 1)

  def add(self, i: int, delta: int) -> None:
    while i < len(self.sums):
      self.sums[i] += delta
      i += FenwickTree.lowbit(i)

  def get(self, i: int) -> int:
    summ = 0
    while i > 0:
      summ += self.sums[i]
      i -= FenwickTree.lowbit(i)
    return summ

  @staticmethod
  def lowbit(i: int) -> int:
    return i & -i


class Solution:
  def countSmaller(self, nums: list[int]) -> list[int]:
    ans = []
    ranks = self._getRanks(nums)
    tree = FenwickTree(len(ranks))

    for num in reversed(nums):
      ans.append(tree.get(ranks[num] - 1))
      tree.add(ranks[num], 1)

    return ans[::-1]

  def _getRanks(self, nums: list[int]) -> dict[int, int]:
    ranks = collections.Counter()
    rank = 0
    for num in sorted(set(nums)):
      rank += 1
      ranks[num] = rank
    return ranks
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.