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.lengthm == operations.length1 <= n, m <= 10^5All values in nums are distinctoperations[i].length == 21 <= nums[i], operations[i][0], operations[i][1] <= 10^6operations[i][0] is in nums and operations[i][1] is not, when operation i is applied
Hints for Replace Elements in an Array
Hint 1
Searching the array for
aon every operation costs O(n) each time.Hint 2
Since the values stay distinct, a value identifies one position.
Hint 3
Keep a map from value to index; each operation moves that index from key
ato keyb.
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
- Build
pos[value] = indexfor the initial array. - For each operation
[a, b]: look upi = pos[a], setnums[i] = b, removeafrom the map and recordpos[b] = i. - 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
indexOfper operation; that is O(n·m). - Removing
afrom 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 resJava
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