912. Sort an Array

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

Constraints:

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

Approach 01

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        unordered_map<int, int> countMap;  // Map to store the count of each number
        int minValue = *min_element(nums.begin(), nums.end());
        int maxValue = *max_element(nums.begin(), nums.end());

        // Count the occurrences of each number in the list
        for (const int num : nums) {
            countMap[num]++;
        }

        nums.clear();

        // Reconstruct the sorted list based on the countMap
        for (int value = minValue; value <= maxValue; ++value) {
            if (countMap.find(value) != countMap.end()) {
                nums.insert(nums.end(), countMap[value], value);
            }
        }

        return nums;
    }
};

from typing import List

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        countMap = {}  # Dictionary to store the count of each number
        minValue = min(nums)
        maxValue = max(nums)

        # Count the occurrences of each number in the list
        for num in nums:
            if num in countMap:
                countMap[num] += 1
            else:
                countMap[num] = 1

        nums.clear()

        # Reconstruct the sorted list based on the countMap
        for value in range(minValue, maxValue + 1):
            if value in countMap:
                nums.extend([value] * countMap[value])

        return nums

Time Complexity

• Counting Occurrences:

  Iterating through the input array nums to count the occurrences of each number takes \( O(n) \) time, where \( n \) is the number of elements in the input array.

• Finding Min and Max Values:

  Finding the minimum and maximum values in the array requires \( O(n) \) time each.

• Reconstructing the Sorted List:

  Reconstructing the sorted list involves iterating over the range from minValue to maxValue, which takes \( O(m) \) time, where \( m = \max(\text{nums}) – \min(\text{nums}) + 1 \). For each value, the elements are inserted into nums based on their counts.

• Overall Time Complexity:

  The overall time complexity is \( O(n + m) \), where \( n \) is the number of elements in the input array and \( m \) is the range of the values in the input array.

Space Complexity

• Count Map:

  The unordered map countMap stores the count of each unique number in the input array. In the worst case, the space required is \( O(n) \) if all elements are unique.

• Input Array:

  The input array nums is cleared and then rebuilt. The space used by nums remains \( O(n) \).

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), where \( n \) is the number of elements in the input array.