LeetCode 75
Kth Largest Element in an Array
- Problem
- LC 215
- Topic
- Heap / PQ
- File
- official75_LC215KthLargestElementInAnArray.java
- Path
- pkg5leetcode/official75/official75_LC215KthLargestElementInAnArray.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC215KthLargestElementInAnArray.java
- Approach
- Min-heap of size k.
- Complexity
- Time O(n log k), Space O(k)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Kth Largest Element in an Array | LC 2155 * APPROACH: Min-heap of size k.6 * COMPLEXITY: Time O(n log k), Space O(k)7 */8import java.util.*;9 10public class official75_LC215KthLargestElementInAnArray {11 static int findKthLargest(int[] nums, int k) {12 PriorityQueue<Integer> pq = new PriorityQueue<>();13 for (int n : nums) {14 pq.offer(n);15 if (pq.size() > k) pq.poll();16 }17 return pq.peek();18 }19 20 public static void main(String[] args) {21 check(findKthLargest(new int[]{3,2,1,5,6,4}, 2) == 5, "case1");22 check(findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4) == 4, "case2");23 System.out.println("all tests passed");24 }25 26 static void check(boolean cond, String name) {27 if (!cond) throw new AssertionError("FAILED: " + name);28 System.out.println(" PASS " + name);29 }30}