#3522

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Calculate Score After Performing Instructions

Simulate a series of add and jump instructions on arrays to compute the final score efficiently using array scanning and hash lookup.

array hash table string simulation

Problem Statement

You are given two arrays of length n: instructions and values. Each instruction is either 'add' or 'jump', and values contains corresponding integer numbers. You must simulate the instructions starting from index 0, modifying a running score according to the rules below.

Follow these rules step by step: for an 'add' instruction, add the value to your score; for a 'jump' instruction, move the pointer by the value. The process ends when the pointer moves outside the array bounds or all instructions are processed. Return the final score after simulating all instructions.

Examples

Example 1

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

Output: 1

Simulate the process starting at instruction 0:

Example 2

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

Output: 0

Simulate the process starting at instruction 0:

Example 3

Input: instructions = ["jump"], values = [0]

Output: 0

Simulate the process starting at instruction 0:

Constraints

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

Solution Approach

Sequential Simulation

Iterate through the instructions array, applying each 'add' or 'jump' in order. Keep track of the current index and update the running score on 'add'. For 'jump', adjust the index and verify bounds to prevent errors. This directly follows the array scanning plus hash lookup pattern.

Hash Table Optimization

Use a hash table to record previous positions or values to avoid repeated computation on identical sequences. This ensures that when similar instructions or values occur, you can retrieve prior results instantly, maintaining efficiency for large n.

Edge Case Handling

Carefully handle negative jumps and boundary conditions. Ensure that adding negative values or jumping beyond array limits does not cause runtime errors. Always check the hash table first for existing entries to prevent unnecessary recalculation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for scanning all instructions with O(1) hash lookups per operation. Space complexity is O(n) due to storing positions or values in the hash table for fast access.

What Interviewers Usually Probe

Focus on array scanning combined with hash table lookups.
Check edge conditions for jumps going out of array bounds.
Look for opportunities to reuse computed values for repeated sequences.

Common Pitfalls or Variants

Common pitfalls

Failing to check array bounds after a jump, leading to runtime errors.
Overwriting or ignoring previous hash entries, causing incorrect scores.
Confusing the order of add and jump operations when updating score.

Follow-up variants

Instructions could include multiply operations requiring dynamic score adjustments.
Allow variable-length jumps based on previous scores, increasing simulation complexity.
Use nested instruction sequences, requiring multi-level hash tracking for correctness.

FAQ

What is the main strategy for Calculate Score After Performing Instructions?

Simulate instructions sequentially while tracking values with a hash table to efficiently compute the final score.

Can jumps move the pointer outside the array?

Yes, the process ends immediately if a jump causes the pointer to go out of bounds.

How do I handle repeated instruction sequences?

Use a hash table to store previously computed results for identical sequences to avoid recalculation.

Are negative values allowed in the instructions array?

Yes, negative values can occur and must be handled correctly for both add and jump operations.

Why is array scanning plus hash lookup crucial here?

Because it allows fast traversal of instructions while quickly accessing prior results to maintain efficiency on large inputs.

terminal

Solution

Solution 1: Simulation

We can simulate the process based on the problem description.

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#2744 find maximum number of string pairs #3527 find the most common response #3510 minimum pair removal to sort array ii