Задача Remove Duplicates from Sorted Array

Уровень: easy

Итак, задачка следующая: дан отсортированный массив чисел (по возрастанию), в котором нужно удалить дубликаты, и вернуть количество чисел, которые останутся в исходном массиве.

Пример:
Исходный массив: [1,1,2,3,4,4,5,6,6]
Ответ: 6, массив на выходе - [1,2,3,4,5,6,_,_,_] (последние 3 элемента тоже будут заполнены, но этот кусок массива нас уже не интересует)

Ограничения:
1. Длина массива от 1 до 3 * 10^4
2. Значения элементов массива от -100 до 100
3. Массив отсортирован по возрастанию

Ссылочка на задачу, как всегда

Подход к решению:
Нам нужно будет обойти весь массив и сравнивать последний уникальный элемент с текущим. Если они не равны, то значит найден новый уникальный элемент, его значение записывается в текущее значение массива, а индекс последнего уникального элемента увеличивается на 1. По завершению алгоритма мы вернем значение индекса, увеличенного на 1.

Итак, код (пройдемся по шагам по нему)

public int removeDuplicates(int[] nums) {
    int index = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[index] != nums[i]) {
            index++;
            nums[index] = nums[i];
        }
    }
    return index + 1;
}

1. Инициализация переменной index, которая указывает на последний уникальный элемент нашего массива.
2. Цикл, с помощью которого мы будем обходить все элементы массива
3. Сравнение элементов внутри цикла: сравниваем текущий элемент с последним уникальным
4. Если последний уникальный элемент не равен текущему (nums[index] != nums[i]), значит найден новый уникальный элемент.
5. Если обнаружен новый уникальный элемент, то происходит обновление переменной index на 1, и этот новый элемент (nums[i]) записывается в позицию nums[index].
6. По завершению цикла возвращается значение, соответствующее кол-ву уникальных элементов в массиве, т.е. значение index увеличенное на 1 (т.к. длина массива на 1 больше, чем индекс последнего уникального элемента)

Временная сложность алгоритма составит O(n), т.к. придется пройтись по всем элементам массива
Пространственная сложность составит O(1), т.к. будет выделено ограниченное кол-во памяти под переменные index и i, которые не зависят от размера входного массива.