1.1 Arrays, Memory & In-Place Matrix Operations

1. What Is an Array? (In Plain Everyday Language)

Imagine a row of numbered lockers in a school hallway: Locker 0, Locker 1, Locker 2, all the way up to Locker N - 1.

• Every locker is the exact same size.
• They are built right next to each other with zero gaps in between.

An Array is the exact same thing inside your computer's memory (RAM). It is a single, unbroken strip of memory boxes that holds a list of items side by side.

2. Why Do We Need Arrays & How Do They Work Inside Memory?

Why is an Array the #1 most common data structure in programming? Because of instant random access (O(1) time).

Suppose an array of 32-bit integers (4 bytes each) starts at memory address 1000, and you ask for arr[3]. Your computer does not walk past arr[0], arr[1], and arr[2] to get there. Instead, it calculates one simple math formula:

address of arr[i] = start_address + (i * size_of_each_item) address of arr[3] = 1000 + (3 * 4) = 1012

Whether your array has 10 items or 10,000,000 items, jumping to arr[i] always takes 1 single step (O(1))!

The Catch: Why Inserting or Deleting in the Middle Is Slow (O(N))

Because an array must stay packed together with no empty gaps:

• Inserting at the front (arr.insert(0, x)): Every single existing item (arr[0], arr[1], ..., arr[N-1]) has to shift one locker to the right to make room. For 1 million items, that's 1 million shifts (O(N)).
• Deleting from the front/middle (arr.pop(0)): Every item after the deleted spot has to shift one locker to the left to close the gap (O(N)).
• Adding/removing at the very end (arr.append(x) / arr.pop()): Nothing else has to move! Dynamic arrays (list in Python, vector in C++, ArrayList in Java) keep extra spare slots at the end and double their capacity whenever they fill up, making appends O(1) on average.

Step Through the Visual Drawing: In-Place Array Reversal

Click Next below to watch how an array reverses its elements in-place using index math without allocating a second array:

3. Basic Operations & Syntax (All 4 Languages)

Before solving interview problems, make sure you know how to create, read, update, append, and loop through 1D arrays and 2D matrices in your language:

# 1. Create a 1D array (Python list is a dynamic array)
nums = [10, 20, 30, 40]

# 2. Read & update by index -> O(1)
first = nums[0]       # 10
nums[2] = 99          # [10, 20, 99, 40]

# 3. Append & pop at the end -> O(1) amortized
nums.append(50)       # [10, 20, 99, 40, 50]
last = nums.pop()     # 50

# 4. Loop with index and value
for i, val in enumerate(nums):
  pass

# 5. Create an R x C 2D matrix filled with 0s
rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]

3B. More Operations: Static vs. Dynamic Arrays, Prefix/Suffix & 2D Matrix Traversals

Competitor platforms often jump straight from arr[0] into Hard LeetCode questions without showing how dynamic arrays resize or how to walk a 2D matrix. Let's master both first:

Warm-Up Examples Before Interview Problems

1. Warm-Up 1 (1D Array): Left-Rotate an Array by k Steps in O(1) Extra Space Suppose nums = [1, 2, 3, 4, 5, 6, 7] and you want to rotate it right by k = 3 steps to get [5, 6, 7, 1, 2, 3, 4]. Instead of allocating a new array, use 3 in-place reversals:
   • Reverse the whole array: [7, 6, 5, 4, 3, 2, 1]
   • Reverse the first k items (0..k-1): [5, 6, 7, 4, 3, 2, 1]
   • Reverse the remaining items (k..n-1): [5, 6, 7, 1, 2, 3, 4] — done in O(N) time and O(1) space!
2. Warm-Up 2 (2D Matrix): Transpose + Row-Reverse (90° Clockwise Rotation) See the 4-language implementation below:

# Warm-Up 1: Rotate Array Right by k Steps in O(1) Space (3-Reversal Trick)
def rotate_array(nums: list[int], k: int) -> None:
  n = len(nums)
  k %= n
  def rev(l: int, r: int) -> None:
      while l < r:
          nums[l], nums[r] = nums[r], nums[l]
          l += 1; r -= 1
  rev(0, n - 1)
  rev(0, k - 1)
  rev(k, n - 1)

# Warm-Up 2: Rotate an N x N 2D Matrix 90° Clockwise In-Place
def rotate_matrix_90(matrix: list[list[int]]) -> None:
  n = len(matrix)
  # Step 1: Transpose across main diagonal (swap matrix[r][c] with matrix[c][r])
  for r in range(n):
      for c in range(r + 1, n):
          matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
  # Step 2: Reverse each row left-to-right
  for row in matrix:
      row.reverse()

4. Interview Pattern: In-Place Index Marking & Cyclic Sort (O(1) Space)

When Do You Use This?

Suppose an interviewer gives you an array of size N where the numbers are in the range 1 to N (like [4, 3, 2, 7, 8, 2, 3, 1]) and asks: "Find all missing numbers (or the first missing positive number) in O(N) time using O(1) extra memory (you are NOT allowed to create a Hash Set!)."

The Simple Intuition

Every number v between 1 and N has a natural "home locker" at index v - 1 (1 belongs at index 0, 2 belongs at index 1, ..., N belongs at index N - 1).

• Cyclic Sort (Swap into Home Index): Stand at index i. While nums[i] is between 1 and N and is not sitting at its home (nums[nums[i] - 1] != nums[i]), swap it into its home locker! Once everyone is home, scan the array: the first index i that doesn't hold i + 1 is your missing number!
• 2D Matrix In-Place Trick (Rotate Image): To rotate an N x N matrix 90° clockwise without allocating a second matrix: 1) Transpose across the diagonal (swap(mat[r][c], mat[c][r])), then 2) Reverse each row left-to-right!

for i in range(n):
  while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
      home = nums[i] - 1
      nums[i], nums[home] = nums[home], nums[i]

5. Practice On Your Own (Curated Submodule Problems)

Try solving the problems below using the exact patterns from this lesson. Click Intuition on any row if you need a nudge!