Count Elements With Strictly Smaller And Greater Elements - Leetcode Solution

Problem Statement Given an integer array nums, return the number of elements in the array that are strictly smaller than nums[i]. Also, you need to count the number of elements that are strictly larger than nums[i].

Detailed Solution We can solve the problem by iterating over the array nums and for each element nums[i], we can count the number of elements that are strictly smaller than nums[i] and the number of elements that are strictly larger than nums[i].

To count the number of elements that are strictly smaller than nums[i], we can simply iterate over the array and compare the current element with nums[i]. If the current element is smaller than nums[i], we increment a counter. Similarly, to count the number of elements that are strictly larger than nums[i], we can iterate over the array and compare the current element with nums[i]. If the current element is larger than nums[i], we increment a counter.

We can store these counts in two separate arrays, one for the number of elements that are strictly smaller than nums[i] and the other for the number of elements that are strictly larger than nums[i]. Finally, we can return the sum of these two arrays for each index.

Here is the Python code implementation of the above approach:

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        smaller = [0] * n
        greater = [0] * n

        # count number of elements strictly smaller than nums[i]
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if nums[j] < nums[i]:
                    smaller[i] += 1

        # count number of elements strictly greater than nums[i]
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if nums[j] > nums[i]:
                    greater[i] += 1

        # return the sum of smaller[i] and greater[i] for each index
        return [smaller[i] + greater[i] for i in range(n)]

Time Complexity Analysis The time complexity of the above solution is O(n^2) since we are using two nested loops to iterate over the array nums. This solution will give a Time Limit Exceeded error for large input sizes.

Optimized Solution We can optimize the above solution by using a sorting and searching algorithm. We can sort the array nums and then use binary search to find the index of each element in the sorted array. The index gives us the number of elements that are strictly smaller than nums[i]. Similarly, we can subtract the index from n-1 to obtain the number of elements that are strictly larger than nums[i].

Here is the Python code implementation of the optimized approach:

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        sorted_nums = sorted(nums)
        res = []

        for i in range(n):
            index = bisect_left(sorted_nums, nums[i])
            res.append(index)

        # subtract index from n-1 to get the number of elements greater than nums[i]
        for i in range(n):
            res[i] = n - 1 - res[i]

        return res

Time Complexity Analysis The time complexity of the optimized solution is O(n log n) since we are using sorting and binary search algorithms which have a time complexity of O(n log n) and O(log n) respectively.

1