Arrays — Theory & Patterns

Arrays are the most fundamental data structure in programming. Nearly 40% of all DSA interview questions involve arrays in some form. Master these patterns, and you'll breeze through them.

What is an Array?

An array is a contiguous block of memory that stores elements of the same type, accessed by index.

const nums = [10, 20, 30, 40, 50];
// Index:      0   1   2   3   4

console.log(nums[2]); // 30 — O(1) access

Time Complexities

6 Patterns You Must Know

1. Two Pointer

Use when the array is sorted or you need to find pairs/triplets.

// Find pair that sums to target in sorted array
function twoSumSorted(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }
  return [-1, -1];
}

When to use: Sorted array, finding pairs, removing duplicates in-place, palindrome checks.

2. Sliding Window

Use when you need to find a subarray that satisfies a condition.

// Maximum sum of subarray of size k
function maxSubarraySum(nums, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i];

  let maxSum = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

When to use: Fixed/variable window, contiguous subarray problems, string substring problems.

3. Hash Map for O(1) Lookup

Use when you need to check if an element exists or count frequencies.

// Two Sum — unsorted array
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) return [map.get(complement), i];
    map.set(nums[i], i);
  }
  return [-1, -1];
}

When to use: Finding complements, counting frequencies, detecting duplicates.

4. Prefix Sum

Pre-compute cumulative sums to answer range queries in O(1).

// Build prefix sum
function buildPrefixSum(nums) {
  const prefix = [0];
  for (const num of nums) {
    prefix.push(prefix[prefix.length - 1] + num);
  }
  return prefix;
}

// Sum of elements from index l to r
function rangeSum(prefix, l, r) {
  return prefix[r + 1] - prefix[l];
}

When to use: Range sum queries, subarray sum equals K, equilibrium index.

5. Kadane's Algorithm

Find the maximum subarray sum in O(n).

function maxSubArray(nums) {
  let current = nums[0], best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

When to use: Maximum/minimum subarray sum, maximum product subarray.

6. Sort + Greedy

Sometimes sorting first simplifies the problem dramatically.

// Find if any two elements differ by at most 1
function containsNearbyDuplicate(nums) {
  nums.sort((a, b) => a - b);
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] - nums[i - 1] <= 1) return true;
  }
  return false;
}

When to use: Meeting rooms, merge intervals, finding closest pairs.

JavaScript Array Methods Cheat Sheet

// Essential methods for DSA
arr.push(x)         // Add to end — O(1)
arr.pop()           // Remove from end — O(1)
arr.shift()         // Remove from start — O(n)
arr.unshift(x)      // Add to start — O(n)
arr.slice(l, r)     // Copy subarray [l, r) — O(r-l)
arr.splice(i, 1)    // Remove at index — O(n)
arr.indexOf(x)      // Find index — O(n)
arr.includes(x)     // Check existence — O(n)
arr.sort((a,b) => a-b)  // Sort numbers — O(n log n)
arr.reverse()       // Reverse in-place — O(n)
arr.fill(0)         // Fill with value — O(n)
Array.from({length: n}, (_, i) => i)  // Create [0,1,...,n-1]

Tips for Interviews

1. Always ask: Is the array sorted? Can it contain duplicates? Negatives?
2. Think HashMap first if brute force is O(n²) — it often gives O(n)
3. Two pointers work on sorted arrays — if unsorted, consider sorting first
4. In-place usually means two pointers or swapping
5. Subarray problems → think sliding window or prefix sum

Now head to the problems and start coding! 💪