15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Array traversal visits each element once, by index. A forward traversal starts at index 0 and loops while i < length, so index length is never read. A reverse traversal starts at length - 1 and loops while i >= 0. Both take O(n) time and O(1) extra space, not counting any output array.
| Valid index | 0 <= i < length |
|---|---|
| Forward loop | i = 0; while i < length; i = i + 1 |
| Reverse loop | i = length - 1; while i >= 0; i = i - 1 |
| One read or write at a valid index | O(1) |
| Full traversal | O(n) time, O(1) extra space (output array excluded) |
| Empty array | The loop runs zero times, so the sum is 0 |
Assume you know that an array stores a sequence of elements and has a logical length.
Arrays use zero-based indexing:
0.length - 1.i must satisfy:For an array of length 3, the valid indices are 0, 1, and 2. Index 3 is not valid.
When an index is known to be valid, reading A[i] takes a constant number of operations. Writing a new value into A[i] also takes a constant number of operations. The work is in keeping the index within the valid bounds.
Use this array:
1index: 0 1 2
2A: [5, 1, 4]
3length = 3Compute the sum of:
1index: 0 1 2
2A: [5, 1, 4]Start with two pieces of state:
1i = 0
2sum = 0i identifies the array position to process next.
sum stores the total of the values already processed.
The forward-traversal boundary is:
1while i < lengthHere, length is 3, so the loop may process i = 0, i = 1, and i = 2.
Stop before i = 3, because A[3] does not exist.
Start with the array unchanged:
A forward traversal: while i < length, read A[i], add it to sum, and move i up by one. With length = 3 the loop reads indices 0, 1 and 2, then stops at i = 3 and returns 10.
i = 0, so check the loop condition:
10 < 3 → trueIndex 0 is valid. Read A[0].
1A[0] = 5
2sum = 0 + 5 = 5
3i = 1Now the state is:
1i = 1
2sum = 5Check the condition:
11 < 3 → trueIndex 1 is valid. Read A[1].
1A[1] = 1
2sum = 5 + 1 = 6
3i = 2Now the state is:
1i = 2
2sum = 6Check the condition:
12 < 3 → trueIndex 2 is valid. Read A[2].
1A[2] = 4
2sum = 6 + 4 = 10
3i = 3Now the state is:
1i = 3
2sum = 10Check the condition:
13 < 3 → falseStop. i has reached length, so there is no next valid element to read.
Return:
110| State | i before read | Current value | sum after update | i after advance |
|---|---|---|---|---|
| 0 | 0 | 5 | 5 | 1 |
| 1 | 1 | 1 | 6 | 2 |
| 2 | 2 | 4 | 10 | 3 |
| 3 | 3 | no read | 10 | stop |
Look at the state just before each array read.
Before processing index i, sum contains the total of every element to the left of i. No element at index i or farther right has been included yet.
For the example:
Before processing i | Processed indices | sum |
|---|---|---|
| 0 | none | 0 |
| 1 | 0 | 5 |
| 2 | 0, 1 | 6 |
| 3 | 0, 1, 2 | 10 |
The loop invariant is:
Before processing index
iin a forward sum traversal,sumequals the sum of elements at indices0throughi - 1, and no index at or beyondihas been processed.
The phrase “through i - 1” specifies which elements are already included.
i = 0, there are no earlier indices, so sum must be 0.i = 2, the earlier indices are 0 and 1, so sum is 5 + 1 = 6.i = length, every valid index is earlier than i, so the sum includes the entire array.Use the invariant to construct the traversal.
i = 0.0, because no elements have been processed.i < length.A[i].sum.i so the next iteration processes the next index.i = length, return sum.A reverse traversal follows the valid-index rule and starts at the last valid index:
1length - 1Then it moves down:
1i = i - 1The reverse loop condition includes zero:
1while i >= 0For [5, 1, 4], reverse visit order is:
1A[2], A[1], A[0]
24, 1, 5The boundaries follow from the endpoints:
0, stop before length.length - 1, stop after processing 0.1FUNCTION ReadAt(A, length, i) RETURNS value
2 INPUT:
3 A: array
4 length: number of logical elements in A
5 i: requested index
6 MUTATION:
7 Does not modify A.
8 PRECONDITION:
9 0 <= i < length
10 RETURN:
11 The value stored at A[i].
12
13 RETURN A[i]
14END FUNCTIONA caller must guard the access with 0 <= i < length. If that condition is false, the index is out of bounds and must be rejected rather than read.
1FUNCTION SumForward(A, length) RETURNS integer
2 INPUT:
3 A: array of integers
4 length: number of logical elements in A
5 MUTATION:
6 Does not modify A.
7 BOUNDARY:
8 Valid indices are 0 through length - 1.
9 If length = 0, the loop runs zero times.
10 RETURN:
11 The sum of all logical elements in A.
12
131. sum = 0
142. i = 0
153. WHILE i < length
164. sum = sum + A[i]
175. i = i + 1
186. END WHILE
197. RETURN sum
20END FUNCTION1FUNCTION ReverseVisitOrder(A, length) RETURNS array
2 INPUT:
3 A: array
4 length: number of logical elements in A
5 MUTATION:
6 Does not modify A.
7 BOUNDARY:
8 Valid indices are 0 through length - 1.
9 If length = 0, i starts at -1 and the loop runs zero times.
10 RETURN:
11 A new array containing A's elements in reverse visit order.
12
131. result = empty array
142. i = length - 1
153. WHILE i >= 0
164. append A[i] to result
175. i = i - 1
186. END WHILE
197. RETURN result
20END FUNCTIONFor the worked array, ReverseVisitOrder([5, 1, 4], 3) returns:
1[4, 1, 5]Dry-run SumForward(A, 3) using the same array:
1index: 0 1 2
2A: [5, 1, 4]| Pseudocode line | State and action |
|---|---|
| 1 | Set sum = 0. |
| 2 | Set i = 0. |
| 3 | Check 0 < 3. True, so enter the loop. |
| 4 | Read A[0] = 5. Set sum = 0 + 5 = 5. |
| 5 | Set i = 0 + 1 = 1. |
| 3 | Check 1 < 3. True, so enter the loop. |
| 4 | Read A[1] = 1. Set sum = 5 + 1 = 6. |
| 5 | Set i = 1 + 1 = 2. |
| 3 | Check 2 < 3. True, so enter the loop. |
| 4 | Read A[2] = 4. Set sum = 6 + 4 = 10. |
| 5 | Set i = 2 + 1 = 3. |
| 3 | Check 3 < 3. False, so leave the loop. |
| 7 | Return sum, which is 10. |
The array remains unchanged:
1A = [5, 1, 4]Only the local variables changed:
1i: 0 → 1 → 2 → 3
2sum: 0 → 5 → 6 → 10We prove that SumForward returns the sum of every logical element in the array.
Before the first loop iteration:
1i = 0
2sum = 0There are no indices from 0 through i - 1, because i - 1 is -1.
The sum of zero processed elements is 0. No index at or beyond 0 has been processed.
So the invariant is true before the loop begins.
Assume the invariant is true before an iteration with some index i.
The loop condition is:
1i < lengthTogether with i starting at 0 and only increasing, this gives:
10 <= i < lengthTherefore A[i] is a valid indexed read.
Before the iteration, sum equals the sum of indices 0 through i - 1.
Line 4 adds exactly A[i], so sum now equals the sum of indices 0 through i.
Line 5 changes i to i + 1. At that new index, the processed indices are exactly 0 through (i + 1) - 1.
No later index has been processed.
So the invariant remains true for the next iteration.
The loop stops when:
1i < lengthis false. Since i began at 0 and increased by one each iteration, termination occurs at:
1i = lengthAt that moment, the invariant says sum contains the sum of indices:
10 through length - 1Those are exactly all valid array indices. Each was processed once because i moved from 0 to length - 1 one step at a time.
Therefore SumForward returns the sum of every logical element exactly once.
A read at one already-valid index, such as A[1], performs a constant number of operations.
So a direct valid indexed read is:
1Time: O(1)
2Auxiliary space: O(1)The same applies to writing one value at a known valid index.
Let n be length.
The loop index takes these values:
10, 1, 2, ..., n - 1That is exactly n iterations.
Each iteration performs constant work:
A[i].sum.i.The total work grows with n:
1Time: O(n)The function uses only:
1i
2sumThese are a constant number of variables regardless of array length:
1Auxiliary space: O(1)For ReverseVisitOrder, the traversal also performs one iteration per index. Its returned array contains n values, so that output occupies O(n) storage. Apart from the returned output, the traversal uses only i, which is O(1) auxiliary space.
i <= length in a forward traversalIncorrect loop condition:
1WHILE i <= lengthExposing input:
1A = [5, 1, 4]
2length = 3The traversal correctly processes indices 0, 1, and 2. Then i becomes 3.
The incorrect condition checks:
13 <= 3 → trueThe code attempts:
1A[3]But the valid indices are only 0, 1, and 2.
Correction:
1WHILE i < lengthlengthIncorrect initialization:
1i = lengthExposing input:
1A = [7]
2length = 1The initialization sets:
1i = 1The first attempted access is:
1A[1]But the only valid index is 0.
Correction:
1i = length - 1For [7], this gives i = 0. The traversal visits A[0] once, decrements to -1, and stops before another access.
Incorrect initialization and loop:
1sum = A[0]
2i = 0
3
4WHILE i < length
5 sum = sum + A[i]
6 i = i + 1
7END WHILEExposing input:
1A = [5, 1]Initial state:
1sum = A[0] = 5
2i = 0First loop iteration adds A[0] again:
1sum = 5 + 5 = 10Second iteration adds A[1]:
1sum = 10 + 1 = 11The correct sum is 6, not 11.
Correction: initialize to zero and process every index in the loop.
1sum = 0
2i = 0Alternatively, deliberately initialize from the first element and start at index 1. That version needs separate handling for an empty array, because A[0] is invalid when length = 0.
Input:
1A = []
2length = 0For forward sum traversal:
1i = 0
2sum = 0The condition is:
10 < 0 → falseThe loop runs zero times and returns:
10Reading A[0] from this array is invalid because:
10 <= 0 < 0is false.
For reverse traversal:
1i = length - 1 = -1The condition i >= 0 is false immediately. The result is an empty array.
Implement functions that:
The tests will include:
1[]
2[7]
3[5, 1, 4]Your functions must satisfy these contracts:
[] returns 0.[7] is visited exactly once in both directions.0 through length - 1.length - 1 and ends after processing 0.1def sum_forward(a):
2 total = 0
3 i = 0
4 while i < len(a): # stop before index length
5 total += a[i]
6 i += 1
7 return total
8
9def reverse_visit_order(a):
10 result = []
11 i = len(a) - 1 # last valid index
12 while i >= 0: # includes index 0
13 result.append(a[i])
14 i -= 1
15 return result
16
17print("sum([5, 1, 4]) =", sum_forward([5, 1, 4]))
18print("reverse([5, 1, 4]) =", reverse_visit_order([5, 1, 4]))
19print("sum([]) =", sum_forward([]))
20print("reverse([7]) =", reverse_visit_order([7]))1import java.util.Arrays;
2
3public class Main {
4 static int sumForward(int[] a) {
5 int sum = 0;
6 int i = 0;
7 while (i < a.length) { // stop before index length
8 sum += a[i];
9 i++;
10 }
11 return sum;
12 }
13
14 static int[] reverseVisitOrder(int[] a) {
15 int[] result = new int[a.length];
16 int count = 0;
17 int i = a.length - 1; // last valid index
18 while (i >= 0) { // includes index 0
19 result[count++] = a[i];
20 i--;
21 }
22 return result;
23 }
24
25 public static void main(String[] args) {
26 System.out.println("sum([5, 1, 4]) = " + sumForward(new int[]{5, 1, 4}));
27 System.out.println("reverse([5, 1, 4]) = " + Arrays.toString(reverseVisitOrder(new int[]{5, 1, 4})));
28 System.out.println("sum([]) = " + sumForward(new int[]{}));
29 System.out.println("reverse([7]) = " + Arrays.toString(reverseVisitOrder(new int[]{7})));
30 }
31}1#include <iostream>
2#include <vector>
3using namespace std;
4
5int sumForward(const vector<int>& a) {
6 int sum = 0;
7 int i = 0;
8 while (i < (int)a.size()) { // stop before index length
9 sum += a[i];
10 i++;
11 }
12 return sum;
13}
14
15vector<int> reverseVisitOrder(const vector<int>& a) {
16 vector<int> result;
17 int i = (int)a.size() - 1; // last valid index
18 while (i >= 0) { // includes index 0
19 result.push_back(a[i]);
20 i--;
21 }
22 return result;
23}
24
25void show(const vector<int>& a) {
26 cout << "[";
27 for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
28 cout << "]";
29}
30
31int main() {
32 cout << "sum([5, 1, 4]) = " << sumForward({5, 1, 4}) << "\n";
33 cout << "reverse([5, 1, 4]) = "; show(reverseVisitOrder({5, 1, 4})); cout << "\n";
34 cout << "sum([]) = " << sumForward({}) << "\n";
35 cout << "reverse([7]) = "; show(reverseVisitOrder({7})); cout << endl;
36}1function sumForward(a) {
2 let sum = 0;
3 let i = 0;
4 while (i < a.length) { // stop before index length
5 sum += a[i];
6 i++;
7 }
8 return sum;
9}
10
11function reverseVisitOrder(a) {
12 const result = [];
13 let i = a.length - 1; // last valid index
14 while (i >= 0) { // includes index 0
15 result.push(a[i]);
16 i--;
17 }
18 return result;
19}
20
21const show = (a) => `[${a.join(', ')}]`;
22console.log(`sum([5, 1, 4]) = ${sumForward([5, 1, 4])}`);
23console.log(`reverse([5, 1, 4]) = ${show(reverseVisitOrder([5, 1, 4]))}`);
24console.log(`sum([]) = ${sumForward([])}`);
25console.log(`reverse([7]) = ${show(reverseVisitOrder([7]))}`);For an array the lesson covers two: forward from index 0 and reverse from length - 1. The usual three-way split, inorder, preorder and postorder, belongs to tree traversal, not arrays.
Use an index loop such as for (int i = 0; i < n; i++). A C array does not carry its length, so you pass n yourself. A C++ vector gives you size(), and a range-based for loop reads each element without an index.
The access must be rejected before it happens. In the lesson, the bug is a forward loop written as i <= length, which reads A[3] on a length-3 array. Languages react differently: Java throws an exception, Python raises IndexError and C or C++ has undefined behaviour.
One read at a known valid index is a fixed amount of work. A traversal repeats that work once per element, so n elements cost n iterations. The loop index takes the values 0 through n - 1.
The same loop works. With length 0, the forward condition 0 < 0 is false and the sum is 0. A reverse loop starts at -1, fails i >= 0 at once and returns an empty result.