Skip to main content
Talentd

Replace Elements in an Array - Solution & Explanation

MediumArrayHash TableSimulation10 min readAsked at: Amazon
Practice this problem

Problem Statement

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.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.

Approach Overview

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 1: Approach 1: Use a Hash Map for Direct Replacements

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.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Direct Array Modifications

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Hash Table

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) for storing the indices in the hash map.

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.
Space Complexity: O(1) as modifications occur in-place.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map for Direct ReplacementsO(n + m)O(n)Best general solution when many replacement operations exist
Direct Array ScanO(n * m)O(1)Useful for small inputs or when avoiding extra memory

Video Solution

2295. Replace Elements in an Array (Leetcode Medium) • Programming Live with Larry • 2,888 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Replace Elements in an Array easy or hard?
Replace Elements in an Array is classified as a Medium difficulty problem. The logic is straightforward, but recognizing that a hash map eliminates repeated array scans is the key insight needed for the optimal solution.
Replace Elements in an Array Python/Java solution
Python and Java solutions typically implement the hash map strategy. Build a dictionary or HashMap mapping values to indices, then process each operation by updating the array and adjusting the map entry. This keeps the runtime at O(n + m).
How to solve Replace Elements in an Array in O(n)?
Use a hash map that stores the index of every element in the array. For each operation [oldValue, newValue], look up the index of oldValue in the map, update the array at that index, and update the mapping to point from newValue to the same index. Each operation becomes O(1).
What is the best approach for Replace Elements in an Array?
The best approach uses a hash map that stores value-to-index mappings for the array. Each replacement operation performs a constant-time lookup to find the element's index, updates the array, and updates the map. This reduces the total complexity to O(n + m), where n is the array length and m is the number of operations.
Is Replace Elements in an Array asked at Google/Amazon/Meta?
This type of problem appears in interviews at companies that emphasize hash map and array manipulation patterns, including Amazon and other large tech companies. It tests the ability to avoid repeated scans by maintaining fast lookup structures.
What data structure is used in Replace Elements in an Array?
The optimal solution relies on a hash table (hash map) to store value-to-index mappings. This structure enables constant-time lookups and updates while modifying the array during replacement operations.
What is the time complexity of Replace Elements in an Array?
The optimal solution runs in O(n + m) time. Building the initial hash map from the array takes O(n), and processing each replacement operation takes O(1). A naive approach that scans the array for every operation results in O(n * m) time.

Ready to solve this problem?

Practice Replace Elements in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find All Numbers Disappeared in an Array

Next

Maximum Number of Integers to Choose From a Range I