Two Pointers

Introdução

Two Pointers é uma técnica muito utilizada em questões de leetcode envolvendo estruturas de dados iteráveis. Como o próprio nome sugere, consiste de utilizar 2, ou mais, ponteiros para percorrer a estrutura.

Através dessa técnica, podemos criar algoritmos mais eficientes, escapando muitas vezes de uma time complexity de O(N^2).

Prefix Sum

O principal objetivo da técnica Prefix Sum é permitir você fazer queries de soma em tempo constante.

Por exemplo, imagine o array [0, 1, 2, 3, 4, 5] e eu peço a você para fazer um algoritmo que some todos os elementos desse array.

Você poderia iterar o array, e fazer a soma, resultando em 15, e isso te custaria um tempo de execução O (N).

Imagine, agora, que você precisa saber a soma até o índice 2 do array, do índice 2 até o índice 4, e a soma de todos os elementos do array. Você teria 3 operações O (N). Fica nítido que se você precisa fazer muitas operações de queries de soma você acaba consumindo muito processamento, então o que vamos fazer, é uma troca.

Vamos criar um array que consiste em todas as somas do índice 0 até o índice i, nesse caso:

[0, 1, 3, 6, 10, 15]

Então, se eu quiser saber a soma de todos os elementos até o índice 2, basta eu acessar o índice 2 do array. É claro que criar esse array custa O (N) tanto no tempo de execução, quanto na memória. Mas acessar as somas depois é O (1), reduzindo demasiadamente o tempo de execução de fazer muitas operações. Ou seja, nós fizemos uma troca, trocamos uma parte da memória para termos um algoritmo mais rápido!