Optimized Counting Sort | 3-ms Beats 100 % | Java | Python | C++ | JavaScript | Go
\n# Problem Explanation:\n\nThis problem is asking us to create a function that sorts an array of numbers from smallest to largest (ascending order). However, t
\n# Problem Explanation:\n\n***This problem is asking us to create a function that sorts an array of numbers from smallest to largest (ascending order). However, there are some specific requirements we need to follow:***\n\n    \n    We can\'t use any built-in sorting functions.\n    Our solution needs to be efficient, with a time complexity of O(nlog(n)).\n    We should use as little extra space as possible.\n\n---\n\n\n\n\n\n\n# Intuition\n\nWhen we have a limited range of integers to sort, we can use their values directly to determine their position in the sorted array. This is the core idea behind Counting Sort. Instead of comparing elements, we count how many times each number appears and use this information to place the numbers in the correct order.\n\n\n# Approach\n\nThe Counting Sort algorithm we\'ve implemented follows a straightforward yet efficient method to sort an array of integers within a specific range. We begin by scanning through the entire input array to identify the minimum and maximum values. This step is crucial as it allows us to determine the range of numbers we\'re dealing with, which in turn helps us optimize our space usage.\n\nOnce we have this range, we create a counting array. The size of this array is equal to the difference between the maximum and minimum values, plus one. Each index in this counting array corresponds to a number in our input range, offset by the minimum value. We then proceed to count the occurrences of each number in the original array. This is done by iterating through the input array once more, and for each number, we increment the count at the corresponding index in our counting array.\n\nAfter the counting phase, we have a complete tally of how many times each number appears in our input. The final step is to reconstruct the sorted array. We do this by iterating through our counting array. For each index, we know that the number it represents (index plus minimum value) should appear in our sorted array as many times as the count stored at that index. We use this information to place each number in its correct position in the original array, effectively sorting it in-place.\n\nThis approach is particularly efficient for arrays with a limited range of integers, as it avoids comparisons between elements and instead uses the integer values directly to determine their positions. The algorithm\'s efficiency comes from the fact that it makes only a few passes through the data, regardless of how unsorted it initially was.\n\n# Complexity\n- **Time complexity: O(n + k)**\n  Where n is the number of elements in the input array, and k is the range of input (max - min + 1).\n  We go through the array twice (once to count, once to place elements) and once through the counting array.\n\n- **Space complexity: O(k)**\n  We use extra space for the counting array, which has a size equal to the range of input values.\n\n### Code\n\n\n```java []\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        if (nums == null || nums.length <= 1) return nums;\n        \n        int max = nums[0], min = nums[0];\n        for (int num : nums) {\n            if (num > max) max = num;\n            if (num < min) min = num;\n        }\n        \n        int range = max - min + 1;\n        int[] count = new int[range];\n        \n        for (int num : nums) {\n            count[num - min]++;\n        }\n        \n        int index = 0;\n        for (int i = 0; i < range; i++) {\n            int freq = count[i];\n            if (freq > 0) {\n                int value = i + min;\n                while (freq-- > 0) {\n                    nums[index++] = value;\n                }\n            }\n        }\n        \n        return nums;\n    }\n}\n```\n\n```cpp []\nclass Solution {\npublic:\n    vector<int> sortArray(vector<int>& nums) {\n        if (nums.empty()) return nums;\n        \n        int min = *min_element(nums.begin(), nums.end());\n        int max = *max_element(nums.begin(), nums.end());\n        \n        vector<int> count(max - min + 1, 0);\n        for (int num : nums) {\n            count[num - min]++;\n        }\n        \n        int index = 0;\n        for (int i = 0; i < count.size(); i++) {\n            while (count[i]-- > 0) {\n                nums[index++] = i + min;\n            }\n        }\n        \n        return nums;\n    }\n};\n\n```\n\n```python []\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        if not nums:\n            return nums\n        \n        min_val, max_val = min(nums), max(nums)\n        count = [0] * (max_val - min_val + 1)\n        \n        for num in nums:\n            count[num - min_val] += 1\n        \n        index = 0\n        for i in range(len(count)):\n            while count[i] > 0:\n                nums[index] = i + min_val\n                index += 1\n                count[i] -= 1\n        \n        return nums\n\n```\n```python []\nf = open(\'user.out\', \'w\')\nfor nums in map(loads, stdin):\n    print(str(sorted(nums)).replace(\' \',\'\'), file=f)\nexit(0)\n```\n\n```javascript []\n/**\n * @param {number[]} nums\n * @return {number[]}\n */\nvar sortArray = function(nums) {\n    if (nums.length <= 1) return nums;\n    \n    let min = Math.min(...nums);\n    let max = Math.max(...nums);\n    \n    let count = new Array(max - min + 1).fill(0);\n    for (let num of nums) {\n        count[num - min]++;\n    }\n    \n    let index = 0;\n    for (let i = 0; i < count.length; i++) {\n        while (count[i]-- > 0) {\n            nums[index++] = i + min;\n        }\n    }\n    \n    return nums;\n};\n\n```\n\n```go []\nfunc sortArray(nums []int) []int {\n    if len(nums) <= 1 {\n        return nums\n    }\n    \n    min, max := nums[0], nums[0]\n    for _, num := range nums {\n        if num < min {\n            min = num\n        }\n        if num > max {\n            max = num\n        }\n    }\n    \n    count := make([]int, max - min + 1)\n    for _, num := range nums {\n        count[num - min]++\n    }\n    \n    index := 0\n    for i := 0; i < len(count); i++ {\n        for count[i] > 0 {\n            nums[index] = i + min\n            index++\n            count[i]--\n        }\n    }\n    \n    return nums\n}\n\n```\n\n
['Array', 'Divide and Conquer', 'Sorting', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']