Technical Interview Question

Implement a function removeDuplicates that takes in a sorted array of integers and removes duplicates in-place. The function should return the length of the updated array. You don't need to worry about the elements beyond the returned length.

For example:

arr = [1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6]
removeDuplicates(arr)

Output:

6

Note:

• The input array is sorted in non-decreasing order.
• The elements of the array should be modified in-place.

Answer

The problem can be solved using the Two Pointers technique. We will maintain two pointers, i and j, representing the current index and the index of the next unique element, respectively.

1. Initialize i = 0 and j = 1.
2. Iterate through the array until j reaches the end.
3. If the element at index i is equal to the element at index j, increment j to move to the next element.
4. If the element at index i is not equal to the element at index j, update the value at index i+1 with the value at index j and increment both i and j.
5. Repeat steps 3 and 4 until j reaches the end of the array.
6. The final length of the array will be i + 1. Return this length.

Let's implement this in code:

def removeDuplicates(arr):
    if len(arr) == 0:
        return 0

    i = 0
    for j in range(1, len(arr)):
        if arr[i] != arr[j]:
            i += 1
            arr[i] = arr[j]

    return i + 1

This solution has a time complexity of O(n), where n is the length of the input array, because we need to iterate through the array once. The space complexity is O(1), as we are modifying the input array in-place and not using any extra space proportional to the input size.