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] <= 104The Binary Indexed Tree (BIT) allows us to efficiently update elements and calculate cumulative frequencies in an iterative manner. In this approach, we traverse the input array from right to left, update the BIT with the index of the current number, and use the BIT to find the count of numbers which are smaller.
This C program uses a static array to represent a Binary Indexed Tree, or Fenwick Tree. It processes each element of the array from right to left and maintains cumulative frequencies of numbers within the bounds. First, it retrieves the cumulative frequency up to one less than the current index using the BIT, which gives the count of numbers less than the current number. Then, it updates the BIT with the frequency of the current number.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), where n is the number of elements in nums. Updating the BIT and querying both take O(log n) time.
Space Complexity: O(n) for the BIT and result array.
This approach takes advantage of the divide and conquer strategy combined with a binary search tree (BST). As we process each number from right to left, we insert them into the BST, which allows us to compute the count of elements smaller than the current number efficiently.
The C approach utilizes a binary search tree structure for efficient storage and retrieval of number counts. The insert function adds numbers to the tree while maintaining information about left and right subtree node counts. This allows quick determination of how many smaller elements precede the current number.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) on average, assuming balanced inserts into the BST.
Space Complexity: O(n) for storing BST nodes and result array.
| Approach | Complexity |
|---|---|
| Approach 1: Binary Indexed Tree (Fenwick Tree) | Time Complexity: O(n log n), where n is the number of elements in |
| Approach 2: Divide and Conquer with Binary Search Tree | Time Complexity: O(n log n) on average, assuming balanced inserts into the BST. |
[New Solution Link Below] LeetCode 315.Count of Smaller Numbers After Self Explanation and Solution • happygirlzt • 18,406 views views
Watch 9 more video solutions →Practice Count of Smaller Numbers After Self with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor