K-th Largest Element in an Array

55.4k
0

An integer array nums and a positive integer k are given. Arrange every array occurrence by value from largest to smallest and consider every duplicate occurrence as a separate position.

Return the value occupying position k in the descending order.

Example 1

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Explanation: Descending order becomes [6, 5, 5, 4, 3, 3, 2, 2, 1]. Position 4 contains 4, and both occurrences of 5 occupy separate positions.

Example 2

Input: nums = [7], k = 1
Output: 7
Explanation: A single-element array has the same value as the largest and smallest ranked element.

Brute Force Approach

Sorting the complete array makes the k-th largest element easy to locate. After sorting in ascending order, the k-th largest value appears at index n - k.

This approach is simple and provides a clear baseline, but it sorts all elements even though only one value is required.

Algorithm

  • Copy nums into sortedNums so the original array remains unchanged.

  • Sort sortedNums in ascending order so every element gets its correct sorted position.

  • Store the array size in n because the k-th largest position depends on the total number of elements.

  • Calculate the required index as n - k, because the k-th largest element appears at that position in ascending order.

  • Return sortedNums[n - k] as the k-th largest element.

Dry Run

k-th-largest-element-in-an-array-brute-force-heading-brute-approach-final.png

k-th-largest-element-in-an-array-brute-force-heading-brute-approach-final.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the kth largest value by sorting a copy.
int findKthLargest(vector<int>& nums, int k) {
// Copy the array to preserve the original order.
vector<int> sortedNums = nums;
// Sort the copied values in ascending order.
sort(sortedNums.begin(), sortedNums.end());
int n = sortedNums.size();
// Convert the descending rank to an ascending index.
int targetIndex = n - k;
// Read the value stored at the required rank.
return sortedNums[targetIndex];
}
};
// Driver code
int main() {
vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
Solution obj;
cout << obj.findKthLargest(nums, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of elements in the array, because sorting all N copied values determines their complete order.

Space Complexity: O(N), because the copied array stores N values apart from language-specific sorting overhead.

Better Approach

Sorting the whole array does more work than needed because only the k largest elements matter. A min-heap of size k keeps only these useful candidates, with the smallest among them always available at the root.

Whenever the heap grows beyond k, remove its smallest value because it cannot remain among the current top k elements. After processing the complete array, the heap contains exactly the k largest occurrences, so its root is the k-th largest element.

Algorithm

  • Create an empty min-heap named minHeap so the smallest retained candidate always stays at the root.

  • Traverse every value in nums so each occurrence gets a chance to enter the top k.

  • Push the current value into minHeap because it may belong among the k largest elements.

  • If the heap size becomes greater than k, remove the root because the smallest candidate is no longer needed.

  • Keep duplicate values as separate heap entries because each occurrence has its own rank in sorted order.

  • After processing all elements, return the heap root because it is the smallest value among the k largest elements, making it the k-th largest.

Dry Run

Kth largest element in array better

Kth largest element in array better

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the kth largest value with a size-k heap.
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
// Process every value as a ranked candidate.
for (int value : nums) {
// Add the current value to the candidate heap.
minHeap.push(value);
// An overflow contains one unnecessary value.
if (minHeap.size() > k) {
// Remove the smallest candidate after overflow.
minHeap.pop();
}
}
// The root is smallest among the top k values.
return minHeap.top();
}
};
// Driver code
int main() {
vector<int> nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
int k = 4;
Solution obj;
cout << obj.findKthLargest(nums, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log k), where N is the number of elements in the array, because every element is inserted into a heap containing at most k + 1 elements.

Space Complexity: O(k), because the min-heap stores at most k candidate elements.

Optimal Approach

Quickselect avoids fully sorting the array because only the position of the k-th largest element matters. Convert it to the ascending target index n - k, then repeatedly partition only the part of the array that can still contain this index.

A three-way partition separates values into smaller, equal, and greater groups around a pivot. This handles duplicate values efficiently because all values equal to the pivot are processed together. Random pivot selection helps avoid consistently unbalanced partitions.

Algorithm

  • Convert the k-th largest rank into target index n - k, because Quickselect works naturally with ascending positions.

  • Set left = 0 and right = n - 1 to represent the active range containing the target.

  • Choose a random pivot from the active range to reduce the chance of repeatedly poor partitions.

  • Use three pointers:

    • smaller marks where values smaller than the pivot should go.

    • current scans the active range.

    • greater marks where values greater than the pivot should go.

  • While current <= greater:

    • If the current value is smaller than the pivot, move it toward smaller and advance both pointers.

    • If the current value is greater than the pivot, move it toward greater and decrease greater.

    • If the current value equals the pivot, advance current so equal values remain in the middle.

  • After partitioning:

    • If the target lies inside the equal region, return the pivot because the required rank has been found.

    • If the target lies to the left, continue only with the left part.

    • Otherwise, continue only with the right part.

  • Repeat until the target value is found.

Dry Run

kth largest array optimal

kth largest array optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Swaps values stored at two array positions.
void swapValues(vector<int>& nums, int first, int second) {
int temporary = nums[first];
nums[first] = nums[second];
nums[second] = temporary;
}
// Splits a range into smaller, equal, and larger.
pair<int, int> partition(vector<int>& nums, int left, int right) {
// Choose a pivot from the active range.
int pivotIndex = left + rand() % (right - left + 1);
int pivotValue = nums[pivotIndex];
int smaller = left;
int current = left;
int greater = right;
// Classify every value in the active range.
while (current <= greater) {
// Smaller values grow the left region.
if (nums[current] < pivotValue) {
swapValues(nums, current, smaller);
smaller++;
current++;
continue;
}
// Larger values grow the right region.
if (nums[current] > pivotValue) {
swapValues(nums, current, greater);
greater--;
continue;
}
// Equal values grow the middle region.
current++;
}
return make_pair(smaller, greater);
}
public:
// Finds the kth largest value with Quickselect.
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
// Seed pivot choices before selection begins.
srand(time(0));
// Convert the descending rank to an ascending index.
int targetIndex = n - k;
int left = 0;
int right = n - 1;
// Narrow search to the range containing the target.
while (left <= right) {
pair<int, int> equalRange = partition(nums, left, right);
int equalStart = equalRange.first;
int equalEnd = equalRange.second;
// A target inside the equal band has the answer.
if (targetIndex >= equalStart && targetIndex <= equalEnd) {
return nums[targetIndex];
}
// A left target discards the middle and right.
if (targetIndex < equalStart) {
right = equalStart - 1;
} else {
// A right target discards the middle and left.
left = equalEnd + 1;
}
}
// Valid inputs always locate a target value.
return -1;
}
};
// Driver code
int main() {
vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
Solution obj;
cout << obj.findKthLargest(nums, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N) on average, where N is the number of elements in the array, because each partition reduces the active search range. In the worst case, repeatedly choosing extreme pivots leads to O(N2) time.

Space Complexity: O(1), because in-place partitioning and iterative range updates use only a fixed number of variables.

Interview follow-up Questions

Yes. Every duplicate occurrence occupies a separate sorted-order position. For example, descending order [5, 5, 4] gives rank 2 to value 5.

Heap

Read Similar Blogs

Heap

Find K Pairs with Smallest Sums

Given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k , form every index-pair [firstIndex, secondIndex] . The sum of an index-pair is nums1[firstIndex] + nums2[se...

61.1k
Heap

Introduction to Heap

Imagine an emergency room with several waiting patients. The patient needing the most urgent care is treated first, even if another patient arrived earlier. The next choice depends on priority, not...

72.8k
Heap

Meeting Rooms II

Given an array intervals , where every entry [start, end] represents one meeting, find the minimum number of conference rooms needed to hold every meeting without a scheduling conflict. An end time...

57.7k
Comments0