Arrays are the most fundamental data structure in programming. Every DSA concept builds on arrays. Master them first, and everything else becomes easier.

Index-based AccessO(1) LookupCache-FriendlyFoundation of all DSAContiguous Memory

💡 Python learners: In Python, arrays are implemented using list. All examples show the Python equivalent.

// 01 — Introduction

What is an Array?

An array is a collection of elements stored in contiguous memory locations. Each element can be accessed using its index, starting from 0.

In Python, the built-in list acts as a dynamic array. In Java, int[] is fixed and ArrayList is dynamic. In C++, vector<int> is standard.

Memory Layout — arr = [10, 20, 30, 40, 50]

idx 0

+0B

idx 1

+4B

idx 2

+8B

idx 3

+12B

idx 4

+16B

arr[2] → jumps to address+8 → returns 30 in O(1)

💡 Key Insight — CPU Cache Locality

Because elements sit side-by-side in memory, the CPU can cache an entire array row at once. Array iteration is faster in practice than O(n) suggests — it benefits enormously from CPU cache locality.

Language Terminology Mapping

DSA Concept	Java	Python	C++	Note
Fixed Array	`int[] arr`	`arr = [1,2,3]`	`int arr[5]`	Python lists are always dynamic
Dynamic Array	`ArrayList<Integer>`	`list`	`vector<int>`	Grows automatically
Length	`arr.length`	`len(arr)`	`arr.size()`	O(1) in all languages
Access	`arr[i]`	`arr[i]`	`arr[i]`	O(1) in all
Append	`.add(x)`	`.append(x)`	`.push_back(x)`	Amortized O(1)
Sort	`Arrays.sort(arr)`	`arr.sort()`	`sort(beg,end)`	O(n log n)

// 02 — Creation

Creation & Initialization

Multiple ways to create arrays in Python. Choose the right one for your use case.

Basic Creation

python

arr = []                  # empty list
arr = list()              # empty list (constructor)
arr = [1, 2, 3, 4, 5]    # with initial values
zeros = [0] * 5           # [0, 0, 0, 0, 0]
nums = list(range(1, 6))  # [1, 2, 3, 4, 5]

2D Arrays

python

# CORRECT way — list comprehension
rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]

# ⚠️ WRONG — all rows share the SAME inner list!
bad_grid = [[0] * cols] * rows   # Do NOT use this

⚠️ Common Pitfall — 2D Array Aliasing

[[0]*4]*3 creates 3 references to the same inner list. Always use: [[0]*4 for _ in range(3)]

List Comprehension

python

squares = [x**2 for x in range(10)]
evens = [x for x in range(20) if x % 2 == 0]

# Flatten 2D to 1D
matrix = [[1,2],[3,4],[5,6]]
flat = [num for row in matrix for num in row]
# [1, 2, 3, 4, 5, 6]

// 03 — Access & Update

Accessing & Updating Elements

Index Access — O(1)

python

arr = [10, 20, 30, 40, 50]
arr[0]   # 10  — first element
arr[2]   # 30  — third element
arr[-1]  # 50  — last element (negative indexing)
arr[-2]  # 40  — second from last

Slicing — O(k)

python

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
arr[2:5]   # [2, 3, 4]           → stop is EXCLUDED
arr[:4]    # [0, 1, 2, 3]        → from start
arr[6:]    # [6, 7, 8, 9]        → to end
arr[::2]   # [0, 2, 4, 6, 8]    → every 2nd element
arr[::-1]  # [9,8,7,6,5,4,3,2,1,0] → reverse

📌 Slicing always returns a new list

Slicing creates a shallow copy. Modifying the slice does NOT affect the original array.

Updating & Membership

python

arr = [10, 20, 30, 40, 50]
arr[2] = 99          # Update single → [10,20,99,40,50]
arr[-1] = 0          # Update last   → [10,20,99,40,0]
arr[1:3] = [200,300] # Update slice  → [10,200,300,40,0]
del arr[1:3]         # Delete slice  → [10,40,0]

print(3 in arr)      # True  — O(n)

// 04 — Iteration

Iterating Over Arrays

Basic Loops

python

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

for val in arr:
    print(val)

for i, val in enumerate(arr):
    print(f"arr[{i}] = {val}")

Reverse & Two-Pointer

python

for val in reversed(arr):
    print(val)   # 50 40 30 20 10

left, right = 0, len(arr) - 1
while left < right:
    print(arr[left], arr[right])
    left += 1
    right -= 1

2D Arrays & zip()

python

matrix = [[1,2,3],[4,5,6],[7,8,9]]
for row in matrix:
    for val in row:
        print(val, end=' ')

names  = ["Alice", "Bob", "Charlie"]
scores = [95, 87, 92]
for name, score in zip(names, scores):
    print(f"{name}: {score}")

// 05 — Built-in Methods

Built-in Methods & Functions

Know the time complexities — interviewers test this constantly.

Method / Function	Description	Time	Example
`append(x)`	Add element to end	O(1)	`arr.append(5)`
`insert(i, x)`	Insert at index i	O(n)	`arr.insert(2, 10)`
`pop()`	Remove & return last element	O(1)	`arr.pop()`
`pop(i)`	Remove & return element at index i	O(n)	`arr.pop(0)`
`remove(x)`	Remove first occurrence of x	O(n)	`arr.remove(3)`
`sort()`	Sort in-place ascending	O(n log n)	`arr.sort()`
`sort(reverse=True)`	Sort in-place descending	O(n log n)	`arr.sort(reverse=True)`
`reverse()`	Reverse in-place	O(n)	`arr.reverse()`
`len(arr)`	Number of elements	O(1)	`len(arr)`
`sorted(arr)`	Return new sorted list	O(n log n)	`b = sorted(arr)`
`min(arr)`	Minimum value	O(n)	`min(arr)`
`max(arr)`	Maximum value	O(n)	`max(arr)`
`sum(arr)`	Sum of all elements	O(n)	`sum(arr)`
`enumerate(arr)`	Iterate with index	O(n)	`for i, v in enumerate(arr)`
`zip(a, b)`	Pair elements from two arrays	O(n)	`for x, y in zip(a, b)`

// 06 — Common Patterns

5 Essential DSA Patterns

These 5 patterns solve 80% of array interview problems. Learn them in this order.

Pattern 1Two Pointers

Use two indices moving toward or away from each other. Reduces O(n²) brute force to O(n).

python

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:   return [left, right]
        elif s < target:  left += 1
        else:             right -= 1
    return []
# Time: O(n)  |  Space: O(1)

Pattern 2Sliding Window

Maintain a window sliding across the array. Reduces O(n²) to O(n).

python

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum
# Time: O(n)  |  Space: O(1)

Pattern 3Prefix Sum

Precompute cumulative sums so any range sum query answers in O(1).

python

arr = [3, 1, 4, 1, 5, 9, 2, 6]
n = len(arr)
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i+1] = prefix[i] + arr[i]

def range_sum(l, r):
    return prefix[r+1] - prefix[l]
# Build: O(n)  |  Query: O(1)

Pattern 4Kadane's Algorithm

Find max sum contiguous subarray in O(n).

python

def max_subarray(arr):
    max_sum = current = arr[0]
    for num in arr[1:]:
        current = max(num, current + num)
        max_sum = max(max_sum, current)
    return max_sum
# Time: O(n)  |  Space: O(1)

Pattern 5Binary Search

Search a sorted array in O(log n).

python

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:   return mid
        elif arr[mid] < target:  left = mid + 1
        else:                    right = mid - 1
    return -1
# Time: O(log n)  |  Space: O(1)

// 07 — Complexity

Time & Space Complexity

Know when to use arrays and when not to. Complexity guides that decision.

Operation	Average	Worst	Notes
Access by index	O(1)	O(1)	Direct memory offset
Search (unsorted)	O(n)	O(n)	Linear scan
Search (sorted)	O(log n)	O(log n)	Binary search
Insert at end	O(1)*	O(n)	*Amortized for dynamic arrays
Insert at index i	O(n)	O(n)	Shift elements right
Delete at end	O(1)	O(1)	Just decrement size
Delete at index i	O(n)	O(n)	Shift elements left
Sort	O(n log n)	O(n log n)	TimSort in Python

✅ Use Arrays When

Random access by index needed
Iterating sequentially
Cache performance matters
Size is roughly known upfront

🚫 Avoid Arrays When

Frequent insertions/deletions at front
Need O(1) search by value → use HashMap
Unknown size, heavy resizing
FIFO/LIFO patterns → use deque/stack

// 08 — Practice Problems

Curated Problem Set

Solve in order — Easy → Medium → Hard. Each builds on the previous.

← Back to DSA Overview Next: Strings →