Topic Overview

Arrays

Master array data structure, common operations, and array-based algorithms for interviews.

Beginner8 min read

Arrays are the most fundamental data structure - a collection of elements stored in contiguous memory locations, accessible by index.

Array Fundamentals

Characteristics

Fixed or dynamic size: Depending on language (Java: fixed, Python/JavaScript: dynamic)
Contiguous memory: Elements stored next to each other
Random access: O(1) access by index
Homogeneous: Usually same data type (typed arrays)

Time Complexities

Access by index: O(1)
Search (unsorted): O(n)
Search (sorted): O(log n) with binary search
Insert at end: O(1) amortized (dynamic arrays)
Insert at beginning: O(n) - must shift elements
Delete: O(n) - must shift elements

Common Operations

Traversal

1// Forward traversal
2for (let i = 0; i < arr.length; i++) {
3  console.log(arr[i]);
4}
5
6// Backward traversal
7for (let i = arr.length - 1; i >= 0; i--) {
8  console.log(arr[i]);
9}
10
11// For-of (values only)
12for (const value of arr) {
13  console.logvalue

Two Pointers Technique

1// Find pair that sums to target
2function twoSum(arr: number[], target: number): [number, number] | null {
3  let left = 0;
4  let right = arr.length - 1;
5
6  while (left < right) {
7    const sum = arr[left] + arr[right];
8    if (sum === target) {
9      return [left, right];
10    } else if sum  target

Sliding Window

1// Maximum sum of subarray of size k
2function maxSumSubarray(arr: number[], k: number): number {
3  let windowSum = 0;
4  let maxSum = 0;
5
6  // Initialize first window
7  for (let i = 0; i < k; i++) {
8    windowSum += arr[i];
9  }
10  maxSum = windowSum;
11
12  // Slide window
13  for (let i = k; i < arr.length; i++) {

Examples

Find Maximum Element

1function findMax(arr: number[]): number {
2  if (arr.length === 0) throw new Error('Empty array');
3  
4  let max = arr[0];
5  for (let i = 1; i < arr.length; i++) {
6    if (arr[i] > max) {
7      max = arr[i];
8    }
9  }
10  return max;

Reverse Array

1function reverse(arr: number[]): number[] {
2  let left = 0;
3  let right = arr.length - 1;
4
5  while (left < right) {
6    // Swap
7    [arr[left], arr[right]] = [arr[right], arr[left]];
8    left++;
9    right--;
10  }
11  return arr;
12}
13
14// Time: O(n)

Rotate Array

1// Rotate array k positions to the right
2function rotate(arr: number[], k: number): void {
3  k = k % arr.length; // Handle k > array length
4  
5  // Reverse entire array
6  reverse(arr, 0, arr.length - 1);
7  // Reverse first k elements
8  reverse(arr, 0, k - 1);
9  // Reverse remaining elements
10  reverse(arr, k, arr.length - 1);
11}
12
13function arr  start  end

Find Duplicates

1// Find all duplicates in array (1 ≤ arr[i] ≤ n)
2function findDuplicates(arr: number[]): number[] {
3  const duplicates: number[] = [];
4  
5  for (let i = 0; i < arr.length; i++) {
6    const index = Math.abs(arr[i]) - 1;
7    if (arr[index] < 0) {
8      // Already seen
9      duplicates.push(Matharri

Merge Sorted Arrays

1function mergeSorted(arr1: number[], arr2: number[]): number[] {
2  const merged: number[] = [];
3  let i = 0, j = 0;
4
5  while (i < arr1.length && j < arr2.length) {
6    if (arr1[i] <= arr2[j]) {
7      merged.push(arr1[i++]);

Common Pitfalls

Off-by-one errors: Using <= instead of < in loops, or accessing arr[arr.length]
Not handling empty arrays: Always check arr.length === 0 before processing
Modifying array while iterating: Can cause skipped elements or infinite loops
Assuming array is sorted: Always verify or sort first if needed
Index out of bounds: Always validate indices before access
Not considering edge cases: Empty array, single element, all same elements
Inefficient operations: Using unshift() or splice() in loops (O(n) each)
Memory issues: Creating new arrays unnecessarily instead of in-place operations

Interview Questions

Beginner

Q: Find the maximum element in an array. What's the time complexity?

1function findMax(arr: number[]): number {
2  if (arr.length === 0) throw new Error('Empty array');
3  
4  let max = arr[0];
5  for (let i = 1; i < arr.length; i++) {
6    if (arr[i] > max) {
7      max = arr[i];
8    }
9  }
10  return max;

Alternative: Use Math.max(...arr) but it's still O(n) internally.

Intermediate

Q: Given an array of integers, find two numbers that add up to a target. Optimize for time complexity.

Brute Force (O(n²)):

1function twoSum(arr: number[], target: number): [number, number] | null {
2  for (let i = 0; i < arr.length; i++) {
3    for (let j = i + 1; j < arr.length; j++) {
4      if (arr[i] + arr[j] === target) {
5        return [i, j];
6      }

Optimized with Hash Map (O(n)):

1function twoSum(arr: number[], target: number): [number, number] | null {
2  const map = new Map<number, number>(); // value -> index
3
4  for (let i = 0; i < arr.length; i++) {
5    const complement = target - arr[i];
6    if (map.has(complement)) {
7      return mapcomplement i

If array is sorted, use two pointers (O(n)):

1function twoSumSorted(arr: number[], target: number): [number, number] | null {
2  let left = 0;
3  let right = arr.length - 1;
4
5  while (left < right) {
6    const sum = arr[left] + arr[right];
7    if (sum === target) {
8      return [left, right];
9    } else if (sum < target

Senior

Q: Design a data structure that supports insert, delete, and getRandom all in O(1) time. How would you implement it?

Challenge: Arrays have O(1) insert/getRandom but O(n) delete. Hash maps have O(1) insert/delete but can't get random.

Solution: Combine array and hash map.

1class RandomizedSet {
2  private arr: number[] = [];
3  private map: Map<number, number> = new Map(); // value -> index in array
4
5  insert(val: number): boolean {
6    if (this.map.has(val)) {
7      return false; // Already exists
8    }
9
10    // Add to end of array
11    this.arr.push(val)

Key insight: When deleting, swap with last element and pop (O(1)) instead of shifting (O(n)).

Arrays provide O(1) random access by index but O(n) for insert/delete in middle
Two pointers technique: Use for sorted arrays, palindromes, two-sum problems
Sliding window: Efficient for subarray/substring problems with fixed or variable window
In-place operations: Modify array directly to save space (reverse, rotate)
Hash map optimization: Use hash map to reduce O(n²) to O(n) for lookup problems
Edge cases: Always handle empty arrays, single element, out of bounds
Time vs Space trade-off: Can often trade space for time (hash map) or vice versa
Array as hash: For problems with constraints (1 ≤ arr[i] ≤ n), use array itself as hash
Common patterns: Two pointers, sliding window, prefix sum, frequency counting
Two Pointers Technique - Advanced two-pointer patterns for array problems
Sliding Window - Efficient subarray/substring algorithms
Hashing - Hash maps for O(1) lookups in array problems
Sorting Algorithms - Sort arrays before applying two-pointer technique
Prefix Sum - Efficient range sum queries on arrays

Key Takeaways

Arrays provide O(1) random access by index but O(n) for insert/delete in middle

Two pointers technique: Use for sorted arrays, palindromes, two-sum problems

Sliding window: Efficient for subarray/substring problems with fixed or variable window

In-place operations: Modify array directly to save space (reverse, rotate)

Hash map optimization: Use hash map to reduce O(n²) to O(n) for lookup problems

Edge cases: Always handle empty arrays, single element, out of bounds

Time vs Space trade-off: Can often trade space for time (hash map) or vice versa

Array as hash: For problems with constraints (1 ≤ arr[i] ≤ n), use array itself as hash

Common patterns: Two pointers, sliding window, prefix sum, frequency counting

Arrays

Array Fundamentals

Characteristics

Time Complexities

Common Operations

Traversal

Two Pointers Technique

Sliding Window

Examples

Find Maximum Element

Reverse Array

Rotate Array

Find Duplicates

Merge Sorted Arrays

Common Pitfalls

Interview Questions

Beginner

Intermediate

Senior

Key Takeaways

Related Topics