Pointer arithmetic, arrays and pointer to pointer

Why this matters

Arrays are the first data structure most programmers meet, and most of the algorithms in an interview run over arrays. Two-pointer scans, binary search, sliding windows and in-place reversal all move through an array with indexes. Underneath the square brackets, the computer moves through memory with addresses. If you understand that movement, these algorithms stop looking like tricks and start looking like one idea used in several places.

This lesson does three things. It shows that an array name is really an address. It shows how to step through an array with a pointer, so you can see what a[i] means. Then it adds a second level of pointers, a pointer to a pointer, which you need for linked lists and for changing a value that another pointer holds.

The array is a row of boxes

Start with the picture from the last lesson. Memory is a long street of numbered slots. An array is a row of boxes placed next to each other on that street. The boxes have the same type, so they are the same size, and they sit back to back with no gap.

Take int a[5] = {10, 20, 30, 40, 50};. The five boxes each hold an int. An int is 4 bytes on most computers, so the whole array takes 20 bytes. If the first box starts at address 1000, the boxes start at 1000, 1004, 1008, 1012 and 1016. Each box is 4 bytes further on than the box before it.

The address of the first box is the address of the whole array. In C++ the name of an array, used without brackets, turns into the address of its first element. So a means the same as &a[0]. People say the array name decays into a pointer to its first element. You will see that word, decay, in interviews. It means the array name gives you a pointer to its first box.

Here is a table of the five boxes for the array above.

Look at the address column. Each step adds 4. That constant step is the reason arrays are fast. To find box number 3, the computer does not search. It starts at 1000, adds 3 times 4, and reads at 1012.

Five int boxes in a row with their indexes and addresses, and a p arrow over index 2

Pointer arithmetic

A pointer can be moved with + and -. This is called pointer arithmetic. The rule that makes it safe to use is this: adding 1 to a pointer moves it to the next element of its type, not the next byte. For an int* on a machine where int is 4 bytes, p + 1 is 4 bytes further on. p + 3 is 12 bytes further on.

The rule is about elements. You never write the byte count yourself. The compiler multiplies by sizeof the element for you. That is why the same code works for double arrays, whose elements are 8 bytes, and for char arrays, whose elements are 1 byte, without any change.

Here is the key identity of this lesson:

a[i] is the same as *(a + i)

The square bracket operator is shorthand. a[i] means go to the address a + i and read what is there. Read the expression from the inside out. a + i is an address, * follows it, and the result is the element.

Because of this identity, the expression i[a] is also legal. It means the same thing, because addition is commutative. Nobody writes it in real code, but it is a fun fact to know if an interviewer asks you what the brackets really do.

Index or pointer: how to choose

Both styles are correct, and experienced programmers use whichever reads best. An index says "the third element" with one number. That is clear when the loop needs the position itself. A pointer says "this element", and it suits a loop that walks a range, a loop where two positions move at different speeds, and a search whose answer is itself a position.

Use an index when you need the position as a number, for printing or for arithmetic on positions. The output found at index 3 in worked example 3 needs the number, so the program subtracts two pointers to get it.

Use a pointer when the code works on a range. A range is a pair of positions, a start and an end. The standard library works this way. std::sort takes two pointers, and it accepts any contiguous block, including part of an array. A function that takes int* first, int* last is more general than a function that takes an array and a length, because the caller decides which part of the array to work on.

In an interview, both styles are accepted. Say which one you chose and why in one sentence, then make sure the boundaries are right. Most bugs in array code are off-by-one errors, and they happen in either style.

Worked example 1: sum with a pointer

We can walk an array from its first box to one past its last box. Two pointers mark the start and the end. The end pointer is one past the last element, and it is never dereferenced. This "half-open" range is the standard pattern in C++.

Output:

sum = 150
a[3] = 40, *(a + 3) = 40
elements between begin and end: 5

Trace the loop. p starts at begin, which is box 0 with value 10. The loop body adds 10 to total. Then ++p moves p to box 1. The check p != end is true, so the loop continues. The values 20, 30, 40 and 50 are added in turn. After the box with 50, ++p moves p to end, which is one past the last box. The check p != end is now false, and the loop stops. The total is 10 + 20 + 30 + 40 + 50, which is 150.

The second line shows the identity from earlier: a[3] and *(a + 3) both give 40.

The third line subtracts two pointers. The result is the number of elements between them, which is 5. Subtracting two pointers into the same array gives an element count, not a byte count. That is another way pointer arithmetic follows the element size.

Why the end pointer is one past the last element

Look at the range in worked example 1. The end pointer a + 5 points one position past the last element. You may wonder why the standard does not point at the last element instead. There are three reasons, and each one matters in an interview.

The first reason is the empty range. If a range is empty, its start and end must be equal. With the one-past-the-end design, an array of zero elements has begin == end, and the loop p != end runs zero times with no special case. With an end pointer on the last element, an empty array has no last element at all, and the code needs an extra check.

The second reason is the length. The length of a half-open range is end - begin. No + 1 or - 1 appears in the formula, which removes one common source of bugs.

The third reason is joining ranges. If one range ends at position k and the next starts at position k, the two ranges touch with no overlap and no gap. A closed range would need k - 1 as the end of the first range and k as the start of the second, and both ends would have to be remembered carefully.

The rule has one cost. You must never dereference the end pointer, because it points at a box that is not part of the range. Reading *end is undefined behaviour, even though forming the pointer and comparing it is allowed.

Worked example 2: reversing in place with two pointers

Two pointers can walk toward each other from both ends of an array. This pattern is called two pointers, and it appears in dozens of interview problems. The first problem we solve is reversing an array in place, which means changing the array itself rather than building a new one.

The program reads the array from input. Type the first line as the count, then the values on the next line. The input here is 5 followed by a new line, then 1 2 3 4 5.

Input:

5
1 2 3 4 5

Output:

5 4 3 2 1

The pointer left starts at the first box and right at the last box. Each round swaps the two values and moves the pointers one step toward the middle. The loop stops when left is no longer before right. With five elements the rounds swap positions (0, 4), then (1, 3), and the middle element at position 2 stays where it is. That is the reason the condition is left < right and not left != right. With an even number of elements the pointers would still meet, but the condition works for both lengths.

Look at the picture of the two pointers meeting in the middle. The left pointer moves to the right while the right pointer moves to the left, and they stop when they pass each other.

Step through it above. Watch what happens to the two pointers and to the values between them. Notice that each step makes progress on the outside of the array first, then works inward. Every element is touched once, and the program uses no extra array. That gives time O(n) and space O(1), which are the two numbers an interviewer will ask for. Time O(n) means the work grows in step with the number of elements. Space O(1) means the extra memory stays the same size however long the array is.

Worked example 3: binary search with pointers

Binary search is the second big pattern. The array must be sorted. You look at the middle element, and if it is too small you throw away the left half, and if it is too large you throw away the right half. Each step cuts the remaining range in two, so a sorted array of a million values needs at most about 20 comparisons.

Here we write binary search with pointers instead of indexes. The range is half-open, from first up to but not including last, the same as the pattern in worked example 1.

Input:

6
1 3 5 7 9 11
7

Output:

found at index 3

Change the target to 4 in the Input box and the output becomes not found. Try the target 1 and the output is found at index 0. Try 11 and you get found at index 5. Those three edge cases, the first, the last and a missing value, are the ones interviewers test first.

The middle is found with first + (last - first) / 2. You might be tempted to write (first + last) / 2. That line is wrong for pointers, because adding two addresses is not allowed. The subtraction form also avoids a classic overflow bug with indexes, where (low + high) can overflow when the numbers are big.

Step through the search above. Watch the range shrink from both sides. Each comparison throws away half of what is left. The loop can run only about log base 2 of n times, which is the reason binary search is O(log n) in time and O(1) in space.

What happens inside the loop

It helps to see what the processor does for *mid. The pointer mid holds an address. The processor reads the 4 bytes at that address and gives you an int. When the search moves first = mid + 1, the processor does no reading at all. It only computes a new address by adding 4 bytes to the old one, because mid + 1 moves one element. Arithmetic on pointers is just address arithmetic, scaled by the element size. The processor does not need to know about the array as a whole. It only needs the address of the next box.

This is also why a pointer that walks past the end of an array is dangerous. If first goes one step past last and you then read *first, you read memory that may belong to something else. The safe rule is simple: a pointer may point to any element of the array or to one position past the last element, and you must never read the position past the end.

Tracing an array walk on paper

Use the table method from lesson 1 to check a pointer loop. Take the sum loop from worked example 1, where the array holds 10, 20, 30, 40 and 50. Imagine the first element at address 1000, so the others are at 1004, 1008, 1012 and 1016.

Read the last row carefully. After the fifth step, ++p moves the pointer to address 1020. That address is end, one position past the array. The test finds a match and the loop stops before the pointer is read. If the loop read *p before testing it, the sixth row would read garbage, which is the bug described in the common mistakes section.

The addresses in the table are made up, because real ones change from run to run. The step of 4 bytes is real for an int, and the same pattern holds for every array.

Common mistakes in pointer arithmetic

The first mistake is reading past the end. Consider this loop:

int a[3] = {1, 2, 3};
for (int* p = a; p <= a + 3; ++p) {
    cout << *p << endl;
}

It reads a + 3, which is one past the last element, and that box is not part of the array. The bug is the <= in the condition. Write p < a + 3 or p != a + 3. The output of the buggy loop is 1, 2, 3 and then a garbage number, and on some compilers the program may print nothing extra at all. The garbage is the bug.

The second mistake is adding a byte count. Writing p + 4 on an int* moves 16 bytes, not 4. If you need the byte distance, cast to char* first, but normally you should count elements.

The third mistake is subtracting pointers from different arrays. The result has no meaning. Keep the pointers in the same array.

The fourth mistake is size from a pointer. Here is the compile-time trap:

void show(int arr[]) {
    cout << sizeof(arr) << endl;
}

Inside show, arr is a pointer, so sizeof(arr) gives the size of a pointer, which is 8 on a 64-bit machine. It does not give the array size. You must pass the length as a second argument. The next example shows this exactly.

Worked example 4: sizeof inside a function

This program shows the array size in main and inside a function.

On a typical 64-bit machine the output is:

sizeof in main = 16
sizeof inside = 8
n = 4

In main, data is a real array of four ints, so sizeof(data) is 4 times 4, which is 16. Inside show, the parameter arr is a pointer, so sizeof(arr) is 8. The length must travel with the array as a separate value, which is why n is passed in. This is why C++ programmers write a function as void show(int* arr, int n) or void show(const vector<int>& v), the second form carrying its size inside the vector.

Interview view: scanning an array

Most array questions in an interview fall into a few shapes, and each one uses either an index or a pointer, depending on taste. You can write the same algorithm both ways. What the interviewer really checks is whether you can say the time and space costs, and whether you handle the edges: an empty array, one element, duplicates, and a target that is not present.

Say the shape out loud before you write code. "This is a sorted array, so I will use two pointers from both ends." That one sentence shows you know the pattern. Then give the cost: each pointer moves at most n times, so the time is O(n) and the extra space is O(1).

A pointer to a pointer

A pointer holds an address. A pointer to a pointer holds the address of another pointer. You write it with two stars: int** pp. Read it as "pp is a pointer to a pointer to an int".

This matters in one common situation. Suppose a function wants to change which address a pointer holds. A function receives copies of its arguments. If you pass the pointer by value, the function changes its own copy, and the caller's pointer stays the same. To change the caller's pointer, the function needs the address of the pointer, which is a pointer to a pointer.

Output:

1
2
99
1

Trace the important part. p starts at a. The call setTo(&p, &b) passes the address of p, which has type int**. Inside setTo, *pp means "the pointer that pp points at", which is p itself. The assignment *pp = target therefore changes p in main to hold &b. After the call *p is 2.

The next two lines use pp in main. It holds &p, so *pp is p, and **pp walks from p to b. Writing 99 through **pp changes b. The value of a never changes, so it still prints 1.

Count the stars and you can read any pointer chain. One star moves from a pointer to the thing it holds. Two stars move from a pointer to a pointer to the final value. Each extra star is one more walk.

Pointers to pointers are the reason linked lists are tricky to write. Imagine the head of a list is a pointer, and you want to insert at the front. You need to change the head, so the function needs a Node** or a reference to the head pointer. Lesson 5 uses a cleaner method, but the idea underneath is the same.

Two-dimensional arrays and flat indexes

A two-dimensional array such as int grid[2][3] is stored as one row after another. Row 0 comes first, followed by row 1. There is no gap between rows. That means you can use one pointer, starting at the first element, to walk the whole grid. The formula to find element (r, c) is r * columns + c.

Output:

total = 21
grid[1][2] = 6

The index 1 * 3 + 2 is 5, so flat + 5 points at the sixth element of the flat array, which is the value 6 in row 1, column 2. The total is 1 + 2 + 3 + 4 + 5 + 6, which is 21. Notice that flat[i] works here, because a pointer can also be indexed with brackets. The identity from earlier applies to every pointer, not only to arrays.

A common mistake is to think of a two-dimensional array as an array of pointers. Writing int** g and then g[1][2] needs a real array of pointers to rows, which you build yourself with new. Lesson 4 shows how.

What a pointer to an array is

A pointer to an array is different from an array of pointers, and the two look alike. int (*p)[3] is a pointer to an array of three ints. Moving it with p + 1 moves by a whole row of 12 bytes. That is rare in beginner code, so do not worry about it now. Just know that the parentheses change the meaning, and reading the declaration from the inside out gives you the answer.

Variations and edge cases

An empty array has no first element. a still gives an address, but a + 0 and a + n are the same address when n is 0. A loop from begin to end runs zero times, which is correct. A bug appears when you read *begin anyway, because that box does not hold data you can trust.

A one-element array makes the two-pointer loop start and stop at once. In the reversal example the condition left < right is false from the start, so nothing is swapped. The result is still correct, because one element reversed is itself.

A target that appears more than once is a special question in binary search. The basic version above returns some matching index, not necessarily the first one. Interviewers often ask for the first index, which needs a different loop that keeps searching left after a match. You can build that by changing last = mid on a match rather than returning.

Negative numbers and zero do not change any of these rules. Pointer arithmetic depends on position, not sign.

Common mistakes with messages

When you write int* p = a + 10; for a five-element array, the compiler does not complain. The array is a plain block of memory and the compiler does not track its length through a pointer. The mistake is silent. Only the sanitizer described in lesson 1 can catch it, with a message about a stack or heap buffer overflow.

When you add two pointers, int* c = a + b; where both a and b are pointers, the compiler stops you with this message:

error: invalid operands of types 'int*' and 'int*' to binary 'operator+'

Adding two addresses has no meaning, so the compiler refuses. This is the error that tells you that you wanted a difference, b - a, or you wanted an index, not a sum.

Debugging walkthrough: an off-by-one loop

Suppose your reversal program prints the array in the wrong order, or prints a stray number at the end. Work through these questions in order.

Question 1: what is right at the start? It should be a + n - 1, which is the last element. If you wrote a + n, the pointer starts one past the end, and the first swap reads garbage.

Question 2: what does the loop condition compare? left < right stops when the pointers meet or cross. If you wrote left <= right, the middle element of an odd-length array is swapped with itself. That is harmless, and the loop still stops, because the pointers then cross. The difference shows up only when you add more work inside the loop, so keep the strict form.

Question 3: do the pointers move in the right direction? left++ moves toward the end and right-- moves toward the start. Swapping the two would stop the loop immediately or never end it.

Question 4: print the pointers. Add cout << (left - a) << " " << (right - a) << endl; inside the loop. You will see the indexes, and the bug becomes obvious. This is the fastest way to check pointer code: turn each pointer into an index and print it.

Real-world uses

Pointer arithmetic is the core of fast systems code. Video decoders step through pixel buffers with pointers. Network stacks walk a packet with a pointer and read each header field at a fixed offset. Compilers themselves use pointers to step through the characters of source code. In each case, the programmer uses the same rules you have just learned: an element is a fixed step, and the step depends on the type.

Two-pointer and binary-search techniques are the most common interview patterns. Many problems that look like they need a hash map can be solved with two pointers and O(1) extra space once the array is sorted. Knowing both ways, and being able to say why the pointer version is faster, is a strong sign of understanding.

A checklist for array loops

Before you hand in an array loop, check these points.

1. The start is the first element, and the end is one position past the last element.
2. The loop stops when the pointer equals the end, and the test comes before any read.
3. Nothing reads through the end pointer.
4. Each step moves the pointer by exactly one element, and the direction matches the goal.
5. The empty array, the one-element array and the all-equal array all give the right answer.
6. The length comes from end - begin or is passed in, never from sizeof on a pointer.

These six points cover almost every off-by-one bug. Lesson 5 uses the same range idea for a linked list, where the end is nullptr rather than an address past the last element.

Practice

Exercise 1. Write a loop that prints each element of int a[4] = {7, 8, 9, 10}; using only a pointer, not an index. Print one value per line.

int a[4] = {7, 8, 9, 10};
for (int* p = a; p != a + 4; ++p) {
    cout << *p << endl;
}

Exercise 2. Write what int a[5] = {1, 2, 3, 4, 5}; cout << *(a + 4); prints. Then check it by running the code.

Exercise 3. Write a function int sumPtr(int* first, int* last) that adds the values in the half-open range and returns the total. Test it on the array from worked example 1.

int sumPtr(int* first, int* last) {
    int total = 0;
    for (int* p = first; p != last; ++p) {
        total += *p;
    }
    return total;
}

Exercise 4. Reverse an array with two pointers, but do it for an array of double values. Explain why the same code works without any change for a different element type.

Exercise 5. Write a function int countTarget(int* first, int* last, int target) that counts how many values equal target. Test with an empty range, a range with one match and a range with two matches.

int countTarget(int* first, int* last, int target) {
    int count = 0;
    for (int* p = first; p != last; ++p) {
        if (*p == target) {
            count++;
        }
    }
    return count;
}

Exercise 6. Modify the binary search so it returns the index of the first occurrence of the target in a sorted array with duplicates. Test with 1 2 2 2 3 and the target 2. The answer must be 1.

int* firstOccurrence(int* first, int* last, int target) {
    int* result = nullptr;
    while (first < last) {
        int* mid = first + (last - first) / 2;
        if (*mid == target) {
            result = mid;
            last = mid;
        } else if (*mid < target) {
            first = mid + 1;
        } else {
            last = mid;
        }
    }
    return result;
}

Exercise 7. Given int grid[3][4];, write the expression that gives the address of element (2, 1) using only grid and pointer arithmetic. Check it by printing &grid[2][1] == (int*)grid + 2 * 4 + 1, which must print 1.

Exercise 8. Find the bug in int a[3] = {1, 2, 3}; for (int* p = a; p <= a + 3; ++p) cout << *p;. Fix it and explain the difference between a + 3 and a + 2.

Exercise 9. Explain to a friend why sizeof(arr) inside a function is not the array size. Use the words decay and pointer in your answer.

Exercise 10. Write a function void swapEnds(int* first, int* last) that swaps the values at the two ends, and call it on a one-element range. Explain what it must do and why no swap is the correct answer.

void swapEnds(int* first, int* last) {
    int tmp = *first;
    *first = *last;
    *last = tmp;
}

What you now know

• An array is a block of equal-sized boxes in a row, and its name gives the address of the first box.
• Adding 1 to a pointer moves it to the next element, so p + k moves k elements.
• a[i] and *(a + i) are the same expression, and flat[i] works on any pointer.
• Subtracting two pointers into the same array gives the number of elements between them.
• Two-pointer scans from both ends and binary search each use O(1) extra space, and run in O(n) and O(log n) time.
• Inside a function, an array parameter is a pointer, so sizeof gives 8, and the length must be passed separately.
• A pointer to a pointer lets a function change which address a caller's pointer holds.

Lesson 3 asks a different question. Instead of how to reach a value through an address, it asks how a function should receive a value, by copy, by pointer or by reference, and why that choice matters for speed and for correctness.