Dada uma array [1,2,3,4,5,6,7] e k = 3, a rotação de 3 passos resultaria em [5,6,7,1,2,3,4]

Abordagens de Solução

Abordagem 1: Remover elementos do final e inserir no início

Iremos remover os últimos k elementos e adicioná-los um por um no início da array

Aobrdagem 2: Dividir e combinar

Separar a array em duas partes e combiná-las em ordem invertida

Implementações em Código

Abodragem 1: Usando pop e unshift

/**
 * Rotaciona uma array por k passos utilizando pop e unshift
 * @param array A array original
 * @param k Número de passos de rotação
 * @returns A array rotacionada
 */
export function rotacionarMetodo1(array: number[], k: number): number[] {
    const tamanho = array.length;
    if (!k || tamanho === 0) {
        return array;
    }
    
    // Tratando casos onde k é negativo ou maior que o tamanho da array
    const passos = Math.abs(k % tamanho);
    
    // Complexidade de tempo: O(n²) devido ao unshift dentro do loop
    // Complexidade de espaço: O(1)
    for (let i = 0; i < passos; i++) {
        const elemento = array.pop();
        if (elemento !== undefined) {
            array.unshift(elemento); // unshift tem complexidade O(n)
        }
    }
    
    return array;
}

Abordagem 2: Usando slice e concat

/**
 * Rotaciona uma array por k passos utilizando slice e concat
 * @param array A array original
 * @param k Número de passos de rotação
 * @returns A array rotacionada
 */
export function rotacionarMetodo2(array: number[], k: number): number[] {
    const tamanho = array.length;
    if (!k || tamanho === 0) {
        return array;
    }
    
    const passos = Math.abs(k % tamanho);
    // Complexidade de tempo: O(n)
    // Complexidade de espaço: O(n)
    const parteFinal = array.slice(-passos); // Últimos k elementos
    const parteInicial = array.slice(0, tamanho - passos); // Elementos restantes
    const resultado = parteFinal.concat(parteInicial);
    
    return resultado;
}

Análise de Complexidade

Complexidade de Tempo

• Abordagem 1: O(n²) - Embora haja apenas um loop, cada operação unshift tem complexidade O(n)
• Abordagem 2: O(n) - As operações slice e concat são lineares

Complexidade de Espaço

• Abordagem 1: O(1) - Modifica a array original sem criar estruturas adicionais
• Abordagem 2: O(n) - Cria novas arrays durante o processo

Testes de Desempenho

Código de Teste

import { rotacionarMetodo1, rotacionarMetodo2 } from './array-rotate';

const arrayTeste = [];
for (let i = 0; i < 100000; i++) {
    arrayTeste.push(i);
}

console.time('rotacionarMetodo1');
rotacionarMetodo1(arrayTeste, 90000);
console.timeEnd('rotacionarMetodo1'); // ~546ms

console.time('rotacionarMetodo2');
rotacionarMetodo2(arrayTeste, 90000);
console.timeEnd('rotacionarMetodo2'); // ~1ms

Resultado

Os testes demonstram que a Abordagem 2 é significativamente mais rápida que a Abordagem 1 para arrays grandes.