← Back to algorithms

Algorithms Topic

Arrays: Algorithm Patterns & Interview Problems

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

TypeScript
Python
Java
1

Two Pointers Technique

TypeScript
Python
Java
1

Sliding Window

TypeScript
Python
Java
1

Examples

Find Maximum Element

TypeScript
Python
Java
1

Reverse Array

TypeScript
Python
Java
1

Rotate Array

TypeScript
Python
Java
1

Find Duplicates

TypeScript
Python
Java
1

Merge Sorted Arrays

TypeScript
Python
Java
1

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?

A:

TypeScript
Python
Java
1

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.

A:

Brute Force (O(n²)):

TypeScript
Python
Java
1

Optimized with Hash Map (O(n)):

TypeScript
Python
Java
1

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

TypeScript
Python
Java
1

Senior

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

A:

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.

TypeScript
Python
Java
1

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

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

Related Topics

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

What's next?

Practice this in System Design →Next topic →

Keep exploring

Pattern recognition beats memorization. Practice the next algorithm topic that uses a similar structure or invariant.

QuizPracticeNext