Count of Smaller Numbers After Self in Python

Key takeaways:

The "Count of Smaller Numbers After Self" problem helps in data analysis, ranking systems, and algorithm optimization.
A naive solution with two loops has O(n²) time complexity, making it inefficient for large inputs.
Using Binary Search Trees (BST) or Binary Indexed Trees (BIT) provides a more efficient O(n log n) time complexity.
The solution involves iterating from right to left, inserting elements into the BST, and counting smaller elements.
The algorithm efficiently maintains order and counts smaller numbers using BST properties.

The “Count of Smaller Numbers After Self” problem is valuable for applications in data analysis, ranking systems, and algorithm development. It helps in scenarios like tracking how many elements are smaller than a given number in a dataset or comparing scores in competitive environments. This problem also provides useful practice in advanced techniques such as divide-and-conquer, binary search, and segment trees, which are important for optimizing performance in various computational tasks.

In this Answer, we will create an array where each element represents the count of numbers smaller than it to its right in the input array.

Problem statement

Given an integer array nums, return a new integer array counts, where counts[i] is the number of smaller elements to the right of nums[i].

Constraints:

$1 <=$ nums.length $\leq$ $10{^5}$
$-10{^4} <=$ nums.length $\leq$ $10{^4}$

Let’s take a look at a few examples to get a better understanding of the problem statement:

Algorithm to count smaller numbers after self

A simple approach would be to use two loops, comparing each element to all elements to its right. This, however, results in a time complexity of $O(n*n)$ which is inefficient for larger inputs.

A better approach would be to use a data structure like Binary Indexed Tree (BIT) or Binary Search Tree (BST), achieving a more favorable time complexity of $O(n log n)$ . For simplicity, we will use a variant of the BST approach.

Here’s how the algorithm works:

Start with an empty BST.
Iterate over the input array in reverse order, i.e., from right to left.
For each number, insert it into the BST while tracking how many numbers are smaller to its right.
Use the smaller property of BST nodes to compute the count efficiently.
Finally, we get the result list where each entry corresponds to the count of numbers smaller than the respective entry in nums to its right.

Python solution

Let’s define a Node class that we’ll use for our Binary Search Tree. This Node class will hold the node’s value, a count of nodes in the left subtree, and references to the left and right child nodes.

def count_smaller(nums):
    def insert(node, val, result, i):
      if not node:
        return Node(val), result
      if val <= node.val:
        node.left, result = insert(node.left, val, result, i)
        node.smaller += 1
      else:
        node.right, result = insert(node.right, val, result, i)
        result[i] += node.smaller + 1
      return node, result
    result = [0] * len(nums)
    root = None
    for i in reversed(range(len(nums))):
        root, result = insert(root, nums[i], result, i)
    return result
    
    
# Driver code 
def main():
    test_cases = [
      # Test Case 1: Standard array with distinct values
      ([5, 2, 6, 1], [2, 1, 1, 0]),
      # Test Case 2: Array with duplicates
      ([3, 3, 1, 2], [2, 2, 0, 0]),
      # Test Case 3: Array with all decreasing values
      ([5, 4, 3, 2, 1], [4, 3, 2, 1, 0]),
      # Test Case 4: Array with all increasing values
      ([1, 2, 3, 4, 5], [0, 0, 0, 0, 0]),
      # Test Case 5: Single element array
      ([7], [0])
    ]
    print("Testing count_smaller function:\n")
    for i, (nums, expected) in enumerate(test_cases, 1):
      result = count_smaller(nums)
      print(f"Test Case {i}:")
      print(f"Input: {nums}")
      print(f"Output: {result}")
      print(f"Expected: {expected}")
      print(f"Pass: {result == expected}\n")
# Run the test cases
main()

This approach works efficiently because the BST maintains a sorted order of elements as we iterate. For each insertion:

If the number is smaller or equal to the current node, increment the smaller counter and move left.
If the number is greater, add the smaller count from the node plus one (for the node itself) to the result and move right.

Time complexity

The time complexity of the solution is $O(nlogn)$ on average, as each of the n elements is inserted into a Binary Search Tree (BST) with a height of $O(logn)$ . In the worst case, when the BST becomes skewed, the time complexity can degrade to $O(n^2)$ .

Space complexity

The space complexity is $O(n)$ , accounting for the storage of the BST and the result array.

Practice resources for LeetCode problems

To further strengthen your coding skills and boost your technical interview preparation, here are some LeetCode problems to practice:

Also, you can explore these courses designed specifically to help you ace technical interviews:

Grokking the Coding Interview Patterns

Moreover, if you’re confident in your preparation, consider trying Educative’s AI-powered mock interviews. Mock interviews are excellent for building confidence, sharpening problem-solving skills, and identifying areas to improve before the actual interview.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is the time complexity of the BST approach?

In the average case, the time complexity is $O(nlogn)$ , where $n$ is the length of the input array.

Can this problem be solved using a different data structure?

It can be solved using a Binary Indexed Tree (BIT) or Fenwick Tree for similar time complexity.

What are the common pitfalls in solving this problem?

One common mistake is mishandling duplicate values or not maintaining the smaller property correctly during BST traversal.

Where can I practice similar problems?

You can find this problem and similar ones on platforms like LeetCode or Educative.io.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources