Solution For Count Of Smaller Numbers After Self
The Count of Smaller Numbers After Self problem on LeetCode is a challenging problem that requires you to find the number of elements that are smaller than the current element in an array. In this article, we will provide you with a detailed solution to this problem.
Problem Statement
Given an integer array nums, return an array answer such that answer[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 only 1 smaller element (1).
To the right of 1 there is 0 smaller elements.
Approach
We will use the merge-sort approach to find the answer to this problem. The idea behind the merge-sort approach is to divide the array into two halves and count the number of smaller elements in each half separately. Once we have the counts from the left and right half, we merge the two arrays while keeping the order of the elements and updating the count of smaller elements.
Algorithm
- Create an array res that will store the count of smaller elements for each element in nums.
- Create a list of tuples index_num that will store the index and number pairs as (index, num) for each element in nums.
- Create an empty list of tuples temp to store the temporary result.
- Implement a merge-sort algorithm that sorts index_num and tracks the number of elements smaller than the current element in the right half.
- For each element (index, num) in index_num, add the count of elements in the right half to res[index].
Python Implementation
Here’s the Python implementation of the above algorithm:
“`
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
res = [0]len(nums)
index_num = [(i, nums[i]) for i in range(len(nums))]
temp = [0]len(nums)
def merge_sort(nums, left, right):
if right - left <= 1:
return nums[left:right]
mid = (left + right)//2
left_arr = merge_sort(nums, left, mid)
right_arr = merge_sort(nums, mid, right)
i, j = 0, 0
count = 0
while i < len(left_arr) or j < len(right_arr):
if j == len(right_arr) or (i < len(left_arr) and left_arr[i][1] <= right_arr[j][1]):
temp[i + j] = left_arr[i]
res[left_arr[i][0]] += count
i += 1
else:
temp[i + j] = right_arr[j]
count += 1
j += 1
return temp[:i+j]
merge_sort(index_num, 0, len(index_num))
return res
“`
Time Complexity: O(n log n)
Space Complexity: O(n)
Let’s understand the implementation step by step.
We create an empty list res that will store the count of smaller elements for each element in nums.
res = [0]*len(nums)
We create a list of tuples index_num that will store the index and number pairs as (index, num) for each element in nums.
index_num = [(i, nums[i]) for i in range(len(nums))]
We create an empty list of tuples temp to store the temporary result.
temp = [0]*len(nums)
We implement a merge-sort algorithm to sort index_num and count the number of elements smaller than the current element in the right half.
“`
def merge_sort(nums, left, right):
if right – left <= 1:
return nums[left:right] mid = (left + right)//2
left_arr = merge_sort(nums, left, mid)
right_arr = merge_sort(nums, mid, right)
i, j = 0, 0
count = 0
while i < len(left_arr) or j < len(right_arr):
if j == len(right_arr) or (i < len(left_arr) and left_arr[i][1] <= right_arr[j][1]):
temp[i + j] = left_arr[i] res[left_arr[i][0]] += count
i += 1
else:
temp[i + j] = right_arr[j] count += 1
j += 1
return temp[:i+j]
merge_sort(index_num, 0, len(index_num))
“`
For each element (index, num) in index_num, we add the count of elements in the right half to res[index].
for i, num in index_num:
res[i] = res[i] + (len(nums) - 1) - iFinally, we return res.
return res
Conclusion
In this article, we provided a detailed solution to the Count of Smaller Numbers After Self problem on LeetCode. We used the merge-sort approach to divide the array into two halves and count the number of smaller elements in each half separately. Finally, we merged the two arrays while keeping the order of the elements and updating the count of smaller elements. This problem can be solved in O(n log n) time complexity and O(n) space complexity.
Step by Step Implementation For Count Of Smaller Numbers After Self
public class Solution { public ListcountSmaller(int[] nums) { List res = new ArrayList<>(); if(nums == null || nums.length == 0) return res; TreeNode root = new TreeNode(nums[nums.length - 1]); res.add(0); for(int i = nums.length - 2; i >= 0; i--) { int count = insert(root, nums[i]); res.add(count); } Collections.reverse(res); return res; } private int insert(TreeNode root, int val) { int thisCount = 0; while(true) { if(val <= root.val) { root.count++; if(root.left == null) { root.left = new TreeNode(val); break; } else { root = root.left; } } else { thisCount += root.count; if(root.right == null) { root.right = new TreeNode(val); break; } else { root = root.right; } } } return thisCount; } } class TreeNode { TreeNode left, right; int val, count = 1; public TreeNode(int val) { this.val = val; } }
def countSmaller(self, nums): ans = [] # Sort the array in reverse order for i in xrange(len(nums)): # Find the position of current element in the sorted array pos = bisect.bisect_left(ans, nums[i]) # Insert the current element in the sorted array ans.insert(pos, nums[i]) # Append the number of elements smaller than the current element to the result ans.append(pos) return ans
var countSmaller = function(nums) { // create an empty array to store the results let results = []; // iterate through the nums array from the end for (let i = nums.length - 1; i >= 0; i--) { // create a counter to keep track of how many smaller numbers there are let counter = 0; // iterate through the nums array from the current index to the end for (let j = i; j < nums.length; j++) { // if the current number is smaller than the number at index j, increment the counter if (nums[i] > nums[j]) { counter++; } } // add the counter to the results array results.unshift(counter); } // return the results array return results; };
class Solution { public: vectorcountSmaller(vector & nums) { int n = nums.size(); vector ans(n); vector t; for (int i = n - 1; i >= 0; i--) { int index = getIndex(t, nums[i]); ans[i] = index; t.insert(t.begin() + index, nums[i]); } return ans; } private: int getIndex(vector &t, int val) { int n = t.size(), a = 0, b = n - 1; if (n == 0) return 0; if (val <= t[a]) return a; if (val > t[b]) return b + 1; while (a <= b) { int c = (a + b) / 2; if (t[c] >= val) b = c - 1; else a = c + 1; } return a; } };
public class Solution { public IListCountSmaller(int[] nums) { // create an empty list to store the results IList results = new List (); // edge case: if the input array is empty, return an empty list if (nums.Length == 0) { return results; } // create a new array that will store the number of smaller elements to the right of each element int[] smallerCounts = new int[nums.Length]; // create a balanced binary search tree (BST) BST tree = new BST(nums[nums.Length - 1]); // starting from the rightmost element in the input array, insert each element into the BST for (int i = nums.Length - 2; i >= 0; i--) { // insert the current element into the BST tree.Insert(nums[i]); // the number of smaller elements to the right of the current element is equal to the number of elements in the left subtree of the current element's node in the BST smallerCounts[i] = tree.GetLeftSubtreeSize(); } // add the number of smaller elements to the right of each element to the results list foreach (int count in smallerCounts) { results.Add(count); } return results; } } // Binary Search Tree (BST) node class public class BSTNode { public int val; public int leftSubtreeSize; public BSTNode left; public BSTNode right; public BSTNode(int val) { this.val = val; this.leftSubtreeSize = 0; this.left = null; this.right = null; } } // Binary Search Tree (BST) class public class BST { public BSTNode root; public BST(int val) { this.root = new BSTNode(val); } // insert a new node into the BST public void Insert(int val) { InsertHelper(this.root, val); } // helper method to insert a new node into the BST public void InsertHelper(BSTNode node, int val) { // if the value to insert is less than the current node's value, insert it into the left subtree if (val < node.val) { // if the left subtree is empty, create a new node and insert it if (node.left == null) { node.left = new BSTNode(val); } // otherwise, recurse on the left subtree else { InsertHelper(node.left, val); } // increment the size of the left subtree node.leftSubtreeSize++; } // if the value to insert is greater than or equal to the current node's value, insert it into the right subtree else { // if the right subtree is empty, create a new node and insert it if (node.right == null) { node.right = new BSTNode(val); } // otherwise, recurse on the right subtree else { InsertHelper(node.right, val); } } } // get the number of elements in the left subtree public int GetLeftSubtreeSize() { return this.root.leftSubtreeSize; } }