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

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