How hard is LeetCode 215. Kth Largest Element in an Array?

LeetCode 215. Kth Largest Element in an Array is rated Medium on LeetCode.

What is the time complexity of LeetCode 215. Kth Largest Element in an Array?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 215. Kth Largest Element in an Array?

The Python solution on this page uses O(\log n) auxiliary space.

What topics does LeetCode 215. Kth Largest Element in an Array cover?

LeetCode 215. Kth Largest Element in an Array is tagged Array, Divide and Conquer, Quickselect, Sorting and Heap (Priority Queue) on LeetCode.

Kth Largest Element in an Array — LeetCode 215 Python Solution

MediumArrayDivide and ConquerQuickselectSortingHeap (Priority Queue)

Problem: #215
Pattern: Heap / Priority Queue
Reading time: 4 min
Source: leetcode.com

The problem

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example

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

Python solution

Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_sort(l: int, r: int) -> int:
            if l == r:
                return nums[l]
            i, j = l - 1, r + 1
            x = nums[(l + r) >> 1]
            while i < j:
                while 1:
                    i += 1
                    if nums[i] >= x:
                        break
                while 1:
                    j -= 1
                    if nums[j] <= x:
                        break
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            if j < k:
                return quick_sort(j + 1, r)
            return quick_sort(l, j)

        n = len(nums)
        k = n - k
        return quick_sort(0, n - 1)

Complexity

Measure	Complexity
Time	O(n)
Space	O(\log n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 215. Kth Largest Element in an Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

On study lists

This problem is on NeetCode 150, LeetCode 75 and Top Interview 150.

Frequently asked questions

How hard is LeetCode 215. Kth Largest Element in an Array?: LeetCode 215. Kth Largest Element in an Array is rated Medium on LeetCode.
What is the time complexity of LeetCode 215. Kth Largest Element in an Array?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 215. Kth Largest Element in an Array?: The Python solution on this page uses O(\log n) auxiliary space.
What topics does LeetCode 215. Kth Largest Element in an Array cover?: LeetCode 215. Kth Largest Element in an Array is tagged Array, Divide and Conquer, Quickselect, Sorting and Heap (Priority Queue) on LeetCode.