Replace Elements in an Array
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. For each operation, it iterates through the entire nums array to find the element that needs to be replaced and then updates it. This is the most straightforward but also the least efficient method.
Algorithm
- Iterate through each operation
[old_val, new_val]in theoperationsarray. - For each operation, perform a linear scan on the
numsarray from indexi = 0ton-1. - If
nums[i]is equal toold_val, updatenums[i]tonew_val. - Since all elements in
numsare distinct, you can break the inner loop after finding and replacing the element. - After all
moperations are processed, return the modifiednumsarray.
Walkthrough
The algorithm iterates through each operation provided in the operations array. For a given operation [old_val, new_val], it performs a linear scan on the nums array from beginning to end. When it finds an element nums[i] that matches old_val, it replaces this element with new_val. Because the problem guarantees that elements are distinct, the inner loop can be terminated as soon as the element is found and replaced. This process is repeated for all m operations.
class Solution { public int[] replaceElements(int[] nums, int[][] operations) { for (int[] op : operations) { int oldVal = op[0]; int newVal = op[1]; for (int i = 0; i < nums.length; i++) { if (nums[i] == oldVal) { nums[i] = newVal; break; // Elements are distinct, so we can stop searching. } } } return nums; }}Complexity
Time
O(n * m), where `n` is the length of `nums` and `m` is the number of operations. For each of the `m` operations, we may have to scan the entire `nums` array of size `n` in the worst case.
Space
O(1), as we are modifying the input array in-place and not using any additional data structures that scale with the input size.
Trade-offs
Pros
Simple to understand and implement.
Space-efficient, as it uses constant extra space, O(1), by modifying the array in-place.
Cons
Extremely inefficient for large inputs, with a quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
To improve performance, we can optimize the search for the element to be replaced. Instead of a linear scan which takes O(n) time, we can use a hash map to achieve an average search time of O(1). We first pre-process the nums array to store each number and its corresponding index in a hash map. This allows for quick lookups and updates.
Algorithm
- Create a
HashMapto store the mapping from each number innumsto its index. - Populate the map by iterating through
nums. This takes O(n) time. - Iterate through each operation
[old_val, new_val]inoperations. - Use the map to get the index of
old_valin O(1) average time. - Update the element at that index in
numswithnew_val. - Update the map by removing the entry for
old_valand adding an entry fornew_valwith the same index. - Return the modified
numsarray.
Walkthrough
This approach consists of two main phases: a pre-processing phase and an operations phase.
1. Pre-processing:
- Create a hash map, let's call it
valToIndexMap. - Iterate through the initial
numsarray. For each elementnums[i], store the mapping from the value to its index in the hash map:valToIndexMap.put(nums[i], i).
2. Processing Operations:
- Iterate through each operation
[old_val, new_val]in theoperationsarray. - For each operation, find the index of
old_valby looking it up in thevalToIndexMap. This is an O(1) operation on average:int index = valToIndexMap.get(old_val). - Update the
numsarray at the retrieved index:nums[index] = new_val. - Update the
valToIndexMapto reflect the change. Remove the old value's entry and add the new value's entry:valToIndexMap.remove(old_val); valToIndexMap.put(new_val, index);.
After processing all operations, the nums array is in its final state and can be returned.
import java.util.HashMap;import java.util.Map; class Solution { public int[] replaceElements(int[] nums, int[][] operations) { Map<Integer, Integer> valToIndexMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { valToIndexMap.put(nums[i], i); } for (int[] op : operations) { int oldVal = op[0]; int newVal = op[1]; // Get the index of the old value in O(1) average time int index = valToIndexMap.get(oldVal); // Update the array nums[index] = newVal; // Update the map to maintain consistency valToIndexMap.remove(oldVal); valToIndexMap.put(newVal, index); } return nums; }}Complexity
Time
O(n + m), where `n` is the length of `nums` and `m` is the number of operations. It takes O(n) to build the initial map and O(m) to process all operations (O(1) for each operation).
Space
O(n), for the hash map which stores `n` key-value pairs corresponding to the elements in the `nums` array.
Trade-offs
Pros
Highly efficient time complexity, suitable for large inputs.
The lookup, update, and removal operations in the hash map are all O(1) on average.
Cons
Requires extra space to store the hash map, which is proportional to the number of elements in
nums.
Solutions
Solution
class Solution {public int[] arrayChange(int[] nums, int[][] operations) { Map<Integer, Integer> d = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { d.put(nums[i], i); } for (var op : operations) { int a = op[0], b = op[1]; nums[d.get(a)] = b; d.put(b, d.get(a)); } return nums; }}class Solution {public: vector<int> arrayChange(vector<int> &nums, vector<vector<int>> &operations) { unordered_map<int, int> d; for (int i = 0; i < nums.size(); ++i) { d[nums[i]] = i; } for (auto &op : operations) { int a = op[0], b = op[1]; nums[d[a]] = b; d[b] = d[a]; } return nums; }};class Solution: def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]: d = {v: i for i, v in enumerate(nums)} for a, b in operations: nums[d[a]] = b d[b] = d[a] return numsVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.