3940. Limit Occurrences in Sorted Array

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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

Your task is to return an array in which each distinct value appears at most k times, while keeping the relative order of the elements as they appear in nums.

There is an important rule to keep in mind: if a distinct value occurs at least k times in the original array, then it must appear exactly k times in the resulting array. In other words, for any value that shows up k or more times, you keep exactly k copies of it; for any value that shows up fewer than k times, you keep all of its copies.

Since nums is sorted, all equal values are grouped together, which makes it easy to count consecutive duplicates and decide how many of them to keep.

Example:

If nums = [1, 1, 1, 2, 2, 3] and k = 2, the value 1 appears 3 times (at least k), so it is trimmed to exactly 2 copies; the value 2 appears exactly 2 times, so all are kept; the value 3 appears once, so it is kept. The result is [1, 1, 2, 2, 3].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Two pointers?

This problem maps to Two pointers through a short path in the full flowchart.

Two pointers process the array without extra space.

Open in Flowchart

Intuition

The key observation is that the array is already sorted, which means all equal values are placed next to each other in one continuous block. This grouping makes the problem much simpler, because to control how many times a value appears, we only need to count consecutive equal elements as we scan from left to right.

As we walk through the array, we keep a running counter cnt that tells us how many times the current value has appeared so far. Whenever we move to a position where the value is different from the previous one (nums[r] != nums[r - 1]), we have entered a new block, so we reset cnt back to 1. If the value is the same as the previous one, we are still inside the same block, so we increase cnt by 1.

With this counter in hand, the decision becomes straightforward: as long as cnt <= k, we have not yet exceeded the allowed number of copies for this value, so we should keep the element. Once cnt goes beyond k, we simply skip the element and do not write it.

To avoid using extra space, we can build the answer in place by using a second pointer l as a write position. Every time we decide to keep an element, we place it at nums[l] and move l forward by one. This way, the first l positions of the array gradually fill up with exactly the elements we want to retain, and at the end nums[:l] is the final answer. This naturally leads to a two pointers approach: one pointer r reads through the array, and the other pointer l writes the kept elements.

Pattern Learn more about Two Pointers patterns.

Solution Approach

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.

The reason we start l and cnt at 1 is that the very first element nums[0] is always kept (its first occurrence never exceeds k), so it occupies position 0 and counts as the first appearance of its value.

Then we traverse the array starting from r = 1:

If nums[r] != nums[r - 1], we meet a new value, so we reset cnt to 1.
If nums[r] == nums[r - 1], it is a duplicate of the current value, so we increment cnt by 1.

After updating cnt, we check whether cnt <= k. If the occurrence limit is not exceeded, we keep this element by writing nums[r] to nums[l], then move l one step to the right. If cnt > k, we skip the element entirely and leave l unchanged.

Because l always lags behind or equals r, writing nums[r] into nums[l] never overwrites a value we still need to read. This lets us reuse the input array as the output buffer, so no extra space is required.

Finally, we return the first l elements, i.e., nums[:l], which contains exactly the kept elements in their original order.

The time complexity is O(n), where n is the length of the array, since we scan each element once. The space complexity is O(1) if we ignore the space used by the returned answer, because all work is done in place.

Example Walkthrough

Let's trace through a small example to see how the Two Pointers approach works in practice.

Suppose nums = [1, 1, 1, 2, 2, 3] and k = 2.

Initial setup:

l = 1 (write position) — the first element nums[0] = 1 is always kept, so we start writing from index 1.
cnt = 1 — the value 1 has appeared once so far.
We begin scanning from r = 1.

`r`	`nums[r]`	`nums[r-1]`	Same as prev?	`cnt` update	`cnt <= k`?	Action	`l` after	Array state (kept prefix)
1	1	1	Yes	`cnt = 2`	2 ≤ 2 ✅	Write `nums[1]=1` at `l=1`, advance `l`	2	`[1, 1, ...]`
2	1	1	Yes	`cnt = 3`	3 ≤ 2 ❌	Skip	2	`[1, 1, ...]`
3	2	1	No	`cnt = 1`	1 ≤ 2 ✅	Write `nums[3]=2` at `l=2`, advance `l`	3	`[1, 1, 2, ...]`
4	2	2	Yes	`cnt = 2`	2 ≤ 2 ✅	Write `nums[4]=2` at `l=3`, advance `l`	4	`[1, 1, 2, 2, ...]`
5	3	2	No	`cnt = 1`	1 ≤ 2 ✅	Write `nums[5]=3` at `l=4`, advance `l`	5	`[1, 1, 2, 2, 3, ...]`

Final result:

After the scan finishes, l = 5, so we return nums[:5] = [1, 1, 2, 2, 3].

Why this is correct:

The value 1 appeared 3 times (≥ k), so it was trimmed down to exactly 2 copies — the third 1 at r = 2 was skipped because cnt reached 3.
The value 2 appeared exactly 2 times, so both were kept.
The value 3 appeared only once, so it was kept.

Notice how the write pointer l always lags behind the read pointer r, which guarantees that we never overwrite an element before reading it. This is what lets us build the answer in place without extra space.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def limitOccurrences(self, nums: List[int], k: int) -> List[int]:
6        # Total number of elements in the input list
7        n = len(nums)
8
9        # count: how many times the current value has appeared consecutively
10        # write_index: position where the next valid element should be written
11        # Both start at 1 because the first element (index 0) is always kept
12        count = write_index = 1
13
14        # Iterate from the second element to the end
15        for read_index in range(1, n):
16            # If the current element differs from the previous one,
17            # reset the consecutive count to 1
18            if nums[read_index] != nums[read_index - 1]:
19                count = 1
20            # Otherwise, the same value continues, so increment the count
21            else:
22                count += 1
23
24            # Only keep the element if it has appeared at most k times.
25            # This performs an in-place overwrite, compacting valid elements
26            # toward the front of the list.
27            if count <= k:
28                nums[write_index] = nums[read_index]
29                write_index += 1
30
31        # Return the compacted prefix containing only the allowed occurrences
32        return nums[:write_index]
33

1class Solution {
2    /**
3     * Removes excess duplicates so that each distinct value (in a sorted/grouped
4     * array) appears at most k times, then returns the truncated array.
5     *
6     * @param nums the input array (duplicates of the same value are adjacent)
7     * @param k    the maximum allowed occurrences for each value
8     * @return a new array containing the kept elements
9     */
10    public int[] limitOccurrences(int[] nums, int k) {
11        int length = nums.length;
12
13        // count: how many times the current value has appeared so far in its run
14        // writeIndex: next position to write a kept element (also the resulting size)
15        int count = 1;
16        int writeIndex = 1;
17
18        // Iterate from the second element, comparing each with its predecessor.
19        for (int readIndex = 1; readIndex < length; readIndex++) {
20            if (nums[readIndex] != nums[readIndex - 1]) {
21                // A new value begins, so reset the running count.
22                count = 1;
23            } else {
24                // Same value as before, increment its occurrence count.
25                count++;
26            }
27
28            // Keep the element only if it has not exceeded the allowed limit.
29            if (count <= k) {
30                nums[writeIndex] = nums[readIndex];
31                writeIndex++;
32            }
33        }
34
35        // Return only the portion that holds the kept elements.
36        return Arrays.copyOf(nums, writeIndex);
37    }
38}
39

1class Solution {
2public:
3    vector<int> limitOccurrences(vector<int>& nums, int k) {
4        int n = nums.size();
5
6        // Edge case: if the array is shorter than k, every element is allowed to stay.
7        if (n <= k) {
8            return nums;
9        }
10
11        // 'count' tracks how many times the current value has appeared consecutively.
12        // 'slow' is the position where the next valid element should be written.
13        int count = 1;
14        int slow = 1;
15
16        // 'fast' scans through the array starting from the second element.
17        for (int fast = 1; fast < n; ++fast) {
18            // Reset the counter when a new value begins; otherwise increment it.
19            if (nums[fast] != nums[fast - 1]) {
20                count = 1;
21            } else {
22                ++count;
23            }
24
25            // Keep the element only if its occurrence count does not exceed k.
26            if (count <= k) {
27                nums[slow] = nums[fast];
28                ++slow;
29            }
30        }
31
32        // Trim the array to contain only the kept elements.
33        nums.resize(slow);
34        return nums;
35    }
36};
37

1/**
2 * Removes elements so that each unique value appears at most `k` times,
3 * preserving the original relative order. Modifies the input array in place
4 * and returns the truncated result.
5 *
6 * @param nums - The input array of numbers (assumed grouped/sorted by value)
7 * @param k - The maximum allowed occurrences for each value
8 * @returns A new array containing the retained elements
9 */
10function limitOccurrences(nums: number[], k: number): number[] {
11    const length: number = nums.length;
12
13    // Count of consecutive occurrences of the current value.
14    // The first element is always kept, so start the count at 1.
15    let count: number = 1;
16
17    // Write pointer: the position where the next retained element goes.
18    // The first element occupies index 0, so writing starts at index 1.
19    let writeIndex: number = 1;
20
21    // Read pointer: scan through the array starting from the second element.
22    for (let readIndex: number = 1; readIndex < length; readIndex++) {
23        if (nums[readIndex] !== nums[readIndex - 1]) {
24            // Encountered a new value, reset the occurrence counter.
25            count = 1;
26        } else {
27            // Same value as the previous one, increment the counter.
28            count++;
29        }
30
31        // Only keep the element if it has not exceeded the allowed count.
32        if (count <= k) {
33            nums[writeIndex] = nums[readIndex];
34            writeIndex++;
35        }
36    }
37
38    // Return the portion of the array containing only the retained elements.
39    return nums.slice(0, writeIndex);
40}
41

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The algorithm uses a single loop that iterates over the array with the pointer r from index 1 to n - 1. Each iteration performs only constant-time operations (comparisons, assignments, and pointer increments), so the total time is linear in the size of the input.
Space Complexity: O(1). The algorithm modifies the array in place using two pointers (l and r) and a counter (cnt), all of which require only constant extra space. The returned slice nums[:l] reuses the existing array storage rather than allocating new auxiliary space proportional to the input.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Failing to handle the empty array case

The code initializes count = write_index = 1 based on the assumption that nums[0] always exists and is always kept. However, if nums is empty (n == 0), this assumption breaks down.

When nums = []:

The loop range(1, 0) does not execute, so no error occurs there.
But the function returns nums[:1], which evaluates to [] because slicing an empty list yields an empty list.

In this specific case the bug is masked by Python's lenient slicing, so the result happens to be correct. The danger is that the reasoning (write_index starts at 1 because index 0 is kept) is invalid for an empty input, and any small refactor relying on that assumption could break.

Solution: Explicitly guard against the empty array to make the intent clear and the code robust.

from typing import List


class Solution:
    def limitOccurrences(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        # Guard: an empty array has nothing to keep
        if n == 0:
            return []

        count = write_index = 1

        for read_index in range(1, n):
            if nums[read_index] != nums[read_index - 1]:
                count = 1
            else:
                count += 1

            if count <= k:
                nums[write_index] = nums[read_index]
                write_index += 1

        return nums[:write_index]

Pitfall 2: Forgetting the edge case `k = 0`

If k = 0, the rule means no value should appear in the result. However, the code starts with write_index = 1, which unconditionally keeps nums[0]. The first check count <= k becomes 1 <= 0, which is False, so no further elements are written—but nums[0] was already counted as kept via write_index = 1.

For nums = [1, 1, 2] and k = 0, the code returns [1] instead of the expected [].

Solution: Add a guard for k == 0, or restructure the loop so that the first element is also subject to the count <= k check rather than being kept unconditionally.

from typing import List


class Solution:
    def limitOccurrences(self, nums: List[int], k: int) -> List[int]:
        # Guard: when k is 0, nothing may be kept
        if k <= 0:
            return []

        n = len(nums)
        if n == 0:
            return []

        count = write_index = 1

        for read_index in range(1, n):
            if nums[read_index] != nums[read_index - 1]:
                count = 1
            else:
                count += 1

            if count <= k:
                nums[write_index] = nums[read_index]
                write_index += 1

        return nums[:write_index]

Pitfall 3: Misreading the requirement and using `cnt < k` instead of `cnt <= k`

A subtle off-by-one mistake is writing the condition as count < k. This would keep at most k - 1 copies of each value rather than k. For nums = [1, 1, 1] and k = 2, the buggy condition count < 2 would keep only [1] instead of the correct [1, 1].

Solution: Always use count <= k so that exactly k occurrences are retained when a value appears k or more times, matching the problem's "exactly k" requirement.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: