26. Remove Duplicates from Sorted Array

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description

Definição

$$\begin{align} L = \text{Lista de inteiros ordenada de forma crescente}\\ N = |L| = \text{ Tamanho da lista L}\\ i = \text{Índice do último elemento único da solução parcial}\\ j = \text{Índice do elemento propspecto à último elemento único da solução parcial}\\ \end{align}$$

Intuição

A ideia é encontrar o próximo elemento $L[j]$ que seja diferente do elemento atual $L[i]$. Uma vez que a lista $L$ já está ordernada, é garantido que $L[j] >= L[i]$. Dessa forma, quando $L[i] != L[j]$, aplicamos as seguintes operações:

$$\begin{align} L[i + 1] = L[j]\\ i = i + 1\\ j = j + 1\\ \end{align}$$

Este processo se repete enquanto $j < N$, isto é, enquanto $j$ é um índice válido.

Ilustração

Estado inicial

$i$ e $j$ começam apontando para o primeiro e o segundo elementos, respectivamente. É seguro fazer $j$ apontar para o segundo elemento, mesmo para uma lista de um único elemento, porque a condição de parada é $j < N$. Para listas de tamanho 1, essa condição será quebrada e o algoritmo para porque $1 < 1 == false$.

i

1

1

1

2

2

3

3

j

1ª iteração

$j$ avança tentando encontrar um elemento diferente de $i$

i

1

1

1

2

2

3

3

j

2ª iteração

$j$ avança e agora aponta para um elemento diferente de $i$

i

1

1

1

2

2

3

3

j

Agora copiamos $L[j]$ para $L[i + 1]$ e incrementamos ambos os ponteiros

i

1

2

1

2

2

3

3

j

3ª iteração

$j$ avança e agora aponta para um elemento diferente de $i$

i

1

1

1

2

2

3

3

j

Agora copiamos $L[j]$ para $L[i + 1]$ e incrementamos ambos os ponteiros

i

1

2

3

2

2

3

3

—

j

4ª iteração

Como $j = 7$ e $7 < 7 == false$, o algoritmo termina e retorna o tamanho da lista resultante, neste caso $i + 1 == 3$. Portanto, a resposta final é um array de tamanho 3:

1

2

3

—

—

—

—

Implementação

Clique para revelar a implementação

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        left_index, right_index = 0, 1
        n = len(nums)

        while right_index < n:
            left, right = nums[left_index], nums[right_index]

            if left != right:
                left_index += 1
                nums[left_index] = right
            
            right_index += 1
        
        return left_index + 1

Testes

import pytest
from .solution import Solution

@pytest.mark.parametrize('numbers,expected', [
    ([1, 1, 1, 2, 2, 3, 3], [1, 2, 3])
])
def test_solution(numbers, expected):
    new_size = Solution().removeDuplicates(numbers)
    assert numbers[:new_size] == expected

Complexidade de tempo

Como a lista é iterada por completo da esquerda para a direita através do ponteiro $j$, a complexidade é $O(n)$

Complexidade de espaço

Como a lista é modificada in-place e nenhuma alocação além de variáveis auxiliares é feita, a complexidade é $O(1)$