1985. Find The Kth Largest Integer In The Array - Explanation

1. Sorting

class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        return sorted(nums, key=lambda x: (len(x), x), reverse=True)[k - 1]

Time & Space Complexity

Time complexity: $O(m * n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

Where $n$ is the number of strings and $m$ is the average length of a string.

2. Max-Heap

class Num:
    def __init__(self, s: str):
        self.s = s

    def __lt__(self, other: "Num") -> bool:
        if len(self.s) != len(other.s):
            return len(self.s) > len(other.s)
        return self.s > other.s

class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        maxHeap = [Num(s) for s in nums]
        heapq.heapify(maxHeap)

        for _ in range(k - 1):
            heapq.heappop(maxHeap)

        return heapq.heappop(maxHeap).s

Time & Space Complexity

Time complexity: $O(m * (n + k) * \log n)$
Space complexity: $O(n)$

Where $n$ is the number of strings and $m$ is the average length of a string.

3. Min-Heap

class Num:
    def __init__(self, s: str):
        self.s = s

    def __lt__(self, other: "Num") -> bool:
        if len(self.s) != len(other.s):
            return len(self.s) < len(other.s)
        return self.s < other.s

class Solution:
    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        minHeap = []
        for num in nums:
            heapq.heappush(minHeap, Num(num))
            if len(minHeap) > k:
                heapq.heappop(minHeap)
        return minHeap[0].s

Time & Space Complexity

Time complexity: $O(m * n * \log k)$
Space complexity: $O(k)$

Where $n$ is the number of strings and $m$ is the average length of a string.

4. Quick Select

class Solution:
    def greater(self, x: str, y: str) -> bool:
        if len(x) != len(y):
            return len(x) > len(y)
        return x > y

    def less(self, x: str, y: str) -> bool:
        if len(x) != len(y):
            return len(x) < len(y)
        return x < y

    def partition(self, nums: List[str], left: int, right: int) -> int:
        mid = (left + right) >> 1
        nums[mid], nums[left + 1] = nums[left + 1], nums[mid]

        if self.less(nums[left], nums[right]):
            nums[left], nums[right] = nums[right], nums[left]
        if self.less(nums[left + 1], nums[right]):
            nums[left + 1], nums[right] = nums[right], nums[left + 1]
        if self.less(nums[left], nums[left + 1]):
            nums[left], nums[left + 1] = nums[left + 1], nums[left]

        pivot = nums[left + 1]
        i = left + 1
        j = right

        while True:
            while True:
                i += 1
                if not self.greater(nums[i], pivot):
                    break
            while True:
                j -= 1
                if not self.less(nums[j], pivot):
                    break
            if i > j:
                break
            nums[i], nums[j] = nums[j], nums[i]

        nums[left + 1], nums[j] = nums[j], nums[left + 1]
        return j

    def quickSelect(self, nums: List[str], k: int) -> str:
        left = 0
        right = len(nums) - 1

        while True:
            if right <= left + 1:
                if right == left + 1 and self.greater(nums[right], nums[left]):
                    nums[left], nums[right] = nums[right], nums[left]
                return nums[k]

            j = self.partition(nums, left, right)
            if j >= k:
                right = j - 1
            if j <= k:
                left = j + 1

    def kthLargestNumber(self, nums: List[str], k: int) -> str:
        return self.quickSelect(nums, k - 1)

Time & Space Complexity

Time complexity: $O(m * n)$ in average case, $O(m * n ^ 2)$ in worst case.
Space complexity: $O(1)$