Watch 8 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.
You are given two arrays, instructions and values, both of size n.
You need to simulate a process based on the following rules:
i = 0 with an initial score of 0.instructions[i] is "add":
values[i] to your score.(i + 1).instructions[i] is "jump":
(i + values[i]) without modifying your score.The process ends when you either:
i < 0 or i >= n), orReturn 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:
"jump", move to index 0 + 2 = 2."add", add values[2] = 3 to your score and move to index 3. Your score becomes 3."jump", move to index 3 + 1 = 4."add", add values[4] = -2 to your score and move to index 5. Your score becomes 1."jump", move to index 5 + (-3) = 2.Example 2:
Input: instructions = ["jump","add","add"], values = [3,1,1]
Output: 0
Explanation:
Simulate the process starting at instruction 0:
"jump", move to index 0 + 3 = 3.Example 3:
Input: instructions = ["jump"], values = [0]
Output: 0
Explanation:
Simulate the process starting at instruction 0:
"jump", move to index 0 + 0 = 0.
Constraints:
n == instructions.length == values.length1 <= n <= 105instructions[i] is either "add" or "jump".-105 <= values[i] <= 105Problem 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.
| 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 |