How to Solve How Many Numbers Are Smaller Than the Current Number

To solve this problem, you need to find the count of smaller elements for each number in the array. The optimal approach involves scanning the array while leveraging hashing to efficiently track counts of smaller numbers. Brute-force solutions work but may not be efficient for large inputs.

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

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.

How GhostInterview Helps

• GhostInterview provides detailed step-by-step problem-solving hints, guiding you to optimize brute-force solutions using sorting or hash tables.
• The platform helps you practice and refine your array scanning skills, which is crucial for problems like this that require handling and comparing array elements efficiently.
• GhostInterview emphasizes recognizing performance bottlenecks and introduces better alternatives, such as sorting or hash-based solutions, for problems that require optimization.

Topic Pages

• Array
• Hash Table
• Sorting
• Counting Sort

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.