MediumNo. 0912
Sort an Array — LeetCode 912 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Divide and Conquer, Bucket Sort, Counting Sort, Radix Sort, Sorting, Heap (Priority Queue), Merge Sort
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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
- 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).
Python solution
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 numsComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 912. Sort an Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2343 | Query Kth Smallest Trimmed Number | Medium |
| 0215 | Kth Largest Element in an Array | Medium |
| 0218 | The Skyline Problem | Hard |
| 0973 | K Closest Points to Origin | Medium |
| 1738 | Find Kth Largest XOR Coordinate Value | Medium |
| 1985 | Find the Kth Largest Integer in the Array | Medium |
Frequently asked questions
- How hard is LeetCode 912. Sort an Array?
LeetCode 912. Sort an Array is rated Medium on LeetCode.
- What is the time complexity of LeetCode 912. Sort an Array?
The Python solution on this page runs in O(n log n).
- What is the space complexity of LeetCode 912. Sort an Array?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 912. Sort an Array cover?
LeetCode 912. Sort an Array is tagged Array, Divide and Conquer, Bucket Sort, Counting Sort, Radix Sort, Sorting, Heap (Priority Queue) and Merge Sort on LeetCode.