Skip to main content

Arrays

Arrays are one of the most fundamental data structures in programming—and they show up constantly in coding interviews. If you understand arrays well, many other topics (strings, matrices, sliding window, two pointers, dynamic programming) become much easier.

This lesson explains arrays intuitively, with simple mental models and interview-focused thinking.

What Is an Array?​

An array is a collection of items stored next to each other in memory, where:

  • Each item has the same data type
  • Each item can be accessed using an index
  • Indexing usually starts at 0

Example:

nums = [10, 20, 30, 40]
         0   1   2   3

Think of an array like:

  • A row of mailboxes
  • Each mailbox has a number (index)
  • You can instantly open any mailbox if you know its number

Why Are Arrays Important?​

Arrays are popular because they are:

  • ⚡ Fast to access
  • 🧠 Simple to understand
  • 🧱 The foundation of many advanced problems

In interviews, arrays are often used to test:

  • Logical thinking
  • Index manipulation
  • Time and space complexity awareness

Accessing Elements (O(1))​

Accessing an element by index is constant time.

nums[2] → 30

Why is this fast?

  • The computer knows exactly where the array starts in memory
  • It jumps directly to the correct position

✅ Interview takeaway:

Accessing array[i] is O(1).

Traversing an Array (O(n))​

Traversal means visiting each element once.

for i from 0 to n-1:
    process array[i]

Example use cases:

  • Finding the maximum
  • Calculating a sum
  • Checking if an element exists

⏱ Time complexity: O(n)

Inserting Elements​

Insert at the End (Amortized O(1))​

Appending to the end is usually fast:

nums = [1,2,3]
append 4 → [1,2,3,4]

Most languages optimize this.

Insert at the Beginning or Middle (O(n))​

nums = [1,2,3,4]
insert 99 at index 1 → [1,99,2,3,4]

Why is this slow?

  • All elements after index 1 must shift right

⛔ Interview rule:

Insertion anywhere except the end costs O(n).

Deleting Elements​

Delete from End (O(1))​

[1, 2, 3, 4] → remove 4 → [1,2,3]

Delete from Beginning or Middle (O(n))​

[1, 2, 3, 4]
remove index 1 → [1,3,4]

Elements must shift left.

Searching in an Array​

Linear Search (O(n))​

When the array is unsorted:

for each element:
if element == target:
return true

Worst case: check every element.

Binary Search (O(log n))​

If the array is sorted, you can do much better.

Binary search:

  • Check the middle
  • Eliminate half the array each step

⛔ Requires sorted array

Common Array Patterns in Interviews​

If you see an array problem, look for these patterns:

1. Two Pointers​

Used when:

  • Array is sorted
  • Comparing from both ends

Example:

  • Pair sum
  • Removing duplicates

2. Sliding Window​

Used when:

  • Subarrays or substrings
  • Continuous ranges

Example:

  • Max sum of size k
  • Longest substring

3. Prefix Sum​

Used when:

  • Range sum queries
  • Repeated calculations

4. In-Place Modification​

Used when:

  • Asked to use O(1) extra space

Example:

  • Remove duplicates
  • Move zeros

Common Mistakes Beginners Make​

🚫 Off-by-one errors

for i in range(0, n):// correct
for i in range(0, n-1):// often wrong

🚫 Forgetting bounds

array[i+1]  // check i+1 < n

🚫 Modifying array while iterating

This can cause skipped elements.

Arrays vs Linked Lists (Quick Comparison)​

FeatureArrayLinked List
Access by indexO(1)O(n)
Insert/DeleteO(n)O(1) (if node known)
MemoryContiguousScattered
Cache-friendlyYesNo

✅ Arrays are usually preferred in interviews unless frequent insertions are required.

When Should You Use Arrays?​

Use arrays when:

  • You need fast access
  • The size is known or manageable
  • Order matters

Avoid arrays when:

  • Frequent insertions/deletions in the middle
  • Size changes unpredictably (linked list may help)

Interview Checklist for Array Problems​

Before coding, ask yourself:

  • Is the array sorted?
  • Can I use two pointers?
  • Can I reduce space by modifying in place?
  • What is the time complexity?
  • What edge cases exist?
    • Empty array
    • Single element
    • Duplicate values

Final Thoughts​

Arrays are simple—but powerful.

Mastering arrays means:

  • Cleaner code
  • Faster problem-solving
  • Stronger interview performance

Almost every coding interview starts here. Once arrays feel natural, the rest of data structures become much easier.