3522. Calculate Score After Performing Instructions
Problem Description
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 = 0
with 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.
Intuition
To solve this problem, the key is to simulate the instruction execution process while keeping track of which instructions have already been executed to prevent revisits.
-
Tracking Visited Instructions: Use a boolean array
vis
of the same size as theinstructions
array to record whether each instruction has been executed. Initially, all elements ofvis
are set tofalse
. -
Simulation Process: Start from index
i = 0
with a score of0
. For each instruction, perform the following checks:- If the instruction is
"add"
, update the score by adding the corresponding value fromvalues[i]
and incrementi
by1
. - If the instruction is
"jump"
, update the indexi
by adding the corresponding value fromvalues[i]
toi
.
- If the instruction is
-
Termination Conditions: Continue the process until you move out of bounds (
i < 0 or i >= n
) or encounter an instruction index that has already been executed (vis[i]
istrue
).
The key is the maintenance of the vis
array to prevent repetitive execution of any instruction, which could lead to infinite loops or incorrect score calculations. Once you detect any of the termination conditions, return the current score. This approach ensures efficient and correct simulation of the instruction sequence.
Solution Approach
The solution to this problem is based on the simulation of instruction execution and is implemented using a straightforward approach leveraging arrays and simple control flow.
-
Data Structures Used:
- A boolean array
vis
of lengthn
is used to track whether each instruction has been executed. This helps in avoiding revisiting any instruction, thus preventing infinite loops. - An integer
ans
is used to keep track of the score as the instructions are executed.
- A boolean array
-
Algorithm:
- Initialize
vis
to[False] * n
,ans
to0
, and the indexi
to0
. - Use a
while
loop to iterate through theinstructions
as long asi
is within valid bounds (0 <= i < n
) and the current instruction hasn't been executed before (not vis[i]
). - Inside the loop:
- Mark the current instruction as executed by setting
vis[i]
toTrue
. - Check the type of the instruction:
- If it is
"add"
, increase the score byvalues[i]
and move to the next instruction by incrementingi
by1
. - If it is
"jump"
, adjust the indexi
to jump to the new positioni + values[i]
without changing the score.
- If it is
- Mark the current instruction as executed by setting
- The loop terminates either when an instruction revisitation is detected (
vis[i]
isTrue
) or wheni
becomes out of bounds (i < 0 or i >= n
).
- Initialize
-
Return Result:
- Once the loop exits, return the accumulated score
ans
.
- Once the loop exits, return the accumulated score
This solution efficiently simulates the instructions' effects by combining a simple loop structure and an auxiliary array (vis
) to manage the execution state, ensuring that all rules are followed correctly according to the problem statement.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to demonstrate the solution approach.
Example Input:
instructions
:["add", "jump", "add", "add"]
values
:[2, 2, 1, 1]
Initial Setup:
- Start at index
i = 0
with an initial score of0
. - Initialize a boolean array
vis
to[False, False, False, False]
to track executed instructions.
Step-by-Step Execution:
-
Index
i = 0
:- Instruction:
"add"
- Value:
2
- Action: Add
2
to score. - Updated Score:
2
- Move to the next instruction:
i = 1
- Mark
vis[0]
asTrue
➔vis = [True, False, False, False]
- Instruction:
-
Index
i = 1
:- Instruction:
"jump"
- Value:
2
- Action: Jump to index
i + 2 = 3
- Score remains:
2
- Move to instruction at
i = 3
- Mark
vis[1]
asTrue
➔vis = [True, True, False, False]
- Instruction:
-
Index
i = 3
:- Instruction:
"add"
- Value:
1
- Action: Add
1
to score. - Updated Score:
3
- Move to the next instruction:
i = 4
- Mark
vis[3]
asTrue
➔vis = [True, True, False, True]
- Instruction:
-
Termination:
- Index
i = 4
is out of bounds (since the length ofinstructions
is4
). - The process stops as the termination condition is met.
- Index
Final Score:
- The score after executing all instructions correctly is
3
.
This walkthrough effectively demonstrates how to implement the instruction execution simulation by maintaining a visited state for each instruction and updating the score according to the instructions.
Solution Implementation
1from typing import List
2
3class Solution:
4 def calculateScore(self, instructions: List[str], values: List[int]) -> int:
5 n = len(values) # Determine the number of elements
6 visited = [False] * n # Track visited indices to avoid loops
7 score = current_index = 0 # Initialize score and index pointer
8
9 # Loop to iterate through instructions as long as indices are within bounds and not revisited
10 while 0 <= current_index < n and not visited[current_index]:
11 visited[current_index] = True # Mark the current index as visited
12
13 # Check if the instruction starts with 'a' (indicating 'add')
14 if instructions[current_index][0] == "a":
15 score += values[current_index] # Add current value to score
16 current_index += 1 # Move to the next instruction
17
18 # Otherwise, it's a 'jump' type instruction
19 else:
20 current_index += values[current_index] # Jump to the specified index
21
22 return score # Return the final calculated score
23
1class Solution {
2 // Method to calculate the score based on instructions and values arrays
3 public long calculateScore(String[] instructions, int[] values) {
4 int n = values.length; // Get the size of the values array
5 boolean[] visited = new boolean[n]; // To keep track of visited indices to prevent loops
6 long score = 0; // Initialize score as long to handle large sums
7 int index = 0; // Start from the first element
8
9 // Loop through the array while the index is within bounds and not revisited
10 while (index >= 0 && index < n && !visited[index]) {
11 visited[index] = true; // Mark the current index as visited
12 if (instructions[index].charAt(0) == 'a') {
13 score += values[index]; // Add value to score if instruction starts with 'a'
14 index += 1; // Move to the next index
15 } else {
16 index = index + values[index]; // Jump to a new index based on the value
17 }
18 }
19
20 return score; // Return the final calculated score
21 }
22}
23
1#include <vector>
2#include <string>
3
4class Solution {
5public:
6 // Method to calculate score based on instructions and values
7 long long calculateScore(std::vector<std::string>& instructions, std::vector<int>& values) {
8 int n = values.size();
9 std::vector<bool> visited(n, false); // Array to keep track of visited indices
10 long long score = 0; // Variable to store the accumulated score
11 int index = 0; // Current index position in the vector
12
13 // Loop until the index goes out of bounds or the index has been visited before
14 while (index >= 0 && index < n && !visited[index]) {
15 visited[index] = true; // Mark current index as visited
16
17 // Check if the instruction at current index is 'a'
18 if (instructions[index][0] == 'a') {
19 score += values[index]; // Add the value to the score
20 index += 1; // Move to the next index
21 } else {
22 index += values[index]; // Jump to a new index based on the current value
23 }
24 }
25
26 return score; // Return the calculated score
27 }
28};
29
1// Function to calculate the score based on given instructions and values
2function calculateScore(instructions: string[], values: number[]): number {
3 const n = values.length; // Determine the number of elements
4 const visited: boolean[] = Array(n).fill(false); // Track visited indices
5 let totalScore = 0; // Initialize total score
6 let index = 0; // Start at the first index
7
8 // Traverse through instructions while within bounds and unvisited
9 while (index >= 0 && index < n && !visited[index]) {
10 visited[index] = true; // Mark the current index as visited
11
12 // Check if the instruction at the current index is 'a'
13 if (instructions[index][0] === 'a') {
14 totalScore += values[index]; // Add the value to the score
15 index += 1; // Move to the next index
16 } else {
17 // Jump to another index based on the current value
18 index += values[index];
19 }
20 }
21
22 return totalScore; // Return the computed score
23}
24
Time and Space Complexity
The time complexity of the code is O(n)
, where n
is the length of the values
array. This is because the while loop iterates at most n
times, visiting each index in the values
array just once. Operations inside the loop, such as checking conditions or updating variables, are O(1)
operations, which do not add to the overall complexity.
The space complexity of the code is O(n)
as well. This is due to the vis
list, which stores boolean values indicating whether a specific index has been visited, and its length is equal to n
.
Learn more about how to find time and space complexity quickly.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!