Skip to content

3940. Limit Occurrences in Sorted Array

Description

You are given a sorted integer array nums and an integer k.

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

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

 

Example 1:

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.

  • The element 1 appears 3 times, so only 2 occurrences are kept.
  • The element 2 appears 2 times, so both occurrences are kept.
  • The element 3 appears 1 time, so it is kept.

Thus, the resulting array is [1, 1, 2, 2, 3].

Example 2:

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.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • nums is sorted in non-decreasing order.
  • 1 <= k <= nums.length

 

Follow-up:

  • Can you solve this in-place using O(1) extra space?
  • 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.

Solutions

Solution 1: Two Pointers

Thinking

The array is already sorted, so equal values form runs. Each run must be clipped to length \(k\) and written back as a prefix.

A slow pointer \(l\) marks the next write, a fast pointer \(r\) scans. A value change resets the counter to \(1\), otherwise it grows; a write happens only while the counter is at most \(k\).

\(n\le 100\), so one linear scan is enough.

We define two pointers, \(l\) and \(r\), where \(l\) is the write position and \(r\) is the current read position. We also use a counter \(cnt\) to record how many times the current value has appeared. Initially, both \(l\) and \(cnt\) are set to 1.

Then we traverse the array starting from \(r = 1\):

  1. If \(nums[r] \ne nums[r - 1]\), we meet a new value, so reset \(cnt\) to 1.
  2. If \(nums[r] = nums[r - 1]\), it is a duplicate, so increment \(cnt\) by 1.

If \(cnt \le k\), the occurrence limit is not exceeded, so we keep this element by writing \(nums[r]\) to \(nums[l]\), then move \(l\) one step to the right.

Finally, return the first \(l\) elements, i.e., \(nums[:l]\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\), since only constant extra space is used.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def limitOccurrences(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        cnt = l = 1
        for r in range(1, n):
            if nums[r] != nums[r - 1]:
                cnt = 1
            else:
                cnt += 1
            if cnt <= k:
                nums[l] = nums[r]
                l += 1
        return nums[:l]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] limitOccurrences(int[] nums, int k) {
        int n = nums.length;
        int cnt = 1, l = 1;

        for (int r = 1; r < n; r++) {
            if (nums[r] != nums[r - 1]) {
                cnt = 1;
            } else {
                cnt++;
            }

            if (cnt <= k) {
                nums[l] = nums[r];
                l++;
            }
        }

        return Arrays.copyOf(nums, l);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> limitOccurrences(vector<int>& nums, int k) {
        int n = nums.size();
        int cnt = 1, l = 1;

        for (int r = 1; r < n; r++) {
            if (nums[r] != nums[r - 1]) {
                cnt = 1;
            } else {
                cnt++;
            }

            if (cnt <= k) {
                nums[l] = nums[r];
                l++;
            }
        }

        nums.resize(l);
        return nums;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func limitOccurrences(nums []int, k int) []int {
    n := len(nums)
    cnt, l := 1, 1

    for r := 1; r < n; r++ {
        if nums[r] != nums[r-1] {
            cnt = 1
        } else {
            cnt++
        }

        if cnt <= k {
            nums[l] = nums[r]
            l++
        }
    }

    return nums[:l]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function limitOccurrences(nums: number[], k: number): number[] {
    const n = nums.length;
    let cnt = 1;
    let l = 1;

    for (let r = 1; r < n; r++) {
        if (nums[r] !== nums[r - 1]) {
            cnt = 1;
        } else {
            cnt++;
        }

        if (cnt <= k) {
            nums[l] = nums[r];
            l++;
        }
    }

    return nums.slice(0, l);
}

Comments