Katkat
Back

Return the K Largest Integers

J.P. MorganSoftware Engineer II · Onsite
MediumSoftware Engineer IIOnsiteCoding & Algorithms

Last updated

This problem tests the ability to efficiently find the k largest elements in an unsorted array using heap-based data structures to optimize for cases where k is significantly smaller than the input size.

Problem Statement

Given an array of integers nums and an integer k, return the k largest elements from the array. The output should be returned in descending order. You must handle duplicates, and your solution should be more efficient than sorting the entire array if `k list[int]:


### Constraints
- `1 <= k <= len(nums)`
- `-10^9 <= nums[i] <= 10^9`
- `1 <= len(nums) <= 10^6`

### Examples

**Example 1:**
Input: `nums = [3, 2, 1, 5, 6, 4]`, `k = 2`
Output: `[6, 5]`
Explanation: The two largest elements are 6 and 5.

**Example 2:**
Input: `nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]`, `k = 4`
Output: `[6, 5, 5, 4]`
Explanation: The four largest elements including duplicates are 6, 5, 5, and 4.

### Edge Cases
- `k` is equal to the length of the array.
- The array contains all identical elements.
- The array contains negative integers.

Hints

Hint 1

Consider using a min-heap of size k to keep track of the largest elements encountered so far.

Hint 2

As you iterate through the array, if the current element is larger than the root of the min-heap, replace the root and restore the heap property.

Hint 3

After processing all elements, the min-heap will contain the k largest values; you will then need to sort these k elements in descending order to meet the output requirement.

Follow-up questions

  • How would your approach change if the input array was too large to fit entirely into memory (e.g., a multi-gigabyte file)?
  • What is the time complexity of your solution using a heap, and how does it compare to using a Quickselect-based approach?
  • If the input array was already sorted, how could you optimize your retrieval of the k largest elements?