Employ exhaustive brute-force search to determine the number of pairs of indices (i, j) which exists such that i ≠ j and nums[j] < nums[i].
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
nums_length = len(nums)
output = [0] * nums_length
for i in range(nums_length):
for j in range(nums_length):
if j != i and nums[j] < nums[i]:
output[i] += 1
return output
Sort the input array supplied. For each i in the range 0 through |nums|, determine the number of elements contained within the input array supplied whose value is less than nums[i] - this is equal to the index of nums[i] within the sorted array.
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
if len(nums) >= 2:
sorted_nums = sorted(nums)
for i in range(len(nums)):
nums[i] = sorted_nums.index(nums[i])
return nums
Sort the input array supplied. Construct a mapping between each number contained within the input array and the index at which that number first appears within the sorted input array. For each i in the range 0 through |nums|, determine the number of elements contained within the input array supplied whose value is less than nums[i] - this is equal to the value given the the value_by_first_index mapping for the key nums[i].
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
if len(nums) >= 2:
value_by_first_index = {}
for i, v in enumerate(sorted(nums)):
if v not in value_by_first_index:
value_by_first_index[v] = i
for i, v in enumerate(nums):
nums[i] = value_by_first_index[v]
return nums
This can be further rewritten to employ Python list comprehension:
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
if len(nums) < 2:
return nums
else:
value_by_first_index = {}
for i, v in enumerate(sorted(nums)):
if v not in value_by_first_index:
value_by_first_index[v] = i
return [value_by_first_index[v] for v in nums]