Count of Smaller Numbers After Self
Problem Description
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
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest approach is to check each element and count how many numbers after it are smaller. This involves iterating over each element and then iterating over subsequent elements to count the smaller numbers.
Code:
- Time Complexity: O(n^2), where n is the number of elements in the array.
- Space Complexity: O(1), since we are using only a fixed amount of extra space.
2. Binary Search Tree (BST)
Intuition:
By using a BST, where each node contains the number of times it and all its left descendants have been inserted, we can efficiently insert each number in reverse order and count how many smaller elements have already been inserted.
Code:
- Time Complexity: O(n log n), assuming the BST is balanced.
- Space Complexity: O(n), due to the space needed for the BST.
3. Fenwick Tree (or Binary Indexed Tree)
Intuition:
Fenwick Tree is useful for maintaining prefix sums efficiently. We can translate the problem into finding the frequency of numbers, querying this frequency with a Fenwick Tree while iterating the array backwards.
Code:
- Time Complexity: O(n log n), due to the operations on the Fenwick Tree.
- Space Complexity: O(n), for the Fenwick Tree.
4. Merge Sort
Intuition:
This is a modification of merge sort. What we can do is keep track of how many elements are moved after an item in the merge process.
Code:
- Time Complexity: O(n log n), due to the sorting process.
- Space Complexity: O(n), due to the helper arrays used in merge sort.