LeetCode #215 Kth Largest Element in an Array

Posted on | Post modified | In , , , , , , , , ,

Problem

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example

1
2
Input: [3,2,1,5,6,4] and k = 2
Output: 5
1
2
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Boundary Conditions

  • What if k > array
  • What if k < 0
  • What if array is empty

Solution1

Method: Built-in

Time Complexity: O(n log n)

Space Complexity: 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums or k < 0 or k > len(nums):
            return None
        
        nums.sort(reverse=True)
        return nums[k - 1]

Solution2

Method: Divide and Conquer (recursive)

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums or k < 0 or k > len(nums):
            return None

        def merge(nums):
            if len(nums) == 1:
                return [nums[0]]
            else:
                mid = len(nums) // 2
                left = merge(nums[:mid])
                right = merge(nums[mid:])
                return merge_helper(left, right)

        def merge_helper(left, right):
            ret = []
            len_l = len(left)
            len_r = len(right)
            idx_l = 0
            idx_r = 0
            while idx_l < len_l and idx_r < len_r:
                if left[idx_l] >= right[idx_r]:
                    ret.append(left[idx_l])
                    idx_l += 1
                else:
                    ret.append(right[idx_r])
                    idx_r += 1
            while idx_l < len_l:
                ret.append(left[idx_l])
                idx_l += 1
            while idx_r < len_r:
                ret.append(right[idx_r])
                idx_r += 1

            return ret
            
        sorted_num = merge(nums)
        
        return sorted_num[k - 1]