Most Efficient Solution for LeetCode 912: Sort an Array

Intuition

Sorting is a critical operation in many applications, from organizing data for binary searches to ensuring the proper order of elements in databases. Different sorting algorithms have their strengths and weaknesses depending on the size of the array, its initial order, and memory constraints.

For 912. Sort an Array, the key is to select an algorithm that balances time complexity and implementation simplicity. While many built-in sorting methods exist in programming languages, implementing sorting algorithms like QuickSort, MergeSort, or Counting Sort can deepen your understanding of their workings.

Why Not Use Built-In Sort?

Most programming languages have optimized built-in sorting functions (e.g., sort() in Python or Arrays.sort() in Java). These are reliable but abstract away the implementation details. This problem encourages us to go beyond the built-in tools and implement our own sorting algorithm, offering insights into performance trade-offs and optimizations.

Approach to Solve the Problem

Here’s a step-by-step breakdown of how to solve this problem efficiently:

1. Understand the Input Constraints

• The array can have both positive and negative integers.
• The size of the array can vary significantly, so the algorithm must handle small and large inputs efficiently.
• Performance matters. A naive sorting algorithm with O(n^2) complexity (like Bubble Sort) will not perform well for large inputs.

2. Choose the Right Sorting Algorithm

There are several sorting algorithms to choose from:

• QuickSort: An efficient O(n log n) algorithm with an average-case complexity of O(nlogn) and worst-case complexity of O(n^2).
• MergeSort: A stable O(nlog⁡n) sorting algorithm with consistent performance but requires additional memory.
• Counting Sort: A non-comparison-based algorithm with linear time complexity O(n + k) (where k is the range of elements) but limited to specific use cases.
• HeapSort: Another O(nlogn) algorithm, especially useful when memory is a concern.

For this problem, Counting Sort is ideal when the range of numbers is small, while QuickSort or MergeSort is better for larger and more diverse inputs.

3. Optimizing with Problem-Specific Insights

• Use a single loop to compute the minimum and maximum values in the array. This reduces the overhead of separate passes for min and max.
• Switch to Counting Sort if the range of values (max−min) is relatively small compared to the size of the array.

4. Implementation

We implement a hybrid approach:

• Compute the range of the array using a single loop.
• For small ranges, use Counting Sort for its linear time complexity.
• For larger ranges, fall back to a more general-purpose algorithm like QuickSort.

Detailed Solution

Below is the Python implementation of the solution:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
const sortArray = function (nums) {
  const n = nums.length;
  let min = nums[0], max = nums[0];

  // Find min and max in a single loop
  for (let i = 1; i < n; ++i) {
    min = Math.min(min, nums[i]);
    max = Math.max(max, nums[i]);
  }

  // Use built-in sort for large ranges
  if (n + max - min > n * Math.log2(n)) {
    return nums.sort((a, b) => a - b); // Fallback to JavaScript's Timsort
  }

  // Counting sort for small ranges
  const counts = new Array(max - min + 1).fill(0);
  for (const num of nums) {
    counts[num - min]++;
  }

  let index = 0;
  for (let j = 0; j < counts.length; ++j) {
    while (counts[j] > 0) {
      nums[index++] = j + min;
      counts[j]--;
    }
  }

  return nums;
};

Explanation

1. Finding Min and Max in One Pass

• The loop calculates the minimum and maximum values of the array in O(n) time. This is necessary to determine the range of the numbers, which is used to decide whether to apply Counting Sort.

2. Switching Between Sorting Methods

• If the range (max−min) is too large relative to the size of the array, the algorithm uses the built-in sort() function, which employs Timsort. This approach works well for general cases and maintains O(nlogn) time complexity.
• For smaller ranges, Counting Sort is used because it provides linear time complexity O(n+k), where k=max−min.

3. Counting Sort Implementation

• An array counts is created to store the frequency of each number in the range [min,max].
• The sorted array is reconstructed by iterating through the counts array and placing the values back into nums.

Code

JavaScript

/**
 * @author @dare2solve
 * @param {number[]} nums
 * @return {number[]}
 */
const sortArray = function (nums) {
    const n = nums.length
    let min = nums[0], max = nums[0];
    for (let i = 1; i < n; ++i) min = Math.min(min, nums[i]), max = Math.max(max, nums[i]);
    if (n + max - min > n * Math.log2(n)) return nums.sort((a, b) => a - b);
    let i = 0;
    const counts = new Uint32Array(max - min + 1);
    for (let i = 0; i < n; ++i) counts[nums[i] - min]++;
    for (let j = 0; j < counts.length; ++j) while (counts[j]--) nums[i++] = j + min;
    return nums;
};

C++

class Solution {
public:
    vector sortArray(vector& nums) {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        int n = nums.size(), minVal = nums[0], maxVal = nums[0];
        for (int i = 1; i < n; ++i) {
            minVal = min(minVal, nums[i]);
            maxVal = max(maxVal, nums[i]);
        }
        if (n + maxVal - minVal > n * log2(n)) {
            sort(nums.begin(), nums.end());
            return nums;
        }
        vector counts(maxVal - minVal + 1, 0);
        for (int i = 0; i < n; ++i) ++counts[nums[i] - minVal];
        int index = 0;
        for (int j = 0; j < counts.size(); ++j) while (counts[j]--) nums[index++] = j + minVal;
        return nums;
    }
};

Java

class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length, minVal = nums[0], maxVal = nums[0];
        
        for (int i = 1; i < n; ++i) {
            minVal = Math.min(minVal, nums[i]);
            maxVal = Math.max(maxVal, nums[i]);
        }

        if (n + maxVal - minVal > n * (Math.log(n) / Math.log(2))) {
            Arrays.sort(nums);
            return nums;
        }

        int[] counts = new int[maxVal - minVal + 1];
        for (int num : nums) counts[num - minVal]++;
        int index = 0;
        for (int j = 0; j < counts.length; ++j) while (counts[j]-- > 0) nums[index++] = j + minVal;

        return nums;
    }
}

Python

class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        min_val, max_val = nums[0], nums[0]
        
        for i in range(1, n):
            min_val = min(min_val, nums[i])
            max_val = max(max_val, nums[i])

        if n + max_val - min_val > n * (len(bin(n)) - 2):
            nums.sort()
            return nums

        counts = [0] * (max_val - min_val + 1)
        for num in nums:
            counts[num - min_val] += 1
        index = 0
        for j, count in enumerate(counts):
            while count > 0:
                nums[index] = j + min_val
                index += 1
                count -= 1
        
        return nums

Conclusion

The 912. Sort an Array problem is an excellent opportunity to explore sorting algorithms and their practical applications. By combining insights into the input data and algorithmic efficiency, we can build a solution that is both scalable and optimized. Whether you implement Counting Sort for small ranges or leverage built-in sorting functions for more general cases, understanding the underlying principles will improve your problem-solving skills.

By focusing on performance and adaptability, this solution showcases the power of combining theoretical knowledge with practical implementation strategies.