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.
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; }}Video 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.