algoadvance

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. This behavior needs to be applied for every element in the array. Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: 
For nums[0]=8 there are four numbers smaller than it: [1,2,2,3]. 
For nums[1]=1 there are zero numbers smaller than it.
For nums[2]=2 there is one number smaller than it: [1]. 
For nums[3]=2 there is one number smaller than it: [1].
For nums[4]=3 there are three numbers smaller than it: [1,2,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]

Clarifying Questions

  1. Are there any constraints on the length of the array or the values in the array?
    • Yes, typically the constraints are:
      • 2 <= nums.length <= 500
      • 0 <= nums[i] <= 100
  2. Do we need to handle any edge cases like empty arrays or non-integer inputs?
    • According to the constraints, we don’t need to handle empty arrays, and all inputs will be integers.
  3. What is the desired time complexity for an optimal solution?
    • A brute-force approach would be O(n^2), but we should aim for a more efficient solution, ideally O(n log n) or O(n).

Strategy

  1. Brute-force Solution:
    • For each element in the array, count how many elements are smaller than it.
    • Time Complexity: O(n^2)
  2. Optimized Approach with Sorting:
    • Sort the array and use a dictionary to keep track of the number of elements smaller than the current element as we iterate through the sorted array.
    • Time Complexity: O(n log n)

Python Code

Here’s an optimized approach using sorting and a dictionary to achieve a better time complexity.

def smallerNumbersThanCurrent(nums):
    # Step 1: Sort the array
    sorted_nums = sorted(nums)
    
    # Step 2: Create a dictionary to record the count of smaller numbers
    count_dict = {}
    
    # Step 3: Populate the count_dict
    for i, num in enumerate(sorted_nums):
        if num not in count_dict:
            count_dict[num] = i
            
    # Step 4: Build the result array using the count_dict
    result = [count_dict[num] for num in nums]
    
    return result

# Example usage:
print(smallerNumbersThanCurrent([8,1,2,2,3]))  # Output: [4, 0, 1, 1, 3]
print(smallerNumbersThanCurrent([6,5,4,8]))  # Output: [2, 1, 0, 3]
print(smallerNumbersThanCurrent([7,7,7,7]))  # Output: [0, 0, 0, 0]

Time Complexity

Overall time complexity: O(n log n)

Space Complexity

Overall space complexity: O(n)

Try our interview co-pilot at AlgoAdvance.com