Arrays

Arrays are the foundation of data structures. They store elements in a contiguous block of memory and are indexed starting from zero. Because elements sit next to each other in memory, arrays offer extremely fast random access — but that same contiguity is what makes insertion and deletion in the middle expensive.

Static vs. Dynamic Arrays

Static arrays (like C's int arr[5]) have a fixed size decided at compile time. They live on the stack (or in a fixed memory region) and cannot grow.

Dynamic arrays (like C++'s std::vector, Python's list, or Java's ArrayList) can resize themselves. Under the hood, when a dynamic array runs out of space, it allocates a new, larger block (typically double the current capacity), copies all existing elements over, and frees the old block. This is why appending to a dynamic array is amortized O(1) — most appends are O(1), but occasionally one costs O(n) during a resize.

Basic Operations & Time Complexity

Operation	Static Array	Dynamic Array
Access by index	O(1)	O(1)
Update by index	O(1)	O(1)
Insert/Delete at end	N/A (fixed size)	Amortized O(1)
Insert/Delete at start or middle	O(n)	O(n)
Search (unsorted)	O(n)	O(n)
Search (sorted, binary search)	O(log n)	O(log n)

Memory Layout Illustration

Why Insertion/Deletion in the Middle is O(n)

Because array elements must stay contiguous, inserting or removing an element at index i requires shifting every element after i by one position — an operation proportional to the number of remaining elements.

C++ Example: Declaring & Iterating

array_basics.cpp

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5};

    cout << "Array elements: ";
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Python Example: Common Array Patterns

array_patterns.py

# 1. Reversing an array in place (two-pointer)
def reverse(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

# 2. Finding the maximum subarray sum (Kadane's Algorithm) — O(n)
def max_subarray_sum(arr):
    max_sum = current_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

# 3. Prefix sums for O(1) range sum queries after O(n) preprocessing
def build_prefix_sums(arr):
    prefix = [0] * (len(arr) + 1)
    for i, num in enumerate(arr):
        prefix[i + 1] = prefix[i] + num
    return prefix  # sum(arr[i:j]) == prefix[j] - prefix[i]

Common Array Techniques to Master

Two Pointers — converging or diverging pointers to solve pair-sum, reversal, and partition problems in O(n).
Sliding Window — maintaining a moving subrange to solve subarray/substring problems in O(n) instead of O(n²).
Prefix Sums — precomputing cumulative sums to answer range-sum queries in O(1).
Kadane's Algorithm — a dynamic programming technique for maximum subarray sum problems.
In-place manipulation — reversing, rotating, or partitioning without using extra space.

Quiz

What is the time complexity to access the 3rd element of an array?

A. O(1)
B. O(n)
C. O(log n)
D. O(n log n)

Practice on LeetCode

Once you're comfortable with the concepts above, try solving these problems to reinforce your understanding:

Easy 1. Two Sum — classic hash map + array lookup.
Easy 121. Best Time to Buy and Sell Stock — single-pass array tracking.
Medium 53. Maximum Subarray — apply Kadane's Algorithm.
Medium 238. Product of Array Except Self — prefix/suffix product technique.
Medium 15. 3Sum — sorting + two-pointer technique.

← Back to DSA