3522. Calculate Score After Performing Instructions

MediumArrayHash TableStringSimulation

Leetcode Link

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).
If instructions[i] is "jump":
- Move to the instruction at index (i + values[i]) without modifying your score.

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 the instructions array to record whether each instruction has been executed. Initially, all elements of vis are set to false.
Simulation Process: Start from index i = 0 with a score of 0. For each instruction, perform the following checks:
- If the instruction is "add", update the score by adding the corresponding value from values[i] and increment i by 1.
- If the instruction is "jump", update the index i by adding the corresponding value from values[i] to i.
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] is true).

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 length n 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.
Algorithm:
- Initialize vis to [False] * n, ans to 0, and the index i to 0.
- Use a while loop to iterate through the instructions as long as i 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] to True.
  - Check the type of the instruction:
    - If it is "add", increase the score by values[i] and move to the next instruction by incrementing i by 1.
    - If it is "jump", adjust the index i to jump to the new position i + values[i] without changing the score.
- The loop terminates either when an instruction revisitation is detected (vis[i] is True) or when i becomes out of bounds (i < 0 or i >= n).
Return Result:
- Once the loop exits, return the accumulated score ans.

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 Evaluator

Example 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 of 0.
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] as True ➔ vis = [True, False, False, False]
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] as True ➔ vis = [True, True, False, False]
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] as True ➔ vis = [True, True, False, True]
Termination:
- Index i = 4 is out of bounds (since the length of instructions is 4).
- The process stops as the termination condition is met.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know