#912

Medium

auto_awesomeArray plus Divide and Conquer

LeetCode Problem Workspace

Sort an Array

Sort an array using an optimal algorithm, focusing on time and space complexity considerations.

array divide and conquer sorting heap priority queue merge sort

Problem Statement

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 sorting functions. Additionally, the time complexity of your solution must be O(n log n) or better, and you must minimize the space complexity as much as possible.

Consider the input nums = [5,2,3,1]. After sorting, the correct output is [1,2,3,5]. You may not use any built-in sorting functions, and you must focus on implementing an optimal sorting algorithm that balances both time and space constraints.

Examples

Example 1

Input: nums = [5,2,3,1]

Output: [1,2,3,5]

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]

Note that the values of nums are not necessarily unique.

Constraints

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

Solution Approach

Merge Sort

Merge Sort is a popular divide-and-conquer approach that recursively divides the array into smaller subarrays and sorts them. It has a time complexity of O(n log n) and a space complexity of O(n). This approach is effective for this problem since it meets the time requirement and allows for an efficient sorting of the array.

Quick Sort

Quick Sort is another divide-and-conquer algorithm with an average time complexity of O(n log n). It works by selecting a pivot element, partitioning the array into smaller subarrays, and recursively sorting them. While it is faster than Merge Sort on average, it can have a worst-case time complexity of O(n^2) if not implemented carefully.

Heap Sort

Heap Sort leverages a heap data structure to sort the array. It has a time complexity of O(n log n) and a space complexity of O(1), making it an ideal solution when space efficiency is a priority. It works by repeatedly extracting the maximum (or minimum) element and reordering the heap until the array is sorted.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

For all three approaches (Merge Sort, Quick Sort, and Heap Sort), the time complexity is O(n log n), which meets the problem's requirement. However, Merge Sort has a higher space complexity of O(n), while Heap Sort provides a space-efficient O(1) solution. Quick Sort, on average, also has O(n log n) time complexity but can degrade to O(n^2) in the worst case if the pivot is poorly chosen.

What Interviewers Usually Probe

Understand how divide-and-conquer strategies, like Merge Sort, Quick Sort, and Heap Sort, apply to the sorting problem.
Test candidate's ability to balance time and space complexity considerations when choosing an algorithm.
Look for the candidate's awareness of edge cases and their understanding of sorting algorithm stability and performance.

Common Pitfalls or Variants

Common pitfalls

Not considering the time and space complexity trade-offs for large input sizes.
Choosing Quick Sort without implementing it in a way that handles the worst-case time complexity properly.
Misunderstanding the problem's constraints and opting for a non-O(n log n) algorithm such as Bubble Sort or Insertion Sort.

Follow-up variants

Sorting the array in descending order instead of ascending.
Sorting an array with a custom comparison function for non-numeric values.
Handling arrays with duplicate values and ensuring correct stability in the sorting algorithm.

FAQ

What is the optimal time complexity for sorting an array?

The optimal time complexity for sorting an array is O(n log n), which is achievable by algorithms like Merge Sort, Quick Sort, and Heap Sort.

Can I use built-in sorting functions in this problem?

No, you must implement your own sorting algorithm to meet the constraints of the problem.

What is the difference between Merge Sort and Quick Sort?

Merge Sort guarantees O(n log n) time complexity but requires O(n) space, while Quick Sort has an average O(n log n) time complexity but can degrade to O(n^2) in the worst case.

How does Heap Sort compare to Merge Sort?

Heap Sort has O(n log n) time complexity and O(1) space complexity, making it more space-efficient than Merge Sort, which has O(n) space complexity.

What should I consider when choosing a sorting algorithm?

When choosing a sorting algorithm, consider the time complexity, space complexity, and whether the algorithm handles edge cases like duplicates or large input sizes efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quick_sort(l, r):
            if l >= r:
                return
            x = nums[randint(l, r)]
            i, j, k = l - 1, r + 1, l
            while k < j:
                if nums[k] < x:
                    nums[i + 1], nums[k] = nums[k], nums[i + 1]
                    i, k = i + 1, k + 1
                elif nums[k] > x:
                    j -= 1
                    nums[j], nums[k] = nums[k], nums[j]
                else:
                    k = k + 1
            quick_sort(l, i)
            quick_sort(j, r)

        quick_sort(0, len(nums) - 1)
        return nums

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quick_sort(l, r):
            if l >= r:
                return
            x = nums[randint(l, r)]
            i, j, k = l - 1, r + 1, l
            while k < j:
                if nums[k] < x:
                    nums[i + 1], nums[k] = nums[k], nums[i + 1]
                    i, k = i + 1, k + 1
                elif nums[k] > x:
                    j -= 1
                    nums[j], nums[k] = nums[k], nums[j]
                else:
                    k = k + 1
            quick_sort(l, i)
            quick_sort(j, r)

        quick_sort(0, len(nums) - 1)
        return nums

Solution 3

#### Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def quick_sort(l, r):
            if l >= r:
                return
            x = nums[randint(l, r)]
            i, j, k = l - 1, r + 1, l
            while k < j:
                if nums[k] < x:
                    nums[i + 1], nums[k] = nums[k], nums[i + 1]
                    i, k = i + 1, k + 1
                elif nums[k] > x:
                    j -= 1
                    nums[j], nums[k] = nums[k], nums[j]
                else:
                    k = k + 1
            quick_sort(l, i)
            quick_sort(j, r)

        quick_sort(0, len(nums) - 1)
        return nums

Continue Practicing

#347 top k frequent elements #973 k closest points to origin #692 top k frequent words