Data structures & algorithms3 min

Arrays & Strings

An Array is the most fundamental data structure. It is a collection of items stored at contiguous (adjacent) memory locations. The idea is to store multiple items of the same type together, allowing for incredibly fast access if you know the item's index.

Strings are usually implemented as an array of characters under the hood, so they share almost identical memory layouts and algorithmic properties.

Memory Layout

Because arrays are stored in contiguous memory blocks, the computer knows exactly where every element is. If the array starts at memory address 1000, and each integer takes 4 bytes, then index 2 is mathematically calculated instantly: 1000 + (2 * 4) = 1008.

Static vs Dynamic Arrays

Static Arrays

In languages like C or Java, arrays have a fixed size. When you declare int[] arr = new int[5], the computer allocates exactly enough memory for 5 integers. You cannot add a 6th integer. To resize, you must create a brand new array and copy all the elements over.

Dynamic Arrays

In modern languages (like Python list, JavaScript/TypeScript [], Java ArrayList, C++ std::vector), arrays resize automatically.

How Dynamic Arrays Work Under the Hood:

The computer allocates an underlying static array of a certain capacity (e.g., size 4).
You push elements into it.
When the capacity is reached, the computer allocates a new static array with double the capacity (size 8).
It copies the old elements into the new array and deletes the old one.

Because doubling is rare, the amortized time complexity for pushing to a dynamic array is $O(1)$.

Time Complexity

Operation	Time Complexity	Explanation
Access `arr[i]`	$O(1)$	Direct memory address calculation.
Search (Unsorted)	$O(N)$	Must check every element one by one.
Insert at End	$O(1)$	*Amortized $O(1)$ for dynamic arrays.
Insert at Index `i`	$O(N)$	Must shift all subsequent elements one position to the right to make room.
Delete at Index `i`	$O(N)$	Must shift all subsequent elements one position to the left to fill the gap.

Common Array Patterns

1. Two Pointers

Used to search for pairs in sorted arrays, or reverse strings in-place. You start one pointer at the beginning and one at the end, moving them towards each other.

typescript

function reverseString(s: string[]): void {
  let left = 0;
  let right = s.length - 1;
  
  while (left < right) {
    // Swap characters
    const temp = s[left];
    s[left] = s[right];
    s[right] = temp;
    
    left++;
    right--;
  }
}

2. Sliding Window

Used for finding subarrays (like the max sum of a contiguous subarray of size K). Instead of recalculating the entire window from scratch, you subtract the element falling out of the window and add the new element entering it.

typescript

// Find max sum of contiguous subarray of size K
function maxSumSubarray(arr: number[], k: number): number {
  let maxSum = 0;
  let windowSum = 0;
  
  // Calculate first window
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;
  
  // Slide the window
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // Add new, subtract old
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum;
}