Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1365.html

1365. How Many Numbers Are Smaller Than the Current Number

Level

Easy

Description

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 1:

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

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

Explanation:

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 3:

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

Output: [0,0,0,0]

Constraints:

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

Solution

Create another array sorted with the same length and the same elements as nums. Then sort sorted in ascending order. For each element in sorted, all the elements smaller than the element are before the element. Therefore, there is no number smaller than sorted[0], and for i > 0 and sorted[i] != sorted[i - 1], there are i numbers smaller than sorted[i]. Use a map to store each number and how many numbers are smaller than the number.

Then create a result array. For each number in nums, obtain how many numbers are smaller than the number and put the value in the result array. Finally, return the result array.

  • class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int length = nums.length;
        int[] sorted = new int[length];
        System.arraycopy(nums, 0, sorted, 0, length);
        Arrays.sort(sorted);
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < length; i++) {
            if (i > 0 && sorted[i] == sorted[i - 1])
                continue;
            else
                map.put(sorted[i], i);
        }
        int[] smaller = new int[length];
        for (int i = 0; i < length; i++)
            smaller[i] = map.get(nums[i]);
        return smaller;
    }
}

  • class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        cnt = [0] * 101
        for num in nums:
            cnt[num] += 1
        for i in range(1, 101):
            cnt[i] += cnt[i - 1]
        res = []
        for num in nums:
            res.append(0 if num == 0 else cnt[num - 1])
        return res



  • class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int cnt[102]{};
        for (int& x : nums) {
            ++cnt[x + 1];
        }
        for (int i = 1; i < 102; ++i) {
            cnt[i] += cnt[i - 1];
        }
        vector<int> ans;
        for (int& x : nums) {
            ans.push_back(cnt[x]);
        }
        return ans;
    }
};

  • func smallerNumbersThanCurrent(nums []int) (ans []int) {
	cnt := [102]int{}
	for _, x := range nums {
		cnt[x+1]++
	}
	for i := 1; i < len(cnt); i++ {
		cnt[i] += cnt[i-1]
	}
	for _, x := range nums {
		ans = append(ans, cnt[x])
	}
	return
}

  • function smallerNumbersThanCurrent(nums: number[]): number[] {
    const cnt: number[] = new Array(102).fill(0);
    for (const x of nums) {
        ++cnt[x + 1];
    }
    for (let i = 1; i < cnt.length; ++i) {
        cnt[i] += cnt[i - 1];
    }
    const n = nums.length;
    const ans: number[] = new Array(n);
    for (let i = 0; i < n; ++i) {
        ans[i] = cnt[nums[i]];
    }
    return ans;
}

All Problems

All Solutions