Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 912 with 18 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 912 # by problem number
lcpy gen -s sort_an_array # by problem name
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.
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).
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessarily unique.
class Solution:
# Time: O(n log n)
# Space: O(n)
def sort_array(self, nums: list[int]) -> list[int]:
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = self.sort_array(nums[:mid])
right = self.sort_array(nums[mid:])
merged: list[int] = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
| Time | Space |
|---|---|
| O(n log n) | O(n) |