LeetCode Problem 3940

Difficulty: 🟢 Easy
Topics: —

Solution

LeetCode 3940 - Limit Occurrences in Sorted Array

Problem Understanding

This problem gives us a sorted integer array nums and an integer k. Our goal is to produce a result where every distinct value appears no more than k times.

Because the array is already sorted in non-decreasing order, all occurrences of the same value appear consecutively. This property is extremely important because it allows us to process duplicates as we scan the array from left to right.

The requirement is slightly stronger than simply removing extra duplicates. If an element appears at least k times, then exactly k copies must remain in the final array. If it appears fewer than k times, all occurrences must remain.

For example, if k = 2 and a value appears five times, we keep exactly the first two occurrences and discard the remaining three. If a value appears once, we keep that single occurrence.

The input consists of:

• A sorted integer array nums
• An integer k

The output is:

• An array containing the same values in the same relative order
• Each distinct value appearing at most k times

The constraints are small:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• nums is sorted
• 1 <= k <= nums.length

Although the constraints are small enough for many solutions to pass, the follow-up asks for an in-place solution using constant extra space, which suggests that we should think about a more efficient approach.

Important edge cases include arrays with no duplicates, arrays where every element is identical, situations where k = 1, and situations where k is larger than or equal to every frequency in the array. The problem guarantees that the input array is sorted, which greatly simplifies duplicate handling.

Approaches

Brute Force Approach

A straightforward solution is to count how many times each value has already been added to the result.

Since the array is sorted, we can iterate through nums, track the current value and its frequency, and append values to a separate result array only while the count does not exceed k.

This approach is correct because every element is processed exactly once, and we explicitly enforce the frequency limit before adding an element to the output.

Although this solution is already efficient for the given constraints, it requires constructing a separate result array, which uses additional memory proportional to the output size.

Key Insight

The crucial observation is that the array is sorted.

Because equal values appear consecutively, we only need to know how many copies of the current value have already been kept. We do not need a hash map or any global frequency tracking.

An even better observation enables an in-place solution. Suppose we have already built a valid prefix of the answer. When processing a new element, we only need to determine whether adding it would create more than k occurrences of the same value.

If the current write position is less than k, the element is always valid because we have not yet written enough elements to violate the limit.

Otherwise, we compare the current value with the element located k positions before the write position. If they are different, adding the current value cannot create more than k occurrences. If they are the same, we already have k copies of that value in the result, so the current element must be skipped.

This gives an elegant one-pass, constant-space solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Builds a separate result array
Optimal	O(n)	O(1)	Uses two pointers and modifies the array in place

Algorithm Walkthrough

1. Initialize a write pointer write = 0. This pointer represents the length of the valid result constructed so far.
2. Iterate through every value in nums from left to right.
3. If write < k, write the current value into position write and increment write. The first k elements can always be kept because no value can yet exceed the allowed frequency.
4. Otherwise, compare the current value with nums[write - k].
5. If the two values are different, write the current value into position write and increment write. This means fewer than k copies of the current value have been kept so far.
6. If the two values are the same, skip the current value because keeping it would create more than k occurrences.
7. After processing all elements, return the prefix nums[:write], which contains the valid result.

Why it works

The invariant is that the first write positions always contain a valid answer for all elements processed so far.

When write >= k, the element at position write - k represents the earliest element among the last k kept elements. If this element equals the current value, then exactly k copies of that value already exist in the result, so another copy would violate the limit. If it differs, then fewer than k copies have been kept, so the current value may safely be added.

Because every element is processed once and the invariant is maintained throughout the scan, the final prefix is a correct solution.

Python Solution

class Solution:
    def limitOccurrences(self, nums: list[int], k: int) -> list[int]:
        write = 0

        for value in nums:
            if write < k or value != nums[write - k]:
                nums[write] = value
                write += 1

        return nums[:write]

The implementation uses the array itself as storage for the answer. The variable write tracks the next position where a valid element should be placed.

As we iterate through each value, we decide whether that value can be kept. The condition write < k guarantees that the first k elements are accepted. After that point, we compare the current value with nums[write - k].

If the values differ, fewer than k copies of the current value have been retained, so we write it into the result region. If the values are equal, the limit has already been reached and the element is skipped.

At the end, the valid answer occupies the prefix nums[:write], which is returned.

Go Solution

func limitOccurrences(nums []int, k int) []int {
    write := 0

    for _, value := range nums {
        if write < k || value != nums[write-k] {
            nums[write] = value
            write++
        }
    }

    return nums[:write]
}

The Go implementation follows exactly the same logic as the Python version.

The primary language-specific detail is that Go returns a slice representing the valid prefix of the original array. Since slices are views into an underlying array, nums[:write] efficiently represents the answer without allocating another array unless required by the runtime.

Integer overflow is not a concern because the constraints are very small. The input length is at most 100, so all index calculations are safe.

Worked Examples

Example 1

Input:

nums = [1,1,1,2,2,3]
k = 2

Current Value	write Before	Comparison	Keep?	Array Prefix
1	0	write < k	Yes	[1]
1	1	write < k	Yes	[1,1]
1	2	nums[0] = 1	No	[1,1]
2	2	nums[0] = 1	Yes	[1,1,2]
2	3	nums[1] = 1	Yes	[1,1,2,2]
3	4	nums[2] = 2	Yes	[1,1,2,2,3]

Final result:

[1,1,2,2,3]

Example 2

Input:

nums = [1,2,3]
k = 1

Current Value	write Before	Comparison	Keep?	Array Prefix
1	0	write < k	Yes	[1]
2	1	nums[0] = 1	Yes	[1,2]
3	2	nums[1] = 2	Yes	[1,2,3]

Final result:

[1,2,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only the write pointer is used, excluding the returned result

The algorithm performs a single linear scan through the array. Every iteration executes a constant amount of work, resulting in O(n) time complexity.

The solution modifies the input array directly and only stores a few variables, so the auxiliary space complexity is O(1).

Test Cases

sol = Solution()

assert sol.limitOccurrences([1, 1, 1, 2, 2, 3], 2) == [1, 1, 2, 2, 3]  # provided example
assert sol.limitOccurrences([1, 2, 3], 1) == [1, 2, 3]  # already unique

assert sol.limitOccurrences([5], 1) == [5]  # single element
assert sol.limitOccurrences([1, 1, 1, 1], 1) == [1]  # keep only one copy
assert sol.limitOccurrences([1, 1, 1, 1], 2) == [1, 1]  # keep exactly k copies
assert sol.limitOccurrences([1, 1, 1, 1], 4) == [1, 1, 1, 1]  # frequency equals k

assert sol.limitOccurrences([1, 1, 2, 2, 3, 3], 2) == [1, 1, 2, 2, 3, 3]  # all frequencies already valid
assert sol.limitOccurrences([1, 1, 1, 2, 2, 2, 3, 3, 3], 2) == [1, 1, 2, 2, 3, 3]  # trim every group
assert sol.limitOccurrences([1, 1, 1, 2, 3, 4], 2) == [1, 1, 2, 3, 4]  # only first group trimmed

assert sol.limitOccurrences([1, 2, 2, 2, 3], 3) == [1, 2, 2, 2, 3]  # k larger than most frequencies
assert sol.limitOccurrences([7, 7, 7, 7, 7], 3) == [7, 7, 7]  # many duplicates
assert sol.limitOccurrences([1, 1, 2, 3, 3, 3, 4, 4], 1) == [1, 2, 3, 4]  # deduplication case

Test Summary

Test	Why
[1,1,1,2,2,3], k=2	Official example with trimming
[1,2,3], k=1	Already valid array
[5], k=1	Minimum length input
[1,1,1,1], k=1	Strong duplicate reduction
[1,1,1,1], k=2	Keep exactly k occurrences
[1,1,1,1], k=4	Frequency equals limit
[1,1,2,2,3,3], k=2	No modifications needed
[1,1,1,2,2,2,3,3,3], k=2	Multiple groups trimmed
[1,1,1,2,3,4], k=2	Only one group exceeds limit
[1,2,2,2,3], k=3	Larger k value
[7,7,7,7,7], k=3	Single repeated value
[1,1,2,3,3,3,4,4], k=1	Deduplication scenario

Edge Cases

All Elements Are Identical

An array such as [5,5,5,5,5] can easily expose mistakes in duplicate handling. A naive implementation might accidentally keep too many copies or remove too many. The two-pointer solution correctly keeps only the first k occurrences because every later occurrence matches nums[write - k] and is therefore skipped.

k Equals 1

When k = 1, the problem becomes equivalent to removing all duplicates and keeping only one occurrence of each value. Some implementations may require special-case logic, but this algorithm handles it naturally. The comparison with nums[write - 1] ensures that only the first occurrence of each distinct value is retained.

No Frequency Exceeds k

Consider an input such as [1,1,2,2,3,3] with k = 2. In this situation, no values should be removed. The algorithm correctly accepts every element because the comparison never detects more than k occurrences of the same value.

k Equals the Array Length

If k is equal to nums.length, no value can possibly exceed the limit. The condition write < k remains true for the entire scan, causing every element to be retained. The original array is returned unchanged.

Very Small Arrays

Arrays containing only one element or very few elements can sometimes cause index-related bugs. The condition write < k guarantees that the expression nums[write - k] is never evaluated until it is safe, preventing out-of-bounds access.