KTH 가장 큰 요소 | 힙

Problem Statement

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

Note:

Not the kth distinct element.

Enter fullscreen mode Exit fullscreen mode

Brute Force Intuition

In an interview, you can explain it like this:

Sort the entire array in descending order and return the kth element.

Complexity

• Time Complexity: O(N log N)
• Space Complexity: O(1)

Brute Force Code

Arrays.sort(nums);

return nums[nums.length - k];

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Better Heap Approach

Do we really need the entire sorted array?

No.

We only care about:

Top K largest elements

Enter fullscreen mode Exit fullscreen mode

A Min Heap of size K is sufficient.

Pattern Recognition

Whenever you see:

• Kth Largest
• Kth Smallest
• Top K Elements

Think:

Heap

Better Approach

Maintain a Min Heap.

For every element:

pq.add(num);

Enter fullscreen mode Exit fullscreen mode

If heap size exceeds:

k

Enter fullscreen mode Exit fullscreen mode

remove smallest.

pq.poll();

Enter fullscreen mode Exit fullscreen mode

At the end:

Top of heap
=
Kth Largest Element

Enter fullscreen mode Exit fullscreen mode

Optimal Java Solution

class Solution {

    public int findKthLargest(int[] nums, int k) {

        PriorityQueue<Integer> pq =
            new PriorityQueue<>();

        for (int num : nums) {

            pq.add(num);

            if (pq.size() > k) {
                pq.poll();
            }
        }

        return pq.peek();
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

nums = [3,2,1,5,6,4]

k = 2

Enter fullscreen mode Exit fullscreen mode

Heap:

3

2 3

1 2 3
remove 1

2 3

2 3 5
remove 2

3 5

3 5 6
remove 3

5 6

4 5 6
remove 4

5 6

Enter fullscreen mode Exit fullscreen mode

Answer:

5

Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

Metric Complexity Time Complexity O(N log K) Space Complexity O(K)

Interview One-Liner

Maintain a Min Heap of size K. The top of the heap always represents the kth largest element seen so far.

Pattern Learned

Top K
+
Largest / Smallest

=> Heap

Enter fullscreen mode Exit fullscreen mode