Array Field Notes

0Why arrays are the first data structure

A data structure is a way to store data efficiently inside RAM (Random Access Memory, usually just called "memory"). An array is the simplest one: an ordered collection of contiguous elements. Contiguous means "side by side in memory, with no gaps". Everything else on this page - reading, inserting, deleting, growing, stacking - follows from that one property.

The four lessons build on each other: lesson 1 shows what RAM looks like, lesson 2 does the four operations on a fixed-size array, lesson 3 makes the array grow, and lesson 4 restricts it to one end and calls it a stack.

1RAM: where the array lives

Bits, bytes, gigabytes

Computers only understand bits: 0s and 1s. A byte is 8 bits. A laptop may have 8 GB of RAM, which is 8 × 1024 × 1024 × 1024 bytes (about 8.6 billion slots). Each integer has a binary representation: the same number written with only 0s and 1s. Using one byte each:

format(1, "08b")   # '00000001'
format(3, "08b")   # '00000011'
format(5, "08b")   # '00000101'
bin(5)             # '0b101'  (Python drops the leading zeros)

Addresses: every value has a location

When we store [1, 3, 5] in RAM, each element is stored contiguously (continuously, in order). Each value gets an address: a distinct location, written here as $0, $4, $8. Integers commonly occupy 4 bytes (32 bits), so integer addresses are 4 bytes apart. Characters occupy 1 byte each, so a char array has addresses 1 byte apart.

The address formula in Python, tested on both arrays:

def address_of(start, i, size):
    # address of element i when each element takes `size` bytes
    return start + i * size

[address_of(0, i, 4) for i in range(3)]   # [0, 4, 8]   int array
[address_of(0, i, 1) for i in range(3)]   # [0, 1, 2]   char array
address_of(100, 2, 4)                       # 108: works from any start

Lesson 1 is mostly theory. The next three lessons cover the operations, their efficiency, and where you use them.

2Static arrays: fixed size, four operations

In statically typed languages (Java, C++, C#) an array must be given a size and a type when it is created. That is a static array: its size cannot change once declared, and once it is full you cannot store more. Python and JavaScript do not have static arrays; their default array is a dynamic array (section 3). We still use Python here and simulate the fixed size with two extra numbers: length and capacity.

Reading: O(1)

myArray = [1, 3, 5]
myArray[i]      # access the element at index i
myArray[0]      # 1
myArray[2]      # 5

Accessing a single element is always instant, because each index maps to an address in RAM (section 1). Regardless of the array's size, the time is the same: O(1), "constant time".

Traversing: O(n)

Traverse means "visit every element from first to last". Two equivalent loops:

for i in range(len(myArray)):
    print(myArray[i])

# OR
i = 0
while i < len(myArray):
    print(myArray[i])
    i += 1

The last element is at index n - 1, where n is the size. Size 3 → last index 2. Both loops stop before index 3, because range(3) gives 0, 1, 2 and i < 3 fails at 3. Traversal is O(n): the number of operations grows linearly with the size. 10 elements → 10 operations, 100 elements → 100 operations.

Deleting from the end: O(1)

In statically typed languages every index is filled with 0 (or some default value like null or -1) when the array is created. So "removing" the last element is a soft delete: overwrite it with the default and consider the length reduced by 1. The slot still exists; we simply stop counting it.

# Remove from the last position in the array if the array
# is not empty (i.e. length is non-zero).
def removeEnd(arr, length):
    if length > 0:
        # Overwrite last element with some default value.
        # We would also consider the length to be decreased by 1.
        arr[length - 1] = 0

arr = [4, 5, 6]
removeEnd(arr, 3)     # arr is now [4, 5, 0], length is treated as 2
removeEnd(arr, 0)     # empty: nothing happens

NeetCode's version does not return the new length, so a version that does (this is what "we would consider the length decreased" means in practice):

def removeEnd2(arr, length):
    if length > 0:
        arr[length - 1] = 0
        length -= 1
    return length          # removeEnd2([4,5,6], 3) → 2

Deleting at index i: shift left, O(n)

Naively writing 0 into the middle would break the contiguous nature of the array: you would have a hole, and every later read would have to skip it. Deleting from the end keeps the array contiguous; deleting from the middle does not. The fix is to close the hole by moving everything after it one step left:

1. Given the deletion index i.
2. Iterate from i + 1 to the end.
3. Shift each element 1 position to the left.
4. (Optional) replace the last element with 0 / None and decrement the length.

# Remove value at index i before shifting elements to the left.
# Assuming i is a valid index.
def removeMiddle(arr, i, length):
    # Shift starting from i + 1 to end.
    for index in range(i + 1, length):
        arr[index - 1] = arr[index]
    # No need to 'remove' arr[i], since we already shifted

arr = [4, 5, 6, 7, 8]
removeMiddle(arr, 1, 5)    # arr is now [4, 6, 7, 8, 8]; length is treated as 4

Inserting at the end: O(1)

The next open position is always index length. If there is room (length is below capacity), write there.

# Insert n into arr at the next open position.
# Length is the number of 'real' values in arr, and capacity
# is the size (aka memory allocated for the fixed size array).
def insertEnd(arr, n, length, capacity):
    if length < capacity:
        arr[length] = n

arr = [4, 5, 0, 0]           # length 2, capacity 4
insertEnd(arr, 6, 2, 4)      # [4, 5, 6, 0]
insertEnd(arr, 7, 3, 4)      # [4, 5, 6, 7]
insertEnd(arr, 8, 4, 4)      # full: nothing happens

Inserting at index i: shift right, O(n)

Consider [4, 5, 6] and insert at i = 1 or i = 0. You cannot simply overwrite arr[i]: that value would be lost. Instead, shift every value from index i onward one position to the right, starting from the end, then write the new value at i.

# Insert n into index i after shifting elements to the right.
# Assuming i is a valid index and arr is not full.
def insertMiddle(arr, i, n, length):
    # Shift starting from the end to i.
    for index in range(length - 1, i - 1, -1):
        arr[index + 1] = arr[index]
    # Insert at i
    arr[i] = n

arr = [4, 5, 6, 0]           # length 3, one spare slot
insertMiddle(arr, 1, 8, 3)   # [4, 8, 5, 6]
arr = [4, 5, 6, 0]
insertMiddle(arr, 0, 8, 3)   # [8, 4, 5, 6]  worst case: every element moved

NeetCode's example goes one step further: insert 8 at index 1 into [4, 5, 6] when there is no spare capacity. The shifting still happens before the insert, so no value is overwritten by the 8, but the last element 6 has nowhere to go. It falls off the end and is lost.

In real Python

Python's list does the shifting for you, but the cost is the same. Know which methods hide an O(n) shift:

lst = [4, 5, 6]
lst.insert(1, 8)    # [4, 8, 5, 6]   shift right: O(n)
lst.pop(1)          # [4, 5, 6]      shift left:  O(n)
lst.pop()           # [4, 5]         end: O(1)
del lst[0]          # [5]            shift left:  O(n)
lst.append(9)       # [5, 9]         end: O(1)*  (star explained in section 3)

Time complexity of a static array

These operations are critical for many interview problems. The key to a lot of them is doing insert-middle and delete-middle efficiently, usually by avoiding the shift entirely (see the two-pointer pattern in section 5).

3Dynamic arrays: the array that grows

A dynamic array grows as elements are added. It is much more common than a static array, and it is the default array in Python and JavaScript: no size needed when you create it. Some languages assign a default starting size (Java 10, C# 4) and resize automatically at runtime. Under the hood a dynamic array is a static array plus a rule for what to do when it is full.

Insertion at the end: pushback

# Insert n in the last position of the array
def pushback(self, n):
    if self.length == self.capacity:
        self.resize()
    # insert at next empty position
    self.arr[self.length] = n
    self.length += 1

Resize: copy into a bigger static array

Resizing means allocating a new static array that is double the size of the original (size 3 → size 6), copying every value across, and pointing self.arr at the new one. After the copy, the first static array is deallocated (its memory is given back).

def resize(self):
    # Create new array of double capacity
    self.capacity = 2 * self.capacity
    newArr = [0] * self.capacity
    # Copy elements to newArr
    for i in range(self.length):
        newArr[i] = self.arr[i]
    self.arr = newArr

The full class (NeetCode's "Design Dynamic Array")

class DynamicArray:
    def __init__(self, capacity=1):
        self.capacity = capacity
        self.length = 0
        self.arr = [0] * capacity

    def get(self, i):
        return self.arr[i]

    def set(self, i, n):
        self.arr[i] = n

    # Insert n in the last position of the array
    def pushback(self, n):
        if self.length == self.capacity:
            self.resize()
        # insert at next empty position
        self.arr[self.length] = n
        self.length += 1

    def popback(self):
        if self.length > 0:
            self.length -= 1          # soft delete: the value stays, length hides it
        return self.arr[self.length]

    def resize(self):
        # Create new array of double capacity
        self.capacity = 2 * self.capacity
        newArr = [0] * self.capacity
        # Copy elements to newArr
        for i in range(self.length):
            newArr[i] = self.arr[i]
        self.arr = newArr

    def getSize(self):
        return self.length

    def getCapacity(self):
        return self.capacity

d = DynamicArray(3)
for v in [1, 3, 5]:
    d.pushback(v)              # size 3, capacity 3
d.pushback(7)                  # full → resize to 6, then insert: size 4, capacity 6

Amortized O(1): the honest average

Adding an element runs in O(1) amortized time. Amortized means "averaged over a whole sequence of operations". A single resize is O(n), but a resize is not performed on every push, so the average cost per push works out to O(1). This is only true because we double the size when we run out of space. Grow by a fixed amount (say +1 or +10) and you would resize almost every time, and the average would become O(n).

Why double? Count the operations

Start with capacity 1 and push until the array has size 8. The capacities go 1 → 2 → 4 → 8. Count every write, both the pushes and the copies during resizes:

def build_cost(n):
    # count every write (pushes + copies) while pushing n items,
    # starting from capacity 1 and doubling
    cap, length, writes = 1, 0, 0
    for _ in range(n):
        if length == cap:
            writes += length        # copy every existing element
            cap *= 2
        writes += 1                 # the push itself
        length += 1
    return writes

build_cost(8)        # 15  = 8 pushes + (1 + 2 + 4) copies
build_cost(1024)     # 2047 = 2n - 1, still under 2n

Other operations

Insert or remove in the middle of a dynamic array works exactly like the static array: shift elements, O(n). Growing does not help you there; the shift is about keeping the array contiguous, not about space.

Time complexity of a dynamic array

In Python, list is a dynamic array. append is the pushback, pop() is the popback, and the resize happens inside the interpreter (CPython over-allocates by roughly 12.5% instead of doubling, which keeps the same amortized O(1) result).

4Stacks: a dynamic array with one door

A stack supports a subset of the dynamic array operations: add and remove only from one end, called the top. Stacks are dynamic (they grow) and LIFO: Last In, First Out. The last element added is the first one out. There are exactly three operations: push, pop, peek. Compare with a queue (next topic), which is FIFO.

Push: append to the end

Adding to the top is the same as appending to the end of a dynamic array. O(1). Visualize the stack as a vertical array; the top pointer always moves to the item added most recently.

def push(self, n):
    # using the pushback function from dynamic arrays to add to the stack
    self.stack.append(n)

Pop: read and remove the end

Removing from the top is reading and removing the last element of the dynamic array. O(1). Check that the stack is not empty before popping, or Python raises IndexError: pop from empty list.

def pop(self):
    return self.stack.pop()

Peek: look, do not remove

Returns the top element without removing it. O(1). Some languages call it top().

def peek(self):
    return self.stack[-1]

The full class

Many languages have no built-in stack type, so a dynamic array is used directly. In Python a plain list is the standard stack. A class makes the three operations explicit:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, n):
        # using the pushback function from dynamic arrays to add to the stack
        self.stack.append(n)

    def pop(self):
        return self.stack.pop()

    def peek(self):
        return self.stack[-1]

    def isEmpty(self):
        return len(self.stack) == 0

s = Stack()
for v in [1, 2, 3, 4]:
    s.push(v)                # stack is [1, 2, 3, 4], top is 4
s.peek()                     # 4, stack unchanged
s.pop()                      # 4, stack is [1, 2, 3]
s.pop()                      # 3
s.peek()                     # 2

def safe_pop(stack):
    if not stack:          # empty list is falsy
        return None
    return stack.pop()

A stack reverses things

Because a stack removes in the reverse order of insertion, it can be used to reverse any sequence. Push every character of a string, then pop until empty: the characters come back out backwards.

def reverse_string(s):
    stack = []
    for ch in s:
        stack.append(ch)          # push: "n", "e", "e", "t"
    out = []
    while stack:
        out.append(stack.pop())   # pop:  "t", "e", "e", "n"
    return "".join(out)

reverse_string("neet")     # 'teen'
reverse_string("abc")      # 'cba'

Time complexity of a stack

5Four moves that solve most array problems

The lessons teach the structure. Interviews test these moves on top of it. Each one exists to avoid an O(n) shift or an O(n²) double loop.

Move 1: Two pointers (a slow writer and a fast reader)

When to use: "remove / keep / compact elements in place, O(1) extra space". L marks where the next kept value goes; R scans every element. Nothing shifts, because you overwrite as you go.

# LeetCode 26: Remove Duplicates from Sorted Array
def removeDuplicates(nums):
    if not nums:
        return 0
    L = 0                               # index of the last unique value written
    for R in range(1, len(nums)):
        if nums[R] != nums[L]:          # found a new value
            L += 1
            nums[L] = nums[R]           # write it right after the last unique
    return L + 1                        # count of unique values; nums[:L+1] is the answer

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
removeDuplicates(nums)      # 5, and nums[:5] == [0, 1, 2, 3, 4]

The same move from both ends reverses an array in place, which is the array version of what the stack did to the string:

def reverse_in_place(arr):
    L, R = 0, len(arr) - 1
    while L < R:
        arr[L], arr[R] = arr[R], arr[L]   # Python swap, no temp variable
        L += 1
        R -= 1
    return arr

reverse_in_place([1, 3, 5])     # [5, 3, 1]

Move 2: Sliding window

When to use: "best / longest / sum of a contiguous run". Keep a window [L, R]; when R moves right, update the answer with one add and one drop instead of re-summing the whole window.

# fixed-size window: largest sum of any k neighbors
def max_sum_window(arr, k):
    window = sum(arr[:k])
    best = window
    for R in range(k, len(arr)):
        window += arr[R] - arr[R - k]   # add the new right cell, drop the old left cell
        best = max(best, window)
    return best

max_sum_window([2, 1, 5, 1, 3, 2], 3)    # 9  (5 + 1 + 3)

The window can also have a variable size. LeetCode 121 keeps L at the cheapest day seen so far and slides it forward only when a cheaper day appears:

# LeetCode 121: Best Time to Buy and Sell Stock
def maxProfit(prices):
    L, best = 0, 0                      # L = cheapest day so far
    for R in range(1, len(prices)):
        if prices[R] < prices[L]:
            L = R                       # found a cheaper buy day: slide the window start
        else:
            best = max(best, prices[R] - prices[L])
    return best

maxProfit([7, 1, 5, 3, 6, 4])    # 5  (buy at 1, sell at 6)
maxProfit([7, 6, 4, 3, 1])       # 0  (never profitable)

Move 3: Prefix sum

When to use: "sum of a range, asked many times". Precompute prefix[i] = sum of the first i elements. Then any range sum is one subtraction. O(n) to build, O(1) per query.

# LeetCode 303: Range Sum Query - Immutable
class NumArray:
    def __init__(self, nums):
        self.prefix = [0]                   # prefix[i] = nums[0] + ... + nums[i-1]
        for n in nums:
            self.prefix.append(self.prefix[-1] + n)

    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

na = NumArray([-2, 0, 3, -5, 2, -1])
na.prefix              # [0, -2, -2, 1, -4, -2, -3]
na.sumRange(0, 2)      # 1   = prefix[3] - prefix[0]
na.sumRange(2, 5)      # -1  = prefix[6] - prefix[2]

The leading 0 is what makes sumRange(0, r) work without a special case. Always start the prefix array with it.

Move 4: A stack for matching and reversal

When to use: "does this close what was most recently opened?" (brackets, tags, undo) or "process things in reverse order". The stack holds the open items; the top is always the most recent one.

# LeetCode 20: Valid Parentheses
def isValid(s):
    stack = []
    close_to_open = {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in close_to_open:                     # a closing bracket
            if stack and stack[-1] == close_to_open[ch]:
                stack.pop()                         # it matches the most recent open
            else:
                return False                        # wrong type, or nothing open
        else:                                       # an opening bracket
            stack.append(ch)
    return not stack                                # valid only if everything was closed

isValid("{[]}")     # True
isValid("([)]")     # False
isValid("(")        # False: one bracket left open

A second stack that remembers the minimum at every level turns "what is the smallest thing in the stack?" into an O(1) peek:

# LeetCode 155: Min Stack
class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []          # minStack[-1] is the min of everything in stack

    def push(self, val):
        self.stack.append(val)
        val = min(val, self.minStack[-1] if self.minStack else val)
        self.minStack.append(val)

    def pop(self):
        self.stack.pop()
        self.minStack.pop()         # both stacks always have the same height

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.minStack[-1]

ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
ms.getMin()      # -3
ms.pop()
ms.top()         # 0
ms.getMin()      # -2

6Big-O summary

Say these out loud in interviews. Every star has a one-line reason; give the reason without being asked.

* amortized: a single push can cost O(n) when it triggers a resize, but n pushes cost at most 2n writes, so the average is O(1). ** O(1) only after checking the stack is not empty; an empty pop or peek is an error, not a slow operation. NeetCode writes the static-array table the other way round (Insertion O(n)*, "O(1) if at the end") - same facts, different default.

7Mistakes to watch for

8Practice, in this order

Notes do not make you good at this. Solving does. Do these with no notes open, then compare with the templates above. The first row is NeetCode's own exercise and has no LeetCode number.

Your next step today: LeetCode 26. Write it from memory with L and R, run it on [0,0,1,1,1,2,2,3,3,4], then reread the two-pointer diagram and compare.

9Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.