FastPrep
Problem · Array

Keep at Most K Occurrences in a Sorted Array

Learn this problem
● MediumOracle logoOracleFULLTIMEONSITE INTERVIEW

Problem statement

You are given an integer array nums sorted in nondecreasing order and a nonnegative integer k. Compact nums in place so that every distinct value appears at most k times while preserving sorted order.

Return an array containing exactly the compacted prefix. The compaction must use O(1) auxiliary space; the returned array used to expose that prefix to the judge is not counted as auxiliary workspace. If k is 0, return an empty array.

Function

keepAtMostK(nums: int[], k: int) → int[]

Examples

Example 1

nums = [1,1,1,2,2,3]k = 2return = [1,1,2,2,3]

The third 1 is removed; every other occurrence fits within the limit of two.

Example 2

nums = [0,0,0,1,1,1]k = 1return = [0,1]

Only the first occurrence of each distinct value remains.

Example 3

nums = [-2,-2,3]k = 0return = []

A zero occurrence limit removes every value.

Constraints

  • 0 <= nums.length <= 100000
  • -1000000000 <= nums[i] <= 1000000000
  • 0 <= k <= nums.length when nums is non-empty.
  • k = 0 when nums is empty.
  • nums is sorted in nondecreasing order.

More Oracle problems

drafts saved locally
public int[] keepAtMostK(int[] nums, int k) {
  // write your code here
}
nums[1,1,1,2,2,3]
k2
expected[1,1,2,2,3]
checking account