Kth Largest Element in C++

Source: Dev.to

🧩 Problem Statement

Given an array and an integer k, find the k‑th largest element.

Example

• Input: [3, 2, 1, 5, 6, 4], k = 2
• Output: 5

🧠 My First Thought: Single Pass + Greedy Update

Many array problems can be solved with:

• one loop
• constant space
• greedy updates

I asked myself: “Can I track the k‑th largest element while traversing once?”

Attempted Idea (Greedy Thinking)

• Keep updating the largest values.
• Try to maintain the k‑th largest dynamically.

❌ Why This Fails

To find the k‑th largest, you must know how many elements are larger than the current value. In a single pass:

• You don’t know future elements.
• You can’t decide rank accurately.
• Greedy decisions become unreliable.

📌 Key Insight

Greedy works only when local decisions guarantee global correctness.

Example Where Greedy Breaks

Array: {7, 4, 6, 3, 9, 1}, k = 2

While traversing you may think 7 is large, but later 9 appears and changes the ranking. Earlier greedy decisions become invalid. Ranking problems depend on the full context, not a partial traversal.

🧠 Important Learning

✅ Correct Approach: Using STL sort()

#include 
#include 
#include 
using namespace std;

int main() {
    vector arr = {3, 2, 1, 5, 6, 4};
    int k = 2;

    sort(arr.begin(), arr.end(), greater());

    cout << "Kth largest element: " << arr[k - 1];
}

⏱ Time & Space Complexity

• Sorting: O(n log n)
• Space: In‑place sort O(1) (ignoring recursion stack)

This is acceptable in most interview problems unless constraints are huge.

⚠️ But Is Sorting Always the Best?

• For large data sets:
  • priority_queue → O(n log k)
  • nth_element → average O(n)

For learning & interviews, sort() is:

• readable
• reliable
• easy to explain

🧠 Interview Thinking Lesson (Most Important)

When solving a problem, ask:

1. Does the problem need global ordering?
2. Can local greedy decisions guarantee correctness?

If the answer is no, remember: “Optimization comes after correctness.”

🚀 Final Takeaway

• Tried greedy → understood its limits.
• Used STL sort() → got a correct, clean solution.
• Learned when not to optimize.

That’s real progress.

📝 Practice Suggestion

Classify problems using the following checklist:

• ✅ Greedy single‑pass possible?
• ✅ Needs sorting?
• ✅ Needs heap?

Developing this habit improves interview‑thinking speed.