Arrays in Data Structures: Operations, Costs and Patterns

An array is the data structure almost every coding problem hands you its input in. Knowing exactly what it makes cheap and what it makes expensive lets you reject a slow idea before you write it, and a few one-pass patterns over an array solve a surprising share of interview questions. If Big-O is new to you, read Time and Space Complexity first.

How an array is stored

An array keeps its elements contiguously: one unbroken block of memory, in index order, every element the same size. Everything else in this lesson follows from that one fact.

1. The elements sit side by side in one block, in index order, each taking the same 4 bytes. So the address of any element is the start of the block plus its index times 4.
2. Reading arr[3] is one multiplication and one addition: 1000 + 3 × 4 = 1012. Elements 0 to 2 are never looked at, so any index costs the same — O(1). The first element is zero steps from the start, hence index 0.
3. The price: the block was sized when the array was made, and the bytes just after it, from 1020 on, may belong to something else. A plain array cannot grow in place — it has a fixed length.

The address formula is why indexing is O(1) and why indexes start at 0. Contiguity has a second benefit: memory reaches the processor in 64-byte cache lines, so a loop that walks an array in order beats one that jumps around memory, even when both are O(n). Step outside the block and C++ gives undefined behaviour, Java and Python throw, and JavaScript quietly returns undefined.

The operations and their cost

Inserting is the expensive one, because the block must stay unbroken and in order:

1. To put 9 at index 1, the block must stay unbroken and in order, so everything from index 1 onwards has to move one place right first — into the spare slot at the end.
2. Start from the back: 6 moves from index 4 to 5. Moving the front first would overwrite a value before it had been copied.
3. 3 moves from index 3 to 4, into the slot the previous move just emptied.
4. 5 moves from index 2 to 3, into the slot the previous move just emptied.
5. 1 moves from index 1 to 2, into the slot the previous move just emptied. Index 1 is free now.
6. 9 goes into index 1: 4 values moved for one insert. Inserting at index i moves n − i values, so the front costs O(n) and the end costs nothing. Deleting is the mirror image, shifting left.

When order does not matter, deleting has a shortcut: copy the last element into the gap and drop the last slot, O(1).

Dynamic arrays in each language

Most of the time you use a dynamic array — vector<int> in C++, ArrayList in Java, Python's list, a JavaScript Array — which hides the fixed length. When an append finds the block full, it moves everything to a block about twice as big:

1. The first append: 5 goes into a block with room for one. A dynamic array keeps a size (slots in use) and a capacity (slots in the block).
2. Appending 3 finds the block full. A block twice as big (2) is allocated, the 1 value already stored is copied across, and 3 goes in after it.
3. Appending 8 finds the block full. A block twice as big (4) is allocated, the 2 values already stored are copied across, and 8 goes in after them.
4. 1 fits in the spare slot: no copying at all. Most appends are like this — one write, O(1).
5. Appending 9 finds the block full. A block twice as big (8) is allocated, the 4 values already stored are copied across, and 9 goes in after them.
6. The last three appends fit without copying. 8 appends cost 7 copies in all, 1 + 2 + 4. Because the block doubles, the copies always total less than 2n, so n appends are O(n) work: amortised O(1) each.

Because the capacity grows by a factor, not a fixed amount, n appends cost O(n) in total: amortised O(1) each. The Big-O lesson proves it in general. Two traps: Java's ArrayList<Integer> stores boxed objects, several times the memory of an int[], and JavaScript's shift and unshift work at the front, so they are O(n).

The single pass with state

Many problems that seem to need every pair of elements fall to one pass that carries the right state: a few variables summarising everything left of the current index. The classic is Best Time to Buy and Sell Stock: buy on one day, sell on a later one, and find the largest profit, or 0. Trying every pair of days is about 5 × 10⁹ checks when n = 10⁵. The pattern's rules:

• Decide what you need to know about the prefix — here, the cheapest price so far.
• Keep exactly that in variables, updated in O(1) per element.
• Use the state before adding the current element to it, when an element must not pair with itself.

1. Selling on day i earns prices[i] minus the cheapest price before it. So one pass only has to remember two numbers: the cheapest price so far and the best profit so far.
2. Day 0 costs 7. Nothing came before it, so 7 is the cheapest price so far and there is nothing to sell yet.
3. Day 1 costs 1, below the old cheapest 7, so day 1 becomes the day to buy. Selling on the day you buy earns nothing, and the best profit stays 0.
4. Day 2 costs 5. Buying at the cheapest earlier price (1, day 1) and selling today earns 5 − 1 = 4, so best = 4. Earlier days other than the cheapest can be forgotten: none of them is a better day to buy.
5. Day 3 costs 3: selling today would earn 2, less than the best 4, and 3 is not below 1, so neither number changes.
6. Day 4 costs 6. Buying at the cheapest earlier price (1, day 1) and selling today earns 6 − 1 = 5, so best = 5.
7. Day 5 costs 4: selling today would earn 3, less than the best 5, and 4 is not below 1, so neither number changes.
8. The best trade is to buy on day 1 at 1 and sell on day 4 at 6, a profit of 5. Each day was looked at once with two numbers kept, so it is O(n) time and O(1) space.

Why the running minimum is enough

A shortcut is only safe if it never skips the best answer. Fix the sell day: every trade selling that day subtracts its buy price from the same sell price, so the cheapest earlier day beats all the others.

1. Each cell is one trade: buy on the row's day, sell on the column's later day, profit written in. Trying every pair means all 15 cells — about n²/2, five billion when n = 100,000.
2. Selling at 1 (day 1) has only one possible buy day, at 7. Keep it.
3. Every cell in the "sell at 5" column subtracts from the same 5, so the row with the cheapest earlier price, 1, wins. The other 1 can never be the answer.
4. Every cell in the "sell at 3" column subtracts from the same 3, so the row with the cheapest earlier price, 1, wins. The other 2 can never be the answer.
5. Every cell in the "sell at 6" column subtracts from the same 6, so the row with the cheapest earlier price, 1, wins. The other 3 can never be the answer.
6. Every cell in the "sell at 4" column subtracts from the same 4, so the row with the cheapest earlier price, 1, wins. The other 4 can never be the answer.
7. One kept cell per column, and the best of them, 5, is the answer. The cheapest earlier price is exactly what a running minimum holds when the pass reaches each day — n candidates instead of n²/2.

As an invariant: after day i, minPrice is the cheapest price of days 0 to i and best the largest profit of any trade selling by day i. Both hold after day 0 and each step keeps them. It also shows why "highest minus lowest" is wrong: the highest price may come first.

The same shape gives a running total in Running Sum of 1d Array or a running maximum. Maximum Subarray carries a cleverer state, the best sum ending here: Kadane's algorithm.

The code

The program runs the pass on the example above and on a price list that only falls.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Best profit from one buy followed by one later sell; 0 if prices only fall.
int maxProfit(const vector<int>& prices) {
    int minPrice = prices[0];   // cheapest price seen so far
    int best = 0;               // best profit seen so far
    for (int i = 1; i < (int)prices.size(); i++) {
        best = max(best, prices[i] - minPrice);   // sell today, bought on the cheapest day before
        minPrice = min(minPrice, prices[i]);      // today may be the cheapest day for later sales
    }
    return best;
}

int main() {
    vector<vector<int>> examples = {{7, 1, 5, 3, 6, 4}, {7, 6, 4, 3, 1}};
    for (const vector<int>& prices : examples) {
        cout << "Prices";
        for (int p : prices) cout << " " << p;
        cout << ": best profit " << maxProfit(prices) << "\n";
    }
    return 0;
}

public class Main {
    // Best profit from one buy followed by one later sell; 0 if prices only fall.
    static int maxProfit(int[] prices) {
        int minPrice = prices[0];   // cheapest price seen so far
        int best = 0;               // best profit seen so far
        for (int i = 1; i < prices.length; i++) {
            best = Math.max(best, prices[i] - minPrice);   // sell today, bought on the cheapest day before
            minPrice = Math.min(minPrice, prices[i]);      // today may be the cheapest day for later sales
        }
        return best;
    }

    public static void main(String[] args) {
        int[][] examples = {{7, 1, 5, 3, 6, 4}, {7, 6, 4, 3, 1}};
        for (int[] prices : examples) {
            StringBuilder line = new StringBuilder("Prices");
            for (int p : prices) line.append(" ").append(p);
            line.append(": best profit ").append(maxProfit(prices));
            System.out.println(line);
        }
    }
}

def max_profit(prices):
    """Best profit from one buy followed by one later sell; 0 if prices only fall."""
    min_price = prices[0]   # cheapest price seen so far
    best = 0                # best profit seen so far
    for i in range(1, len(prices)):
        best = max(best, prices[i] - min_price)   # sell today, bought on the cheapest day before
        min_price = min(min_price, prices[i])     # today may be the cheapest day for later sales
    return best


examples = [[7, 1, 5, 3, 6, 4], [7, 6, 4, 3, 1]]
for prices in examples:
    print("Prices", *prices, end="")
    print(f": best profit {max_profit(prices)}")

// Best profit from one buy followed by one later sell; 0 if prices only fall.
function maxProfit(prices) {
  let minPrice = prices[0]; // cheapest price seen so far
  let best = 0; // best profit seen so far
  for (let i = 1; i < prices.length; i++) {
    best = Math.max(best, prices[i] - minPrice); // sell today, bought on the cheapest day before
    minPrice = Math.min(minPrice, prices[i]); // today may be the cheapest day for later sales
  }
  return best;
}

const examples = [
  [7, 1, 5, 3, 6, 4],
  [7, 6, 4, 3, 1],
];
for (const prices of examples) {
  console.log(`Prices ${prices.join(" ")}: best profit ${maxProfit(prices)}`);
}

Prices 7 1 5 3 6 4: best profit 5
Prices 7 6 4 3 1: best profit 0

Left and right passes

Some questions ask, for every index, about everything on both sides of it. Product of Array Except Self wants the product of every element except nums[i], in O(n) and without division (which breaks on zeros anyway). Multiplying the other n − 1 values per index is O(n²); splitting the question in two is O(n):

1. The product of everything except index 2 splits in two: everything to its left times everything to its right. Both halves are running products, and one pass can build each.
2. Pass 1 stores left products in answer itself. answer[0] = 1, since nothing is left of index 0; then answer[1] = answer[0] × nums[0] = 1 × 1 = 1.
3. answer[2] = answer[1] × nums[1] = 1 × 2 = 2: the product of everything left of index 2, from one multiplication.
4. answer[3] = answer[2] × nums[2] = 2 × 3 = 6: the product of everything left of index 3, from one multiplication.
5. Pass 2 walks back with one variable, right, the product of everything after i — 1 at the end. answer[3] = 6 × 1 = 6, then right picks up nums[3] and becomes 4.
6. answer[2] = 2 (left) × 4 (right) = 8, and right becomes 4 × 3 = 12.
7. answer[1] = 1 (left) × 12 (right) = 12, and right becomes 12 × 2 = 24.
8. answer[0] = 1 (left) × 24 (right) = 24, and right becomes 24 × 1 = 24.
9. answer = [24, 12, 8, 6]: two passes of n steps, no division, and only one extra variable besides the output. A zero in nums needs no special case — it simply sits in the left or right product.

The output array does not count as extra space by convention, so this is O(1) extra. The same left and right passes find the tallest bar on each side in Trapping Rain Water and the sums on either side in Find Pivot Index.

The code

#include <iostream>
#include <vector>
using namespace std;

// answer[i] = product of every element except nums[i], without division.
vector<int> productExceptSelf(const vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);
    for (int i = 1; i < n; i++)
        answer[i] = answer[i - 1] * nums[i - 1];   // left pass: product of everything before i
    int right = 1;                                 // product of everything after i
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= right;                        // left product times right product
        right *= nums[i];
    }
    return answer;
}

int main() {
    vector<vector<int>> examples = {{1, 2, 3, 4}, {-1, 1, 0, -3, 3}};
    for (const vector<int>& nums : examples) {
        vector<int> answer = productExceptSelf(nums);
        cout << "Input:";
        for (int x : nums) cout << " " << x;
        cout << " -> output:";
        for (int x : answer) cout << " " << x;
        cout << "\n";
    }
    return 0;
}

public class Main {
    // answer[i] = product of every element except nums[i], without division.
    static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        answer[0] = 1;
        for (int i = 1; i < n; i++)
            answer[i] = answer[i - 1] * nums[i - 1];   // left pass: product of everything before i
        int right = 1;                                 // product of everything after i
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= right;                        // left product times right product
            right *= nums[i];
        }
        return answer;
    }

    public static void main(String[] args) {
        int[][] examples = {{1, 2, 3, 4}, {-1, 1, 0, -3, 3}};
        for (int[] nums : examples) {
            int[] answer = productExceptSelf(nums);
            StringBuilder line = new StringBuilder("Input:");
            for (int x : nums) line.append(" ").append(x);
            line.append(" -> output:");
            for (int x : answer) line.append(" ").append(x);
            System.out.println(line);
        }
    }
}

def product_except_self(nums):
    """answer[i] = product of every element except nums[i], without division."""
    n = len(nums)
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]   # left pass: product of everything before i
    right = 1                                     # product of everything after i
    for i in range(n - 1, -1, -1):
        answer[i] *= right                        # left product times right product
        right *= nums[i]
    return answer


examples = [[1, 2, 3, 4], [-1, 1, 0, -3, 3]]
for nums in examples:
    print("Input:", *nums, "-> output:", *product_except_self(nums))

// answer[i] = product of every element except nums[i], without division.
function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  for (let i = 1; i < n; i++) {
    answer[i] = answer[i - 1] * nums[i - 1]; // left pass: product of everything before i
  }
  let right = 1; // product of everything after i
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= right; // left product times right product
    right *= nums[i];
  }
  return answer;
}

const examples = [
  [1, 2, 3, 4],
  [-1, 1, 0, -3, 3],
];
for (const nums of examples) {
  console.log(`Input: ${nums.join(" ")} -> output: ${productExceptSelf(nums).join(" ")}`);
}

Input: 1 2 3 4 -> output: 24 12 8 6
Input: -1 1 0 -3 3 -> output: 0 0 9 0 0

Editing in place

"In place" means changing the input instead of building a new array, so the extra space is O(1). The tools are swaps (reverse; rotate with three reversals, as in Rotate Array), a write index (the read-and-write two pointers behind Move Zeroes) and running updates such as nums[i] += nums[i - 1]. The danger in all of them is overwriting a value you still need to read:

1. Build Array from Permutation asks for ans[i] = nums[nums[i]]. The top row is the right answer, computed from an untouched copy. Now try writing each answer straight back into nums.
2. i = 0: nums[0] is 0, so ans[0] = nums[0] = 0. That is right, and writing it back into nums[0] changes nothing yet.
3. i = 1: nums[1] is 2, and nums[2] is 1, which matches. But writing 1 over index 1 erases the 2 that sat there — and a later index may look it up.
4. i = 2: nums[2] is 1, so it reads nums[1] — but that slot was overwritten at step 1 and now holds 1, not 2. The answer here should be 2: the in-place write destroyed a value still needed.
5. The fix is to never read a slot you have written: fill a second array ans (O(n) space), or keep both numbers in one slot with nums[i] += n × (nums[nums[i]] % n), then divide every slot by n (O(1) space).

The encoding works because every value is below n, so one slot holds the old value as the remainder and the new one as the quotient. Deleting while looping forwards fails the same way — the next element shifts into the current index and is skipped — so loop backwards, or use a write index.

Two-dimensional arrays

A grid with m rows and n columns is an array of arrays, grid[r][c]. Java, Python and JavaScript store each row as its own array; a fixed C-style int grid[m][n] is one block:

Rows outside, columns inside visits memory in order, O(m × n) — Richest Customer Wealth is one sum per row. In Python, never write [[0] * n] * m: it repeats one row object, so writing to one row writes to all; use [[0] * n for _ in range(m)]. Spirals and rotation are in the matrix lesson.

Time and space complexity

The brute force recomputes something for every index; the fast version computes it once and carries it along. That is the point of this stage.

How to recognise the pattern

• "Before" and "after" in a pair, such as buy before sell: a running minimum or maximum.
• "For each element, everything else": left and right passes.
• A range sum asked many times: prefix sums.
• "In place" or "O(1) extra space": a write index or swaps.
• A contiguous subarray with a best sum or a condition: Kadane's algorithm or a sliding window.
• "Have I seen this value before?": a hash map — Hashing.

Common mistakes

• Off by one at the ends. The last index is n − 1; a pass that reads i - 1 starts at 1.
• Empty input. prices[0] on an empty array crashes; guard when n = 0 is allowed.
• Front inserts inside a loop. Each is O(n), so the loop becomes O(n²).
• Overflow. 10⁵ values up to 10⁹ need 64 bits: long long in C++, long in Java.
• Aliasing. b = a names one array twice in Java, Python and JavaScript; copy with a.clone(), a[:] or a.slice().

Practice in this order

1. Running Sum of 1d Array: a running total, in place.
2. Concatenation of Array: indexing with an offset.
3. Build Array from Permutation: the overwrite trap and its encoding.
4. Richest Customer Wealth: one sum per row of a grid.
5. Contains Duplicate: sort and compare neighbours, or a set.
6. Best Time to Buy and Sell Stock: the running minimum.
7. Maximum Subarray: one pass with smarter state.
8. Product of Array Except Self: left and right passes.

Every array problem in the catalogue is on the array problem list, easiest first. When the first six feel routine, move on to Hashing.