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.

Clarifying Questions

  1. Can the array contain duplicate numbers?
    • Yes, the array can contain duplicate numbers.
  2. What is the range of the values in the array?
    • The values in the array are in the range 0 <= nums[i] <= 100.
  3. What is the size range of the array?
    • The size of the array is in the range 2 <= nums.length <= 500.

Code

import java.util.Arrays;

public class SmallerNumbersThanCurrent {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] count = new int[101];
        
        // Count the number of occurrences of each number
        for (int num : nums) {
            count[num]++;
        }
        
        // Modify count array to store the number of elements less than or equal to the current index
        for (int i = 1; i < 101; i++) {
            count[i] += count[i - 1];
        }
        
        // Create result array
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                result[i] = 0;
            } else {
                result[i] = count[nums[i] - 1];
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        SmallerNumbersThanCurrent solution = new SmallerNumbersThanCurrent();
        int[] nums = {8, 1, 2, 2, 3};
        System.out.println(Arrays.toString(solution.smallerNumbersThanCurrent(nums)));
    }
}

Strategy

  1. Count Frequencies:
    • Use an array count of size 101 (since nums[i] ranges from 0 to 100) to count occurrences of each number in the nums array.
  2. Prefix Sum Array:
    • Convert the count array to a prefix sum array where each element at index i contains the sum of all counts from 0 to i. This helps in easily counting how many numbers are smaller than the current number.
  3. Construct the Result:
    • For each number in nums, use the prefix sum array to find out how many numbers are smaller than the current number. If the current number is 0, then there are no numbers less than 0, otherwise, use the value from the prefix sum array.

Time Complexity

So, the overall time complexity is O(n).

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