Arrays

What is an Array?

An array is a fundamental data structure that stores elements of the same type in contiguous memory locations. Each element can be accessed directly using its index, making arrays one of the most efficient data structures for random access operations.

Arrays are the building blocks of many other data structures and are essential for solving countless programming problems.

Array Operations & Time Complexity

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

Common Array Algorithms

1. Reverse an 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. Find Maximum/Minimum

// 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. Remove Duplicates (Sorted Array)

// 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. Two Sum Problem

// 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. Rotate 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. Sliding Window Maximum

// 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]

JavaScript Array Methods