#2295

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Replace Elements in an Array

Replace Elements in an Array involves applying a series of operations to replace values in an array with new ones based on given instructions.

array hash table simulation

Problem Statement

You are given a 0-indexed array nums that consists of n distinct positive integers. You are also given m operations where each operation is represented by a pair [x, y]. For each operation, you must replace the number x in nums with y. The ith operation guarantees that x is present in nums, and y will not already exist in nums.

Return the array after applying all the m operations sequentially. Ensure that the elements of the array are updated correctly and efficiently as you perform each operation in the given order.

Examples

Example 1

Input: nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]

Output: [3,2,7,1]

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]

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.length
m == operations.length
1 <= n, m <= 105
All the values of nums are distinct.
operations[i].length == 2
1 <= nums[i], operations[i][0], operations[i][1] <= 106
operations[i][0] will exist in nums when applying the ith operation.
operations[i][1] will not exist in nums when applying the ith operation.

Solution Approach

Use a Hash Map for Efficient Lookups

To quickly find the position of elements, store each element's index in a hash table. This allows O(1) time complexity for locating elements that need replacement, ensuring efficiency when performing multiple operations.

Simulate the Operations

Iterate over the operations and replace the corresponding elements in the nums array. Use the hash map to find and replace each target element with the new value in constant time.

Iterate and Update Array

For each operation, apply the replacement to the correct index in the array, maintaining the array's integrity as you work through the operations list.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for element lookup. Using a hash table provides O(1) time complexity per operation, making the overall time complexity O(m), where m is the number of operations. The space complexity is O(n) due to the storage of indices in the hash table.

What Interviewers Usually Probe

Can the candidate identify the need for a hash map to optimize lookups?
Does the candidate recognize the importance of maintaining constant time complexity for updates?
How well does the candidate handle large inputs with the given constraints?

Common Pitfalls or Variants

Common pitfalls

Not using a hash map, leading to inefficient scanning for each operation.
Forgetting to update the array after each operation, causing incorrect results.
Overcomplicating the solution by attempting to optimize prematurely without considering basic functionality first.

Follow-up variants

What if we were given an array with duplicate elements? How would the solution change?
How would the solution be affected if the replacement values could already exist in the array?
What if the number of operations were much larger than the number of elements in the array?

FAQ

What is the time complexity of replacing elements in an array using a hash map?

The time complexity of each replacement operation is O(1), so the overall time complexity for m operations is O(m).

How does a hash map help solve the problem efficiently?

The hash map provides O(1) time complexity for looking up the index of the element to replace, ensuring fast replacements for each operation.

What is the space complexity for this problem?

The space complexity is O(n), where n is the number of distinct elements in the array, due to the hash map storing the index of each element.

Can the solution be optimized further for larger inputs?

The solution is already efficient with O(1) time complexity per operation, so optimizing further would likely require focusing on the overall system architecture rather than the algorithm itself.

How does the pattern of array scanning plus hash lookup apply to this problem?

This pattern allows for efficient direct access to array elements that need to be replaced, ensuring that each operation is performed in constant time.

terminal

Solution

Solution 1: Hash Table

First, we use a hash table $d$ to record the indices of each number in the array $\textit{nums}$. Then, we iterate through the operation array $\textit{operations}$. For each operation $[x, y]$, we replace the number at index $d[x]$ in $\textit{nums}$ with $y$, and update the index of $y$ in $d$ to $d[x]$.

1

2

3

4

5

6

7

class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        d = {x: i for i, x in enumerate(nums)}
        for x, y in operations:
            nums[d[x]] = y
            d[y] = d[x]
        return nums

Continue Practicing

#2352 equal row and column pairs #2357 make array zero by subtracting equal amounts #2365 task scheduler ii