LC-0912 Medium LeetCode

912. Sort an Array

Array Divide and Conquer Sorting Heap (Priority Queue) Merge Sort Bucket Sort Radix Sort Counting Sort

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 57% Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Merge Sort, Bucket Sort, Radix Sort, Counting Sort

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Divide & Conquer 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

# merge sort solution
class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def mergeSort(left, right, nums):
            if left == right:
                return
            mid = left + (right-left)//2
            mergeSort(left, mid, nums)
            mergeSort(mid+1, right,  nums)
            r = mid+1
            tmp = []
            for l in xrange(left, mid+1):
                while r <= right and nums[r] < nums[l]:
                    tmp.append(nums[r])
                    r += 1
                tmp.append(nums[l])
            nums[left:left+len(tmp)] = tmp

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


# Time:  O(nlogn), on average
# Space: O(logn)
import random
# quick sort solution
class Solution2(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def nth_element(nums, left, n, right, compare=lambda a, b: a < b):
            def tri_partition(nums, left, right, target):
                i = left
                while i <= right:
                    if compare(nums[i], target):
                        nums[i], nums[left] = nums[left], nums[i]
                        left += 1
                        i += 1
                    elif compare(target, nums[i]):
                        nums[i], nums[right] = nums[right], nums[i]
                        right -= 1
                    else:
                        i += 1
                return left, right

            while left <= right:
                pivot_idx = random.randint(left, right)
                pivot_left, pivot_right = tri_partition(nums, left, right, nums[pivot_idx])
                if pivot_left <= n <= pivot_right:
                    return
                elif pivot_left > n:
                    right = pivot_left-1
                else:  # pivot_right < n.
                    left = pivot_right+1

        def quickSort(left, right, nums):
            if left > right:
                return
            mid = left + (right-left)//2
            nth_element(nums, left, mid, right)
            quickSort(left, mid-1, nums)
            quickSort(mid+1, right, nums)

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

Solution from kamyu104/LeetCode-Solutions · MIT