Count 1, 2, or 3-step paths in Swift: Three Moves

Count ordered sequences of moves of length 1, 2, or 3 that advance exactly n positions. For n = 3, the sequences are [1, 1, 1], [1, 2], [2, 1], and [3], giving four. Zero has one sequence, the empty sequence. A negative target has no valid sequence and returns zero.

Group sequences by their final move

A sequence ending at position n must end with a move of 1, 2, or 3. Removing that final move leaves a sequence ending at n - 1, n - 2, or n - 3 respectively. Conversely, appending the corresponding final move to any sequence for one of those positions creates a valid sequence for n.

The three groups are disjoint because their final moves differ. Add their counts to obtain ways(n) = ways(n - 1) + ways(n - 2) + ways(n - 3). This counts order: [1, 2] and [2, 1] belong to different final-move groups. Counting unordered combinations would require a different state and iteration rule.

Initialize the empty sequence correctly

Set the count for position zero to one. Without that seed, the recurrence would multiply an all-zero history into all-zero answers. Positions below zero contribute zero because a positive-length move cannot arrive there from the start. The first positive counts are one for n = 1, two for n = 2, and four for n = 3.

The chosen implementation keeps only three rolling values instead of a full table. At each iteration, their sum becomes the next count. Shift the older values backward and store the new sum as the most recent value. After n iterations, the most recent value represents exactly position n.

Trace enough steps to check the shift

Start with history for positions -2, -1, and 0 equal to 0, 0, and 1. The next sum is 1, leaving history 0, 1, 1. The next sum is 2, leaving 1, 1, 2. The next sum is 4, leaving 1, 2, 4. Position four then has 1 + 2 + 4 = 7 sequences.

Compute the sum before overwriting any history value. Updating the most recent count too early can make later assignments reuse the new count twice. A trace that names the represented positions exposes that error more clearly than a trace of unnamed variables alone.

Explain the improvement over recursion

A direct recursive function follows the recurrence literally and repeatedly recomputes the same positions. Memoization reduces that repetition to one computation per position. Bottom-up iteration also computes each position once and removes recursive frames. Since only the previous three counts are needed, rolling state reduces auxiliary storage further.

The selected version takes O(n) additions and O(1) stored counts under bounded-integer arithmetic. Counts grow quickly. Once they exceed a language's integer range, overflow can corrupt the answer or trap. Arbitrary-precision integers avoid that fixed bound but make arithmetic cost and numeric storage grow with the answer's digit length.

Test ordering and boundary values

Test negative targets, zero, one, two, three, and four. Values 0 and 3 reject common incorrect base cases. Compare short targets with an independent recursive enumeration that records every complete move sequence and counts it. Keep that oracle's inputs small because it intentionally generates exponentially many paths.

A follow-up can permit an arbitrary set of positive move lengths. The recurrence sums counts from each allowed predecessor position, with time proportional to n times the number of allowed moves. Zero or negative move lengths need separate restrictions because they can create cycles or infinitely many sequences. If the task instead asks for a shortest sequence, replace the counting objective with a minimum-distance recurrence.

Swift implementation

The negative guard precedes the range loop. Adding the three Int counts can trap if expanded targets exceed the representable range.

The course uses the class shown here and supplies any declared node classes. Swift arrays have value semantics with copy-on-write storage, while class instances such as linked nodes retain reference identity. Optional values require an explicit absence case. Keep the starter's argument labels when calling the method. Swift integer overflow traps, so expanded constraints require a checked arithmetic policy.

class Solution {
    func countTotalMoves(_ boardLength: Int) -> Int {
        if boardLength < 0 {
            return 0
        }

        var threeSpotsBack = 0
        var twoSpotsBack = 0
        var oneSpotBack = 1

        for _ in 0..<boardLength {
            let finalSpot = oneSpotBack + twoSpotsBack + threeSpotsBack

            threeSpotsBack = twoSpotsBack
            twoSpotsBack = oneSpotBack
            oneSpotBack = finalSpot
        }

        // We return oneSpotBack because it was actually updated to the finalSpot
        // during the last iteration of the loop when we moved values forward
        return oneSpotBack
    }
}

Practice this implementation

Open Three Moves to run the implementation against the course tests, then change one boundary condition and explain the first failing case. The editor supplies the starter signature and any node types or helper APIs used above. Copy the implementation into that environment; the snippet is the solution body, without the input parser or test driver. Your saved progress belongs to the original lesson.

For more Swift conventions and practice problems, use the Swift interview guide.