python-fenwick-count-smaller-after-self
The problem is "Count of Smaller Numbers After Self" (LeetCode 315): for each index i, return how many elements at positions j > i are strictly smaller than nums[i]. An O(n²) approach times out on 100k elements (~145s extrapolated), so I use a Fenwick tree (BIT) with coordinate compression for O(n log n).
Algorithm (~/solution.py):
1. Coordinate compression — map every value to a dense 1-based rank via sorted(set(nums)). This handles negatives and collapses duplicates to the same rank.
2. Right-to-left sweep — maintain a Fenwick tree of ranks of elements already seen (i.e., everything to the right). For nums[i] with rank r, the count of strictly smaller elements to its right is the prefix sum of ranks 1..r-1. Then insert rank r.
Strictness comes from querying r - 1 (never counting equal values), and the reverse sweep guarantees only right-side elements are in the tree.
from typing import List
class FenwickTree:
__slots__ = ("n", "bit")
def __init__(self, n: int) -> None:
self.n = n
self.bit = [0] * (n + 1)
def add(self, idx: int, delta: int = 1) -> None:
while idx <= self.n:
self.bit[idx] += delta
idx += idx & -idx
def prefix_sum(self, idx: int) -> int:
s = 0
while idx > 0:
s += self.bit[idx]
idx -= idx & -idx
return s
def count_smaller(nums: List[int]) -> List[int]:
n = len(nums)
if n == 0:
return []
sorted_vals = sorted(set(nums))
rank_of = {v: i + 1 for i, v in enumerate(sorted_vals)} # 1-based ranks
ft = FenwickTree(len(sorted_vals))
result = [0] * n
for i in range(n - 1, -1, -1):
r = rank_of[nums[i]]
result[i] = ft.prefix_sum(r - 1) # strictly smaller than nums[i]
ft.add(r)
return result
I also include a merge-sort variant (count_smaller_merge) that counts cross-inversions during merge, giving the same O(n log n) bound as an alternative. Example: count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0].
Verified in `~` against a brute-force reference `[sum(1 for j in range(i+1, n) if nums[j] < nums[i]) for i in range(n)]`: - **Randomized correctness**: 300+ random arrays (n up to 60, values in [−100, 100]) plus handcrafted cases — Fenwick and merge variants both match brute force exactly. Included edge cases: `[]`, `[1]`, all-equal `[1,1,1,1]`, descending `[3,2,1]`, negatives `[-1,-2,-3]`, `[0,0,0,1,0]`, and heavy duplicates `[2,2,2,1,1,1,0]`. - **Duplicate handling**: `count_smaller([2**31-1, -2**31, 0, 2**31-1]) == [2, 0, 0, 0]` — the duplicate max is correctly *not* counted (strictly smaller only). 50k all-identical elements return all zeros; a 2k heavy-duplicate pattern (`[-3,0,42,42,1000000]`) matched brute force exactly. - **Negatives / extreme values**: negative-heavy and full int32-range values (`-2**31` … `2**31-1`) verified exactly. - **Exactness on large input**: full brute-force comparison on 5,000 elements (fenwick == merge == brute); exact spot-checks at positions 0, 1, 5, 99, 100, 999 on a 100k-element array. - **Performance**: 100k random elements (range ±10⁹) run in **0.16–0.26s** (Fenwick) and ~0.35s (merge). Sorted-ascending (all zeros) and sorted-descending (`[n-1-i]`) 100k arrays verified. - **Naive time-out confirmed**: O(n²) measured 0.36s/1.43s/5.90s at n = 5k/10k/20k, extrapolating to ~145s at n = 100k — comfortably over any reasonable limit, so the O(n log n) requirement is meaningful. - Standalone `python3 solution.py` runs its assert self-check cleanly.
{"model": "claude", "problem_class": "python-fenwick-count-smaller-after-self", "result": "passed", "tests": 300}The problem is "Count of Smaller Numbers After Self" (LeetCode 315): for each index i, return how many elements at positions j > i are strictly smaller than nums[i]. An O(n²) approach times out on 100k elements (~145s extrapolated), so I use a Fenwick tree (BIT) with coordinate compression for O(n log n).
Algorithm (~/solution.py):
1. Coordinate compression — map every value to a dense 1-based rank via sorted(set(nums)). This handles negatives and collapses duplicates to the same rank.
2. Right-to-left sweep — maintain a Fenwick tree of ranks of elements already seen (i.e., everything to the right). For nums[i] with rank r, the count of strictly smaller elements to its right is the prefix sum of ranks 1..r-1. Then insert rank r.
Strictness comes from querying r - 1 (never counting equal values), and the reverse sweep guarantees only right-side elements are in the tree.
from typing import List
class FenwickTree:
__slots__ = ("n", "bit")
def __init__(self, n: int) -> None:
self.n = n
self.bit = [0] * (n + 1)
def add(self, idx: int, delta: int = 1) -> None:
while idx <= self.n:
self.bit[idx] += delta
idx += idx & -idx
def prefix_sum(self, idx: int) -> int:
s = 0
while idx > 0:
s += self.bit[idx]
idx -= idx & -idx
return s
def count_smaller(nums: List[int]) -> List[int]:
n = len(nums)
if n == 0:
return []
sorted_vals = sorted(set(nums))
rank_of = {v: i + 1 for i, v in enumerate(sorted_vals)} # 1-based ranks
ft = FenwickTree(len(sorted_vals))
result = [0] * n
for i in range(n - 1, -1, -1):
r = rank_of[nums[i]]
result[i] = ft.prefix_sum(r - 1) # strictly smaller than nums[i]
ft.add(r)
return result
I also include a merge-sort variant (count_smaller_merge) that counts cross-inversions during merge, giving the same O(n log n) bound as an alternative. Example: count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0].
Verified in `~` against a brute-force reference `[sum(1 for j in range(i+1, n) if nums[j] < nums[i]) for i in range(n)]`: - **Randomized correctness**: 300+ random arrays (n up to 60, values in [−100, 100]) plus handcrafted cases — Fenwick and merge variants both match brute force exactly. Included edge cases: `[]`, `[1]`, all-equal `[1,1,1,1]`, descending `[3,2,1]`, negatives `[-1,-2,-3]`, `[0,0,0,1,0]`, and heavy duplicates `[2,2,2,1,1,1,0]`. - **Duplicate handling**: `count_smaller([2**31-1, -2**31, 0, 2**31-1]) == [2, 0, 0, 0]` — the duplicate max is correctly *not* counted (strictly smaller only). 50k all-identical elements return all zeros; a 2k heavy-duplicate pattern (`[-3,0,42,42,1000000]`) matched brute force exactly. - **Negatives / extreme values**: negative-heavy and full int32-range values (`-2**31` … `2**31-1`) verified exactly. - **Exactness on large input**: full brute-force comparison on 5,000 elements (fenwick == merge == brute); exact spot-checks at positions 0, 1, 5, 99, 100, 999 on a 100k-element array. - **Performance**: 100k random elements (range ±10⁹) run in **0.16–0.26s** (Fenwick) and ~0.35s (merge). Sorted-ascending (all zeros) and sorted-descending (`[n-1-i]`) 100k arrays verified. - **Naive time-out confirmed**: O(n²) measured 0.36s/1.43s/5.90s at n = 5k/10k/20k, extrapolating to ~145s at n = 100k — comfortably over any reasonable limit, so the O(n log n) requirement is meaningful. - Standalone `python3 solution.py` runs its assert self-check cleanly.
{"model": "claude", "problem_class": "python-fenwick-count-smaller-after-self", "result": "passed", "tests": 300}