algoadvance

Leetcode 1365. How Many Numbers Are Smaller Than the Current Number

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.

Example

Input:

nums = [8, 1, 2, 2, 3]

Output:

[4, 0, 1, 1, 3]

Explanation:

• For nums[0]=8 there are four smaller numbers: 1, 2, 2, 3.
• For nums[1]=1 there are no smaller numbers.
• For nums[2]=2 there is one smaller number: 1. Note that the number occurs twice.
• For nums[3]=2 there is also one smaller number: 1.
• For nums[4]=3 there are three smaller numbers: 1, 2, 2.

Clarifying Questions

1. Size of the input array: What can be the maximum size of the input array?
   • Answer: The size can be up to 500.
2. Range of numbers: What values can the elements in the array take?
   • Answer: The elements can take values between 0 and 100 inclusive.

Strategy

1. Brute Force Approach:
   • For each number, we count how many numbers are smaller than it by comparing it to all other numbers in the list.
   • Time Complexity: O(n^2), where n is the number of elements in the array. This is because for each element, we iterate through all other elements to get the count of smaller numbers.
2. Optimal Approach:
   • Use sorting and a hash map to store counts of elements.
   • Steps:
     1. Create a copy of the nums array and sort this copy.
     2. Create a hash map to store the smallest count for each distinct number.
     3. Iterate over the sorted array and populate the hash map.
     4. Use the hash map to fill the result array with counts of smaller numbers.
   • Time Complexity: O(n log n) due to sorting, and O(n) for creating the hash map and generating the results, yielding an overall complexity of O(n log n).

Code

Here is the implementation of the optimal approach:

#include <vector>
#include <algorithm>
#include <unordered_map>

std::vector<int> smallerNumbersThanCurrent(std::vector<int>& nums) {
    // Create a sorted copy of nums
    std::vector<int> sorted_nums(nums);
    std::sort(sorted_nums.begin(), sorted_nums.end());

    // Create a hash map to store the first occurrence index of each number
    std::unordered_map<int, int> num_to_count;
    for (int i = 0; i < sorted_nums.size(); i++) {
        if (num_to_count.find(sorted_nums[i]) == num_to_count.end()) {
            num_to_count[sorted_nums[i]] = i;
        }
    }

    // Generate the result array using the hash map
    std::vector<int> result(nums.size());
    for (int i = 0; i < nums.size(); i++) {
        result[i] = num_to_count[nums[i]];
    }

    return result;
}

Time Complexity

• Sorting: O(n log n) due to the sort function.
• Hash Map Creation: O(n) where n is the size of the array.
• Result Array Generation: O(n) to iterate and fill the result array.
• Overall Complexity: O(n log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?