LeetCode 315: Count of Smaller Numbers After Self Solution in Python – A Step-by-Step Guide

What Is LeetCode 315: Count of Smaller Numbers After Self?

In LeetCode 315: Count of Smaller Numbers After Self, you’re given an integer array nums, and your task is to return a new array where each element result[i] is the count of numbers to the right of nums[i] that are strictly smaller. For example, with [5, 2, 6, 1], the result is [2, 1, 1, 0]—5 has 2 smaller (2, 1), 2 has 1 (1), 6 has 1 (1), and 1 has 0. This problem tests your ability to process arrays dynamically, building on concepts from LeetCode 307: Range Sum Query - Mutable.

Problem Statement

• Input: An integer array nums.
• Output: An integer array—count of smaller numbers to the right for each element.
• Rules:
• Count only strictly smaller numbers (<, not <=).
• Consider only elements to the right.

Constraints

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

Examples

• Input: [5,2,6,1]
• Output: [2,1,1,0]
• Input: [1]
• Output: [0]
• Input: [1,2,3,4]
• Output: [0,0,0,0]

Understanding the Problem: Counting Smaller Numbers

To solve LeetCode 315: Count of Smaller Numbers After Self in Python, we need to compute, for each index, how many subsequent elements are smaller, efficiently handling large arrays. A naive approach—scanning right for each element—is O(n²), too slow for 10⁵ elements. Instead, we’ll use:

• Best Solution (BIT): O(n log n) time, O(n) space—fast and scalable.
• Alternative Solution (Merge Sort): O(n log n) time, O(n) space—intuitive but complex.

Let’s start with the BIT solution, explained in a beginner-friendly way.

Best Solution: Binary Indexed Tree (BIT)

Why This Is the Best Solution

The Binary Indexed Tree (BIT) approach is the top choice for LeetCode 315 because it’s efficient—O(n log n) time, O(n) space—and elegantly handles dynamic counting. It processes the array right-to-left, using a BIT to track frequencies of numbers and query counts of smaller ones in logarithmic time. It’s like a real-time scoreboard—smart and quick!

How It Works

Think of BIT as a cumulative frequency tracker:

• Step 1: Normalize Numbers:
• Shift numbers to positive range (add min + 1) to fit BIT indexing.
• Step 2: Process Right-to-Left:
• For each number, query BIT for count of smaller, then update BIT with this number.
• Step 3: Use BIT Operations:
• Update: Add 1 to frequency at index.
• Query: Sum frequencies up to index - 1.
• Step 4: Why It Works:
• BIT supports fast updates and prefix sums.
• Right-to-left ensures only future elements are counted.

It’s like tallying scores as you go—efficiently!

Step-by-Step Example

Example: nums = [5,2,6,1]

• Normalize: Min = 1, Shift = 2, Adjusted = [7,4,8,3]
• BIT Size: 9 (max + 1)
• Process:
• 1 (3): Query(2) = 0, Update(3), Result[3] = 0
• 6 (8): Query(7) = 1, Update(8), Result[2] = 1
• 2 (4): Query(3) = 1, Update(4), Result[1] = 1
• 5 (7): Query(6) = 2, Update(7), Result[0] = 2
• Output: [2,1,1,0]

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        # Normalize numbers to positive range
        min_val = min(nums)
        offset = abs(min_val) + 1 if min_val < 0 else 1
        adjusted = [num + offset for num in nums]
        max_val = max(adjusted)

        # Initialize BIT
        bit = [0] * (max_val + 1)

        def update(index):
            while index <= max_val:
                bit[index] += 1
                index += index & (-index)  # Next index via LSB

        def query(index):
            total = 0
            while index > 0:
                total += bit[index]
                index -= index & (-index)  # Prev index via LSB
            return total

        # Process right-to-left
        result = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):
            result[i] = query(adjusted[i] - 1)  # Count smaller
            update(adjusted[i])                 # Add current

        return result

• Lines 3-4: Handle empty case.
• Lines 6-9: Normalize numbers for BIT (1-based).
• Line 11: BIT array sized to max value.
• Lines 13-17: Update BIT with frequency.
• Lines 19-24: Query sum of frequencies up to index.
• Lines 27-30: Right-to-left:
• Query smaller count, update BIT.
• Time Complexity: O(n log n)—n updates/queries.
• Space Complexity: O(n)—BIT and result.

This is like a counting ninja—fast and precise!

Alternative Solution: Merge Sort with Index Tracking

Why an Alternative Approach?

The Merge Sort approach also runs in O(n log n) time, O(n) space, but uses a divide-and-conquer strategy, counting inversions during the merge step. It’s more intuitive for those familiar with sorting, though it’s trickier to implement. It’s like sorting the leaderboard while tallying—clever and educational!

How It Works

Sort and count:

• Step 1: Pair numbers with indices.
• Step 2: Merge Sort:
• During merge, count elements from right half smaller than left.
• Step 3: Build result from inversion counts.

Step-by-Step Example

Example: nums = [5,2,6,1]

• Pairs: [(5,0), (2,1), (6,2), (1,3)]
• Merge Sort:
• Split: [(5,0), (2,1)], [(6,2), (1,3)]
• Merge: [(2,1), (5,0)], [(1,3), (6,2)]
• Counts: 2>5 (1), 1<6 (1), 2<5 (1), 5<6 (1)
• Final: [(1,3), (2,1), (5,0), (6,2)]
• Result: [2,1,1,0]

Code for Merge Sort Approach

Copy codeclass Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        # Pair numbers with indices
        arr = [(num, i) for i, num in enumerate(nums)]
        result = [0] * len(nums)

        def merge_sort(arr, left, right):
            if left >= right:
                return
            mid = (left + right) // 2
            merge_sort(arr, left, mid)
            merge_sort(arr, mid + 1, right)
            merge(arr, left, mid, right)

        def merge(arr, left, mid, right):
            temp = []
            i, j = left, mid + 1
            while i <= mid and j <= right:
                if arr[i][0] <= arr[j][0]:
                    temp.append(arr[i])
                    i += 1
                else:
                    result[arr[j][1]] += mid - i + 1
                    temp.append(arr[j])
                    j += 1
            while i <= mid:
                temp.append(arr[i])
                i += 1
            while j <= right:
                temp.append(arr[j])
                j += 1
            arr[left:right + 1] = temp

        merge_sort(arr, 0, len(nums) - 1)
        return result

• Time Complexity: O(n log n)—merge sort.
• Space Complexity: O(n)—temp arrays and result.

It’s a sorting counter—ingenious!

Comparing the Two Solutions

• BIT (Best):
• Pros: O(n log n) time, O(n) space, straightforward.
• Cons: BIT less intuitive.
• Merge Sort (Alternative):
• Pros: O(n log n) time, O(n) space, sorting-based.
• Cons: More complex logic.

BIT wins for simplicity and speed.

Additional Examples and Edge Cases

• [1,1]: [0,0].
• [2,0,1]: [2,0,0].
• []: [].

Both handle these well.

Complexity Breakdown

• BIT: Time O(n log n), Space O(n).
• Merge Sort: Time O(n log n), Space O(n).

BIT is leaner in practice.

Key Takeaways

• BIT: Dynamic counting—brilliant!
• Merge Sort: Sort and count—clever!
• Python: Arrays and logic shine—see [Python Basics](/python/basics).
• Counting: Right-side focus is key.

Final Thoughts: Count the Small fry

LeetCode 315: Count of Smaller Numbers After Self in Python is a data structure delight. BIT offers efficiency and elegance, while Merge Sort provides a sorting twist. Want more counting challenges? Try LeetCode 327: Count of Range Sum or LeetCode 493: Reverse Pairs. Ready to tally? Head to Solve LeetCode 315 on LeetCode and count those smaller numbers today!