class Solution {
    // time O(n)
    // space O(1)
    public int[] smallerNumbersThanCurrent(int[] nums) {
        // Due to the constraint 0 <= nums[i] <= 100, we can use an array
        // to keep track of the number of smaller numbers for counts[nums[i]].
        int[] counts = new int[102];

        for (int i = 0; i < nums.length; i++) {
            // store count one number to the right to simplify code later on.
            // because we allocate room for index 101, it won't go out of bounds.
            counts[nums[i] + 1]++;
        }

        for (int i = 1; i < counts.length; i++) {
                counts[i] += counts[i - 1];
        }
        // afterward: counts[i] gives count of numbers < i

        // note: if you don't want to mutate nums,
        // create an ans array and set & return that instead
        for (int i = 0; i < nums.length; i++) {
            nums[i] = counts[nums[i]];
        }

        return nums;
    }

    // time O(n^2)
    // space O(n)
    // public int[] smallerNumbersThanCurrent(int[] nums) {
    //     int[] counts = new int[nums.length];

    //     for (int i = 0; i < nums.length; i++) {
    //         int n = nums[i];
    //         for (int j = 0; j < nums.length; j++) {
    //             if (i != j && nums[j] < n) {
    //                 counts[i]++;
    //             }
    //         }
    //     }

    //     return counts;
    // }
}