Kth Largest Element in an Array – Intuition, Dry Run & C++ Solution

1. Problem Statement

In Simple Words: Imagine you have a list of numbers that are completely jumbled up. Your task is to find the number that would be in the $k$-th position from the end if the list were perfectly sorted from smallest to largest. Note that we are looking for the $k$-th largest element in the sorted order, not the $k$-th distinct element (duplicates count).

Original Problem Statement:

Given an integer array nums and an integer $k$, return the $k$-th largest element in the array.

Input Format:

• An integer array nums of size $N$.
• An integer $k$.

Output Format:

• A single integer representing the $k$-th largest element.

Constraints:

• $1 \le k \le nums.length \le 10^5$
• $-10^4 \le nums[i] \le 10^4$

2. Examples

Let's look at a few examples to understand how the counting works, especially with duplicates.

Example 1

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

Output: 5

Step-by-Step Explanation:

1. If we sort the array in ascending order, it becomes: [1, 2, 3, 4, 5, 6].
2. The largest element (1st largest) is 6.
3. The 2nd largest element is 5.

Example 2 (With Duplicates)

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

Output: 4

Step-by-Step Explanation:

1. Sorted array: [1, 2, 2, 3, 3, 4, 5, 5, 6].
2. 1st largest is 6.
3. 2nd largest is 5.
4. 3rd largest is 5 (duplicates count as separate positions).
5. 4th largest is 4.

Example 3 (Edge Case)

Input: nums = [1], $k = 1$

Output: 1

Step-by-Step Explanation:

1. The array only has one element.
2. The 1st largest element is simply 1.

3. Key Observations

Before jumping into solutions, here are the hidden truths of the problem:

• Sorting Solves Everything, But Does Too Much: Completely sorting the array naturally gives you the answer. However, sorting puts every element in its exact place. We only care about one specific position. Doing unnecessary work is the enemy of an optimal algorithm.
• Top-K Implies a Filter: Whenever you hear "Kth largest" or "Top K", you should immediately think about filtering mechanisms that can hold exactly $k$ items, throwing away anything smaller.
• Partitioning: If you put one element in its correct sorted position (and make sure everything larger is on its right, and everything smaller is on its left), you can count how many elements are larger than it. If exactly $k-1$ elements are larger, you've found your answer without sorting the rest!

4. Intuition

Let's build the intuition gradually.

Why is sorting inefficient?

Sorting takes $O(N \log N)$ time. If you have an array of 100,000 elements and you only want the 1st largest element (the maximum), sorting the whole thing is massive overkill. You'd just scan the array once in $O(N)$ time. We need an approach that scales better for any $k$.

The "VIP Club" approach (Heap)

Imagine a VIP club that only allows exactly $k$ people inside. As people (numbers) line up to enter, you let the first $k$ in. When the $(k+1)$-th person arrives, you compare them to the "weakest" (smallest) person in the club. If the newcomer is stronger (larger), you kick out the weakest person and let the newcomer in. By the time you've processed everyone, the club contains the $k$ largest elements, and the weakest person in the club is exactly the $k$-th largest element! This is the intuition for a Min-Heap.

The "Divide and Conquer" approach (QuickSelect)

Imagine picking a random person in a room and asking everyone taller to stand on their right, and everyone shorter on their left.

• If there are exactly $k-1$ people on their right, the person you picked is the $k$-th tallest!
• If there are more than $k$ people on their right, the $k$-th tallest must be in that right group. You can completely ignore the left group.
• If there are fewer than $k-1$ people on their right, the $k$-th tallest must be in the left group.This is the intuition for the QuickSelect algorithm.

5. Brute Force Solution

Thought Process

The simplest way to find the $k$-th largest element is to just sort the array from largest to smallest (or smallest to largest) and pick the element at the correct index.

Algorithm

1. Sort the nums array in ascending order.
2. The $k$-th largest element will be located at the index N - k, where N is the size of the array.
3. Return nums[N - k].

Dry Run

• Array = [3, 2, 1, 5, 6, 4], $k = 2$. Length $N = 6$.
• Sort: [1, 2, 3, 4, 5, 6].
• Target index: $6 - 2 = 4$.
• nums[4] is 5. Return 5.

C++ Implementation

#include <vector>
#include <algorithm>

using namespace std;

int findKthLargestBrute(vector<int>& nums, int k) {
    // Sort in ascending order
    sort(nums.begin(), nums.end());
    // Return the element at index N - k
    return nums[nums.size() - k];
}

Explanation

We use a Min-Heap (Priority Queue) to maintain a "VIP club" of size $k$. A Min-Heap always keeps the smallest element at the top. We push elements into the heap. If the heap size exceeds $k$, we pop the top element (the smallest one in our current top-$k$ collection). At the end, the top of the heap will be the $k$-th largest element.

Algorithm

1. Create a Min-Heap.
2. Loop through each number in the array:
   • Push the number into the heap.
   • If the heap size becomes greater than $k$, pop the top element.
3. Return the top element of the heap.

C++ Code

#include <vector>
#include <queue>

using namespace std;

int findKthLargestHeap(vector<int>& nums, int k) {
    // Min-heap in C++
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    return minHeap.top();
}

Complexity Analysis

• Time Complexity: $O(N \log k)$. We iterate through $N$ elements, and each insertion/deletion in a heap of size $k$ takes $O(\log k)$ time.
• Space Complexity: $O(k)$ to store the elements in the heap.

7. Optimal Solution (QuickSelect)

this solution is aimed for people who are preparing foe maang companies

QuickSelect is a modification of QuickSort. Instead of sorting both halves of a partitioned array, QuickSelect only recurses into the half that contains the $k$-th largest element.

Search Space

The search space is the entire array, represented by a left pointer (initially 0) and a right pointer (initially $N-1$).

Why QuickSelect is Valid

Every time we partition the array around a pivot, that pivot is placed in its absolute final sorted position. By comparing this final index with our target index ($N - k$), we can determine exactly which side of the pivot holds our answer, entirely discarding the other side.

Proof of Correctness (Why it works)

When a pivot is placed at index p:

1. All elements to the left of p are smaller than nums[p].
2. All elements to the right of p are larger than nums[p].Therefore, if p == N - k, nums[p] is guaranteed to be the $k$-th largest element, regardless of whether the left or right partitions are fully sorted!

8. Partition Function

The core engine is the partition function. Let's break it down:

• Choosing a pivot: We can pick the last element as the pivot. (Note: in production code, picking a random pivot avoids the worst-case time complexity, but for simplicity, we'll explain using the rightmost element).
• The Pointer p: We maintain a pointer p that keeps track of where the next smaller element should go.
• Swapping: As we iterate, if we find an element smaller than the pivot, we swap it to position p and increment p.
• Final Placement: At the end, we swap the pivot itself into position p. Now everything left of p is smaller, and everything right is larger.

9. Dry Run

Let's dry run QuickSelect.

• Array = [3, 2, 1, 5, 6, 4], $k = 2$.
• Target index = $6 - 2 = 4$.

Iteration 1:

• left = 0, right = 5. Pivot = nums[5] = 4.
• Partitioning:
  • 3 < 4 (swap, p becomes 1)
  • 2 < 4 (swap, p becomes 2)
  • 1 < 4 (swap, p becomes 3)
  • 5 > 4 (ignore)
  • 6 > 4 (ignore)
• Swap pivot (4) with nums[p] (5).
• Array becomes [3, 2, 1, 4, 6, 5]. Pivot index p is now 3.
• Compare: p (3) < target index (4).
• Decision: The answer must be in the right half. Update left = p + 1 = 4.

Iteration 2:

• left = 4, right = 5. Subarray: [6, 5]. Pivot = nums[5] = 5.
• Partitioning:
  • 6 > 5 (ignore)
• Swap pivot (5) with nums[p] (6).
• Array becomes [3, 2, 1, 4, 5, 6]. Pivot index p is now 4.
• Compare: p (4) == target index (4).
• Decision: Match found! Return nums[4] which is 5.

10. Algorithm

1. Define target = nums.size() - k.
2. Create a helper function quickSelect(left, right).
3. Pick a pivot (e.g., the rightmost element).
4. Partition the subarray nums[left...right] around the pivot. Let the final pivot index be p.
5. If p == target, return nums[p].
6. If p < target, the answer is to the right. Recursively call quickSelect(p + 1, right).
7. If p > target, the answer is to the left. Recursively call quickSelect(left, p - 1).

11. C++ Code

Here is the clean, interview-ready implementation using randomized QuickSelect to avoid worst-case scenarios:

#include <vector>
#include <cstdlib> // for rand()

using namespace std;

class Solution {
private:
    int partition(vector<int>& nums, int left, int right) {
        // Pick a random pivot to avoid O(N^2) worst case on already sorted arrays
        int pivotIndex = left + rand() % (right - left + 1);
        
        // Move pivot to the end
        swap(nums[pivotIndex], nums[right]);
        int pivot = nums[right];
        
        int p = left; // Pointer for smaller elements
        
        for (int i = left; i < right; i++) {
            if (nums[i] <= pivot) {
                swap(nums[i], nums[p]);
                p++;
            }
        }
        // Move pivot to its final sorted place
        swap(nums[p], nums[right]);
        return p;
    }

    int quickSelect(vector<int>& nums, int left, int right, int target) {
        if (left == right) return nums[left]; // Base case: only one element

        int p = partition(nums, left, right);

        if (p == target) {
            return nums[p];
        } else if (p < target) {
            return quickSelect(nums, p + 1, right, target); // Search right
        } else {
            return quickSelect(nums, left, p - 1, target); // Search left
        }
    }

public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int target = n - k; // We are looking for the element at this index
        return quickSelect(nums, 0, n - 1, target);
    }
};

(Note: In an actual C++ interview, you can also mention std::nth_element(nums.begin(), nums.begin() + nums.size() - k, nums.end());, which handles this entire problem optimally under the hood.)

12. Complexity Analysis

• Average Time Complexity: $O(N)$. Because we discard roughly half the array on each step, the work done is $N + N/2 + N/4 + ... \approx 2N$.
• Worst-Case Time Complexity: $O(N^2)$. If the array is already sorted and we always pick the worst pivot (e.g., the last element), we only discard one element per iteration. This is why randomizing the pivot is crucial!
• Space Complexity: $O(1)$ auxiliary space (modifying array in place), though recursive stack space can take $O(\log N)$ on average, and $O(N)$ in the worst case.

13. Correctness Proof

Why are we absolutely sure QuickSelect works?

1. Pivot Finality: The partition algorithm guarantees that upon completion, the pivot element is in the exact index it would occupy if the entire array were fully sorted.
2. Absolute Discarding: Because everything to the left of the pivot is smaller, and everything to the right is larger, if our target index is greater than the pivot index, it is mathematically impossible for the target element to exist in the left partition. Thus, discarding half the array is entirely safe and guarantees we never skip the answer.

14. Common Mistakes

Watch out for these frequent pitfalls during interviews:

• Index Confusion: Forgetting that $k$-th largest translates to index N - k when sorting in ascending order. (e.g., 1st largest in a 5-element array is index 4).
• Not Randomizing Pivot: Using a fixed pivot (like the last element) leaves you vulnerable to an $O(N^2)$ worst-case, which interviewers will penalize you for.
• Off-By-One Errors: Incorrectly handling the boundaries in the partition loop (e.g., looping i <= right instead of i < right before swapping the pivot back).
• Memory Limit Exceeded: Creating new subarray copies during QuickSelect instead of passing the left and right pointers to operate in place.

15. Pattern Recognition

How do you know an unseen problem uses this exact logic? Look for the "Top K Elements" pattern.

Indicators:

1. The problem asks for the "$K$-th most/least/largest/smallest" of something.
2. The problem asks for the "Top $K$" frequent elements.
3. You need to find a statistical measure like the median (which is just the $N/2$-th element).

17. Interview Tips

When you present this in an interview, keep these tips in mind:

• Start with the Heap, end with QuickSelect: Always present the $O(N \log k)$ Min-Heap solution first. Mention that it is superior if the data is streaming (doesn't fit in memory all at once). Then introduce QuickSelect as the optimal $O(N)$ solution for in-memory arrays.
• Expected Follow-up: "What if the array is continuously growing?"
  • Answer: QuickSelect fails here because it needs the entire array. The Min-Heap approach shines here because you can just continuously push incoming stream data into the heap and pop if size exceeds $k$.
• Know the standard library: If coding in C++, casually mentioning std::nth_element shows deep language proficiency. In Python, mention heapq.nlargest.

Video reference

problem link:

https://leetcode.com/problems/kth-largest-element-in-an-array/description/