This problem looks busy at first, but the accepted solution is built around one steady invariant. For 215. Kth Largest Element in an Array, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: heap / priority queue, binary search, two pointers.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are findKthLargest, randomizedPartition, randomizedSelect.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//Runtime: 12 ms, faster than 77.42% of C++ online submissions for Kth Largest Element in an Array.
02//Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Kth Largest Element in an Array.
03
04class Solution {
05public:
06 int findKthLargest(vector<int>& nums, int k) {
07 //the smaller the earlier to be popped
08 priority_queue<int, vector<int>, greater<int>> pq;
09
10 for(int num : nums){
11 pq.push(num);
12 if(pq.size() > k){
13 pq.pop();
14 }
15 }
16
17 //the smallest in top k elements
18 return pq.top();
19 }
20};
21
22//Divide and conquer
23//https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60495/Sharing-my-12ms-divide-and-conquer-solution-in-c%2B%2B
24// /Runtime: 8 ms, faster than 97.62% of C++ online submissions for Kth Largest Element in an Array.
25//Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Kth Largest Element in an Array.
26class Solution {
27public:
28 int randomizedPartition(vector<int>& nums, int start, int end){
29 srand(time(NULL));
30 int choose = rand()%(end-start+1) + start;
31 //move random selected element to the end
32 swap(nums[choose], nums[end]);
33 //set it as pivot
34 int pivot = nums[end];
35 int l = start-1; //the end of left partition
36 for(int r = start; r < end; r++){
37 if(nums[r] <= pivot){
38 //elements < pivot will be partitioned into left part
39 swap(nums[r], nums[++l]);
40 }
41 }
42 l++; //now l becomes the start of right partition
43 swap(nums[l], nums[end]);
44 return l;
45 };
46
47 int randomizedSelect(vector<int>& nums, int start, int end, int k){
48 //find kth smallest
49 if(start == end) return nums[start];
50 int mid = randomizedPartition(nums, start, end);
51 //here mid is the index to nums
52 //now we need to convert it to the index to nums[start:end] (1-based)
53 int i = mid-start+1; //+1 for 1-based
54 if(i == k){
55 return nums[mid];
56 }else if(i < k){
57 //find (k-i)th smallest in the right partition
58 return randomizedSelect(nums, mid+1, end, k-i);
59 }else{
60 //find kth element in the lest partition
61 return randomizedSelect(nums, start, mid-1, k);
62 }
63 }
64
65 int findKthLargest(vector<int>& nums, int k) {
66 //find kth largest -> find (nums.size()-k+1)th smallest
67 return randomizedSelect(nums, 0, nums.size()-1, nums.size()-k+1);
68 }
69};Cost