Problem Description

You have an array nums containing n distinct positive integers (0-indexed). You need to perform m operations on this array, where each operation is defined in an operations array.

Each operation operations[i] contains two values:

• operations[i][0]: the number to find and replace in nums
• operations[i][1]: the new number to replace it with

The problem guarantees that:

• The number operations[i][0] will always exist in nums when the i-th operation is performed
• The number operations[i][1] will never already exist in nums when the i-th operation is performed

Your task is to apply all operations sequentially and return the final modified array.

Example:

If nums = [1, 2, 4, 6] and operations = [[1, 3], [4, 7], [6, 1]], the process would be:

• Operation 1: Replace 1 with 3 → nums = [3, 2, 4, 6]
• Operation 2: Replace 4 with 7 → nums = [3, 2, 7, 6]
• Operation 3: Replace 6 with 1 → nums = [3, 2, 7, 1]

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

Intuition

The key insight is that we need to efficiently find where a specific value is located in the array to replace it. If we were to search through the entire array for each operation to find the value to replace, it would take O(n) time per operation, leading to O(m * n) total time complexity.

Instead, we can maintain a hash table that maps each value to its index in the array. This allows us to find any value's position in O(1) time.

Here's the thought process:

1. Why a hash table? Since all numbers in nums are distinct, we can create a one-to-one mapping between values and their indices. This mapping allows instant lookup of where any value is located.

2. How to handle replacements? When we replace value x with value y:

   • We know exactly where x is located (from our hash table: d[x])
   • We update the array at that position: nums[d[x]] = y
   • We need to update our hash table to reflect that y is now at that position: d[y] = d[x]
   • We don't need to remove x from the hash table since it will never be referenced again (the problem guarantees each value to be replaced exists only once and won't be replaced again)

3. Why this works? The problem guarantees that when replacing x with y, y doesn't already exist in the array. This means we won't accidentally overwrite an existing mapping in our hash table. Also, once a value is replaced, it's gone from the array forever, so we don't need to worry about tracking multiple positions for the same value.

This approach reduces our time complexity from O(m * n) to O(n + m), where n is for building the initial hash table and m is for processing all operations.

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.

Solution Implementation

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