Frontend School

Find K Largest Elements

DSA
easy

Find K Largest Elements

Easy
Arrays
Heap
Priority Queue

Overview

In many data processing scenarios, identifying the most significant data points is crucial. Whether it's tracking top-performing metrics, detecting critical system alerts, or analyzing trending topics, efficiently extracting the 'largest' or 'most important' items from a vast dataset is a common requirement. This problem simulates a core task in such systems: finding the k largest numerical values from a given collection.

What you need to do / Task

You are tasked with implementing a function findKLargestElements that takes an array of integers nums and an integer k. Your function should return an array containing the k largest elements from nums. If there are duplicate values, they should be included if they fall within the top k largest values.

Input & output

  • Input:
    • nums: An array of integers representing the dataset.
    • k: An integer representing the number of largest elements to find.
  • Output: An array of k integers, which are the k largest elements from nums.

Clarifications

  • Order of output: The order of elements in the returned array does not matter.
  • Duplicates: If nums contains duplicate values, they should be treated as individual elements. For example, if nums = [5, 5, 2] and k = 2, the output should be [5, 5] (order agnostic).
  • k vs. nums.length: You can assume k will always be a valid positive integer and 1 <= k <= nums.length.

Examples

1

Example 1

Input:

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

Output:

[5,6]

Note:

The 2 largest elements in [3,2,1,5,6,4] are 5 and 6. The order of elements in the output array does not matter.

2

Example 2

Input:

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

Output:

[3,5,5,6]

Note:

The 4 largest elements are 6, 5, 5, and 4. The output can be [6,5,5,4] or any permutation thereof.

3

Example 3

Input:

nums = [7,8,9,1,2], k = 3

Output:

[7,8,9]

Note:

The 3 largest elements are 7, 8, and 9. The output can be [9,8,7] or any permutation thereof.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 1 <= k <= nums.length
  • Your solution should aim for optimal time and space complexity.

Out of scope

  • Handling non-integer inputs or inputs that are not arrays.
  • Validating k if it falls outside the specified constraints (e.g., k=0 or k > nums.length). Assume valid k.

What interviewers evaluate

  • Correctness: The solution must accurately identify and return the k largest elements.
  • Efficiency: The solution should demonstrate an understanding of data structures to achieve optimal time complexity (e.g., O(N log K)) and space complexity (e.g., O(K)).
  • Code Quality: The code should be clean, readable, well-structured, and easy to understand.

Loading editor...