Replace Elements in an Array

Replace Elements in an Array

What is this problem about?

The Replace Elements in an Array interview question gives you an integer array nums and a 2D array operations. Each operation [original, replacement] means you replace every occurrence of original in nums with replacement. After applying all operations in sequence, return the resulting array. The challenge is efficiency: a naive approach that scans nums for each operation is too slow for large inputs.

Why is this asked in interviews?

Amazon asks this problem to test a candidate's understanding of hash map-based value tracking and lazy evaluation. The efficient solution uses an indirection map to resolve what each original value ultimately becomes, then applies it in a single pass over nums. It evaluates whether candidates recognize when a mapping layer is more efficient than repeated linear scans — a pattern common in compiler symbol tables and database query planners.

Algorithmic pattern used

The pattern is hash table simulation with value chaining. Build a map tracking final substitution values. For each operation [orig, repl]: check if orig is itself a substituted value in the current map (chain resolution). Add orig → repl to the map, and if repl is already a key in the map (meaning it will be further replaced), update accordingly. After processing all operations, do a single pass over nums and apply the map.

Example explanation

nums = [1, 2, 4, 6], operations = [[1,3],[4,7],[6,1]]

Process operations:

• 1 → 3
• 4 → 7
• 6 → 1, but 1 → 3, so chain: 6 → 3

Final map: {1:3, 4:7, 6:3}.

Apply to nums: 1→3, 2→2 (unchanged), 4→7, 6→3. Result: [3, 2, 7, 3].

Common mistakes candidates make

• Scanning and modifying nums for each operation — O(n × m) and too slow.
• Not chaining replacements when a replacement target has itself been replaced by a prior operation.
• Forgetting that elements not in any operation remain unchanged.
• Building the map incorrectly by only tracking single-step replacements.

Interview preparation tip

For the Replace Elements in an Array coding problem, the hash table and simulation interview pattern is the efficient path. Build the final mapping first, apply once. Practice tracing chained substitutions (A→B, B→C yields A→C). Amazon interviewers may ask "what if operations cycle?" — show you can detect cycles using a visited set or cycle-detection logic.