Replace Elements in an Array solution and explanation
9 more videos on this problem
2295. Replace Elements in an Array (Leetcode Medium)Programming Live with Larry · 5:09 · 2K views
2295. Replace Elements in an Array || leetcode weekly 296 || Leetcode MediumBinaryMagic · 13:41 · 2K views
Leetcode 2295. Replace Elements in an Array | HindiThinkCode · 2:21 · 1K views
Weekly Contest 296 | 2295. Replace Elements in an ArraycodingMohan · 26:21 · 1K views
2295 Replace Elements in an Array | Zero to FAANG | Weekly 296 | Striver SDE Sheet | Shapnesh | WE2Programmers Zone · 10:07 · 845 views
Replace Elements in an Array - LeetCode 2295 - Java Solutionalgobest - Computer Science · 2:30 · 127 views
Leetcode 2295 replace elements in an arrayCode-Yao · 9:10 · 84 views
Replace Element In an Array | LeetCode 2295 | Contest | HashMap | Array | LeetCode Medium Level |BottomUp · 9:45 · 67 views
LeetCode 2295 Replace Elements in an Array[CE] Code Engineering · 19:21 · 54 views
Heavenislost Leetcode #2295 Replace Elements in an ArrayLei Feng · 7:13 · 21 views
The problem
You are given a 0-indexed array nums that consists of n distinct positive integers. Apply m operations to this array, where in the ith operation you replace the number operations[i][0] with operations[i][1].
It is guaranteed that in the ith operation:
operations[i][0]exists innums.operations[i][1]does not exist innums.
Return the array obtained after applying all the operations.
Example 1:
Input: nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]] Output: [3,2,7,1] Explanation: We perform the following operations on nums: - Replace the number 1 with 3. nums becomes [3,2,4,6]. - Replace the number 4 with 7. nums becomes [3,2,7,6]. - Replace the number 6 with 1. nums becomes [3,2,7,1]. We return the final array [3,2,7,1].
Example 2:
Input: nums = [1,2], operations = [[1,3],[2,1],[3,2]] Output: [2,1] Explanation: We perform the following operations to nums: - Replace the number 1 with 3. nums becomes [3,2]. - Replace the number 2 with 1. nums becomes [3,1]. - Replace the number 3 with 2. nums becomes [2,1]. We return the array [2,1].
Constraints:
n == nums.lengthm == operations.length1 <= n, m <= 105- All the values of
numsare distinct. operations[i].length == 21 <= nums[i], operations[i][0], operations[i][1] <= 106operations[i][0]will exist innumswhen applying theithoperation.operations[i][1]will not exist innumswhen applying theithoperation.
Approach overview
Problem Overview: You are given an array of distinct integers and a list of replacement operations. Each operation replaces an existing value with a new value in the array. After processing all operations sequentially, return the final state of the array.
Approach 1: Use a Hash Map for Direct Replacements (O(n + m) time, O(n) space)
The efficient solution stores the position of every value in a hash map. First iterate through the array and build a mapping value -> index. When processing an operation [oldValue, newValue], perform a constant-time lookup to find the index of oldValue. Update the array at that index with newValue, then update the hash map by removing the old entry and inserting newValue with the same index.
This avoids scanning the array for every replacement. Each operation becomes a constant-time hash lookup and update. The total cost is building the map in O(n) and processing m operations in O(m), giving O(n + m) time overall. Space complexity is O(n) for the hash map. This pattern is common in problems involving value-to-position tracking using a hash table combined with array updates.
Approach 2: Direct Array Modifications (O(n * m) time, O(1) space)
A straightforward simulation processes each replacement by scanning the array. For every operation [oldValue, newValue], iterate through the array until you find oldValue, then replace it with newValue. Because the array contains distinct values, the search stops once the element is found.
This approach uses constant extra space since no additional data structures are required. However, every operation may require scanning the entire array. With n elements and m operations, the worst-case time complexity becomes O(n * m). While simple to implement, it becomes inefficient when the number of operations grows. The logic is essentially a brute-force simulation over the array.
Recommended for interviews: The hash map solution is the expected approach. Interviewers want to see that you avoid repeated scans by tracking indices directly. The brute-force scan shows basic understanding of the problem, but the hash map optimization demonstrates awareness of lookup costs and how to reduce them to constant time.
Approach 1: Approach 1: Use a Hash Map for Direct Replacements
This approach involves using a hash map to keep track of positions of elements in the array. As operations are processed, the map is updated to reflect the new positions of replaced elements.
def replaceElements(nums, operations):
index_map = {num: i for i, num in enumerate(nums)}
for old, new in operations:
idx = index_map.pop(old)
nums[idx] = new
index_map[new] = idx
return numsimport java.util.HashMap;
import java.util.Map;
public int[] replaceElements(int[] nums, int[][] operations) {
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
indexMap.put(nums[i], i);
}
for (int[] op : operations) {
int idx = indexMap.remove(op[0]);
nums[idx] = op[1];
indexMap.put(op[1], idx);
}
return nums;
}#include <unordered_map>
#include <vector>
std::vector<int> replaceElements(std::vector<int>& nums, std::vector<std::vector<int>>& operations) {
std::unordered_map<int, int> indexMap;
for (int i = 0; i < nums.size(); ++i) {
indexMap[nums[i]] = i;
}
for (const auto& op : operations) {
int idx = indexMap[op[0]];
nums[idx] = op[1];
indexMap.erase(op[0]);
indexMap[op[1]] = idx;
}
return nums;
}function replaceElements(nums, operations) {
const indexMap = new Map();
nums.forEach((num, i) => indexMap.set(num, i));
operations.forEach(([oldNum, newNum]) => {
const idx = indexMap.get(oldNum);
nums[idx] = newNum;
indexMap.delete(oldNum);
indexMap.set(newNum, idx);
});
return nums;
}using System.Collections.Generic;
public class Solution {
public int[] ReplaceElements(int[] nums, int[][] operations) {
Dictionary<int, int> indexMap = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
indexMap[nums[i]] = i;
}
foreach (var op in operations) {
int idx = indexMap[op[0]];
nums[idx] = op[1];
indexMap.Remove(op[0]);
indexMap[op[1]] = idx;
}
return nums;
}
}We begin by creating a hash map named `index_map` which keeps track of each number's index in the 'nums'. As each operation is processed, we update the array and modify the map to remove the replaced number and add the new one. This ensures lookups and updates are efficient.
Time Complexity: O(n + m) where n is the length of nums and m is the number of operations. This efficiency is due to each element being processed once and only a constant time operation (hash map access) being executed per operation.
Space Complexity: O(n) for storing the indices in the hash map.
Approach 2: Approach 2: Direct Array Modifications
Although less efficient than using a hash map, this approach iteratively searches for each number to replace in the current 'nums' list and substitutes it directly within the array. This results in a naive implementation.
def replaceElements(nums, operations):
for old, new in operations:
idx = nums.index(old)
nums[idx] = new
return numspublic int[] replaceElements(int[] nums, int[][] operations) {
for (int[] op : operations) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == op[0]) {
nums[i] = op[1];
break;
}
}
}
return nums;
}This Python straightforward solution leverages `list.index()` which searches for each element to replace, thereby directly modifying the list. Although easy to understand, it's not optimal.
Time Complexity: O(n * m) as re-searching for the position of each element isn't ideal, especially with larger arrays.
Space Complexity: O(1) as modifications occur in-place.
Approach 3: Hash Table
First, we use a hash table d to record the indices of each number in the array nums. Then, we iterate through the operation array operations. For each operation [x, y], we replace the number at index d[x] in nums with y, and update the index of y in d to d[x].
Finally, we return nums.
The time complexity is O(n + m), and the space complexity is O(n). Here, n and m are the lengths of the array nums and the operation array operations, respectively.
function arrayChange(nums: number[], operations: number[][]): number[] {
const d: Map<number, number> = new Map(nums.map((x, i) => [x, i]));
for (const [x, y] of operations) {
nums[d.get(x)!] = y;
d.set(y, d.get(x)!);
}
return nums;
}func arrayChange(nums []int, operations [][]int) []int {
d := map[int]int{}
for i, x := range nums {
d[x] = i
}
for _, op := range operations {
x, y := op[0], op[1]
nums[d[x]] = y
d[y] = d[x]
}
return nums
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use a Hash Map for Direct Replacements | Time Complexity: O(n + m) where n is the length of nums and m is the number of operations. This efficiency is due to each element being processed once and only a constant time operation (hash map access) being executed per operation. |
| Approach 2: Direct Array Modifications | Time Complexity: O(n * m) as re-searching for the position of each element isn't ideal, especially with larger arrays. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map for Direct Replacements | O(n + m) | O(n) | Best general solution when many replacement operations exist |
| Direct Array Scan | O(n * m) | O(1) | Useful for small inputs or when avoiding extra memory |
Frequently asked questions
Is Replace Elements in an Array easy or hard?
Replace Elements in an Array is classified as a Medium difficulty problem. The logic is straightforward, but recognizing that a hash map eliminates repeated array scans is the key insight needed for the optimal solution.
Replace Elements in an Array Python/Java solution
Python and Java solutions typically implement the hash map strategy. Build a dictionary or HashMap mapping values to indices, then process each operation by updating the array and adjusting the map entry. This keeps the runtime at O(n + m).
How to solve Replace Elements in an Array in O(n)?
Use a hash map that stores the index of every element in the array. For each operation [oldValue, newValue], look up the index of oldValue in the map, update the array at that index, and update the mapping to point from newValue to the same index. Each operation becomes O(1).
What is the best approach for Replace Elements in an Array?
The best approach uses a hash map that stores value-to-index mappings for the array. Each replacement operation performs a constant-time lookup to find the element's index, updates the array, and updates the map. This reduces the total complexity to O(n + m), where n is the array length and m is the number of operations.
Is Replace Elements in an Array asked at Google/Amazon/Meta?
This type of problem appears in interviews at companies that emphasize hash map and array manipulation patterns, including Amazon and other large tech companies. It tests the ability to avoid repeated scans by maintaining fast lookup structures.
What data structure is used in Replace Elements in an Array?
The optimal solution relies on a hash table (hash map) to store value-to-index mappings. This structure enables constant-time lookups and updates while modifying the array during replacement operations.
What is the time complexity of Replace Elements in an Array?
The optimal solution runs in O(n + m) time. Building the initial hash map from the array takes O(n), and processing each replacement operation takes O(1). A naive approach that scans the array for every operation results in O(n * m) time.