limit-occurrences-in-sorted-array

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a sorted integer array <code>nums</code> and an integer <code>k</code>.

Return an array such that each distinct element appears at most <code>k</code> times, while preserving the relative order of the elements in <code>nums</code>.

Note: If a distinct element appears at least <code>k</code> times, then it must appear exactly <code>k</code> times in the resulting array.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,1,2,2,3]

Explanation:

Each element can appear at most 2 times.

<ul>
	<li>The element 1 appears 3 times, so only 2 occurrences are kept.</li>
	<li>The element 2 appears 2 times, so both occurrences are kept.</li>
	<li>The element 3 appears 1 time, so it is kept.</li>
</ul>

Thus, the resulting array is <code>[1, 1, 2, 2, 3]</code>.
</div>

Example 2:

<div class="example-block">
Input: nums = [1,2,3], k = 1

Output: [1,2,3]

Explanation:

All elements are distinct and already appear at most once, so the array remains unchanged.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
	<li><code>nums</code> is sorted in non-decreasing order.</li>
	<li><code>1 &lt;= k &lt;= nums.length</code></li>
</ul>

&nbsp;
Follow-up:

<ul>
	<li>Can you solve this in-place using O(1) extra space?</li>
	<li>Note that the space used for returning or resizing the result does not count toward the space complexity mentioned above, as some languages do not support in-place resizing.</li>
</ul>