Limit Occurrences in Sorted Array - Video Solutions

Problem Overview: You are given a sorted array and must ensure each distinct value appears no more than k times. Extra duplicates should be removed in-place while preserving the original order. The task typically returns the new valid length of the array after limiting occurrences.

Approach 1: Brute Force Shifting (O(n^2) time, O(1) space)

The simplest idea is to scan the array and count how many times the current number appears consecutively. When the count exceeds the allowed limit k, shift all remaining elements one position left to overwrite the extra occurrence. This approach works because the array is already sorted, so duplicates appear next to each other. However, repeated shifting creates a quadratic worst-case cost when many elements must be moved multiple times. This method demonstrates the core constraint but is rarely acceptable in interviews for large inputs.

Approach 2: Counting with Overwrite Pointer (O(n) time, O(1) space)

Instead of shifting elements repeatedly, maintain a write index that marks where the next valid value should go. Iterate through the array while counting occurrences of the current number. If the count is less than or equal to k, copy the element to the write position and advance it. If the count exceeds k, simply skip the element. Because each element is processed once and written at most once, the algorithm runs in linear time. This method uses basic arrays manipulation and avoids unnecessary data movement.

Approach 3: Two Pointers with Window Check (O(n) time, O(1) space)

The cleanest solution uses the two pointers technique. Maintain a slow pointer that tracks the position for the next valid element and iterate a fast pointer through the array. For each value, check whether placing it would violate the allowed occurrence limit. This can be done by comparing the current value with the element k positions before the slow pointer. If they differ, the value is valid and written at the slow index; otherwise it is skipped. Because the array is sorted, this comparison guarantees that no element appears more than k times in the result.

This two-pointer strategy performs a single linear pass and modifies the array in place. No auxiliary data structures are needed, which keeps the space complexity constant. The pattern appears frequently in sorted-array problems involving duplicate removal or compaction.

Recommended for interviews: The two-pointer approach is the expected solution. Interviewers want to see that you recognize how sorted order enables constant-time duplicate checks without additional memory. Mentioning the brute-force shifting method shows baseline reasoning, but implementing the linear-time two-pointer technique demonstrates familiarity with common array patterns and in-place optimization.