Arrays

¿Qué es un array?

Un array es una estructura de datos fundamental que almacena elementos del mismo tipo en posiciones de memoria contiguas. Cada elemento puede accederse directamente usando su índice, lo que hace a los arrays muy eficientes para acceso aleatorio.

Los arrays son la base de muchas otras estructuras de datos y son esenciales para resolver innumerables problemas de programación.

Operaciones de arrays y complejidad temporal

const arr = [10, 20, 30, 40, 50];

// Direct access by index - O(1)
console.log(arr[0]);  // 10
console.log(arr[3]);  // 40

// JavaScript also allows negative indexing (not O(1))
console.log(arr[arr.length - 1]);  // 50 (last element)

// Linear search - O(n)
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;  // Found at index i
    }
  }
  return -1;  // Not found
}

const numbers = [5, 2, 8, 1, 9];
console.log(linearSearch(numbers, 8));  // 2
console.log(linearSearch(numbers, 7));  // -1

// Using built-in methods
console.log(numbers.indexOf(8));     // 2
console.log(numbers.includes(8));    // true
console.log(numbers.find(x => x > 5)); // 8

// Insert at beginning - O(n)
const arr = [2, 3, 4, 5];
arr.unshift(1);  // [1, 2, 3, 4, 5]

// Insert at end - O(1) amortized
arr.push(6);     // [1, 2, 3, 4, 5, 6]

// Insert at specific position - O(n)
function insertAt(arr, index, element) {
  // Shift elements to the right
  for (let i = arr.length; i > index; i--) {
    arr[i] = arr[i - 1];
  }
  arr[index] = element;
  return arr;
}

// Or use splice
arr.splice(2, 0, 99);  // Insert 99 at index 2

// Delete from beginning - O(n)
const arr = [1, 2, 3, 4, 5];
arr.shift();  // [2, 3, 4, 5]

// Delete from end - O(1)
arr.pop();    // [2, 3, 4]

// Delete at specific position - O(n)
function deleteAt(arr, index) {
  // Shift elements to the left
  for (let i = index; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1];
  }
  arr.length--;  // Reduce array size
  return arr;
}

// Or use splice
arr.splice(1, 1);  // Remove 1 element at index 1

Algoritmos comunes de arrays

1. Invertir un array

// Two-pointer approach - O(n) time, O(1) space
function reverseArray(arr) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    // Swap elements
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  
  return arr;
}

const nums = [1, 2, 3, 4, 5];
console.log(reverseArray(nums));  // [5, 4, 3, 2, 1]

// Or use built-in method
nums.reverse();

2. Encontrar máximo/mínimo

// Find max - O(n) time, O(1) space
function findMax(arr) {
  if (arr.length === 0) return null;
  
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

const numbers = [3, 7, 2, 9, 1, 5];
console.log(findMax(numbers));  // 9

// Using built-in methods
console.log(Math.max(...numbers));  // 9
console.log(Math.min(...numbers));  // 1

3. Eliminar duplicados (array ordenado)

// Two-pointer technique - O(n) time, O(1) space
function removeDuplicates(arr) {
  if (arr.length === 0) return 0;
  
  let writeIndex = 1;
  
  for (let readIndex = 1; readIndex < arr.length; readIndex++) {
    if (arr[readIndex] !== arr[readIndex - 1]) {
      arr[writeIndex] = arr[readIndex];
      writeIndex++;
    }
  }
  
  arr.length = writeIndex;  // Trim array
  return writeIndex;
}

const sorted = [1, 1, 2, 2, 2, 3, 4, 4, 5];
const newLength = removeDuplicates(sorted);
console.log(sorted.slice(0, newLength));  // [1, 2, 3, 4, 5]

4. Problema Two Sum

// Find two numbers that add up to target - O(n) time, O(n) space
function twoSum(arr, target) {
  const seen = new Map();
  
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    
    seen.set(arr[i], i);
  }
  
  return null;  // No solution found
}

const nums = [2, 7, 11, 15];
console.log(twoSum(nums, 9));   // [0, 1] (2 + 7 = 9)
console.log(twoSum(nums, 26));  // [2, 3] (11 + 15 = 26)

5. Rotar un array

// Rotate array k positions to the right - O(n) time, O(1) space
function rotateArray(arr, k) {
  k = k % arr.length;  // Handle k > length
  
  // Helper function to reverse portion of array
  function reverse(start, end) {
    while (start < end) {
      [arr[start], arr[end]] = [arr[end], arr[start]];
      start++;
      end--;
    }
  }
  
  // Reverse entire array
  reverse(0, arr.length - 1);
  // Reverse first k elements
  reverse(0, k - 1);
  // Reverse remaining elements
  reverse(k, arr.length - 1);
  
  return arr;
}

const nums = [1, 2, 3, 4, 5, 6, 7];
console.log(rotateArray(nums, 3));  // [5, 6, 7, 1, 2, 3, 4]

6. Máximo en ventana deslizante

// Find maximum in each sliding window of size k
function maxSlidingWindow(arr, k) {
  const result = [];
  const deque = [];  // Store indices
  
  for (let i = 0; i < arr.length; i++) {
    // Remove elements outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Remove smaller elements (they're not useful)
    while (deque.length > 0 && arr[deque[deque.length - 1]] < arr[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add to result once window is full
    if (i >= k - 1) {
      result.push(arr[deque[0]]);
    }
  }
  
  return result;
}

const nums = [1, 3, -1, -3, 5, 3, 6, 7];
console.log(maxSlidingWindow(nums, 3));  // [3, 3, 5, 5, 6, 7]

Métodos de arrays en JavaScript