Calculate Score After Performing Instructions

Calculate Score After Performing Instructions - Problem

You are given two arrays, instructions and values, both of size n. You need to simulate a process based on the following rules:

Starting conditions:

You start at the first instruction at index i = 0
Initial score is 0

Instruction processing:

If instructions[i] is "add": Add values[i] to your score and 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)
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.

Input & Output

Example 1 — Basic Simulation

$ Input: instructions = ["add","jump","add"], values = [2,-1,3]

› Output: 2

💡 Note: Start at i=0: execute 'add', score becomes 2, move to i=1. At i=1: execute 'jump', jump to i=0 (already visited). Process ends with score 2.

Example 2 — Out of Bounds

$ Input: instructions = ["add","jump"], values = [5,2]

› Output: 5

💡 Note: Start at i=0: execute 'add', score becomes 5, move to i=1. At i=1: execute 'jump', jump to i=3 (out of bounds). Process ends with score 5.

Example 3 — Multiple Adds

$ Input: instructions = ["add","add","jump"], values = [1,2,-1]

› Output: 3

💡 Note: i=0: add 1, score=1, move to i=1. i=1: add 2, score=3, move to i=2. i=2: jump to i=1 (already visited). Process ends with score 3.

Constraints

1 ≤ instructions.length ≤ 10⁴
instructions[i] is either "add" or "jump"
-10⁴ ≤ values[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Arrays of instructions and corresponding values

Process

Simulate execution while tracking visited positions

Output

Final score when process terminates

Key Takeaway

🎯 Key Insight: Use visited tracking to detect cycles and prevent infinite loops during simulation

Asked in

A Amazon 15 M Microsoft 12

This problem requires simulation of instruction execution with cycle detection. The key insight is to track visited positions using a set or boolean array to detect when we revisit a position. We execute 'add' instructions by adding to score and moving forward, while 'jump' instructions move us by the given offset. Process terminates on out-of-bounds access or cycle detection. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with Visited Set	O(n)	O(n)	Simulate the process step by step while tracking visited indices
Optimized Simulation	O(n)	O(n)	Same approach as brute force - this problem requires simulation

Simulation with Visited Set — Algorithm Steps

Start at index 0 with score 0
For each position, check if already visited
Execute 'add' or 'jump' instruction
Stop when out of bounds or cycle detected

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start at index 0, score 0, empty visited set

Execute

Follow add/jump instructions, mark positions as visited

Terminate

Stop when out of bounds or cycle detected

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(char instructions[][10], int* values, int n) {
    int score = 0;
    int i = 0;
    bool* visited = (bool*)calloc(n, sizeof(bool));
    
    while (i >= 0 && i < n && !visited[i]) {
        visited[i] = true;
        
        if (strcmp(instructions[i], "add") == 0) {
            score += values[i];
            i += 1;
        } else { // jump
            i += values[i];
        }
    }
    
    free(visited);
    return score;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse instructions - simple parsing for basic cases
    char instructions[100][10];
    int n = 0;
    char* token = strtok(line, "[],\"\n");
    while (token != NULL && n < 100) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            strcpy(instructions[n], token);
            n++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    fgets(line, sizeof(line), stdin);
    // Parse values
    int values[100];
    int count = 0;
    token = strtok(line, "[],\n");
    while (token != NULL && count < n) {
        if (strlen(token) > 0) {
            values[count] = atoi(token);
            count++;
        }
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(instructions, values, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case, we visit each instruction exactly once before detecting a cycle or going out of bounds

✓ Linear Growth

Space Complexity

O(n)

We need a set to store visited indices, which can contain up to n elements

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation with Visited Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler