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)
Difficulty
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
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 327: Count of Range Sum
- problem 406: Queue Reconstruction by Height
- problem 493: Reverse Pairs
- problem 1215: Stepping Numbers
- problem 1365: How Many Numbers Are Smaller Than the Current Number
- problem 2179: Count Good Triplets in an Array
- problem 2659: Make Array Empty
Solved On The Same Day
- problem 195: Tenth Line
- problem 53: Maximum Subarray
- problem 56: Merge Intervals
- problem 78: Subsets
- problem 86: Partition List
- problem 89: Gray Code
- problem 90: Subsets II
- problem 98: Validate Binary Search Tree
- problem 179: Largest Number
- problem 456: 132 Pattern
- problem 473: Matchsticks to Square
- problem 542: 01 Matrix
- problem 916: Word Subsets
- problem 1930: Unique Length-3 Palindromic Subsequences
- problem 233: Number of Digit One
- problem 295: Find Median from Data Stream
Extra
- 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