Problem : https://leetcode.com/problems/count-of-smaller-numbers-after-self/
The original array is unsorted. Iterate the input array from the rear and use insert sort to create a sorted sequence. The insert position indicates the number of smaller elements.
Time Complexity = O ( N * Log N + N * N ). Inserting number to array is O(N) time complexity operation.
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
def lowerBound(n, dp):
"""
the first poistion on the left where dp[i] <= n
"""
left, right = 0, len(dp)
while left < right:
mid = left + (right - left) // 2
if dp[mid] == n:
right = mid
elif dp[mid] < n:
left = mid + 1
elif dp[mid] > n:
right = mid
return right
result = [0] * len(nums)
dp = []
for i in reversed(range(len(nums))):
n = nums[i]
# insert sort
j = lowerBound(n, dp)
dp.insert(j, n)
result[i] = j
return result
Use Python build-in lib:
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
dp = []
result = [0] * len(nums)
for i in reversed(range(len(nums))):
lowerBound = bisect.bisect_left(dp, nums[i])
result[i] = lowerBound
bisect.insort_left(dp, nums[i])
return result
Use segment tree:
class SegmentTree:
def __init__(self, m):
# M = number of leafs of the segement tree
self.M = m
# Because segement tree is a completed binary tree.
# If number of leafs = M, then number of internal nodes = M - 1.
# Because tree[0] will not be used, the total number of nodes = 2 * M
self.tree = [0] * (2 * self.M)
def update(self, n, delta):
"""
update counter of number on index n
"""
# number n leaf node index = n + M
n += self.M
self.tree[n] += delta
n //= 2
while n > 0:
# left child node index = 2 * n
# right child node index = 2 * n
self.tree[n] = self.tree[2*n] + self.tree[2*n+1]
n //= 2
def query(self, left, right):
"""
query accumulative count between range [left, right).
the 'right' is excluded.
"""
result = 0
left += self.M
right += self.M
while left < right:
if left & 1 == 1:
# on left side, the left child node is not in the needed range.
result += self.tree[left]
left += 1
left //= 2
if right & 1 == 1:
# on right side, the right child node is not in the needed range
right -= 1
result += self.tree[right]
right //= 2
return result
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
if not nums: return []
mi = min(nums)
mx = max(nums) + 1
m = mx - mi + 1
segmentTree = SegmentTree(m)
# query in segement tree for number of smaller elements to the right of nums[i]
result = [0] * len(nums)
for i in reversed(range(len(nums))):
n = nums[i] - mi
result[i] = segmentTree.query(0, n)
segmentTree.update(n, 1)
return result
Use fenwick tree:
class FenwickTree:
def __init__(self, m):
self.tree = [0] * m
def update(self, n, delta):
while n < len(self.tree):
self.tree[n] += delta
n += self.lowbit(n)
def query(self, n):
result = 0
while n > 0 :
result += self.tree[n]
n -= self.lowbit(n)
return result
def lowbit(self, n):
return n & (~(n-1))
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
if not nums: return []
mi = min(nums)
mx = max(nums) + 1
m = mx - mi + 1
fenwickTree = FenwickTree(m)
result = [0] * len(nums)
for i in reversed(range(len(nums))):
# fenwick tree node index starts with 1
n = nums[i] - mi + 1
result[i] = fenwickTree.query(n-1)
fenwickTree.update(n, 1)
return result
Use merge sort approach.
Split the nums array into left and right parts.
Sort the right part first, then for each number on the left part, use binary-search to find count of number less than it. (lower-bound)
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
if not nums: return []
result = [0] * len(nums)
def mergeSort(left, right):
if left + 1 == right:
return
mid = left + (right - left) // 2
# sort right side
mergeSort(mid, right)
# for each number on left side, find
# how many number is smaller than it on right side.
for i in range(left, mid):
lowerBound = bisect.bisect_left(nums, nums[i], mid, right)
# count of smaller numbers = lowerBound - mid
result[i] += lowerBound - mid
# sort left side
mergeSort(left, mid)
# merge the sorted left and right side
tmp = []
i = left
j = mid
while i < mid and j < right:
if nums[i] < nums[j]:
tmp.append(nums[i])
i += 1
else:
tmp.append(nums[j])
j += 1
while i < mid:
tmp.append(nums[i])
i += 1
while j < right:
tmp.append(nums[j])
j += 1
for i in range(right - left):
nums[left+i] = tmp[i]
# merge sort starts
mergeSort(0, len(nums))
return result