Array Updates: Check the Index and the Direction

Read the current value before you write

Two loops can use the same assignment and finish with different arrays because they visit the indices in a different order. In an in-place update, the next read may use a value changed by an earlier write. A reliable trace records the whole state after every assignment, rather than repeatedly looking back at the starting row.

This paper model declares A as an integer array with exactly six elements, indexed from 1 through 6. Its initial values are [9, 4, 17, 6, 23, 11]. Reset to this original state before each independent case. There is no automatic resizing, wraparound or hidden second array.

Define the notation and bounds

A[k] means the element at index k. The assignment A[k+1] ← A[k] first reads the current value at index k, then writes that value into index k+1. The arrow assigns a value; it is not a mathematical equality claiming both positions have always been identical.

Both indices must be valid. With this assignment and bounds 1 through 6, k must run only from 1 through 5. At k = 5, the destination is 6, the final valid position. At k = 6, the destination would be 7, which does not exist in this model.

Worked case 1: forward propagation

Use k = 1, 2, 3, 4, 5 in that order. On each pass perform A[k+1] ← A[k]. The first assignment copies 9 from A[1] into A[2]. The next read is therefore from the new A[2], whose value is already 9.

The final state is [9, 9, 9, 9, 9, 9]. The original 4 disappears before a later pass can copy it; the same happens to 17, 6 and 23. A[1] is never a destination, so it remains 9. This is propagation of the first value, not a rightward copy of all the original values.

A common incorrect answer is [9, 9, 4, 17, 6, 23]. That answer assumes each read comes from an untouched starting array. The loop specified here has only one mutable array, so the assumption changes the algorithm.

Worked case 2: backward copying

Reset A. Now use k = 5, 4, 3, 2, 1, performing exactly the same assignment A[k+1] ← A[k]. Reading A[5] before writing A[6] preserves 23 at the right-hand end. The next source, A[4], has not yet been overwritten.

The final state is [9, 9, 4, 17, 6, 23]. Indices 2 through 6 contain the original values from indices 1 through 5. The original final value, 11, is overwritten, and index 1 remains unchanged. This operation is not a rotation: a rotation would need an explicit rule for preserving and relocating 11.

Backward order works here because the destinations lie one place to the right of their sources. Do not memorise “backward is always correct”. For a leftward copy, the safe direction changes. Determine which write could destroy a value before it is read.

Worked case 3: a separate unchanged source

Let S be a separate six-element array holding [9, 4, 17, 6, 23, 11], unchanged throughout this case. A begins as [0, 0, 0, 0, 0, 0]. First assign A[1] ← S[1]. Then, for k = 1 through 5, assign A[k+1] ← S[k]. The two arrays do not share their element storage.

The result matches the backward in-place case, but the reason differs. A forward pass is safe because it reads S, not the changing A. Keeping two names for the same underlying storage would not supply this protection. The separate-source assumption is explicit and essential.

Catch an invalid final destination

Suppose the forward case mistakenly continues to k = 6. After the five valid assignments, A is [9, 9, 9, 9, 9, 9]. The next attempted instruction is A[7] ← A[6]. Record “invalid destination 7; stop before this assignment” and retain the last valid state. Do not create a seventh element or report an invented value for it.

The model specifies rejection before the invalid write. Actual languages and implementations handle invalid access in different ways; this paper trace does not predict their behaviour. Correct the loop boundary to 5 when the required destinations are 2 through 6.

Three solved practice tasks

Task 1: stop after two forward writes

Start with [8, 3, 12, 5, 19, 7]. Perform A[k+1] ← A[k] for k = 1 then 2 only. Solution: after k = 1: [8, 8, 12, 5, 19, 7]. After k = 2: [8, 8, 8, 5, 19, 7]. The second source is the updated A[2].

Task 2: reverse the movement

Reset that array. Perform A[k] ← A[k+1] for k = 1 through 5. Solution: successive states are [3, 3, 12, 5, 19, 7], [3, 12, 12, 5, 19, 7], [3, 12, 5, 5, 19, 7], [3, 12, 5, 19, 19, 7], then [3, 12, 5, 19, 7, 7]. Forward order preserves the needed right-hand sources for this leftward copy.

Task 3: check a proposed boundary

For A[1:6], can A[k+1] ← A[k] run at k = 6? Solution: no. Source 6 exists, but destination 7 does not. A valid source alone is insufficient; check the entire indexed assignment.

Further reading

Technical background: Cambridge International — array notation and assignment; Python Software Foundation — mutable sequences. Examples, questions and diagrams in this lesson are original.