LeetCode 3522 - Calculate Score After Performing Instructions

LeetCode Problem 3522

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

Solution

Problem Understanding

This problem asks you to simulate a linear sequence of instructions that can either modify a running score or move the instruction pointer by a specified offset. You are given two arrays, instructions and values, both of size n. Each index i represents an instruction. If instructions[i] is "add", you add values[i] to a running score and advance to the next instruction. If instructions[i] is "jump", you move the instruction pointer by values[i] without changing the score.

The simulation stops if you either move out of bounds or attempt to execute an instruction you have already executed. The problem requires returning the total score accumulated when the process stops.

Constraints indicate that n can be as large as 10^5 and values can range from -10^5 to 10^5. This implies the solution must handle large input efficiently, and naive repeated traversal could be too slow if not careful.

Important edge cases include:

• A jump of 0, which could immediately lead to revisiting the same instruction.
• Jumps that move out of bounds immediately.
• All instructions being "add" or all "jump".
• Negative values causing backward jumps.

Approaches

Brute Force Approach

The simplest approach is a direct simulation. Start at index 0, maintain a visited set to track executed instructions, and iterate according to the rules. For each instruction, check whether the next index would be out of bounds or previously visited. If not, perform the operation (add or jump) and continue.

This approach is correct but has a time complexity of O(n) in the best case, but O(n) worst-case is acceptable given n <= 10^5. Using a set for visited indices ensures O(1) lookup, so this naive simulation is actually efficient enough for the constraints.

Optimal Approach

Since the brute-force simulation is already O(n) and each instruction is executed at most once, it is effectively optimal. There are no hidden optimizations needed because revisiting instructions ends the simulation, and each instruction is processed exactly once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Direct simulation with a set to track visited instructions
Optimal	O(n)	O(n)	Same as brute force; each instruction executed at most once

Algorithm Walkthrough

1. Initialize score to 0 and index to 0 to track the current instruction.
2. Create a set visited to store indices that have already been executed.
3. Loop while index is within bounds (0 <= index < n) and not in visited.
4. Add the current index to the visited set.
5. Check the instruction type:

• If "add", increment score by values[index] and move to index + 1.
• If "jump", move to index + values[index] without changing score.

6. Repeat until the loop terminates because the index is out of bounds or revisited.
7. Return the final score.

Why it works: Each instruction is executed at most once, and the simulation follows the exact rules. The use of a visited set ensures that revisits immediately terminate the process. All edge cases like jumps out of bounds or zero jumps are handled naturally by the loop condition.

Python Solution

from typing import List

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

Explanation: The while loop ensures that the simulation stops correctly. The visited set prevents revisiting instructions. "add" instructions update the score and move sequentially, while "jump" updates the index without changing the score. This implements the algorithm directly and efficiently.

Go Solution

func calculateScore(instructions []string, values []int) int64 {
    var score int64 = 0
    index := 0
    visited := make(map[int]bool)
    n := len(instructions)
    
    for index >= 0 && index < n && !visited[index] {
        visited[index] = true
        if instructions[index] == "add" {
            score += int64(values[index])
            index++
        } else { // "jump"
            index += values[index]
        }
    }
    
    return score
}

Explanation: Go requires using int64 to handle large values for score. The visited map tracks visited indices, similar to the Python set. The logic mirrors the Python solution, with proper handling of types and map access.

Worked Examples

Example 1

instructions = ["jump","add","add","jump","add","jump"], values = [2,1,3,1,-2,-3]

Step	Index	Instruction	Value	Score	Next Index	Visited
1	0	jump	2	0	2	{0}
2	2	add	3	3	3	{0,2}
3	3	jump	1	3	4	{0,2,3}
4	4	add	-2	1	5	{0,2,3,4}
5	5	jump	-3	1	2	{0,2,3,4,5}

Index 2 already visited, stop. Final score = 1

Example 2

instructions = ["jump","add","add"], values = [3,1,1]

Step	Index	Instruction	Value	Score	Next Index	Visited
1	0	jump	3	0	3	{0}

Index 3 out of bounds, stop. Final score = 0

Example 3

instructions = ["jump"], values = [0]

Step	Index	Instruction	Value	Score	Next Index	Visited
1	0	jump	0	0	0	{0}

Index 0 already visited, stop. Final score = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each instruction is processed at most once and set lookups are O(1)
Space	O(n)	The visited set stores up to n indices

The algorithm is efficient given the constraints, and both time and space scale linearly with input size.

Test Cases

# Basic examples
assert Solution().calculateScore(["jump","add","add","jump","add","jump"], [2,1,3,1,-2,-3]) == 1
assert Solution().calculateScore(["jump","add","add"], [3,1,1]) == 0
assert Solution().calculateScore(["jump"], [0]) == 0

# All add instructions
assert Solution().calculateScore(["add","add","add"], [1,2,3]) == 6

# All jump instructions
assert Solution().calculateScore(["jump","jump","jump"], [1,2,3]) == 0

# Jump out of bounds
assert Solution().calculateScore(["jump","add"], [5,10]) == 0

# Negative jumps
assert Solution().calculateScore(["add","jump","add"], [1,-1,2]) == 1

# Large input
instructions = ["add"]*100000
values = [1]*100000
assert Solution().calculateScore(instructions, values) == 100000

Test	Why
Provided examples	Validates normal operation and stopping conditions
All add	Ensures sequential adds accumulate correctly
All jump	Ensures jumps alone terminate simulation if out of bounds
Jump out of bounds	Edge case for immediate termination
Negative jumps	Tests backward movement handling
Large input	Stress test for performance

Edge Cases

Zero Jump: A jump of value 0 immediately revisits the same instruction. Without the visited set, this could cause an infinite loop. Using visited ensures proper termination.

Negative Jump: Instructions can move backward in the array. The algorithm correctly updates index and checks for revisits to avoid infinite loops.

Out-of-Bounds Jump: Any jump moving beyond 0 <= index < n terminates the simulation. This includes both forward jumps past n-1 and backward jumps below 0. The while loop condition guarantees termination.