[LeetCode / C++] 215. Kth Largest Element in an Array

1. Question

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

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

Example 2:

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

2. Thoughts

1. Leave only the k large element and iterate the array (karr)
2. If a bigger element is found, swap with the smallest element. => Use min Heap
3. Return the k-1th element of the karr

3. Tips learned

3.1 Min Heap

A min heap in C++ can be implemented using various approaches, but the most common and easiest way is to use the priority queue from the Standard Template Library (STL). By default, std::priority_queue is a max heap, but you can transform it into a min heap by using a custom comparator.

Here’s a step-by-step guide on how to use a min heap in C++ using std::priority_queue:

1. Include the necessary header:

You need to include the <queue> and <vector> headers for using priority_queue.

#include <iostream>
#include <queue>
#include <vector>

2. Define the min heap:

By default, std::priority_queue is a max heap, so you need to use greater<T> as the comparator to create a min heap.

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

• The first parameter int defines the data type.
• The second parameter std::vector<int> specifies that you will store the elements in a vector.
• The third parameter std::greater<int> defines that it should act as a min heap.

3. Operations on the min heap:

Push elements into the min heap:

You can use the push function to insert elements into the heap.

minHeap.push(10);
minHeap.push(30);
minHeap.push(20);
minHeap.push(5);

Access the minimum element:

The minimum element is always at the top of the heap. You can access it using the top function.

std::cout << "Min element: " << minHeap.top() << std::endl;  // Output will be 5

Pop the minimum element:

You can remove the top (minimum) element using the pop function.

minHeap.pop();  // Removes the element 5

Check if the heap is empty:

You can check if the heap is empty using the empty function.

if (minHeap.empty()) {
    std::cout << "The heap is empty." << std::endl;
}

Get the size of the heap:

To get the number of elements in the heap, use the size function.

std::cout << "Size of heap: " << minHeap.size() << std::endl;

Full Example:

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // Define a min heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // Push elements into the heap
    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);
    minHeap.push(5);

    // Access and remove elements
    std::cout << "Min element: " << minHeap.top() << std::endl;  // Output: 5
    minHeap.pop();  // Removes the element 5

    std::cout << "Next min element: " << minHeap.top() << std::endl;  // Output: 10

    return 0;
}

Key Points:

• Push Operation: Insert an element into the heap using push().
• Top Operation: Access the minimum element using top().
• Pop Operation: Remove the top element using pop().
• Empty Check: Use empty() to check if the heap is empty.
• Size Check: Use size() to check how many elements are in the heap.

This should help you use a min heap in C++ effectively! Let me know if you need more details.

4. My solution

class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        priority_queue<int, vector<int>, greater<int>> karr;

        for (int i = 0; i < k; i++)
        {
            karr.push(nums.at(i));
        }

        for (int i = k; i < nums.size(); i++)
        {
            if (nums.at(i) > karr.top())
            {
                karr.pop();
                karr.push(nums.at(i));
            }
        }

        return karr.top();
    }
};

62/62 cases passed (10 ms)
Your runtime beats 99.59 % of cpp submissions
Your memory usage beats 90.68 % of cpp submissions (12 MB)

5. AI Solution and Improvements

Your solution is already quite efficient and follows the correct approach using a min heap to find the k-th largest element. To make it more "C++-style" and improve readability, there are a few minor adjustments you can consider:

1. Use Range-based for Loops:

Range-based for loops make your code more readable and are considered more modern in C++.

2. Use emplace Instead of push:

The emplace() method constructs the element directly in the container, which can be slightly more efficient than push().

3. Avoid at() Method in Favor of Direct Access:

Since you are certain about the bounds, accessing elements with nums[i] is more idiomatic and doesn't incur the overhead of boundary checking.

4. Const Reference for the Input Vector:

Passing the input vector as a const reference ensures that the function won't modify the input and avoids unnecessary copying.

Here’s the improved version of your solution:

class Solution
{
public:
    int findKthLargest(const std::vector<int> &nums, int k)
    {
        std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

        // Insert the first k elements into the min heap
        for (int i = 0; i < k; ++i)
        {
            minHeap.emplace(nums[i]);
        }

        // Process the remaining elements
        for (int i = k; i < nums.size(); ++i)
        {
            if (nums[i] > minHeap.top())
            {
                minHeap.pop();
                minHeap.emplace(nums[i]);
            }
        }

        return minHeap.top();
    }
};

Key Improvements:

1. Range-based for loop: This was not applied here since we're handling elements differently, but in other contexts, it might be useful.
2. emplace(): It is used to construct elements in-place in the heap.
3. Direct access: nums[i] is used instead of nums.at(i) since it’s more efficient and appropriate here.
4. const reference: Passing the vector as a constant reference ensures that the function doesn’t modify the input and improves performance.

These small improvements make the code more idiomatic and efficient in C++ while maintaining the same functionality.