LeetCode 215: Kth Largest Element in an Array Solution in Python Explained

Problem Statement

In LeetCode 215: Kth Largest Element in an Array, you’re given:

• nums: An array of integers.
• k: An integer (1 ≤ k ≤ nums.length).
• Your task is to return the kth largest element in the array (1-indexed, so k=1 is the largest).

The array isn’t sorted, and you’re encouraged to minimize time complexity beyond O(n log n). This differs from palindrome construction in LeetCode 214: Shortest Palindrome, focusing instead on order statistics in an array.

Constraints

• 1 ≤ k ≤ nums.length ≤ 10⁵.
• -10⁴ ≤ nums[i] ≤ 10⁴.

Examples

Let’s see some cases:

Copy codeInput: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: Sorted = [6,5,4,3,2,1], 2nd largest = 5.

Copy codeInput: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Explanation: Sorted = [6,5,5,4,3,3,2,2,1], 4th largest = 4.

Copy codeInput: nums = [1], k = 1
Output: 1
Explanation: Single element is the 1st largest.

These examples show we’re targeting the kth largest value.

Understanding the Problem

How do we solve LeetCode 215: Kth Largest Element in an Array in Python? For nums = [3,2,1,5,6,4], k = 2, sorting gives [6,5,4,3,2,1], so the 2nd largest is 5. Sorting takes O(n log n), but we can do better. This isn’t a circular DP problem like LeetCode 213: House Robber II; it’s about efficiently finding a specific order statistic. We’ll use: 1. QuickSelect: O(n) average time, O(1) space—our best solution. 2. Min-Heap: O(n + k log n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: QuickSelect Approach

Explanation

The QuickSelect approach adapts QuickSort’s partitioning:

• Pick a pivot and partition the array so elements less than the pivot are on the left, and greater on the right.
• If the pivot lands at index n-k (where kth largest is), it’s our answer.
• If pivot index > n-k, recurse on the left; if < n-k, recurse on the right.
• Average case is O(n) due to random pivot selection reducing recursion depth.

This runs in O(n) average time (O(n²) worst case) and O(1) space (in-place), making it optimal—our best solution.

For [3,2,1,5,6,4], k=2, it finds 5 efficiently.

Step-by-Step Example

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

Goal: Return 5.

• Step 1: Initialize.
• n = 6, target index = n - k = 6 - 2 = 4 (0-indexed, 5th element in sorted order).
• left = 0, right = 5.
• Step 2: Partition (pivot = 4, random choice).
• [3,2,1,5,6,4] → [3,2,1,4,6,5], pivot at 3.
• Pivot < 4, recurse on [6,5] (left=4, right=5).
• Step 3: Partition [6,5] (pivot = 5).
• [6,5] → [5,6], pivot at 4.
• Pivot = 4, return nums[4] = 5.
• Output: 5.

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

Goal: Return 4.

• Step 1: n = 9, target = 9 - 4 = 5.
• Step 2: Partition (pivot = 6).
• [3,2,3,1,2,4,5,5,6] → [3,2,3,1,2,4,5,5,6], pivot at 8.
• Pivot > 5, recurse on [3,2,3,1,2,4,5,5] (right=7).
• Step 3: Partition (pivot = 4).
• [3,2,3,1,2,4,5,5] → [3,2,3,1,2,4,5,5], pivot at 5.
• Pivot = 5, return nums[5] = 4.
• Output: 4.

How the Code Works (QuickSelect) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codeimport random

def findKthLargest(nums: list[int], k: int) -> int:
    # Line 1: QuickSelect main function
    def quickselect(left: int, right: int, k_smallest: int) -> int:
        # Find k_smallest index (adjusted for largest)
        if left == right:
            # Single element (e.g., left=4, right=4)
            return nums[left]
            # Return it (e.g., 5)

        # Line 2: Partition around random pivot
        pivot_idx = partition(left, right)
        # Get pivot position (e.g., 3)

        # Line 3: Recurse based on pivot position
        if k_smallest == pivot_idx:
            # Pivot is target (e.g., 4 == 4)
            return nums[pivot_idx]
            # Return value (e.g., 5)
        elif k_smallest < pivot_idx:
            # Target in left (e.g., 4 < 5)
            return quickselect(left, pivot_idx - 1, k_smallest)
            # Recurse left (e.g., 0, 4)
        else:
            # Target in right (e.g., 5 > 3)
            return quickselect(pivot_idx + 1, right, k_smallest)
            # Recurse right (e.g., 4, 5)

    # Line 4: Partition helper function
    def partition(left: int, right: int) -> int:
        # Choose random pivot (e.g., 4)
        pivot_idx = random.randint(left, right)
        # Random index (e.g., 3)
        pivot = nums[pivot_idx]
        # Pivot value (e.g., 4)
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        # Move pivot to end (e.g., [...,4] → [...,6])

        store_idx = left
        # Where smaller elements go (e.g., 0)
        for i in range(left, right):
            # Iterate range (e.g., 0 to 4)
            if nums[i] < pivot:
                # Smaller than pivot (e.g., 3 < 4)
                nums[store_idx], nums[i] = nums[i], nums[store_idx]
                # Swap (e.g., [3,2,...] → [3,2,...])
                store_idx += 1
                # Move store (e.g., 1)

        nums[store_idx], nums[right] = nums[right], nums[store_idx]
        # Place pivot (e.g., [3,2,1,4,6,5])
        return store_idx
        # Return pivot index (e.g., 3)

    # Line 5: Convert kth largest to k_smallest
    n = len(nums)
    # Array length (e.g., 6)
    k_smallest = n - k
    # Index of kth largest (e.g., 6-2=4)
    return quickselect(0, n - 1, k_smallest)
    # Find it (e.g., quickselect(0, 5, 4))

This solution optimizes by avoiding full sorting.

Alternative: Min-Heap Approach

Explanation

The Min-Heap approach uses a heap to track the k largest:

• Build a min-heap of size k.
• For each element, if larger than the heap’s minimum, replace and re-heapify.
• The heap’s root is the kth largest.

It’s O(n + k log n) time (build heap + updates) and O(k) space, straightforward but slower than QuickSelect.

Step-by-Step Example

For [3,2,1,5,6,4], k=2:

• Heap: [3,2], min = 2.
• 1 < 2, skip.
• 5 > 2, heap = [3,5], min = 3.
• 6 > 3, heap = [5,6], min = 5.
• 4 < 5, skip.
• Output: 5.

How the Code Works (Min-Heap)

Copy codeimport heapq

def findKthLargestHeap(nums: list[int], k: int) -> int:
    heap = nums[:k]
    heapq.heapify(heap)
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, num)
    return heap[0]

Complexity

• QuickSelect:
• Time: O(n) average, O(n²) worst – partition and recurse.
• Space: O(1) – in-place.
• Min-Heap:
• Time: O(n + k log n) – build heap + updates.
• Space: O(k) – heap size.

Efficiency Notes

QuickSelect is our best solution with O(n) average time and O(1) space. Min-Heap is reliable but slower for large n.

Key Insights

• QuickSelect: Pivot-based pruning.
• Heap: Maintains k largest.
• Order Statistic: kth largest focus.

Additional Example

For [7,4,6,3,9,1], k=3:

• QuickSelect: Target index 3, finds 6.
• Heap: [6,7,9], returns 6.

Edge Cases

• k=1: Largest element.
• k=n: Smallest element.
• Single element: Works fine.

Both handle these well.

Final Thoughts

LeetCode 215: Kth Largest Element in an Array in Python is a gem of an algorithm problem. QuickSelect shines with speed, while Min-Heap offers simplicity. Want more? Try LeetCode 347: Top K Frequent Elements or LeetCode 23: Merge k Sorted Lists. Test your skills—Solve LeetCode 215 on LeetCode with [3,2,1,5,6,4], k=2 (expecting 5)—find that kth largest today!