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 in nums.operations[i][1] does not exist in nums.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 <= 105nums are distinct.operations[i].length == 21 <= nums[i], operations[i][0], operations[i][1] <= 106operations[i][0] will exist in nums when applying the ith operation.operations[i][1] will not exist in nums when applying the ith operation.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.
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.
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.
Python
Java
C++
C#
JavaScript
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
2295. Replace Elements in an Array (Leetcode Medium) • Programming Live with Larry • 2,864 views views
Watch 9 more video solutions →Practice Replace Elements in an Array with our built-in code editor and test cases.
Practice on FleetCode