Key Insight: Arrays provide O(1) random access but O(n) insertion/deletion. This trade-off makes them perfect for scenarios where you frequently access elements by index but rarely modify the structure.

What is an Array?

Array: A collection of elements of the same type stored in contiguous memory locations.

Key Properties:

›Fixed size (in most languages)
›Indexed starting from 0
›Homogeneous (same data type)
›Contiguous memory (elements stored sequentially)

Real-World Analogy:

Think of an array like apartment buildings:

›Each apartment has a number (index)
›All apartments are in the same building (contiguous)
›You can instantly find apartment #5 without checking #1-4
›Adding a new apartment requires rebuilding (insertion is costly)

Memory Layout:

Array: [10, 20, 30, 40, 50]
Index:  0   1   2   3   4

Memory:
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │
└────┴────┴────┴────┴────┘
1000 1004 1008 1012 1016  (memory addresses)

Each element is 4 bytes apart (for integers).

Array Declaration and Initialization

Static Arrays (Fixed Size)

Python

# Python uses lists (dynamic arrays) by default
# But we can demonstrate fixed-size behavior

# Method 1: Initialize with values
arr = [1, 2, 3, 4, 5]

# Method 2: Initialize with size (all zeros)
arr = [0] * 5  # [0, 0, 0, 0, 0]

# Method 3: Empty list
arr = []

# Method 4: Using array module (true arrays)
import array
arr = array.array('i', [1, 2, 3, 4, 5])  # 'i' = integer type

# Access elements
print(arr[0])  # Output: 1
print(arr[2])  # Output: 3

Dynamic Arrays (Variable Size)

Python

# Python lists are dynamic by default

# Create empty list
arr = []

# Add elements dynamically
arr.append(10)  # [10]
arr.append(20)  # [10, 20]
arr.append(30)  # [10, 20, 30]

# Insert at specific position
arr.insert(1, 15)  # [10, 15, 20, 30]

# Remove element
arr.remove(15)  # [10, 20, 30]

# Pop (remove and return last)
last = arr.pop()  # last=30, arr=[10, 20]

# Length
print(len(arr))  # Output: 2

Basic Array Operations

1. Accessing Elements - O(1)

Random access is the superpower of arrays!

Python

arr = [10, 20, 30, 40, 50]

# Access by index
print(arr[0])   # Output: 10 (first element)
print(arr[2])   # Output: 30
print(arr[-1])  # Output: 50 (last element, Python only)

# Modify element
arr[2] = 35
print(arr)  # Output: [10, 20, 35, 40, 50]

# Out of bounds raises IndexError
# print(arr[10])  # Error!

2. Traversing (Iterating) - O(n)

Visit every element in the array.

Python

arr = [10, 20, 30, 40, 50]

# Method 1: For loop with index
for i in range(len(arr)):
    print(arr[i], end=' ')
print()  # Output: 10 20 30 40 50

# Method 2: For-each loop (Pythonic)
for num in arr:
    print(num, end=' ')
print()  # Output: 10 20 30 40 50

# Method 3: With index using enumerate
for i, num in enumerate(arr):
    print(f"arr[{i}] = {num}")

3. Searching - O(n) Linear, O(log n) Binary

Find if an element exists in the array.

Linear Search (Unsorted Array):

Python

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Found at index i
    return -1  # Not found

# Example
arr = [10, 20, 30, 40, 50]
print(linear_search(arr, 30))  # Output: 2
print(linear_search(arr, 35))  # Output: -1

Binary Search (Sorted Array):

Python

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid  # Found
        elif arr[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half
    
    return -1  # Not found

# Example (array must be sorted!)
arr = [10, 20, 30, 40, 50]
print(binary_search(arr, 30))  # Output: 2
print(binary_search(arr, 35))  # Output: -1

4. Insertion - O(n)

Insert an element at a specific position.

Python

# Python lists handle insertion automatically
arr = [10, 20, 30, 50]

# Insert 40 at index 3
arr.insert(3, 40)
print(arr)  # Output: [10, 20, 30, 40, 50]

# Manual implementation (for fixed-size array simulation)
def insert_at(arr, pos, value):
    arr.append(0)  # Make space
    # Shift elements to the right
    for i in range(len(arr) - 1, pos, -1):
        arr[i] = arr[i - 1]
    arr[pos] = value
    return arr

arr = [10, 20, 30, 50]
arr = insert_at(arr, 3, 40)
print(arr)  # Output: [10, 20, 30, 40, 50]

Why O(n)? Must shift all elements after the insertion point.

5. Deletion - O(n)

Remove an element from a specific position.

Python

arr = [10, 20, 30, 40, 50]

# Remove by index
del arr[2]  # Removes element at index 2
print(arr)  # Output: [10, 20, 40, 50]

# Remove by value
arr.remove(40)  # Removes first occurrence of 40
print(arr)  # Output: [10, 20, 50]

# Manual implementation
def delete_at(arr, pos):
    # Shift elements to the left
    for i in range(pos, len(arr) - 1):
        arr[i] = arr[i + 1]
    arr.pop()  # Remove last element
    return arr

arr = [10, 20, 30, 40, 50]
arr = delete_at(arr, 2)
print(arr)  # Output: [10, 20, 40, 50]

Why O(n)? Must shift all elements after the deletion point.

Array Operations Complexity Summary

Operation	Time Complexity	Explanation
Access	O(1)	Direct index calculation
Search	O(n) linear, O(log n) binary	Must check each element / binary split
Insert at end	O(1) amortized	Append is fast
Insert at position	O(n)	Must shift elements
Delete at end	O(1)	Pop is fast
Delete at position	O(n)	Must shift elements
Traverse	O(n)	Visit each element once

Multi-Dimensional Arrays

2D Arrays (Matrices)

Python

# Method 1: List of lists
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Access element
print(matrix[1][2])  # Output: 6 (row 1, col 2)

# Traverse 2D array
for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        print(matrix[i][j], end=' ')
    print()

# Method 2: Initialize with zeros
rows, cols = 3, 4
matrix = [[0] * cols for _ in range(rows)]

Common Array Patterns

Pattern 1: Two Pointers

Use two pointers moving toward each other.

Python

def reverse_array(arr):
    left, right = 0, len(arr) - 1
    
    while left < right:
        # Swap elements
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    
    return arr

# Example
arr = [1, 2, 3, 4, 5]
print(reverse_array(arr))  # Output: [5, 4, 3, 2, 1]

Pattern 2: Sliding Window

Maintain a window of fixed or variable size.

Python

def max_sum_subarray(arr, k):
    # Find maximum sum of k consecutive elements
    n = len(arr)
    if n < k:
        return -1
    
    # Calculate sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, n):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# Example
arr = [1, 4, 2, 10, 23, 3, 1, 0, 20]
k = 4
print(max_sum_subarray(arr, k))  # Output: 39 (10+23+3+1)

Pattern 3: Kadane's Algorithm

Find maximum subarray sum.

Python

def max_subarray_sum(arr):
    max_sum = arr[0]
    current_sum = arr[0]
    
    for i in range(1, len(arr)):
        # Either extend current subarray or start new
        current_sum = max(arr[i], current_sum + arr[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

# Example
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))  # Output: 6 (subarray [4,-1,2,1])

When to Use Arrays

✅ Use Arrays When:

›Need random access - O(1) access by index
›Fixed size known - Size doesn't change
›Sequential data - Data naturally ordered
›Memory efficiency - Contiguous storage is cache-friendly
›Simple iteration - Processing all elements in order

❌ Avoid Arrays When:

›Frequent insertions/deletions - O(n) cost is too high
›Dynamic size - Size changes frequently (use dynamic arrays/lists)
›Sparse data - Many unused elements waste memory
›Need fast search - Use hash table for O(1) search
›Complex structure - Need hierarchical data (use trees)

Common Mistakes

Mistake 1: Off-by-One Errors

Python

arr = [1, 2, 3, 4, 5]

# Wrong: Goes out of bounds
for i in range(len(arr) + 1):  # ❌ Bug!
    print(arr[i])  # IndexError on last iteration

# Correct
for i in range(len(arr)):  # ✅ Correct
    print(arr[i])

Mistake 2: Not Checking Bounds

Python

def get_element(arr, index):
    # Wrong: No bounds checking
    return arr[index]  # ❌ May crash

# Correct: Check bounds
def get_element_safe(arr, index):
    if 0 <= index < len(arr):
        return arr[index]
    return None  # Or raise exception

Key Takeaways

Array Fundamentals:

Definition: Contiguous memory storage with fixed size and O(1) access

Strengths:

›O(1) random access by index
›Memory efficient (cache-friendly)
›Simple to use and understand

Weaknesses:

›O(n) insertion/deletion at arbitrary positions
›Fixed size (in most languages)
›Wasted space if not fully utilized

Common Operations:

›Access: O(1)
›Search: O(n) linear, O(log n) binary (if sorted)
›Insert/Delete: O(n)

Key Patterns:

›Two pointers for reversals and searches
›Sliding window for subarray problems
›Kadane's algorithm for maximum subarray

Remember: Arrays are perfect when you need fast random access but rarely modify the structure

What's Next?

Now that you understand arrays:

›Sorting Algorithms - Learn to sort arrays efficiently
›Two Pointers Pattern - Master array manipulation
›Dynamic Arrays - Understand ArrayList/Vector internals

Practice Problems

Problem 1: Find Second Largest

Find the second largest element in an array.

Problem 2: Remove Duplicates

Remove duplicates from a sorted array in-place.

Problem 3: Rotate Array

Rotate an array to the right by k steps.

Problem 4: Missing Number

Find the missing number in array containing n-1 distinct numbers from 1 to n.

Congratulations! You now understand arrays deeply and can use them effectively!

←

PreviousModular Arithmetic

Next2D Arrays

→