Kth Largest Element in an Array

Finding the Kth largest element in an array is a practical problem you’ll face when you need to compute statistics on large datasets—think fetching the 90th percentile of response times or the third-best score in a game. In an interview, it tests your ability to move from brute-force toward more efficient selection algorithms under time and space constraints.

Problem Statement

Given an unsorted 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.

Implement:

1. Clarify Requirements Before Jumping Into Code

I need to be sure I’ve got all the details:

Are values guaranteed to fit in memory? Yes.
Will k always be between 1 and nums.length? Assume yes.
Should duplicates count separately? Yes, duplicates count toward the Kth position.
Can I modify the input array? That’s allowed unless stated otherwise.
What time/space targets? Ideally faster than O(n log n) sorting if possible.

2. Identify the Category of the Question

This is a selection problem on unsorted data. It’s related to sorting but doesn’t require full order—only a pivot into the correct position. Common patterns include sorting, heap, or quickselect (a variation of quicksort’s partition).

3. Consider a Brute-Force Approach to Understand the Problem

Brute-force: sort the entire array in descending order, then return the element at index k-1.

Time Complexity: O(n log n)
Space Complexity: O(1) or O(n) depending on sort implementation
Pros: Very simple
Cons: More work than needed if we only want the Kth element

4. Brainstorm More Solutions

I want to do better than full sort.

One idea is to maintain a min-heap of size k:

Iterate through nums, push into the heap.
If the heap size exceeds k, pop the smallest.
At the end, the top of the heap is the Kth largest.

That uses O(n log k) time and O(k) space.

Can I do it in average O(n) time with O(1) extra space? I recall the Quickselect algorithm:

Pick a pivot, partition the array so that elements greater than pivot go one side, smaller on the other.
If the pivot lands at index p, compare p to k-1:
- If p == k-1, pivot is the answer.
- If p > k-1, recurse into the left partition.
- If p < k-1, recurse into the right partition with adjusted k.

This partition-based selection avoids sorting the whole array and runs in average O(n) time, O(1) extra space. It does require careful in-place swaps and good pivot choice—random pivot can guard against worst-case O(n²).

5. Discuss Trade-Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Sort + Index	O(n log n)	O(1) or O(n)	trivial to implement	more work than necessary
Min-Heap (size k)	O(n log k)	O(k)	simpler than quickselect, stable	uses extra space ~O(k)
Quickselect	O(n) average	O(1)	fastest average runtime, in-place	worst-case O(n²), more code

Heap is safe and easy; Quickselect is optimal if implemented correctly.

6. Write Pseudocode to Structure Your Thoughts

function findKthLargest(nums, k):
  target = k - 1
  left = 0, right = len(nums) - 1

  while True:
    pivotIndex = partition(nums, left, right)
    if pivotIndex == target:
      return nums[pivotIndex]
    else if pivotIndex > target:
      right = pivotIndex - 1
    else:
      left = pivotIndex + 1

function partition(nums, left, right):
  pivot = nums[right]
  storeIndex = left
  for i from left to right-1:
    if nums[i] > pivot:
      swap(nums[i], nums[storeIndex])
      storeIndex += 1
  swap(nums[storeIndex], nums[right])
  return storeIndex

7. Consider Edge Cases

k = 1 → largest element
k = n → smallest element
All elements equal → any element is correct
Array of length 1 → return that element
Negative and positive mix → works with comparisons

8. Write Full Code Syntax

import random

def findKthLargest(nums, k):
    target = k - 1
    left, right = 0, len(nums) - 1

    def partition(l, r):
        pivot_index = random.randint(l, r)
        nums[pivot_index], nums[r] = nums[r], nums[pivot_index]
        pivot = nums[r]
        store = l
        for i in range(l, r):
            if nums[i] > pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[r] = nums[r], nums[store]
        return store

    while True:
        idx = partition(left, right)
        if idx == target:
            return nums[idx]
        elif idx > target:
            right = idx - 1
        else:
            left = idx + 1

9. Test Your Code

print(findKthLargest([3,2,1,5,6,4], 2))  # 5
print(findKthLargest([3,2,3,1,2,4,5,5,6], 4))  # 4
print(findKthLargest([1], 1))  # 1
print(findKthLargest([2,1], 1))  # 2
print(findKthLargest([2,1], 2))  # 1
print(findKthLargest([5,5,5,5], 2))  # 5

Expected outputs commented; all should match.

10. Key Lessons to Remember for Future Questions

When you need just the Kth element, avoid full sorting—consider selection algorithms.
Heaps are a straightforward path to O(n log k) performance with minimal extra code.
Quickselect generalizes quicksort’s partition to selection, giving average O(n) time in-place.
Always handle k = 1 and k = n as smoke tests.
Writing clear partition logic in pseudocode helps catch pointer swaps before coding.
Randomizing the pivot guards against worst-case inputs and ensures average-case performance.

Good Luck and Happy Coding!