Problem Description

You are given an array nums containing integers. For each element in the array, you need to count how many other elements in the array are smaller than it.

Specifically, for each nums[i], count the number of valid indices j where:

• j != i (the index is different from the current element's index)
• nums[j] < nums[i] (the value at index j is strictly less than the value at index i)

Return an array where each position contains the count of smaller elements for the corresponding position in the original array.

For example, if nums = [8, 1, 2, 2, 3], the output would be [4, 0, 1, 1, 3] because:

• For nums[0] = 8: there are 4 smaller elements (1, 2, 2, 3)
• For nums[1] = 1: there are 0 smaller elements
• For nums[2] = 2: there is 1 smaller element (1)
• For nums[3] = 2: there is 1 smaller element (1)
• For nums[4] = 3: there are 3 smaller elements (1, 2, 2)

The solution uses sorting and binary search. It creates a sorted copy of the array arr, then for each element x in the original array, uses bisect_left to find the position where x would be inserted in the sorted array. This position represents exactly how many elements are smaller than x.

Intuition

The key insight is that if we sort the array, the position of an element in the sorted array tells us exactly how many elements are smaller than it.

Think about it this way: when we sort an array in ascending order, the smallest element goes to position 0, the second smallest to position 1, and so on. So if an element ends up at position k in the sorted array, it means there are exactly k elements smaller than it.

For example, with nums = [8, 1, 2, 2, 3], the sorted array would be [1, 2, 2, 3, 8]. The element 8 is at index 4 in the sorted array, which means there are 4 elements smaller than it.

However, we can't just sort the original array and return the indices because we need to maintain the original order of elements in our answer. So we:

1. Create a sorted copy of the array
2. For each element in the original array, find where it would be placed in the sorted array

The position where an element would be inserted in a sorted array is exactly the count of elements smaller than it. This is what bisect_left does - it finds the leftmost position where we could insert an element to maintain sorted order. This position equals the number of elements that are strictly less than our target element.

The reason we use bisect_left instead of bisect_right is to handle duplicates correctly. When there are duplicate values, bisect_left gives us the position of the first occurrence, which correctly counts only the elements that are strictly smaller than our target value.

Learn more about Sorting patterns.

Solution Approach

The solution uses sorting combined with binary search to efficiently count smaller elements for each position.

Step 1: Create a sorted copy

arr = sorted(nums)

We create a new array arr that contains all elements from nums but in sorted ascending order. This sorted array serves as our reference to count smaller elements.

Step 2: Use binary search for each element

return [bisect_left(arr, x) for x in nums]

For each element x in the original nums array, we use bisect_left(arr, x) to find its position in the sorted array.

How bisect_left works:

• bisect_left(arr, x) returns the leftmost position where x should be inserted in arr to maintain sorted order
• This position is exactly equal to the count of elements that are strictly less than x
• For example, if arr = [1, 2, 2, 3, 8] and x = 3, then bisect_left(arr, 3) returns 3, meaning there are 3 elements smaller than 3

Time Complexity Analysis:

• Sorting the array takes O(n log n) time
• For each of the n elements, we perform a binary search which takes O(log n) time
• Total time complexity: O(n log n) + O(n * log n) = O(n log n)

Space Complexity:

• We create a sorted copy of the array, which takes O(n) space
• The result array also takes O(n) space
• Total space complexity: O(n)

Why this approach works for duplicates: When there are duplicate values in the array, bisect_left always returns the index of the first occurrence in the sorted array. This ensures we only count elements that are strictly smaller than the current element, not equal to it.

Example Walkthrough

Let's walk through the solution with nums = [5, 2, 6, 1].

Step 1: Create a sorted copy

• Original array: nums = [5, 2, 6, 1]
• Sorted array: arr = [1, 2, 5, 6]

Step 2: Process each element using binary search

For nums[0] = 5:

• Use bisect_left(arr, 5) on [1, 2, 5, 6]
• Binary search finds that 5 should be inserted at index 2
• This means there are 2 elements smaller than 5 (which are 1 and 2)
• Result: 2

For nums[1] = 2:

• Use bisect_left(arr, 2) on [1, 2, 5, 6]
• Binary search finds that 2 should be inserted at index 1
• This means there is 1 element smaller than 2 (which is 1)
• Result: 1

For nums[2] = 6:

• Use bisect_left(arr, 6) on [1, 2, 5, 6]
• Binary search finds that 6 should be inserted at index 3
• This means there are 3 elements smaller than 6 (which are 1, 2, and 5)
• Result: 3

For nums[3] = 1:

• Use bisect_left(arr, 1) on [1, 2, 5, 6]
• Binary search finds that 1 should be inserted at index 0
• This means there are 0 elements smaller than 1
• Result: 0

Final answer: [2, 1, 3, 0]

Let's verify:

• 5 has 2 smaller elements (2, 1) ✓
• 2 has 1 smaller element (1) ✓
• 6 has 3 smaller elements (5, 2, 1) ✓
• 1 has 0 smaller elements ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by two operations:

1. Sorting the array using sorted(nums) takes O(n × log n) time, where n is the length of the input array
2. The list comprehension performs n binary searches using bisect_left(), where each binary search takes O(log n) time, resulting in O(n × log n) total time

Since both operations have the same complexity, the overall time complexity is O(n × log n).

Space Complexity: O(n)

The space complexity comes from:

1. The sorted array arr which stores a copy of all n elements from the input, requiring O(n) space
2. The output list created by the list comprehension, which also contains n elements, requiring O(n) space

Therefore, the total space complexity is O(n), where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing bisect_left with bisect_right for duplicate values

The Problem: A common mistake is using bisect_right instead of bisect_left, or not understanding the difference when dealing with duplicates. This would give incorrect counts for duplicate elements.

Example of the issue:

nums = [8, 1, 2, 2, 3]
sorted_nums = [1, 2, 2, 3, 8]

# Using bisect_right (WRONG):
bisect_right(sorted_nums, 2)  # Returns 3 (includes both 2's)
# This would incorrectly count the other 2 as "smaller"

# Using bisect_left (CORRECT):
bisect_left(sorted_nums, 2)   # Returns 1 (position before all 2's)
# This correctly counts only elements strictly less than 2

Solution: Always use bisect_left for this problem since we need to count elements strictly less than the current element. bisect_left returns the leftmost insertion point, which equals the count of smaller elements.

Pitfall 2: Modifying the original array instead of creating a sorted copy

The Problem: Sorting the original array in-place would destroy the original order, making it impossible to map results back to the correct positions.

Incorrect approach:

def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
    nums.sort()  # WRONG: This modifies the original array
    return [bisect_left(nums, x) for x in nums]
    # This would return [0, 1, 2, 3, 4] for any sorted input

Solution: Always create a separate sorted copy:

sorted_nums = sorted(nums)  # Creates a new sorted array
# Original nums array remains unchanged

Pitfall 3: Not handling edge cases properly

The Problem: Forgetting to test edge cases like empty arrays, single-element arrays, or arrays with all identical elements.

Edge cases to consider:

# Empty array
nums = []  # Should return []

# Single element
nums = [5]  # Should return [0]

# All elements identical
nums = [3, 3, 3, 3]  # Should return [0, 0, 0, 0]

# Negative numbers
nums = [-1, -2, 3, 0]  # Should work correctly with negatives

Solution: The binary search approach naturally handles these edge cases correctly, but it's important to verify:

def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
    if not nums:  # Handle empty array explicitly if needed
        return []
  
    sorted_nums = sorted(nums)
    return [bisect_left(sorted_nums, num) for num in nums]