📊 Array Fundamentals

Beginner ~10 min read

You're building a game leaderboard. Players can view their rank instantly - that's O(1) access! But adding a new player requires shifting everyone below - that's O(1). Arrays are perfect for some tasks and terrible for others. Let's see when to use them.

What is an Array?

An array is a collection of elements stored in contiguous memory. Think of it like numbered boxes in a row:

Array Structure

Index:  0    1    2    3    4
Value: [10] [20] [30] [40] [50]
        ↑
    Memory address: 1000, 1004, 1008, 1012, 1016...

Key insight: Because elements are next to each other in memory, you can jump directly to any index using math:

address = base_address + (index × element_size)

This makes access O(1) - instant, regardless of array size!

Array Operations

Let's see the core operations and their complexities:

# Array Operations - The Essentials
# Understanding O(1) access vs O(n) operations

# Game leaderboard example
leaderboard = ["Alice", "Bob", "Charlie", "David", "Eve"]

print("=== Array Access: O(1) ===")
print(f"Rank 1 (index 0): {leaderboard[0]}")  # Instant!
print(f"Rank 3 (index 2): {leaderboard[2]}")  # Also instant!
print(f"Rank 5 (index 4): {leaderboard[4]}")  # Still instant!
print("✅ Direct index access = O(1) time\n")

print("=== Array Search: O(n) ===")
def find_player_rank(leaderboard, name):
    """Find a player's rank by name - must check each element"""
    for i, player in enumerate(leaderboard):
        if player == name:
            return i + 1  # Rank is 1-indexed
    return -1  # Not found

rank = find_player_rank(leaderboard, "Charlie")
print(f"Charlie's rank: {rank}")
print("❌ Search by value = O(n) time (worst case)\n")

print("=== Array Insert: O(n) ===")
print(f"Before insert: {leaderboard}")
# Insert "Frank" at rank 2 (index 1)
leaderboard.insert(1, "Frank")  # Shifts Bob, Charlie, David, Eve
print(f"After insert:  {leaderboard}")
print("❌ Insert = O(n) time (must shift elements)\n")

print("=== Array Delete: O(n) ===")
print(f"Before delete: {leaderboard}")
del leaderboard[1]  # Remove Frank, shifts everyone back
print(f"After delete:  {leaderboard}")
print("❌ Delete = O(n) time (must shift elements)\n")

print("=== Key Takeaway ===")
print("Arrays are great for:")
print("  ✅ Fast access by index: O(1)")
print("  ✅ Iterating through all elements: O(n)")
print("\nArrays are slow for:")
print("  ❌ Inserting/deleting (except at end): O(n)")
print("  ❌ Searching by value: O(n)")

Output

Click Run to execute your code

The Tradeoff:

✅ Access by index: O(1) - Lightning fast!
❌ Insert/Delete: O(n) - Must shift elements
❌ Search by value: O(n) - Must check each element

Quick Quiz

Why is array[100] instant (O(1))?

Show answer
The computer calculates the exact memory address using base + (100 × size) and jumps directly there. No loop needed!
Why is inserting at index 0 slow (O(n))?

Show answer
You must shift ALL existing elements one position to the right to make room. For n elements, that's n shifts = O(n).

See It in Action

Common Array Patterns

Here are techniques you'll use frequently:

# Common Array Patterns
# Techniques you'll use frequently

arr = [5, 2, 8, 1, 9, 3, 7]

print("=== Pattern 1: Traversal ===")
print("Forward:")
for i in range(len(arr)):
    print(f"  arr[{i}] = {arr[i]}")

print("\nReverse:")
for i in range(len(arr) - 1, -1, -1):
    print(f"  arr[{i}] = {arr[i]}")

print("\n=== Pattern 2: Find Min/Max ===")
min_val = arr[0]
max_val = arr[0]

for num in arr:
    if num < min_val:
        min_val = num
    if num > max_val:
        max_val = num

print(f"Min: {min_val}, Max: {max_val}")

print("\n=== Pattern 3: Two Pointers (Preview) ===")
# Reverse array in-place using two pointers
temp = arr.copy()
left = 0
right = len(temp) - 1

while left < right:
    # Swap elements
    temp[left], temp[right] = temp[right], temp[left]
    left += 1
    right -= 1

print(f"Original: {arr}")
print(f"Reversed: {temp}")
print("✅ Two pointers = O(n) time, O(1) space")

print("\n=== Pattern 4: Sliding Window (Preview) ===")
# Find maximum sum of 3 consecutive elements
def max_sum_window(arr, k=3):
    """Maximum sum of k consecutive elements"""
    if len(arr) < k:
        return None
    
    # Calculate first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

result = max_sum_window(arr, 3)
print(f"Array: {arr}")
print(f"Max sum of 3 consecutive: {result}")
print("✅ Sliding window = O(n) time")

print("\n=== Key Patterns ===")
print("1. Traversal: Visit each element")
print("2. Two Pointers: Work from both ends")
print("3. Sliding Window: Fixed-size subarray")
print("4. Prefix Sum: Cumulative sums (next lesson)")

Output

Click Run to execute your code

When to Use Arrays

Use Arrays When	Avoid Arrays When
✅ You need fast random access	❌ Frequent insertions/deletions
✅ Size is known or fixed	❌ Size changes unpredictably
✅ Iterating through all elements	❌ Searching by value frequently
✅ Memory efficiency matters	❌ Need fast insertions at beginning

Real-World Uses

Leaderboards: Fast rank lookup
Image pixels: Direct coordinate access
Audio samples: Sequential processing
Database records: Index-based queries

Common Mistakes

❌ Index Out of Bounds

arr = [1, 2, 3]
print(arr[3])  # Error! Valid indices: 0, 1, 2

Fix: Always check if index < len(arr)

❌ Modifying While Iterating

for i in range(len(arr)):
    arr.append(i)  # Infinite loop!

Fix: Create a copy or iterate backwards

Summary

The 3-Point Array Guide

Access: O(1) - Use arrays when you need fast lookups by index
Insert/Delete: O(n) - Avoid arrays for frequent modifications
Memory: Contiguous storage = cache-friendly and efficient

Interview tip: When asked "Why use an array?", mention O(1) access and memory locality!

What's Next?

Now that you understand arrays, you're ready for array techniques! Next lesson: Two Pointers - a powerful pattern for solving array problems efficiently.

Preview: Two pointers can solve problems like "find two numbers that sum to target" in O(n) instead of O(n²). Stay tuned!

Previous Algorithm Analysis

Next Two Pointers Technique