Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Count Smaller elements

Hard Acceptance 38.16% Points 40

Given an array arr containing non-negative integers. Count and return an array res where res[i] denotes the number of smaller elements on right side of arr[i].

Examples
Example 1

Example 1

Input: arr[] = [12, 1, 2, 3, 0, 11, 4]

Output: [6, 1, 1, 1, 0, 1, 0]

Explanation: There are 6 smaller elements right after 12. There is 1 smaller element right after 1. And so on.

Example 2

Example 2

Input: arr[] = [1, 2, 3, 4, 5]

Output: [0, 0, 0, 0, 0]

Explanation: There are 0 smaller elements right after 1. There are 0 smaller elements right after 2. And so on.

Constraints
  • 1 = arr.size() = 10^6
  • 0 = arr[i] = 10^8
Hints
  • Expected Time Complexity: O(n log n)
  • Expected Auxiliary Space: O(n)
Topics
Array
Companies
Google
Added 01 Jan 2025 38.16% acceptance
Ln 1, Col 1Sign in to save your code
12 1 2 3 0 11 4
6 1 1 1 0 1 0