Day 2: Mastering Arrays in DSA
The humble parking lot of computer memory.
IN 30 SECONDS
An array is the most fundamental data structure in computer science. It is simply a collection of items stored right next to each other in the computer's memory. Because everything is perfectly aligned and numbered, you can instantly find any item if you know its position. It is the building block for almost every other complex structure.
THE REAL-WORLD ANALOGY
Think of an array like a perfectly organized egg carton. Every slot has a number (an index). If you want the 3rd egg, you don't have to check the 1st or 2nd egg—you just reach directly into slot #3. But there is a catch: if you want to squeeze a new egg into the middle, you have to shift all the other eggs over to make room.
PICTURE THIS
Memory Slots (Contiguous):\n[0] -> 'A'\n[1] -> 'B'\n[2] -> 'C'\n\nInserting 'X' at index 1:\n1. Copy 'C' to index 3\n2. Copy 'B' to index 2\n3. Insert 'X' at index 1\nResult: ['A', 'X', 'B', 'C']
The first diagram shows how elements are stored directly next to each other. The second illustrates the painful process of shifting elements when inserting into the middle.
HOW IT ACTUALLY WORKS
- Initialization: When you create an array, the computer carves out a single, unbroken block of memory.
- Indexing: Each compartment is given an index, usually starting at 0.
- Accessing: The computer calculates the exact memory address instantly by doing a simple math trick: (Start Address) + (Index * Item Size).
- Modifying: Changing a value is instant, but adding or removing elements in the middle requires shifting everything after it.
SHOW ME THE CODE
def insert_element(arr, val, index):\n # Python lists handle shifting automatically, \n # but under the hood, it's doing this:\n arr.append(0) # Make space at the end\n \n # Shift elements to the right\n for i in range(len(arr)-1, index, -1):\n arr[i] = arr[i-1]\n \n # Drop the new value in\n arr[index] = val\n return arr
DRY RUN
Input: arr=[10, 20], val=15, index=1
| Step | Action | State | Output |
|---|---|---|---|
| 1 | Make space | [10, 20, 0] | - |
| 2 | Shift index 1 to 2 | [10, 20, 20] | - |
| 3 | Insert 15 at index 1 | [10, 15, 20] | [10, 15, 20] |
SPEED & MEMORY
Reading is lightning fast because of the math formula. Inserting is slow because we have to physically move items to keep the memory contiguous.
| Action | Time | Space |
|---|---|---|
| Access (Read) | O(1) | O(1) |
| Insert/Delete (Middle) | O(N) | O(1) |
WHERE YOU'LL SEE IT IN REAL LIFE
- Pixels on a screen: A 2D array of color values.
- Contact lists: Storing sequential records where you frequently read but rarely delete.
TRAPS TO AVOID
- Trap 1: Forgetting arrays are 0-indexed. Fix: The first item is always at index 0, not 1!
- Trap 2: Out of bounds errors. Fix: Never try to access index N in an array of size N; the last item is N-1.
- Trap 3: Assuming insertions are fast. Fix: Remember the shifting penalty!
PRACTICE
- Easy: Find the maximum number in an unsorted array.
- Medium: Reverse an array in-place without creating a second array.
TL;DR
- Arrays store items in contiguous memory slots.
- Reading is instant (O(1)), but inserting/deleting requires shifting (O(N)).
- They are 0-indexed, meaning counting starts at zero.
REFERENCES CONSULTED
Referenced for verification — all content above is original. Consulted Wikipedia and GeeksforGeeks Arrays.
COVERED LOG UPDATE
Added: Day 2: Arrays