# Calculate Score After Performing Instructions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/calculate-score-after-performing-instructions)
Canonical: https://scaleengineer.com/dsa/problems/calculate-score-after-performing-instructions
**Data structures:** Array, Hash Table, String
---
## Problem
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.

**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 index `0 + 2 = 2`.
* At index 2: Instruction is `"add"`, add `values[2] = 3` to your score and move to index 3\. Your score becomes 3.
* At index 3: Instruction is `"jump"`, move to index `3 + 1 = 4`.
* At index 4: Instruction is `"add"`, add `values[4] = -2` to your score and move to index 5\. Your score becomes 1.
* At index 5: Instruction is `"jump"`, move to index `5 + (-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 index `0 + 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 index `0 + 0 = 0`.
* At index 0: Already visited. The process ends.

**Constraints:**

* `n == instructions.length == values.length`
* `1 <= n <= 105`
* `instructions[i]` is either `"add"` or `"jump"`.
* `-105 <= values[i] <= 105`

# Approaches
## Brute-Force Simulation using a List
This approach directly simulates the process described in the problem. We use a loop that tracks the current instruction index and the score. To handle the rule about not revisiting an instruction, we maintain a list of all indices that have been executed. In each step, before executing an instruction, we check if the current index is already in our list of visited indices.
**Time:** O(n^2), where `n` is the number of instructions. The simulation loop can run at most `n` times. In each iteration `k`, checking for a visited index with `list.contains()` takes O(k) time, leading to a total time complexity of O(1 + 2 + ... + n) = O(n^2). · **Space:** O(n). The `visitedIndices` list can store up to `n` distinct indices.
**Pros:** Simple to understand and implement.; Directly translates the problem statement into code.
**Cons:** Inefficient due to the O(n) check for visited indices in each step.; Likely to result in a 'Time Limit Exceeded' error on larger test cases.
### Explanation
The simulation proceeds step-by-step, starting from index 0 with a score of 0. A `List` is used to keep track of every index visited.

The core of the simulation is a `while` loop. In each iteration, we first check for the two termination conditions:
1.  The `currentIndex` is out of the valid bounds (`0` to `n-1`).
2.  The `currentIndex` is already present in our `visitedIndices` list.

Checking for presence in a list (`List.contains()`) requires scanning the list, which takes time proportional to the number of elements already in it. If the loop continues, we add the current index to the list, execute the 'add' or 'jump' instruction to update the score and the current index, and then proceed to the next iteration.

Because the check for visited indices is slow, this approach is not efficient for large inputs.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public long calculateScore(String[] instructions, int[] values) {
        int n = instructions.length;
        long score = 0;
        int currentIndex = 0;
        List<Integer> visitedIndices = new ArrayList<>();

        while (true) {
            if (currentIndex < 0 || currentIndex >= n) {
                // Out of bounds
                break;
            }
            if (visitedIndices.contains(currentIndex)) {
                // Revisited instruction
                break;
            }

            visitedIndices.add(currentIndex);

            String instruction = instructions[currentIndex];
            int value = values[currentIndex];

            if ("add".equals(instruction)) {
                score += value;
                currentIndex++;
            } else if ("jump".equals(instruction)) {
                currentIndex += value;
            }
        }
        return score;
    }
}
```
### Algorithm
- Initialize `score` to 0, `currentIndex` to 0.
- Initialize an empty `List` called `visitedIndices`.
- Start an infinite loop.
- Inside the loop, check if `currentIndex` is out of bounds or if `visitedIndices` contains `currentIndex`. If either is true, break the loop.
- Add `currentIndex` to `visitedIndices`.
- Based on `instructions[currentIndex]`, update `score` and `currentIndex`.
- Return `score` after the loop terminates.

## Optimized Simulation with O(1) Visited Check
This approach significantly improves the simulation's performance by using a more efficient data structure to track visited indices. Instead of a list which has an O(n) lookup time, we use a data structure with O(1) lookup time, such as a boolean array or a `HashSet`. This optimization reduces the overall time complexity from quadratic to linear.
**Time:** O(n), where `n` is the number of instructions. The simulation loop can run at most `n` times because it stops upon revisiting an index. Each operation inside the loop (array access, comparison, arithmetic) is O(1). · **Space:** O(n). We need a boolean array of size `n` to store the visited status of each index.
**Pros:** Optimal time complexity for this problem.; Efficient and handles large inputs.
**Cons:** Requires O(n) extra space for the visited set/array.
### Explanation
The fundamental simulation logic remains the same, but the efficiency of checking for previously visited indices is drastically improved.

We can use a `boolean[]` array of size `n`, say `visited`, where `visited[i]` being `true` indicates that instruction `i` has been executed. Checking if an index `i` has been visited is now a simple O(1) array lookup: `visited[i]`.

The simulation loop now looks like this: `while (currentIndex >= 0 && currentIndex < n && !visited[currentIndex])`. This combines the bounds check and the visited check into a single, efficient condition. Inside the loop, we mark the current index as visited (`visited[currentIndex] = true;`) and then proceed with the instruction logic.

This change makes each step of the simulation take constant time, leading to an overall linear time solution.

An alternative with the same time complexity is to use a `HashSet<Integer>`, which also provides O(1) average time for insertion and lookup. This is a more general solution if indices weren't constrained to a simple `0..n-1` range.

Here is the implementation using a boolean array:
```java
class Solution {
    public long calculateScore(String[] instructions, int[] values) {
        int n = instructions.length;
        long score = 0;
        int currentIndex = 0;
        boolean[] visited = new boolean[n];

        while (currentIndex >= 0 && currentIndex < n && !visited[currentIndex]) {
            visited[currentIndex] = true;

            String instruction = instructions[currentIndex];
            int value = values[currentIndex];

            if ("add".equals(instruction)) {
                score += value;
                currentIndex++;
            } else { // "jump"
                currentIndex += value;
            }
        }
        return score;
    }
}
```
### Algorithm
- Initialize `score` to 0, `currentIndex` to 0.
- Initialize a `boolean` array `visited` of size `n` to all `false`.
- Loop while `currentIndex` is in bounds and `visited[currentIndex]` is `false`.
- Inside the loop, set `visited[currentIndex]` to `true`.
- Based on `instructions[currentIndex]`, update `score` and `currentIndex`.
- Return `score` after the loop terminates.

# Solutions
### Java

```java
class Solution {
public
  long calculateScore(String[] instructions, int[] values) {
    int n = values.length;
    boolean[] vis = new boolean[n];
    long ans = 0;
    int i = 0;
    while (i >= 0 && i < n && !vis[i]) {
      vis[i] = true;
      if (instructions[i].charAt(0) == 'a') {
        ans += values[i];
        i += 1;
      } else {
        i = i + values[i];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long calculateScore(vector<string> &instructions, vector<int> &values) {
    int n = values.size();
    vector<bool> vis(n, false);
    long long ans = 0;
    int i = 0;
    while (i >= 0 && i < n && !vis[i]) {
      vis[i] = true;
      if (instructions[i][0] == 'a') {
        ans += values[i];
        i += 1;
      } else {
        i += values[i];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def calculateScore(self, instructions: List[str], values: List[int]) -> int: n = len(values) vis = [False] * n ans = i = 0 while 0 <= i < n and not vis[i]: vis[i] = True if instructions[i][0] == "a": ans += values[i] i += 1 else: i = i + values[i] return ans

```