Problem Description

You're given an integer array nums and an integer k. Your task is to find and return the kth largest element in the array.

The key points to understand:

1. Sorted order, not distinct: When we say kth largest, we mean if you were to sort the array in descending order, the element at position k would be your answer. Duplicate values are counted separately. For example, in the array [3,2,3,1,2,4,5,5,6], the 4th largest element is 4 (the sorted descending order would be [6,5,5,4,3,3,2,2,1]).

2. Challenge constraint: The problem asks if you can solve it without fully sorting the array, which would typically take O(n log n) time.

The solution uses the Quick Select algorithm, which is a variation of QuickSort. Instead of fully sorting the array, it strategically partitions the array around a pivot element:

• Elements greater than or equal to the pivot go to the left
• Elements less than or equal to the pivot go to the right
• Based on where the pivot ends up, we know which side contains our target element

The algorithm cleverly converts finding the kth largest to finding the (n-k)th smallest (0-indexed), which simplifies the partitioning logic. For instance, if we want the 2nd largest element in an array of size 5, we're looking for the element at index 3 when sorted in ascending order.

The partition process uses two pointers (i and j) that move toward each other, swapping elements that are on the wrong side of the pivot. Once a partition is complete, if the pivot's position is where we need our answer, we recursively search either the left or right partition until we find the exact position of our kth largest element.

This approach achieves an average time complexity of O(n), making it more efficient than sorting the entire array when we only need one specific element.

Intuition

When asked to find the kth largest element, the straightforward approach would be to sort the entire array and pick the element at index k-1 (for descending order) or index n-k (for ascending order). However, this takes O(n log n) time, and we're doing unnecessary work - we're finding the exact positions of all elements when we only care about one specific position.

Think about it this way: if you need to find the 3rd tallest person in a room of 100 people, you don't need to arrange all 100 people in height order. You just need to ensure that exactly 2 people are taller than your answer, and everyone else is shorter or equal.

This leads us to the key insight: we can use the partitioning idea from QuickSort, but we don't need to sort both halves of the array. In QuickSort's partition step, we pick a pivot and rearrange the array so that:

• All elements greater than the pivot are on one side
• All elements less than the pivot are on the other side
• The pivot ends up in its final sorted position

After one partition, we know the pivot is in its correct position. If this position happens to be k, we're done! If not, we know whether our target is in the left or right half based on the pivot's position:

• If the pivot ends up at position p and p < k, our answer must be in the right half
• If p > k, our answer must be in the left half

By recursively applying this logic only to the half that contains our target, we avoid sorting the entire array. On average, we look at n + n/2 + n/4 + ... ≈ 2n elements, giving us O(n) average time complexity.

The solution cleverly transforms the problem from finding the kth largest to finding the (n-k)th smallest element (using 0-based indexing). This simplification makes the partitioning logic more natural since we're working with ascending order comparisons, which aligns with how we typically think about array indices increasing from left to right.

Solution Approach

The solution implements the Quick Select algorithm, which is a partition-based selection algorithm. Let's walk through the implementation step by step:

1. Problem Transformation:

n = len(nums)
k = n - k

Instead of finding the kth largest element, we transform it to finding the (n-k)th smallest element in 0-based indexing. For example, finding the 2nd largest in an array of size 5 means finding the element at index 3 when sorted in ascending order.

2. The Main Quick Select Function:

def quick_sort(l: int, r: int) -> int:

This recursive function takes the left and right boundaries of the current search range. Despite its name suggesting "sort," it actually performs selection.

3. Base Case:

if l == r:
    return nums[l]

When the search range contains only one element, that element must be our answer.

4. Partition Setup:

i, j = l - 1, r + 1
x = nums[(l + r) >> 1]

• Initialize two pointers: i starts before the left boundary, j starts after the right boundary
• Choose the middle element as the pivot x (using bit shift >> 1 for integer division by 2)

5. Three-Way Partitioning:

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]

This partitioning scheme moves elements such that:

• Elements ≥ pivot go to the left side
• Elements ≤ pivot go to the right side
• Pointer i finds elements that should be on the right (elements ≥ pivot)
• Pointer j finds elements that should be on the left (elements ≤ pivot)
• When both pointers find misplaced elements, we swap them

6. Recursive Selection:

if j < k:
    return quick_sort(j + 1, r)
return quick_sort(l, j)

After partitioning, position j marks the boundary where all elements to the left are ≥ pivot and all elements to the right are ≤ pivot.

• If j < k, our target is in the right partition (smaller elements), so we search [j+1, r]
• Otherwise, our target is in the left partition (larger elements), so we search [l, j]

Key Implementation Details:

1. Why this partitioning works: Unlike standard QuickSort that puts smaller elements on the left, this implementation puts larger elements on the left because we're looking for large elements but working with the (n-k)th position.

2. The partition boundary: The algorithm uses j as the partition point because after the loop, j represents the rightmost position of the left partition (elements ≥ pivot).

3. Time Complexity:

   • Average case: O(n) - we process n + n/2 + n/4 + ... ≈ 2n elements
   • Worst case: O(n²) - when the pivot consistently divides the array poorly
   • The choice of middle element as pivot helps avoid worst-case scenarios for already sorted arrays

4. Space Complexity: O(log n) on average for the recursion stack, O(n) in the worst case.

This implementation elegantly solves the problem without fully sorting the array, achieving better average-case performance than heap-based or sorting-based solutions.

Example Walkthrough

Let's find the 2nd largest element in the array [3, 2, 1, 5, 6, 4] using the Quick Select approach.

Step 1: Transform the problem

• Array: [3, 2, 1, 5, 6, 4], n = 6, k = 2
• Convert to finding (n-k)th smallest: 6 - 2 = 4 (finding element at index 4 in sorted ascending order)
• Target index: k = 4

Step 2: First partition (l=0, r=5)

• Choose pivot: middle element at index (0+5)/2 = 2, pivot = nums[2] = 1
• Initialize pointers: i = -1, j = 6

Partitioning process:

Initial: [3, 2, 1, 5, 6, 4]
       
i moves right, stops at index 0 (3 >= 1)
j moves left, stops at index 2 (1 <= 1)
i < j, so swap: [1, 2, 3, 5, 6, 4]
                 ^     ^
                 i     j

i moves right, stops at index 1 (2 >= 1)
j moves left, stops at index 0 (1 <= 1)
Now i >= j, partitioning complete

• After partition: [1, 2, 3, 5, 6, 4], j = 0
• Since j(0) < k(4), search right partition

Step 3: Second partition (l=1, r=5)

• Choose pivot: middle element at index (1+5)/2 = 3, pivot = nums[3] = 5
• Initialize pointers: i = 0, j = 6

Partitioning process:

Current: [1, 2, 3, 5, 6, 4]
            ^--------^
            search range

i moves right, stops at index 3 (5 >= 5)
j moves left, stops at index 5 (4 <= 5)
i < j, so swap: [1, 2, 3, 4, 6, 5]
                          ^     ^
                          i     j

i moves right, stops at index 4 (6 >= 5)
j moves left, stops at index 3 (4 <= 5)
Now i >= j, partitioning complete

• After partition: [1, 2, 3, 4, 6, 5], j = 3
• Since j(3) < k(4), search right partition

Step 4: Third partition (l=4, r=5)

• Choose pivot: middle element at index (4+5)/2 = 4, pivot = nums[4] = 6
• Initialize pointers: i = 3, j = 6

Partitioning process:

Current: [1, 2, 3, 4, 6, 5]
                     ^--^
                   search range

i moves right, stops at index 4 (6 >= 6)
j moves left, stops at index 5 (5 <= 6)
i < j, so swap: [1, 2, 3, 4, 5, 6]
                             ^  ^
                             i  j

i moves right, stops at index 5 (6 >= 6)
j moves left, stops at index 4 (5 <= 6)
Now i >= j, partitioning complete

• After partition: [1, 2, 3, 4, 5, 6], j = 4
• Since j(4) == k(4), we continue with the left partition

Step 5: Final partition (l=4, r=4)

• Base case: l == r, return nums[4] = 5

Answer: 5 is the 2nd largest element in the array.

To verify: sorting the array in descending order gives [6, 5, 4, 3, 2, 1], and the 2nd element is indeed 5.

Solution Implementation

Time and Space Complexity

The time complexity is O(n) on average, where n is the length of the array nums. This is achieved through the QuickSelect algorithm (a variant of QuickSort). In each recursive call, the algorithm partitions the array around a pivot and only recurses on one side - the side containing the k-th largest element. On average, this reduces the problem size by half in each iteration, leading to the recurrence relation T(n) = T(n/2) + O(n), which solves to O(n). In the worst case (when the pivot is always the minimum or maximum), the time complexity degrades to O(n²), but with good pivot selection (using the middle element as done here), the average case is O(n).

The space complexity is O(log n) due to the recursive call stack. Since the algorithm only recurses on one partition at a time (unlike standard QuickSort which recurses on both), the maximum depth of recursion is O(log n) on average when the array is roughly halved at each level. In the worst case, the space complexity could be O(n) if the partitioning is extremely unbalanced, but the average case is O(log n).

Common Pitfalls

1. Incorrect Partition Logic Direction

One of the most common mistakes is confusion about the partitioning direction. The code partitions with larger elements on the left and smaller elements on the right, which is counterintuitive to standard QuickSort implementations.

Pitfall Example:

# WRONG: Traditional partition logic that puts smaller elements on left
while i < j:
    while nums[i] < pivot:  # Wrong condition!
        i += 1
    while nums[j] > pivot:  # Wrong condition!
        j -= 1
    if i < j:
        nums[i], nums[j] = nums[j], nums[i]

Solution: The correct implementation uses >= and <= comparisons because we're working with the transformed index n - k:

while i < j:
    while True:
        i += 1
        if nums[i] >= pivot:  # Correct: stop when element is >= pivot
            break
    while True:
        j -= 1
        if nums[j] <= pivot:  # Correct: stop when element is <= pivot
            break
    if i < j:
        nums[i], nums[j] = nums[j], nums[i]

2. Infinite Loop in Partition

Without proper bounds checking or break conditions, the partition loop can run indefinitely.

Pitfall Example:

# WRONG: Missing break conditions
while i < j:
    while nums[i] < pivot:
        i += 1  # Can go out of bounds!
    while nums[j] > pivot:
        j -= 1  # Can go out of bounds!

Solution: Use explicit break conditions or ensure the pivot element itself acts as a sentinel:

while True:
    i += 1
    if nums[i] >= pivot:
        break  # Explicit break ensures termination

3. Incorrect Recursion Boundary

Using the wrong pointer for recursion can lead to incorrect results or infinite recursion.

Pitfall Example:

# WRONG: Using i instead of j for partition boundary
if i < target_index:
    return quickselect(i + 1, right)  # Wrong!
return quickselect(left, i)  # Wrong!

Solution: Always use j as the partition boundary because after the loop completes, j correctly marks where the left partition ends:

if j < target_index:
    return quickselect(j + 1, right)  # Correct
return quickselect(left, j)  # Correct

4. Off-by-One Error in Index Transformation

Forgetting that arrays are 0-indexed when converting from kth largest to index position.

Pitfall Example:

# WRONG: Forgetting 0-based indexing
target_index = n - k + 1  # Wrong!

Solution:

target_index = n - k  # Correct: kth largest is at index (n-k) in sorted array

5. Choosing a Poor Pivot

Always choosing the first or last element as pivot can degrade to O(n²) for sorted or nearly sorted arrays.

Pitfall Example:

# WRONG: Always choosing first element
pivot = nums[left]  # Poor choice for sorted arrays

Solution: Choose the middle element or use median-of-three:

# Better: Middle element
pivot = nums[(left + right) >> 1]

# Best: Median of three
def get_pivot(left, right):
    mid = (left + right) >> 1
    candidates = [(nums[left], left), (nums[mid], mid), (nums[right], right)]
    candidates.sort()
    return candidates[1][0]  # Return median value

6. Not Handling Duplicate Values Correctly

The algorithm must handle arrays with many duplicate values efficiently. The current implementation handles this correctly, but modifications might break this property.

Key Point: The use of >= and <= (rather than > and <) ensures that equal elements can be on either side of the partition, preventing infinite loops when all elements are equal.