LeetCode 215 - Kth Largest Element in an Array

LeetCode Problem 215

Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect

Solution

Problem Understanding

The problem asks us to find the kth largest element in an unsorted integer array. The important detail is that we are looking for the element that would appear in the kth position if the array were sorted in descending order. We are not looking for the kth distinct value.

For example, consider the array [3,2,3,1,2,4,5,5,6] with k = 4. If we sort the array in descending order, we get:

[6,5,5,4,3,3,2,2,1]

The 4th largest element is 4.

The input consists of:

• nums, an integer array that may contain duplicate values
• k, an integer representing which largest element we want

The output is a single integer representing the kth largest element.

The constraints are important:

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

An array size of 10^5 means that inefficient algorithms can become too slow. A quadratic solution such as repeatedly scanning the array would not scale well. The problem also explicitly asks whether we can solve it without fully sorting the array, which strongly suggests that a more efficient selection algorithm is expected.

Several edge cases are important:

• Arrays with duplicate values, because the kth largest is based on sorted position, not distinctness
• Arrays with only one element
• Cases where k = 1, meaning we need the maximum element
• Cases where k = len(nums), meaning we need the minimum element
• Negative numbers
• Already sorted or reverse sorted arrays, which can expose weaknesses in poor pivot selection strategies

Approaches

Brute Force Approach

The most direct solution is to sort the array in descending order and return the element at index k - 1.

This works because sorting places every element into its exact ranked position. Once sorted, the kth largest element is immediately accessible.

For example:

nums = [3,2,1,5,6,4]
sorted descending = [6,5,4,3,2,1]
k = 2
answer = 5

This approach is simple and correct, but sorting the entire array costs O(n log n) time. Since the problem only asks for one ranked element, fully sorting all elements does more work than necessary.

Optimal Approach, Quickselect

The key insight is that we do not need the entire array sorted. We only need one element positioned correctly.

Quickselect is based on the same partitioning idea as Quicksort. Instead of recursively sorting both halves, Quickselect only explores the side that contains the target index.

The algorithm works like this:

• Choose a pivot

• Partition the array so:

• larger elements are on one side

• smaller elements are on the other side

• Determine where the pivot ended up

• If the pivot is exactly at the target position, return it

• Otherwise recurse into only one side

This reduces the average time complexity to O(n) because each partition operation eliminates roughly half of the remaining search space.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(1) or O(n) depending on sort	Fully sorts the array even though only one element is needed
Optimal, Quickselect	Average O(n), worst O(n²)	O(1) iterative or O(log n) recursive	Partitions only the necessary side of the array

Algorithm Walkthrough

We will use Quickselect to find the kth largest element.

Instead of thinking in descending order directly, it is often easier to convert the problem into finding an index in sorted ascending order.

If the array length is n, then:

target index = n - k

This corresponds to the position the element would occupy in ascending order.

Step-by-step Algorithm

1. Convert k into a target index.

If the array length is n, then the kth largest element corresponds to index n - k in ascending order.

Example:

nums = [3,2,1,5,6,4]
n = 6
k = 2
target = 6 - 2 = 4

2. Choose a pivot element.

A pivot is selected from the current subarray. Many implementations use the rightmost element because it simplifies partitioning. 3. Partition the array around the pivot.

Rearrange elements so that:

• elements smaller than the pivot are on the left
• elements larger than or equal to the pivot are on the right

After partitioning, the pivot is placed into its final sorted position. 4. Compare the pivot index with the target index.

• If they are equal, we found the answer
• If the pivot index is smaller than the target, search the right side
• If the pivot index is larger than the target, search the left side

5. Repeat until the pivot lands on the target index.

Since each partition narrows the search space, the algorithm converges quickly.

Why it works

Partitioning guarantees that every element on the left side is smaller than the pivot and every element on the right side is larger or equal. Therefore, once the pivot lands at index p, it is exactly the element that would appear at position p in a fully sorted array.

Because the algorithm repeatedly narrows the search space toward the target index, it eventually places the correct element into its final sorted position and returns it.

Python Solution

from typing import List
import random

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        target = len(nums) - k

        def partition(left: int, right: int) -> int:
            pivot_index = random.randint(left, right)
            pivot_value = nums[pivot_index]

            nums[pivot_index], nums[right] = nums[right], nums[pivot_index]

            store_index = left

            for i in range(left, right):
                if nums[i] < pivot_value:
                    nums[i], nums[store_index] = nums[store_index], nums[i]
                    store_index += 1

            nums[store_index], nums[right] = nums[right], nums[store_index]

            return store_index

        left = 0
        right = len(nums) - 1

        while left <= right:
            pivot_index = partition(left, right)

            if pivot_index == target:
                return nums[pivot_index]
            elif pivot_index < target:
                left = pivot_index + 1
            else:
                right = pivot_index - 1

        return -1

The implementation begins by converting the problem from finding the kth largest element into finding the element at index len(nums) - k in sorted ascending order.

The partition helper function performs the core Quickselect operation. A random pivot is chosen to reduce the likelihood of worst-case performance. The pivot is temporarily moved to the end of the subarray so partitioning becomes easier.

The loop scans through the subarray and moves all elements smaller than the pivot to the front. The variable store_index tracks where the next smaller element should be placed.

After partitioning finishes, the pivot is swapped into its correct sorted position. The function then returns the pivot's final index.

The main loop repeatedly partitions the array and checks whether the pivot landed at the target index. Depending on the result, the search space is narrowed to either the left or right portion of the array.

The algorithm stops as soon as the pivot reaches the target index, at which point the correct answer has been found.

Go Solution

package main

import (
	"math/rand"
)

func findKthLargest(nums []int, k int) int {
	target := len(nums) - k

	var partition func(int, int) int

	partition = func(left int, right int) int {
		pivotIndex := rand.Intn(right-left+1) + left
		pivotValue := nums[pivotIndex]

		nums[pivotIndex], nums[right] = nums[right], nums[pivotIndex]

		storeIndex := left

		for i := left; i < right; i++ {
			if nums[i] < pivotValue {
				nums[i], nums[storeIndex] = nums[storeIndex], nums[i]
				storeIndex++
			}
		}

		nums[storeIndex], nums[right] = nums[right], nums[storeIndex]

		return storeIndex
	}

	left := 0
	right := len(nums) - 1

	for left <= right {
		pivotIndex := partition(left, right)

		if pivotIndex == target {
			return nums[pivotIndex]
		} else if pivotIndex < target {
			left = pivotIndex + 1
		} else {
			right = pivotIndex - 1
		}
	}

	return -1
}

The Go implementation closely mirrors the Python version. Slices in Go behave similarly to arrays with dynamic sizing, so in-place partitioning works naturally.

One notable difference is random number generation. Go uses rand.Intn() to select the pivot index. Integer overflow is not a concern here because the constraints are small enough to fit comfortably within Go's standard integer type.

The algorithm mutates the input slice directly, just like the Python implementation mutates the input list.

Worked Examples

Example 1

Input:

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

Target index:

len(nums) - k = 6 - 2 = 4

Suppose the pivot chosen is 4.

Step	Array State	Pivot Index
Initial	[3,2,1,5,6,4]	-
Partition around 4	[3,2,1,4,6,5]	3

The pivot index 3 is smaller than the target 4, so search the right side.

Subarray:

[6,5]

Choose pivot 5.

Step	Array State	Pivot Index
Partition around 5	[3,2,1,4,5,6]	4

Now the pivot index equals the target index.

Answer:

5

Example 2

Input:

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

Target index:

9 - 4 = 5

One possible partition sequence:

Step	Array State	Pivot Index
Initial	[3,2,3,1,2,4,5,5,6]	-
Partition around 4	[3,2,3,1,2,4,5,5,6]	5

The pivot immediately lands at the target index.

Answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	Average O(n), worst O(n²)	Each partition reduces the search space, but poor pivot choices can degrade performance
Space	O(1) iterative	The algorithm rearranges elements in place

The average-case time complexity is O(n) because each partition operation discards roughly half of the remaining elements. This creates a recurrence similar to:

T(n) = T(n/2) + O(n)

which resolves to linear time.

The worst case occurs when the pivot repeatedly ends up at one extreme, producing highly unbalanced partitions. Random pivot selection significantly reduces the likelihood of this scenario in practice.

The algorithm uses constant extra space because all partitioning happens directly inside the input array.

Test Cases

from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        import random

        target = len(nums) - k

        def partition(left: int, right: int) -> int:
            pivot_index = random.randint(left, right)
            pivot_value = nums[pivot_index]

            nums[pivot_index], nums[right] = nums[right], nums[pivot_index]

            store_index = left

            for i in range(left, right):
                if nums[i] < pivot_value:
                    nums[i], nums[store_index] = nums[store_index], nums[i]
                    store_index += 1

            nums[store_index], nums[right] = nums[right], nums[store_index]

            return store_index

        left = 0
        right = len(nums) - 1

        while left <= right:
            pivot_index = partition(left, right)

            if pivot_index == target:
                return nums[pivot_index]
            elif pivot_index < target:
                left = pivot_index + 1
            else:
                right = pivot_index - 1

        return -1

solution = Solution()

assert solution.findKthLargest([3,2,1,5,6,4], 2) == 5  # basic example
assert solution.findKthLargest([3,2,3,1,2,4,5,5,6], 4) == 4  # duplicates
assert solution.findKthLargest([1], 1) == 1  # single element
assert solution.findKthLargest([2,1], 1) == 2  # largest element
assert solution.findKthLargest([2,1], 2) == 1  # smallest element
assert solution.findKthLargest([5,5,5,5], 2) == 5  # all duplicates
assert solution.findKthLargest([-1,-2,-3,-4], 2) == -2  # negative numbers
assert solution.findKthLargest([7,6,5,4,3,2,1], 3) == 5  # descending input
assert solution.findKthLargest([1,2,3,4,5,6,7], 5) == 3  # ascending input
assert solution.findKthLargest([10000,-10000,0], 2) == 0  # boundary values

Test	Why
[3,2,1,5,6,4], k=2	Verifies standard functionality
[3,2,3,1,2,4,5,5,6], k=4	Ensures duplicates are handled correctly
[1], k=1	Tests smallest possible input
[2,1], k=1	Verifies maximum element retrieval
[2,1], k=2	Verifies minimum element retrieval
[5,5,5,5], k=2	Confirms duplicate-heavy arrays work properly
[-1,-2,-3,-4], k=2	Tests negative numbers
Descending sorted array	Checks behavior on already sorted input
Ascending sorted array	Checks opposite ordering
Boundary value array	Verifies handling of extreme constraint values

Edge Cases

One important edge case is arrays containing many duplicate values. Since the problem asks for the kth largest element by sorted position rather than distinct value, duplicates must remain part of the ranking. A faulty implementation might accidentally remove duplicates or treat equal values incorrectly during partitioning. The current implementation preserves duplicates naturally because partitioning compares values directly without deduplication.

Another important case is when k = 1 or k = len(nums). These correspond to finding the maximum and minimum elements respectively. Off-by-one errors are very common here because the target index conversion uses len(nums) - k. The implementation handles this correctly by mapping the rank directly into ascending-order index space.

Arrays that are already sorted or reverse sorted can also be problematic. Deterministic pivot strategies such as always choosing the first element can degrade Quickselect into worst-case O(n²) behavior on these inputs. The implementation reduces this risk by selecting a random pivot, which probabilistically keeps partitions balanced.

A final edge case involves very small arrays, especially arrays of length one. Recursive or iterative partition logic can easily fail if boundary conditions are incorrect. The implementation safely handles these cases because the search loop terminates immediately once the pivot lands on the only valid index.