Replace Elements in an Array

Medium
1156.

Replace Elements in an Array

Replace Elements in an Array is a medium coding problem on arrays, hash table and simulation, asked in Amazon and Google interviews.

nums holds n distinct positive integers. Apply the operations in order: operation operations[i] = [a, b] replaces the element whose value is a with the value b.

Every operation is guaranteed to be valid at the moment it runs: a is currently in nums, and b currently is not (so the elements stay distinct).

Return nums after all the operations.

Example 1

Input
nums = [4,9,2,7], operations = [[9,3],[2,8],[3,1]]
Output
[4,1,8,7]
Explanation
`[4,9,2,7]` → `[4,3,2,7]` → `[4,3,8,7]` → `[4,1,8,7]`. The third operation replaces the value written by the first.

Example 2

Input
nums = [5,6], operations = [[5,1],[1,5],[6,1]]
Output
[5,1]

Constraints

  • n == nums.length
  • m == operations.length
  • 1 <= n, m <= 10^5
  • All values in nums are distinct
  • operations[i].length == 2
  • 1 <= nums[i], operations[i][0], operations[i][1] <= 10^6
  • operations[i][0] is in nums and operations[i][1] is not, when operation i is applied
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[][]} operations
 * @return {number[]}
 */
var arrayChange = function(nums, operations) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Replace Elements in an Array — Problem & Solution

Replace Elements in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Replace Elements in an Array is a medium coding problem on arrays, hash table and simulation, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Simulation
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums holds n distinct positive integers. Apply the operations in order: operation operations[i] = [a, b] replaces the element whose value is a with the value b.

Every operation is guaranteed to be valid at the moment it runs: a is currently in nums, and b currently is not (so the elements stay distinct).

Return nums after all the operations.

Example 1

Input: nums = [4,9,2,7], operations = [[9,3],[2,8],[3,1]]
Output: [4,1,8,7]
Explanation: `[4,9,2,7]` → `[4,3,2,7]` → `[4,3,8,7]` → `[4,1,8,7]`. The third operation replaces the value written by the first.

Example 2

Input: nums = [5,6], operations = [[5,1],[1,5],[6,1]]
Output: [5,1]

Constraints

  • n == nums.length
  • m == operations.length
  • 1 <= n, m <= 10^5
  • All values in nums are distinct
  • operations[i].length == 2
  • 1 <= nums[i], operations[i][0], operations[i][1] <= 10^6
  • operations[i][0] is in nums and operations[i][1] is not, when operation i is applied

Hints for Replace Elements in an Array

  1. Hint 1

    Searching the array for a on every operation costs O(n) each time.

  2. Hint 2

    Since the values stay distinct, a value identifies one position.

  3. Hint 3

    Keep a map from value to index; each operation moves that index from key a to key b.

How to solve Replace Elements in an Array

Distinct values make value → position a well-defined map, and an operation only changes one entry of it, so each replacement costs O(1).

Approach

  1. Build pos[value] = index for the initial array.
  2. For each operation [a, b]: look up i = pos[a], set nums[i] = b, remove a from the map and record pos[b] = i.
  3. Return the array.

Why it works

The guarantees keep the values distinct after every operation, so the map stays a bijection between current values and positions. Each operation reads the correct position for a and updates the map exactly the way the array changed.

Complexity

  • Time — O(n + m)
  • Space — O(n)

Pitfalls

  • An operation may target a value written by an earlier operation — the map must be updated, not built once.
  • Do not search with indexOf per operation; that is O(n·m).
  • Removing a from the map is optional (it can never be looked up again until it is re-inserted) but keeps the map honest.

Reference solution

Python

from typing import List

def arrayChange(nums: List[int], operations: List[List[int]]) -> List[int]:
    res = list(nums)
    pos = {x: i for i, x in enumerate(res)}
    for a, b in operations:
        i = pos.pop(a)
        res[i] = b
        pos[b] = i
    return res

Java

public static int[] arrayChange(int[] nums, int[][] operations) {
    int[] res = nums.clone();
    Map<Integer, Integer> pos = new HashMap<>();
    for (int i = 0; i < res.length; i++) pos.put(res[i], i);
    for (int[] op : operations) {
        int at = pos.remove(op[0]);
        res[at] = op[1];
        pos.put(op[1], at);
    }
    return res;
}

C++

vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
    vector<int> res(nums.begin(), nums.end());
    unordered_map<int, int> pos;
    for (int i = 0; i < (int)res.size(); i++) pos[res[i]] = i;
    for (auto& op : operations) {
        int at = pos[op[0]];
        pos.erase(op[0]);
        res[at] = op[1];
        pos[op[1]] = at;
    }
    return res;
}

JavaScript

var arrayChange = function(nums, operations) {
    var res = nums.slice();
    var pos = new Map();
    for (var i = 0; i < res.length; i++) pos.set(res[i], i);
    for (var k = 0; k < operations.length; k++) {
        var a = operations[k][0], b = operations[k][1];
        var at = pos.get(a);
        pos.delete(a);
        res[at] = b;
        pos.set(b, at);
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets