Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• TypeScript

• 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);
      }
  }
  

• 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;
      }
  };
  

• 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]
  
  

• 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]
  }
  

• 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);
  }
  
  

All Problems

All Solutions