Top K Largest Values with Constant Auxiliary Space
Updated
Problem statement
You are given an integer array nums and an integer k. Return the k largest values from largest to smallest, so each value is no larger than the one before it. Repeated values count separately, so equal values can both appear in the answer.
You may rearrange nums. Use only O(1) extra working space. The returned array of exactly k values does not count toward that space. If k=0, return an empty array.
Function
topKLargest(nums: int[], k: int) → int[]Examples
Example 1
nums = [3,1,5,5,2]k = 3return = [5,5,3]The three largest values are 5, 5 and 3. Both fives count, because repeated values are kept.
Example 2
nums = [-4,-2,-9]k = 2return = [-2,-4]The largest value is -2 and the next one is -4. The smallest value is left out.
Constraints
0 <= nums.length <= 2000-1000000 <= nums[i] <= 10000000 <= k <= nums.length
More BAMTECH Media Phone Screen questions
Similar questions at other companies
- Merge Three Sorted ArraysMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Top K TradesJane Street · PHONE SCREENJane Street interview questions
- Merge Three Sorted ArraysSambaNova Systems · PHONE SCREENSambaNova Systems interview questions
- Top K Frequent ElementsAmazon · OA · PHONE SCREEN
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
- Meeting Rooms IIeBay · PHONE SCREENeBay interview questions
- Median Across Sorted ArraysGoogle · PHONE SCREENGoogle interview questions
- Select the Top User MatchesDuolingo · PHONE SCREENDuolingo interview questions
- Meeting Rooms IIQuince · PHONE SCREENQuince interview questions