Keep At Most K Copies in a Sorted Array

Question

This question asks the candidate to implement a function that modifies a sorted array so that it contains at most K copies of each unique element.

Codemia · Accepted Answer

To solve this problem, we can use a two-pointer technique. The idea is to maintain a pointer for the current position in the array and another pointer to track the number of occurrences of each element. We will iterate through the array and copy elements to the front while ensuring that we do not exceed K copies of any element.

1. Initialize a pointer `i` to 0 to track the position in the modified array.
2. Use a variable `count` to keep track of the occurrences of the current element.
3. Loop through the array with a pointer `j`:
   - If the current element is the same as the previous one, increment `count`.
   - If `count` is less than or equal to K, copy the element to the position `i` and increment `i`.
   - If the current element is different, reset `count` to 1 and copy the element.
4. Finally, return the length of the modified array.

The time complexity of this algorithm is O(n) since we are iterating through the array once. The space complexity is O(1) because we are modifying the array in place and not using any additional data structures.

```python
def remove_duplicates(nums, k):
    if not nums:
        return 0
    i = 0
    count = 1
    for j in range(1, len(nums)):
        if nums[j] == nums[j - 1]:
            count += 1
        else:
            count = 1
        if count <= k:
            nums[i] = nums[j]
            i += 1
    return i
```

Interviewers are looking for clarity in your explanation, your ability to handle edge cases, and your understanding of time and space complexity. They also want to see how well you can write clean and efficient code, and how you approach problem-solving in a structured manner.

Keep At Most K Copies in a Sorted Array

Oracle

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Oracle Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string