Solution Approach

The solution uses a hash table to track the position of each value in the array for efficient lookups and updates.

Step-by-step implementation:

1. Build the position mapping:

   d = {x: i for i, x in enumerate(nums)}

   We create a dictionary d where each key is a value from nums and each value is its corresponding index. For example, if nums = [1, 2, 4, 6], then d = {1: 0, 2: 1, 4: 2, 6: 3}.

2. Process each operation:

   for x, y in operations:  nums[d[x]] = y  d[y] = d[x]

   For each operation [x, y]:

   • d[x] gives us the index where value x is located
   • nums[d[x]] = y replaces the value at that index with y
   • d[y] = d[x] updates our hash table to record that y is now at the position where x used to be

3. Return the modified array:

   return nums

Example walkthrough:

Let's trace through nums = [1, 2, 4, 6] and operations = [[1, 3], [4, 7], [6, 1]]:

• Initial: d = {1: 0, 2: 1, 4: 2, 6: 3}
• Operation [1, 3]: Replace 1 with 3
  • nums[d[1]] = nums[0] = 3 → nums = [3, 2, 4, 6]
  • d[3] = d[1] = 0 → d = {1: 0, 2: 1, 4: 2, 6: 3, 3: 0}
• Operation [4, 7]: Replace 4 with 7
  • nums[d[4]] = nums[2] = 7 → nums = [3, 2, 7, 6]
  • d[7] = d[4] = 2 → d = {1: 0, 2: 1, 4: 2, 6: 3, 3: 0, 7: 2}
• Operation [6, 1]: Replace 6 with 1
  • nums[d[6]] = nums[3] = 1 → nums = [3, 2, 7, 1]
  • d[1] = d[6] = 3 → d = {1: 3, 2: 1, 4: 2, 6: 3, 3: 0, 7: 2}

The final array [3, 2, 7, 1] is returned.

Time Complexity: O(n + m) where n is the length of nums and m is the number of operations Space Complexity: O(n) for the hash table

Example Walkthrough

Let's walk through a smaller example to illustrate the solution approach.

Given:

• nums = [5, 8, 3]
• operations = [[5, 2], [3, 9]]

Step 1: Build the position mapping

We create a hash table that maps each value to its index:

d = {5: 0, 8: 1, 3: 2}

This tells us that:

• Value 5 is at index 0
• Value 8 is at index 1
• Value 3 is at index 2

Step 2: Process first operation [5, 2]

We need to replace 5 with 2:

• Look up where 5 is located: d[5] = 0
• Replace the value at index 0: nums[0] = 2
  • Array becomes: [2, 8, 3]
• Update hash table to record that 2 is now at index 0: d[2] = 0
  • Hash table becomes: {5: 0, 8: 1, 3: 2, 2: 0}

Step 3: Process second operation [3, 9]

We need to replace 3 with 9:

• Look up where 3 is located: d[3] = 2
• Replace the value at index 2: nums[2] = 9
  • Array becomes: [2, 8, 9]
• Update hash table to record that 9 is now at index 2: d[9] = 2
  • Hash table becomes: {5: 0, 8: 1, 3: 2, 2: 0, 9: 2}

Final Result: [2, 8, 9]

The key insight is that by maintaining the hash table, we can find any value's position in O(1) time instead of searching through the entire array. When we replace a value, we update both the array and the hash table to keep them synchronized. The old values remain in the hash table but are never accessed again since the problem guarantees each value is replaced at most once.

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm consists of two main parts:

1. Building the dictionary d with a comprehension that iterates through all n elements in nums - this takes O(n) time
2. Processing all m operations in the for loop, where each operation involves:
   • Dictionary lookup d[x] - O(1) time
   • Array assignment nums[d[x]] = y - O(1) time
   • Dictionary assignment d[y] = d[x] - O(1) time

Since we perform O(1) operations for each of the m operations, the total time for the second part is O(m).

Therefore, the overall time complexity is O(n + m), where n is the length of the array nums and m is the length of the operations array.

Space Complexity: O(n)

The algorithm uses a dictionary d that stores a mapping for each element in nums to its index. Initially, this dictionary contains n key-value pairs. During the operations, we only update existing entries or add new keys for values that replace existing ones, but the dictionary size remains bounded by the number of unique values that have appeared in the array, which is at most O(n) additional entries. Thus, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Attempting to Find Value's Index Without Hash Table

The Problem: A common mistake is trying to locate each value using linear search instead of maintaining a hash table:

# Inefficient approach - DON'T DO THIS for old_value, new_value in operations:  index = nums.index(old_value) # O(n) operation!  nums[index] = new_value

This approach has O(m*n) time complexity, which can cause timeout for large inputs.

The Solution: Always maintain a hash table for O(1) lookups:

value_to_index = {value: index for index, value in enumerate(nums)} for old_value, new_value in operations:  index = value_to_index[old_value] # O(1) operation  nums[index] = new_value  value_to_index[new_value] = index

Pitfall 2: Forgetting to Update the Hash Table

The Problem: After replacing a value in the array, forgetting to update the hash table mapping:

# Incorrect - hash table not updated for old_value, new_value in operations:  index = value_to_index[old_value]  nums[index] = new_value  # Missing: value_to_index[new_value] = index

This causes subsequent operations to fail when trying to find values that were introduced in previous operations.

The Solution: Always update the hash table immediately after modifying the array:

for old_value, new_value in operations:  index = value_to_index[old_value]  nums[index] = new_value  value_to_index[new_value] = index # Critical update!

Pitfall 3: Deleting Old Values from Hash Table

The Problem: Unnecessarily deleting old values from the hash table:

# Unnecessary deletion for old_value, new_value in operations:  index = value_to_index[old_value]  nums[index] = new_value  value_to_index[new_value] = index  del value_to_index[old_value] # Not needed!

While this doesn't break the solution, it adds unnecessary overhead. The problem guarantees that old values won't be referenced again.

The Solution: Simply leave old entries in the hash table - they won't affect correctness:

for old_value, new_value in operations:  index = value_to_index[old_value]  nums[index] = new_value  value_to_index[new_value] = index  # No deletion needed - old_value won't be accessed again