#1365

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

How Many Numbers Are Smaller Than the Current Number

In this problem, you need to determine how many numbers are smaller than each element in an array, focusing on array scanning and hash lookup.

array hash table sorting counting sort

Problem Statement

Given an array nums, for each element nums[i], find how many elements in the array are smaller than it. In other words, for each index i, count the valid indices j such that j != i and nums[j] < nums[i].

Return the resulting counts in a new array. For example, given nums = [8,1,2,2,3], the output should be [4,0,1,1,3], as there are four smaller numbers than 8, none smaller than 1, one smaller than 2, and three smaller than 3.

Examples

Example 1

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

Output: [4,0,1,1,3]

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 details omitted.

Example 3

Input: nums = [7,7,7,7]

Output: [0,0,0,0]

Example details omitted.

Constraints

2 <= nums.length <= 500
0 <= nums[i] <= 100

Solution Approach

Brute Force Approach

A simple brute-force solution involves iterating over each element and comparing it with every other element in the array. This gives a time complexity of O(n^2), which may not be efficient for larger arrays.

Optimized Approach Using Sorting

First, sort the array while keeping track of original indices. Then, count the number of smaller elements by referencing the sorted indices. This approach runs in O(n log n) time, which is much more efficient for larger inputs.

Using a Hash Table

A hash table can be used to store the frequency of elements. After sorting, each number's smaller count can be calculated by summing frequencies of smaller numbers. This technique can reduce the complexity by avoiding repetitive comparisons.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force solution has a time complexity of O(n^2), while the optimized approach using sorting improves it to O(n log n). The hash table approach may offer a trade-off with additional space complexity but can optimize runtime under certain conditions.

What Interviewers Usually Probe

The problem tests the candidate's ability to optimize brute-force solutions using sorting or hashing techniques.
Watch for the candidate's approach to handling larger inputs efficiently, such as using sorting or hash tables.
The problem is an opportunity to assess familiarity with array manipulation and counting methods.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the problem by attempting to use complex algorithms when a simpler sorting approach is enough.
Failing to account for array elements with equal values, which should all have the same smaller count.
Neglecting to optimize the brute force approach, which can lead to performance issues on larger datasets.

Follow-up variants

Modifying the array by adding or removing elements and checking if the solution adapts correctly.
Handling edge cases where all elements are the same, requiring the program to output an array of zeros.
Implementing the solution without sorting, using a hash map or frequency counter to reduce the time complexity.

FAQ

How can I optimize the brute-force approach for this problem?

To optimize the brute-force approach, consider sorting the array first and using a hash table or frequency counter to keep track of smaller numbers, reducing the need for repeated comparisons.

What is the optimal time complexity for solving this problem?

The optimal time complexity for solving this problem is O(n log n), achieved by sorting the array and using efficient lookup techniques.

What should I do if all elements in the array are the same?

If all elements are the same, each element will have zero smaller elements, and the output will be an array of zeros.

How does sorting improve the solution for this problem?

Sorting allows you to determine the number of smaller elements efficiently by referencing the sorted order, reducing the time complexity to O(n log n).

Can I use a hash table to solve this problem?

Yes, using a hash table can help track the frequency of elements and allow you to calculate the count of smaller elements for each number more efficiently than brute force.

terminal

Solution

Solution 1: Sorting + Binary Search

We can make a copy of the array $nums$, denoted as $arr$, and then sort $arr$ in ascending order.

1

2

3

4

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        arr = sorted(nums)
        return [bisect_left(arr, x) for x in nums]

Solution 2: Counting Sort + Prefix Sum

We notice that the range of elements in the array $nums$ is $[0, 100]$. Therefore, we can use the counting sort method to first count the number of each element in the array $nums$. Then we calculate the prefix sum of the counting array. Finally, we traverse the array $nums$. For each element $x$, we directly add the value of the element at index $x$ in the counting array to the answer array.

1

2

3

4

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        arr = sorted(nums)
        return [bisect_left(arr, x) for x in nums]

Continue Practicing

#1122 relative sort array #1366 rank teams by votes #1346 check if n and its double exist