How Many Numbers Are Smaller Than the Current Number
[Leetcode][Arrays][HashTable]
Problem Statement
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i]. Return the answer in an array.URL
Example 1:
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).Example 2:
Input: nums = [6,5,4,8]
Output: [2,1,0,3]Example 3:
Input: nums = [7,7,7,7]
Output: [0,0,0,0]Constraints:
2 <= nums.length <= 5000 <= nums[i] <= 100
#collapse-hide
from typing import List
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
input_list = nums.copy()
if len(nums) == 0:
return []
if len(nums) == 1:
return [0]
sorted_arr = self.merge_sort(nums)
result = []
for i in range(len(input_list)):
count = 0
for j in range(len(sorted_arr)):
if input_list[i] == sorted_arr[j]:
break
else:
count += 1
result.append(count)
return result
def merge_sort(self, arr):
if(len(arr) > 1):
mid_val = len(arr)//2
left_list = arr[:mid_val]
right_list = arr[mid_val:]
self.merge_sort(left_list)
self.merge_sort(right_list)
i, j, k = 0, 0, 0
while(i < len(left_list) and j < len(right_list)):
if left_list[i] < right_list[j]:
arr[k] = left_list[i]
i += 1
else:
arr[k] = right_list[j]
j += 1
k += 1
while(i < len(left_list)):
arr[k] = left_list[i]
i += 1
k += 1
while(j < len(right_list)):
arr[k] = right_list[j]
j += 1
k += 1
return arr
sol = Solution()
sol.smallerNumbersThanCurrent([8,1,2,2,3])
#collapse-hide
class Solution:
def smallerNumbersThanCurrent(self, nums):
count = {}
for i, v in enumerate(sorted(nums)):
if v not in count:
count[v] = i
return [count[v] for v in nums]
sol = Solution()
sol.smallerNumbersThanCurrent([8,1,2,2,3])
Worst case performance in Time: $O(nlogn)$
#collapse-hide
class Solution:
def smallerNumbersThanCurrent(self, nums):
count = [0]*101
result = [0]*len(nums)
for num in nums:
count[num] += 1
for i in range(1, 100):
count[i] += count[i-1]
for ind, val in enumerate(nums):
if val > 0:
result[ind] = count[val-1]
return result
sol = Solution()
sol.smallerNumbersThanCurrent([5,0,10,0,10,6])
Worst case performance in Time: $O(n)$