Day 1 - k largest elements.md

Difficulty	Medium
Source	160 Days of Problem Solving
Tags	Arrays Sorting Heap

🚀 Day 1. K Largest Elements 🧠

The problem can be found at the following link: Question Link

💡 Problem Description:

Given an array arr[] of positive integers and an integer k, your task is to return the k largest elements in decreasing order.

🔍 Example Walkthrough:

Example 1:

Input:

arr = [12, 5, 787, 1, 23]
k = 2

Output:

[787, 23]

Explanation:

• The 1st largest element is 787.
• The 2nd largest element is 23.

Example 2:

Input:

arr = [1, 23, 12, 9, 30, 2, 50]
k = 3

Output:

[50, 30, 23]

Explanation:

• The 3 largest elements in descending order are 50, 30, and 23.

Example 3:

Input:

arr = [12, 23]
k = 1

Output:

[23]

Explanation:

• The 1st largest element is 23.

Constraints:

• $(1 \leq k \leq arr.size() \leq 10^6)$
• $(1 \leq arr[i] \leq 10^6)$

🎯 My Approach:

Optimized Partial Sort (O(N + K log K) Time, O(1) Space)

1. Use nth_element() to partition the k largest elements in O(N).
2. Use partial_sort() to sort the top k elements in O(K log K).
3. Extract and return the k largest elements in descending order.

Algorithm Steps:

1. Use nth_element() to place the k-th largest element at arr.end() - k.
2. Use partial_sort() to sort only the k largest elements in descending order.
3. Return the last k elements in arr.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(N + K log K), due to partitioning and sorting.
• Expected Auxiliary Space Complexity: O(1), since sorting is done in-place.

📝 Solution Code

Code (C++)

class Solution {
  public:
    vector<int> kLargest(vector<int>& arr, int k) {
        nth_element(arr.begin(), arr.end() - k, arr.end());
        partial_sort(arr.end() - k, arr.end(), arr.end(), greater<int>());
        return vector<int>(arr.end() - k, arr.end());
    }
};

⚡ Alternative Approaches

2️⃣ Min-Heap Approach (O(N log K) Time, O(K) Space)

Approach:

1. Maintain a min-heap of size k using a priority queue.
2. Push elements into the heap and ensure it only keeps k largest elements.
3. Extract elements in descending order from the heap.

Code (C++)

class Solution {
  public:
    vector<int> kLargest(vector<int>& arr, int k) {
        priority_queue<int, vector<int>, greater<int>> pq(arr.begin(), arr.begin() + k);
        for (int i = k; i < arr.size(); i++)
            if (arr[i] > pq.top()) pq.pop(), pq.push(arr[i]);
        vector<int> res(k);
        while (!pq.empty()) res[--k] = pq.top(), pq.pop();
        return res;
    }
};

🔹 Pros: Efficient for real-time data processing.
🔹 Cons: Extra space (O(K)) for the heap.

3️⃣ Sorting Approach (O(N log N) Time, O(1) Space)

Approach:

1. Sort the array in descending order using sort().
2. Return the first k elements from the sorted array.

Code (C++)

class Solution {
  public:
    vector<int> kLargest(vector<int>& arr, int k) {
        sort(arr.rbegin(), arr.rend());
        return vector<int>(arr.begin(), arr.begin() + k);
    }
};

🔹 Pros: Simple to implement.
🔹 Cons: Inefficient for large N due to sorting.

📊 Comparison of Approaches

Approach	⏱️ Time Complexity	🗂️ Space Complexity	⚡ Method	✅ Pros	⚠️ Cons
Optimized Partial Sort	🟢 O(N + K log K)	🟢 O(1)	Partial Sort	Best runtime & space efficiency	None
Min-Heap (Priority Queue)	🟡 O(N log K)	🟡 O(K)	Heap-based	Good for streaming data	Extra space usage
Sorting Approach	🔴 O(N log N)	🟢 O(1)	Sorting	Simple & easy to implement	Slow for large N

💡 Best Choice?

• ✅ For best efficiency: Partial Sort (O(N + K log K), O(1)).
• ✅ For real-time data processing: Min-Heap (O(N log K), O(K)).
• ✅ For simplicity: Sorting Approach (O(N log N), O(1)).

Code (Java)

class Solution {
    public ArrayList<Integer> kLargest(int[] arr, int k) {
        Arrays.sort(arr);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = arr.length - 1; i >= arr.length - k; i--) res.add(arr[i]);
        return res;
    }
}

Code (Python)

class Solution:
    def kLargest(self, arr, k):
        return sorted(arr, reverse=True)[:k]

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count