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

1. Create an array res that will store the count of smaller elements for each element in nums.
2. Create a list of tuples index_num that will store the index and number pairs as (index, num) for each element in nums.
3. Create an empty list of tuples temp to store the temporary result.
4. Implement a merge-sort algorithm that sorts index_num and tracks the number of elements smaller than the current element in the right half.
5. 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.

1. We create an empty list res that will store the count of smaller elements for each element in nums.
   res = [0]*len(nums)

2. 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))]

3. We create an empty list of tuples temp to store the temporary result.
   temp = [0]*len(nums)

4. 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))
“`

1. 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) - i

2. Finally, 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 List countSmaller(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:
    vector countSmaller(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 IList CountSmaller(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;
    }
}