Arrays — Complete Guide | DevStackFlow DSA

What is an Array?

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

In Python, the built-in list type acts as a dynamic array — it can grow and shrink at runtime, unlike fixed-size arrays in C/Java.

Memory Layout

idx 0

+0B

idx 1

+4B

idx 2

+8B

idx 3

+12B

idx 4

+16B

arr = [10, 20, 30, 40, 50] → arr[2] = 30 (O(1))

💡 Key Insight

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

Creation & Initialization

There are multiple ways to create arrays in Python. Choose the right one for your use case.

Empty Array

python

# Method 1: Empty list literal
arr = []

# Method 2: list() constructor
arr = list()

Array with Initial Values

python

# Integer array
arr = [1, 2, 3, 4, 5]

# String array
words = ["apple", "banana", "cherry"]

# Mixed types (Python allows this)
mixed = [1, "hello", 3.14, True]

# Nested arrays (2D array)
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

Pre-filled Arrays

python

# Array of zeros (size n=5)
zeros = [0] * 5          # [0, 0, 0, 0, 0]

# Array of a specific value
fives = [5] * 4          # [5, 5, 5, 5]

# Array from a range
nums = list(range(1, 6)) # [1, 2, 3, 4, 5]
evens = list(range(0, 10, 2))  # [0, 2, 4, 6, 8]

# 2D array — CORRECT way (avoid aliasing!)
rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]
# [[0,0,0,0], [0,0,0,0], [0,0,0,0]]

# ⚠️ WRONG — all rows point to the SAME list!
bad_grid = [[0] * cols] * rows   # Do NOT do this

⚠️ Common Pitfall — 2D Array Aliasing

[[0]*4]*3 creates 3 references to the same inner list. Changing grid[0][1] would also change grid[1][1] and grid[2][1]. Always use the list comprehension form: [[0]*4 for _ in range(3)]

List Comprehension (Pythonic)

python

# Squares of 0..9
squares = [x**2 for x in range(10)]
# [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

# Even numbers only
evens = [x for x in range(20) if x % 2 == 0]
# [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

# 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]

Accessing & Updating Elements

Index Access — O(1)

python

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

# Forward indexing (0-based)
print(arr[0])   # 10
print(arr[2])   # 30
print(arr[4])   # 50

# Negative indexing (from end)
print(arr[-1])  # 50  (last)
print(arr[-2])  # 40  (second-to-last)
print(arr[-5])  # 10  (same as arr[0])

Slicing — O(k) where k = slice length

python

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

arr[2:5]      # [2, 3, 4]        → arr[start:stop] (stop excluded)
arr[:4]       # [0, 1, 2, 3]     → from beginning
arr[6:]       # [6, 7, 8, 9]     → to end
arr[::2]      # [0, 2, 4, 6, 8]  → every 2nd element
arr[1::2]     # [1, 3, 5, 7, 9]  → odd indices
arr[::-1]     # [9,8,7,6,5,4,3,2,1,0] → reverse
arr[2:8:3]    # [2, 5]           → start=2, stop=8, step=3

📌 Slicing creates a new list

Slicing always returns a shallow copy — modifying the slice does NOT affect the original array. Use arr[start:stop] = new_vals to modify in-place.

Updating Elements — O(1)

python

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

# Update single element
arr[2] = 99
print(arr)  # [10, 20, 99, 40, 50]

# Update via negative index
arr[-1] = 0
print(arr)  # [10, 20, 99, 40, 0]

# Update a slice (in-place replacement)
arr[1:3] = [200, 300]
print(arr)  # [10, 200, 300, 40, 0]

# Delete a slice
del arr[1:3]
print(arr)  # [10, 40, 0]

Checking Membership — O(n)

python

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

print(3 in arr)     # True
print(10 in arr)    # False
print(10 not in arr)# True

# Get index
idx = arr.index(3)  # 2  → raises ValueError if not found

# Safe check
if 3 in arr:
    idx = arr.index(3)  # only call after confirming it exists

Iterating Over Arrays

Basic for loop

python

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

# Iterate over values
for val in arr:
    print(val)
# 10 20 30 40 50

With index — enumerate()

python

arr = ['a', 'b', 'c', 'd']

for i, val in enumerate(arr):
    print(f"arr[{i}] = {val}")
# arr[0] = a
# arr[1] = b
# arr[2] = c
# arr[3] = d

# Start index from 1
for i, val in enumerate(arr, start=1):
    print(f"{i}. {val}")
# 1. a   2. b   3. c   4. d

Reverse iteration

python

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

# Method 1: reversed() — no copy
for val in reversed(arr):
    print(val)   # 5 4 3 2 1

# Method 2: negative step slice — creates copy
for val in arr[::-1]:
    print(val)   # 5 4 3 2 1

# Method 3: range with step -1
for i in range(len(arr)-1, -1, -1):
    print(arr[i])

Two-pointer iteration (common in DSA)

python

arr = [1, 2, 3, 4, 5]
left, right = 0, len(arr) - 1

while left < right:
    print(arr[left], arr[right])
    left += 1
    right -= 1
# 1 5
# 2 4
# 3 (middle — not printed, left == right)

2D Array iteration

python

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Row by row
for row in matrix:
    for val in row:
        print(val, end=' ')
    print()

# With indices
for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        print(f"matrix[{i}][{j}] = {matrix[i][j]}")

Iterating two arrays together — zip()

python

names = ["Alice", "Bob", "Charlie"]
scores = [95, 87, 92]

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

Built-in Methods & Functions

Python provides a rich set of list methods. Know their time complexities — they matter in interviews.

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)`
`index(x)`	Return first index of x	O(n)	`arr.index(7)`
`count(x)`	Count occurrences of x	O(n)	`arr.count(2)`
`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()`
`copy()`	Shallow copy	O(n)	`b = arr.copy()`
`extend(iterable)`	Append all items from iterable	O(k)	`arr.extend([1,2,3])`
`clear()`	Remove all elements	O(n)	`arr.clear()`
`len(arr)`	Number of elements (built-in fn)	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)`

Code Examples for Key Methods

python

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

# append / pop  (O(1) each)
arr.append(7)         # [3,1,4,1,5,9,2,6,7]
last = arr.pop()      # last=7, arr=[3,1,4,1,5,9,2,6]

# insert / pop(i)  (O(n) each)
arr.insert(0, 0)      # [0,3,1,4,1,5,9,2,6]
first = arr.pop(0)    # first=0, arr=[3,1,4,1,5,9,2,6]

# sort variants
arr.sort()            # in-place → [1,1,2,3,4,5,6,9]
arr.sort(reverse=True)# in-place → [9,6,5,4,3,2,1,1]
sorted_arr = sorted(arr)   # new list, arr unchanged

# sort by custom key
words = ["banana", "apple", "fig", "cherry"]
words.sort(key=len)   # sort by string length
# ["fig", "apple", "banana", "cherry"]

# reverse
arr.reverse()         # in-place reverse

# stats
print(min(arr))       # minimum value
print(max(arr))       # maximum value
print(sum(arr))       # sum of all
print(len(arr))       # count of elements

Common DSA Patterns with Arrays

Pattern 1Two Pointers

Use two indices moving toward or away from each other. Common for: finding pairs, palindrome check, removing duplicates from sorted array.

python

# Two Sum II — sorted array, find pair that sums to target
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    # need larger sum
        else:
            right -= 1   # need smaller sum
    return []

# Time: O(n)  |  Space: O(1)

Pattern 2Sliding Window

Maintain a window of fixed or variable size as you slide across the array. Avoids nested loops — reduces O(n²) to O(n).

python

# Maximum sum of subarray of size k
def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1

    window_sum = sum(arr[:k])  # initial window
    max_sum = window_sum

    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]  # slide
        max_sum = max(max_sum, window_sum)

    return max_sum

# Time: O(n)  |  Space: O(1)
print(max_sum_subarray([2,1,5,1,3,2], 3))  # 9

Pattern 3Prefix Sum

Precompute cumulative sums so that any range sum query is answered in O(1). Essential for subarray problems.

python

# Build prefix sum array
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]
# prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]

# Range sum query: sum of arr[l..r] in O(1)
def range_sum(l, r):
    return prefix[r+1] - prefix[l]

print(range_sum(1, 4))  # 1+4+1+5 = 11

Pattern 4Kadane's Algorithm

Find the maximum sum contiguous subarray in O(n). Classic dynamic programming on arrays.

python

# Maximum Subarray (LeetCode 53)
def max_subarray(arr):
    max_sum = arr[0]
    current_sum = arr[0]

    for num in arr[1:]:
        # Either extend current subarray or start fresh
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)

    return max_sum

print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))  # 6
# Subarray: [4, -1, 2, 1]

Pattern 5Dutch National Flag (3-way partition)

Sort an array of 0s, 1s, and 2s in a single pass without extra space.

python

# Sort Colors (LeetCode 75)
def sort_colors(arr):
    low, mid, high = 0, 0, len(arr) - 1

    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:  # arr[mid] == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
    return arr

print(sort_colors([2,0,2,1,1,0]))  # [0,0,1,1,2,2]
# Time: O(n)  |  Space: O(1)

Pattern 6Binary Search on Arrays

Search a sorted array in O(log n). Learn both iterative and recursive forms.

python

# Binary Search — iterative (preferred)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # avoids overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1   # not found

arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7))   # 3
print(binary_search(arr, 6))   # -1

Time & Space Complexity

Knowing the complexity of each operation tells you when to use (or avoid) arrays.

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

✅ When to use Arrays

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

🚫 When NOT to use Arrays

Frequent insertions/deletions at front
Need O(1) search by value → use Set/HashMap
Unknown/dynamic size with lots of resizing
FIFO/LIFO patterns → use deque/stack

← Back to DSA Overview Next: Strings →

Arrays — The Foundation of Every Algorithm

What is an Array?

Creation & Initialization

Empty Array

Array with Initial Values

Pre-filled Arrays

List Comprehension (Pythonic)

Accessing & Updating Elements

Index Access — O(1)

Slicing — O(k) where k = slice length

Updating Elements — O(1)

Checking Membership — O(n)

Iterating Over Arrays

Basic for loop

With index — enumerate()

Reverse iteration

Two-pointer iteration (common in DSA)

2D Array iteration

Iterating two arrays together — zip()

Built-in Methods & Functions

Code Examples for Key Methods

Common DSA Patterns with Arrays

Time & Space Complexity

Arrays — The Foundation of
Every Algorithm