Problem 315

Abstract / Summary

Given a list of numbers, count how many smaller numbers appear to the right of each number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0315.py

class Solution:
    def getpos(self, nums, value):
        low = 0
        high = len(nums)
        while low < high:
            mid = (low + high) // 2;
            if nums[mid] < value:
                low = mid + 1
            else:
                high = mid
        return low

    def countSmaller(self, nums: List[int]) -> List[int]:
        # modified sorting
        result = []
        done = []
        for i in reversed(nums):
            pos = self.getpos(done, i)
            done.insert(pos, i)
            result.append(pos)

        return reversed(result)
22 lines | 597 bytes | submitted August 17, 2023 | GitHub   5% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 44% (900k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Binary Indexed Tree
  • Binary Search
  • Divide And Conquer
  • Merge Sort
  • Ordered Set
  • Segment Tree
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a class Solution with two methods: getpos and countSmaller. The purpose of the code is to compute, for each element in an input list, the number of smaller elements that appear to its right. The algorithm processes the input list in reverse order, maintaining a sorted auxiliary list (done) that represents the elements already examined. For each element, a binary search (getpos) determines the insertion index in the sorted list, which directly corresponds to the count of smaller elements to the right. The insertion is performed with list.insert, and the index is recorded in the result list. Finally, the result list is reversed to align with the original order of the input.

Key Steps

The binary search routine encapsulated in getpos isolates the logic for locating the correct insertion point within a sorted list.

def getpos(self, nums, value):
    low = 0
    high = len(nums)
    while low < high:
        mid = (low + high) // 2
        if nums[mid] < value:
            low = mid + 1
        else:
            high = mid
    return low

The main method countSmaller iterates over the input list from right to left, using the binary search to find the appropriate position, inserting the element, and storing the position.

def countSmaller(self, nums: List[int]) -> List[int]:
    result = []
    done = []
    for i in reversed(nums):
        pos = self.getpos(done, i)
        done.insert(pos, i)
        result.append(pos)
    return reversed(result)

The reversed(result) call produces an iterator that yields the counts in the original left-to-right order, matching the expected output format.

Edge Cases Handled

When the auxiliary list done is empty, the binary search loop terminates immediately because high is zero, and the function returns 0. This correctly indicates that there are no smaller elements to the right of the current value.

If all previously processed elements are larger than the current element, the binary search will converge to the lower bound 0. Inserting at index 0 places the current element at the beginning of the sorted list, and the recorded position 0 reflects that no smaller elements exist to its right.

Conversely, when the current element is greater than or equal to every element already in done, the binary search advances low until it equals high, which equals the length of done. The insertion at this index appends the element to the end of the list, and the returned position equals the size of done, indicating that all previously seen elements are smaller.

Duplicate values are handled gracefully because the binary search uses a “less than” comparison (nums[mid] < value). When a duplicate is encountered, the algorithm positions the new element at the first index where the existing value is not less than the new one, preserving the stability of the sorted list and ensuring that the count reflects only strictly smaller elements.

Performance Optimizations

The core optimization lies in the use of binary search to locate the insertion point in logarithmic time relative to the size of the auxiliary list. By avoiding a linear scan for each element, the algorithm reduces the overhead of position determination.

The choice of list.insert maintains the sorted order of done without requiring a full re-sort after each insertion. Although insertion into a Python list can involve shifting elements, the overall approach benefits from the fact that the list grows incrementally, and the binary search ensures that the number of shifts per insertion is bounded by the current list size.

Processing the input list in reverse order eliminates the need for additional data structures to track indices or to perform a second pass. The result list is built concurrently with the auxiliary list, and the final reversal is performed lazily via the built-in reversed iterator, which avoids materializing an extra copy of the result.

Collectively, these design choices produce an algorithm that scales efficiently with the length of the input while keeping the code concise and focused on the essential operations.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a line of numbered blocks that you want to put into a special box one by one. You start with the last block and work your way to the front of the line. For every block you pick up, you look inside the box to see where it should go so that everything stays in order from smallest to largest.

The getpos part of the code acts like a helper who looks at all the blocks already in the box. It quickly zooms around to find the exact spot where the new block fits. It keeps cutting the area in half to find that spot much faster than checking every single block one by one. Once it finds the right position, it tells the computer to put the block there.

The countSmaller part acts like a person keeping a tally. Every time a block is placed into the box, the position where it lands shows how many blocks currently in the box are smaller than the one just added. Because the blocks are kept in order, that position number tells you exactly how many are smaller. By doing this for every block from the back to the front, a list is built that remembers how many smaller friends each number had following it in the original line. Everything is gathered up into a final list that tells the story of how many smaller numbers were waiting after each original block.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 5.81 | σ = 1.42

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
chenyanzhe C++
everthis JS
FelixFan1122 C#
fengvyi C++
Garvit244 Python
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
linouk23 C++
lkwq007 Python
MacJim C++
ruoru Rust
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
XiaotaoGuo C++
yuanliu666 Kotlin
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
FelixFan1122 C#
fengvyi C++
Garvit244 Python
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
linouk23 C++
lkwq007 Python
MacJim C++
ruoru Rust
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
XiaotaoGuo C++
yuanliu666 Kotlin
44 links | 31 authors | 10 languages

Videos

13 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

7 similar problems

Solved On The Same Day

1 easy 13 medium 2 hard
17 solutions   August 17, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality