LeetCode 3522 - Calculate Score After Performing Instructions

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Simulation

Solution

Problem Understanding

The problem presents a simulated execution environment defined by two parallel arrays, instructions and values, each of length n. Each index i represents a single instruction. The instructions[i] element can either be "add" or "jump". If the instruction is "add", the associated values[i] is added to a running score, and execution proceeds to the next instruction (i + 1). If the instruction is "jump", the execution moves to the instruction at index i + values[i] without modifying the score. The process halts under two conditions: either the next index is out of bounds (i < 0 or i >= n) or the next instruction has already been executed.

The expected output is a single integer, the score accumulated by the end of the simulation.

Constraints clarify the problem scale and bounds: the arrays can have up to 10^5 elements, instructions are strictly "add" or "jump", and values are bounded between -10^5 and 10^5. These constraints indicate the necessity of an O(n) solution and preclude any approach that revisits indices repeatedly in a naive nested manner.

Important edge cases include:

The first instruction immediately jumps out of bounds.
A jump loops back to an already visited instruction.
A sequence of negative jumps that could exit the array bounds below 0.
A single-element array where the instruction jumps to itself.

Approaches

Brute Force: Simulate the process exactly as described. Maintain a visited array or set to track executed indices. At each step, check bounds and prior execution, then perform the action corresponding to the instruction. This approach is correct because it follows the process specification exactly. The time complexity is O(n) in practice, since each instruction can only be executed once, but naive index calculations could introduce errors in large negative jumps if not handled carefully.

Optimal Insight: The brute-force simulation is already optimal because each index is executed at most once. The key insight is using a hash set or boolean array to efficiently track visited instructions and prevent repeated execution, ensuring O(1) check per step. No complex preprocessing is necessary, and the problem reduces to careful simulation with bounds and visitation checks.

Approach	Time Complexity	Space Complexity	Notes
Brute Force / Simulation	O(n)	O(n)	Execute each instruction once, track visited indices
Optimal	O(n)	O(n)	Same as brute force; optimized by direct hash/set access for visited

Algorithm Walkthrough

Initialize a variable score = 0 to track the accumulated sum.
Initialize a set visited to record indices that have been executed.
Start a pointer i = 0 for the current instruction index.
While i is within bounds (0 <= i < n) and i is not in visited:
Add i to visited.
If instructions[i] is "add", increment score by values[i] and increment i by 1.
If instructions[i] is "jump", increment i by values[i] (can be negative).
When the loop terminates, return score.

Why it works: Each instruction is executed at most once due to the visited set, guaranteeing that the simulation respects the halting conditions. Bounds checks ensure the process terminates correctly if an instruction would move execution out of the array.

Python Solution

from typing import List

class Solution:
    def calculateScore(self, instructions: List[str], values: List[int]) -> int:
        n = len(instructions)
        visited = set()
        score = 0
        i = 0
        
        while 0 <= i < n and i not in visited:
            visited.add(i)
            if instructions[i] == "add":
                score += values[i]
                i += 1
            else:  # instructions[i] == "jump"
                i += values[i]
                
        return score

Implementation Walkthrough: We initialize score and visited. The while loop continues as long as the index is valid and unvisited. For "add", we increment the score and move to the next index. For "jump", we compute the new index as i + values[i]. Using a set allows O(1) membership checks to enforce the revisiting condition.

Go Solution

func calculateScore(instructions []string, values []int) int64 {
    n := len(instructions)
    visited := make(map[int]struct{})
    var score int64 = 0
    i := 0

    for i >= 0 && i < n {
        if _, ok := visited[i]; ok {
            break
        }
        visited[i] = struct{}{}
        if instructions[i] == "add" {
            score += int64(values[i])
            i++
        } else { // "jump"
            i += values[i]
        }
    }
    return score
}

Go-specific Notes: The visited set is implemented as a map[int]struct{} for O(1) membership checks. score is declared int64 to handle potential integer overflows, especially since the sum of large positive and negative numbers may exceed int. The loop and condition logic mirror Python's simulation.

Worked Examples

Example 1:

Step	i	instruction	value	score	visited
1	0	jump	2	0	{0}
2	2	add	3	3	{0,2}
3	3	jump	1	3	{0,2,3}
4	4	add	-2	1	{0,2,3,4}
5	5	jump	-3	1	{0,2,3,4,5}
6	2	add	3	1	stop, revisited

Output: 1

Example 2:

Step	i	instruction	value	score	visited
1	0	jump	3	0	{0}
2	3	out of bounds	-	0	stop

Output: 0

Example 3:

Step	i	instruction	value	score	visited
1	0	jump	0	0	{0}
2	0	revisited	-	0	stop

Output: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is visited at most once; set operations are O(1)
Space	O(n)	`visited` set stores up to n indices

The simulation guarantees each instruction is processed at most once, so the linear time bound holds even for large arrays. The extra space is necessary to enforce the revisiting condition.

Test Cases

sol = Solution()

# Provided examples
assert sol.calculateScore(["jump","add","add","jump","add","jump"], [2,1,3,1,-2,-3]) == 1  # loops and adds
assert sol.calculateScore(["jump","add","add"], [3,1,1]) == 0  # jumps out of bounds
assert sol.calculateScore(["jump"], [0]) == 0  # self-loop

# Edge cases
assert sol.calculateScore(["add"], [5]) == 5  # single add
assert sol.calculateScore(["jump"], [1]) == 0  # single jump out of bounds
assert sol.calculateScore(["add","jump","add"], [2,2,3]) == 2  # jump skips last add
assert sol.calculateScore(["jump","jump","jump"], [-1,-1,-1]) == 0  # negative jumps exit bounds
assert sol.calculateScore(["add"]*100000, [1]*100000) == 100000  # maximum n

# Mixed jumps
assert sol.calculateScore(["add","jump","add","jump"], [1,2,3,-1]) == 1  # revisits

Test	Why
loops and adds	Validates jump and add sequencing with revisits
jumps out of bounds	Halting when index exceeds n-1
self-loop	Halting on revisiting same index
single add	Minimal input
single jump out of bounds	Minimal jump outside array
jump skips last add	Skipped instructions correctly handled
negative jumps	Handles negative indices and bounds
maximum n	Tests performance for n = 10^5
mixed jumps	Tests revisits in mixed instruction sequence

Edge Cases

Single-element arrays: These arrays can either add a value or jump out of bounds or loop to themselves. Implementations must handle i = 0 correctly and avoid index errors or infinite loops. Both Python and Go solutions correctly terminate using the visited set and bounds checks.

Negative jumps: A jump may result in a negative