Arrays and Iteration

Array Sum (Linear Scan)

Walk an array once, accumulating each element into a running total. This is the canonical single-pass linear scan and the simplest possible loop invariant: after step i, total equals the sum of arr[0..i].

Algorithm

Trace Output

basic.dart 
void main() {
  final arr = <int>[3, 1, 4, 1, 5, 9, 2, 6];
  var total = 0;
  for (var i = 0; i < arr.length; i++) {
    total = total + arr[i];
  }
  print(total);
}
trace.dart 
void main() {
  final arr = <int>[3, 1, 4, 1, 5, 9, 2, 6];
  var total = 0;
  for (var i = 0; i < arr.length; i++) {
    final before = total;
    total = total + arr[i];
    print('step $i: arr[$i]=${arr[i]} total $before -> $total');
  }
  print('final total = $total');
}

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • Dart: use an explicit for (var i = 0; i < arr.length; i++) loop. Calling arr.reduce((a, b) => a + b) or arr.fold(0, ...) would hide the iteration the lesson is teaching.
  • The replay shows i, arr[i], and total before and after each addition, matching the lesson spec's state-transition table. The trace variant prints step i: arr[i]=V total B -> T for each visit and a closing final total = 31 summary.
linear scan Visit each element exactly once in index order.
running total `total` accumulates the sum as the loop advances.