Watch 10 video solutions for Replace Elements in an Array, a medium level problem involving Array, Hash Table, Simulation. This walkthrough by Programming Live with Larry has 2,864 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |