LC-1985 Medium LeetCode

1985. Find the Kth Largest Integer in the Array

Array String Divide and Conquer Sorting Heap (Priority Queue) Quickselect

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 47% Topics: Array, String, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Strings 12 min Divide & Conquer 11 min

Reference solution (spoiler · python)

# Time:  O(n) ~ O(n^2), O(n) on average
# Space: O(1)

import random


class Solution(object):
    def kthLargestNumber(self, nums, k):
        """
        :type nums: List[str]
        :type k: int
        :rtype: str
        """
        def nth_element(nums, n, compare=lambda a, b: a < b):
            def tri_partition(nums, left, right, target, compare):
                mid = left
                while mid <= right:
                    if nums[mid] == target:
                        mid += 1
                    elif compare(nums[mid], target):
                        nums[left], nums[mid] = nums[mid], nums[left]
                        left += 1
                        mid += 1
                    else:
                        nums[mid], nums[right] = nums[right], nums[mid]
                        right -= 1
                return left, right

            left, right = 0, len(nums)-1
            while left <= right:
                pivot_idx = random.randint(left, right)
                pivot_left, pivot_right = tri_partition(nums, left, right, nums[pivot_idx], compare)
                if pivot_left <= n <= pivot_right:
                    return
                elif pivot_left > n:
                    right = pivot_left-1
                else:  # pivot_right < n.
                    left = pivot_right+1
        
        nth_element(nums, k-1, compare=lambda a, b: a > b if len(a) == len(b) else len(a) > len(b))
        return nums[k-1]

Solution from kamyu104/LeetCode-Solutions · MIT