Using Sorting and Two-Pointer
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal of this function is to maximize the "greatness" of a list of integers. The "gr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal of this function is to maximize the "greatness" of a list of integers. The "greatness" is defined as the number of pairs **(i,j)** such that **nums[j] > nums[i]** and **i < j**. By sorting the list first, we can efficiently count such pairs.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sorting the List: The function starts by sorting the input list nums. Sorting helps in easily finding pairs where nums[j] > nums[i] because, in a sorted list, any element at a higher index will be greater than the elements at lower indices.\n2. Two-Pointer Technique:\n- Initialize two pointers, i and j, where i starts at 0 and j starts at 1.\n- Traverse the list using the pointer j. For each element nums[j], check if it is greater than nums[i].\n- If nums[j] > nums[i], increment the count and move the pointer i to the next position.\n- Always move the pointer j to the next position.\nCounting Pairs: The count is incremented each time a valid pair (i, j) is found where nums[j] > nums[i].\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- - Sorting the list takes O(n log n), where n is the length of the list.\n- - The while loop runs in O(n) time because each pointer (i and j) traverses the list once.\n- - Therefore, the overall time complexity is O(n log n) + O(n), which simplifies to O(n log n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- - The space complexity is O(1) because the function uses a constant amount of extra space, regardless of the input size. The sorting operation may use additional space depending on the sorting algorithm used, but this is typically considered O(1) for in-place sorting algorithms.\n\n# Code\n```python3 []\nclass Solution:\n    def maximizeGreatness(self, nums: List[int]) -> int:\n        nums.sort() # sorts the array\n        \n        count = 0\n        i = 0\n        j = 1\n        # Checking if nums[j] > nums[i] exists where j > i\n        while j < len(nums):\n            if nums[j] > nums[i]:\n                count += 1\n                i += 1\n            j += 1\n        \n        return count\n\n\n```
['Two Pointers', 'Sorting', 'Python3']