Calculate Score After Performing Instructions - Video Solutions
Q1. Calculate Score After Performing Instructions | Leetcode Contest Solution | @Solution_spot
Calculate Score After Performing Instructions - Video Solution
Watch 9 video solutions for Calculate Score After Performing Instructions, a medium level problem involving Array, Hash Table, String. This walkthrough by Solution Spot has 244 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two arrays, instructions and values, both of size n.
You need to simulate a process based on the following rules:
- You start at the first instruction at index
i = 0with an initial score of 0. - If
instructions[i]is"add":- Add
values[i]to your score. - Move to the next instruction
(i + 1).
- Add
- If
instructions[i]is"jump":- Move to the instruction at index
(i + values[i])without modifying your score.
- Move to the instruction at index
The process ends when you either:
- Go out of bounds (i.e.,
i < 0 or i >= n), or - Attempt to revisit an instruction that has been previously executed. The revisited instruction is not executed.
Return your score at the end of the process.
Example 1:
Input: instructions = ["jump","add","add","jump","add","jump"], values = [2,1,3,1,-2,-3]
Output: 1
Explanation:
Simulate the process starting at instruction 0:
- At index 0: Instruction is
"jump", move to index0 + 2 = 2. - At index 2: Instruction is
"add", addvalues[2] = 3to your score and move to index 3. Your score becomes 3. - At index 3: Instruction is
"jump", move to index3 + 1 = 4. - At index 4: Instruction is
"add", addvalues[4] = -2to your score and move to index 5. Your score becomes 1. - At index 5: Instruction is
"jump", move to index5 + (-3) = 2. - At index 2: Already visited. The process ends.
Example 2:
Input: instructions = ["jump","add","add"], values = [3,1,1]
Output: 0
Explanation:
Simulate the process starting at instruction 0:
- At index 0: Instruction is
"jump", move to index0 + 3 = 3. - At index 3: Out of bounds. The process ends.
Example 3:
Input: instructions = ["jump"], values = [0]
Output: 0
Explanation:
Simulate the process starting at instruction 0:
- At index 0: Instruction is
"jump", move to index0 + 0 = 0. - At index 0: Already visited. The process ends.
Constraints:
n == instructions.length == values.length1 <= n <= 105instructions[i]is either"add"or"jump".-105 <= values[i] <= 105
Approach Overview
Problem Overview: You are given a sequence of instructions represented as a string and must simulate them step by step to calculate the final score. Each instruction updates the current state (such as position, value, or score), and repeated interactions often require tracking previously visited states.
Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)
The straightforward method simulates every instruction exactly as described and recomputes the effect each time the score needs to be updated. For example, when an instruction references a previous state or repeated operation, you scan earlier operations to determine the contribution. This approach uses simple iteration over the instruction string and directly applies the rules without additional data structures. While easy to implement, repeated scans make the solution inefficient when the instruction list grows.
Approach 2: Optimized Simulation with Hash Table (O(n) time, O(n) space)
The efficient strategy still performs a step‑by‑step simulation but stores intermediate results in a hash table. As you iterate through the instruction string once, maintain the current score and update it based on the instruction. A hash map or set tracks previously processed states (such as visited positions or computed values), allowing constant‑time lookups instead of rescanning earlier steps. This eliminates redundant work and keeps each instruction processing to O(1). The algorithm mainly involves iterating through the instruction sequence, updating the running score, and performing hash lookups when an instruction references past information.
This pattern is common in problems involving arrays, strings, and instruction-driven simulation. The hash table acts as a fast cache for previously computed states, a typical optimization when repeated operations appear in instruction streams.
Recommended for interviews: The optimized simulation with a hash table is the approach interviewers expect. Starting with brute force demonstrates you understand the rules of the simulation. Transitioning to the O(n) approach shows you can recognize repeated work and eliminate it using a hash table for constant‑time lookups.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Useful for understanding the instruction rules or when the input size is very small |
| Simulation with Hash Table | O(n) | O(n) | Best general solution when instructions may reference previous states or repeated operations |