Replace Elements in an Array Solution In C++/Java/Python/Javascript
Problem Description
You have 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 need to replace the number operations[i][0] with operations[i][1].'
It is guaranteed that in the ith operation: 1.operations[i][0] exists in nums.
2.operations[i][1] doesn’t exists in nums.
You need to return the array after applying all the operations.
Examples:
Input: nums1 = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]
Output: [3,2,7,1]
Explanation: Performing following operations in nums1.
1. Replace the number 1 with 3. nums become [3,2,4,6].
2. Replace the number 4 with 7. nums become [3,2,7,6].
3. Replace the number 6 with 1. nums become [3,2,7,1].
Return the final array [3,2,7,1].
Input: nums1 = [1,2], operations = [[1,3],[2,1],[3,2]]
Output: [2,1]
Explanation: Performing following operations in nums1.
1. Replace the number 1 with 3. nums become [3,1].
2. Replace the number 2 with 1. nums become [3,1].
3. Replace the number 3 with 2. nums become [2,1].
Return the final array [2,1].
Constraints:
. n==nums.length
. m==operations.length
. 1<=n<=m<=10⁵
. All the values in nums are distinct
operations[i].length == 2
1<=nums[i],operations[i][0],operations[i][1] <=106
Brute Force Approach
Let’s begin with a simple brute-force approach.
The first approach that comes to mind is that for each operation in operations array, we search through the entire nums array to find the element that needs to be replaced. Once found, we update the element with the new value specified in the operations that is operation[i][1].
How to do It:
- Iterate through the operations:
For each operation, we are given two values:
- operations[i][0] is the number to be replaced.
- operations[i][1] is the new number that replaces it.
- Search for the index of operations[i][0] in nums:
Traverse the nums array to find the index of the number to replace.
- Replace the element:
Once the index is found, update nums[index] with operations[i][1].
- Repeat for all operations.
Repeat the process for each operation in the operations list.
Let's walk through an example:
Dry run for Input: nums1 = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]
1. At index 0, operations[0] = [1,3]
- Iterate over nums.
- Match 1 at index 0 and replace with 3.
- Nums become [3,2,4,6].
2. At index 1, operation[1] = [4,7]
- Iterate over nums.
- Match 4 at index 2 and replace with 7.
- Nums become [3,2,7,6].
3. At index 2, operation[2] = [6,1]
- Iterate over nums.
- Match 6 at index 3 and replace with 1.
- Nums become [3,2,7,1] which is final answer.
Output: [3,2,7,1]
How to code it up:
- First, with a for loop we will go through each element in operations. For each element,we will extract the value we need to replace and value to be updated.
- Then with a for loop, we will go through each element in nums and check if it is equal to the value that we want to replace and If a match is found we will replace with newvalue from operations. We repeat this for every element in nums.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
for (const auto& op : operations) {
int toReplace = op[0];
int newValue = op[1];
// Find the index of the element to replace in nums
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == toReplace) {
// Replace with the new value
nums[i] = newValue;
// Break after replacement
break;
}
}
}
return nums;
}
};
2. Java Try on Compiler
class Solution {
public int[] arrayChange(int[] nums, int[][] operations) {
// Loop through each operation
for (int[] op : operations) {
int toReplace = op[0];
int newValue = op[1];
// Find the index of the element to replace in nums
for (int i = 0; i < nums.length; i++) {
if (nums[i] == toReplace) {
// Replace with the new value
nums[i] = newValue;
// Break after replacement
break;
}
}
}
return nums;
}
}
3. Python Try on Compiler
class Solution(object):
def arrayChange(self, nums, operations):
# Loop through each operation
for op in operations:
to_replace = op[0]
new_value = op[1]
# Find the index of the element to replace in nums
for i in range(len(nums)):
if nums[i] == to_replace:
# Replace with the new value
nums[i] = new_value
# Break after replacement
break
return nums
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number[][]} operations
* @return {number[]}
*/
var arrayChange = function(nums, operations) {
// Loop through each operation
for (const operation of operations) {
const toReplace = operation[0];
const newValue = operation[1];
// Find and replace the element
for (let i = 0; i < nums.length; i++) {
if (nums[i] === toReplace) {
// Replace with new value
nums[i] = newValue;
// Stop after replacement
break;
}
}
}
return nums;
};
Time Complexity: O(n*m)
For each operation, the algorithm iterates through the nums array to find the element to be replaced, which takes O(n) time in the worst case. Since this process is repeated for all m operations.
The total number of iterations can be expressed as:
n+n+n+…(repeated m times)
This is equivalent to:
O(n)×O(m)=O(n*m)
Where:
- n is the size of the array nums.
- m is the number of operations.
Space Complexity: O(n+m)
Auxiliary Space Complexity: O(1)
Explanation: Here, apart from the input arrays, we only use a few variables (toReplace, newvalue, so the auxiliary space is O(1).
Total Space Complexity: O(n+m)
Explanation: We are given two array nums and operations. The size of nums is n, and the size of operations is m.Thus the space required to store the elements in nums is O(n) and space required to store the elements in operations is O(m).
So, the total space complexity will be O(n+m).
Will the Brute Force Approach Work Within the Given Constraints?
Let’s analyze the problem with respect to the given constraints:
For the current solution, the time complexity is O(n*m), which is not suitable for n ≤ 10⁵. This means that for each test case, where the length of the array nums is at most 10⁵, the solution might not execute within the given time limits.
Since O(n*m) results in a maximum of 10¹⁰ operations (for n and m = 10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations.
Thus, while the solution meets the time limits for a single test case, the O(nm) time complexity poses a risk for Time Limit Exceeded (TLE).
But wait! Can we optimize it?
Yes! There is a better approach to solve this problem.
Replace Elements in an Array – Optimal Approach
Want to know?
In our previous brute-force approach, we determined the index of the element to replace in the nums array for each operation by iterating through the array from the beginning. This required scanning the entire array for every operation, resulting in a time complexity of O(n * m). Each operation involved a linear traversal of the array, which compounded the cost as the number of operations increased, making the approach inefficient for larger inputs.
To optimize, we need to eliminate this repeated traversal .
Can you think of a data structure that allows us to add or retrieve data in constant time, so we can instantly determine whether an element is present without having to go through the entire list. This significantly improves the efficiency of the process.
Yes, exactly! Hashing is one of the easiest and most effective ways to speed up this process, especially when we need to perform multiple lookups.
What are HashMap's?
Hash maps are a powerful data structure that store key-value pairs, allowing for fast access to values using their keys. They are used to determine where to store each pair, enabling average-case time complexities of O(1) for insertion, search, and deletion.
How does it work?
Ok, Instead of looping through the entire operations array, we can create the mapping between the element and index of nums array in a hash map .A hashmap allows us to check if an element exists in it in constant time, which is much faster than looping through the entire array.
We first iterate over nums to map the element to its index and then traverse over operations and for each operation[i][0] take the index stored for this value in hashmap and replace the value in that index of nums with operations[i][1].
At the end return the nums.
Let’s take an example to make this clearer.
Example:
nums = [1, 2, 4, 6]. operations = [[1, 3], [4, 7], [6, 1]]
Output: [3, 2, 7, 1]
Execution:
Initial hash map:mp = {1: 0, 2: 1, 4: 2, 6: 3}
- First operation [1, 3]:
- Find 1 → index = 0.
- Replace nums[0] with 3: [3, 2, 4, 6].
Update hash map: mp = {3: 0, 2: 1, 4: 2, 6: 3}
- Second operation [4, 7]:
- Find 4 → index = 2.
- Replace nums[2] with 7: [3, 2, 7, 6].
Update hash map: mp = {3: 0, 2: 1, 7: 2, 6: 3}
- Third operation [6, 1]:
- Find 6 → index = 3.
- Replace nums[3] with 1: [3, 2, 7, 1].
Update hash map: mp = {3: 0, 2: 1, 7: 2, 1: 3}
Output: [3, 2, 7, 1]
How to code it up?
- Build a hash map:
Create a map, mp that maps each number in nums to its corresponding index. - Process the operations:
For each operation [oldValue, newValue]: - Use the hash map to find the index of oldValue in O(1) time.
- Replace the value in nums at that index with newValue.
- Update the hash map to remove oldValue and add newValue with the same index.
Return the updated nums.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
// Step 1: Create a hash map to store number-to-index mapping
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++) {
mp[nums[i]] = i;
}
// Step 2: Process each operation
for (const auto& op : operations) {
int oldValue = op[0];
int newValue = op[1];
// Find the index of oldValue in O(1)
int index = mp[oldValue];
// Replace oldValue with newValue in nums
nums[index] = newValue;
// Update the hash map
mp.erase(oldValue);
// Add newValue
mp[newValue] = index;
}
return nums;
2. Java Try on Compiler
class Solution {
public int[] arrayChange(int[] nums, int[][] operations) {
// Step 1: Create a hash map to store number-to-index mapping
Map<Integer, Integer> mp = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
mp.put(nums[i], i);
}
// Step 2: Process each operation
for (int[] op : operations) {
int oldValue = op[0];
int newValue = op[1];
// Find the index of oldValue in O(1)
int index = mp.get(oldValue);
// Replace oldValue with newValue in nums
nums[index] = newValue;
// Update the hash map
mp.remove(oldValue);
// Add newValue
mp.put(newValue, index);
}
return nums;
}
}
3. Python Try on Compiler
class Solution(object):
def arrayChange(self, nums, operations):
# Step 1: Create a dictionary to store number-to-index mapping
mp = {num: i for i, num in enumerate(nums)}
# Step 2: Process each operation
for old_value, new_value in operations:
# Find the index of old_value in O(1)
index = mp[old_value]
# Replace old_value with new_value in nums
nums[index] = new_value
# Update the dictionary
del mp[old_value]
# Add new_value
mp[new_value] = index
return nums
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @param {number[][]} operations
* @return {number[]}
*/
var arrayChange = function(nums, operations) {
// Step 1: Create a map to store number-to-index mapping
const numToIndex = new Map();
nums.forEach((num, i) => {
numToIndex.set(num, i);
});
// Step 2: Process each operation
for (const [oldValue, newValue] of operations) {
// Find the index of oldValue in O(1)
const index = numToIndex.get(oldValue);
// Replace oldValue with newValue in nums
nums[index] = newValue;
// Update the map
numToIndex.delete(oldValue);
// Add newValue
numToIndex.set(newValue, index);
}
return nums;
};
Time Complexity: O(n+m)
1. Creating the hash map from nums:
- We traverse through the nums array (which has n elements) to build a hashmap that stores each number's index. This process takes O(n) time since we visit each element once.
2. Processing each operation:
- For each operation (there are m operations), we:
- Look up the index of the old value in the hash map. This takes O(1) time because hash maps allow quick access.
- Update the value in the nums array and modify the hash map. Both of these actions also take O(1) time.
- Since each operation is O(1) and there are m operations, this step takes O(m) time in total.
3. Combining both steps:
- The total time complexity is the sum of the time to create the hash map (O(n) and the time to process all operations O(m).
- Therefore, the overall time complexity is O(n+m).
Space complexity: O(n+m)
Auxiliary Space complexity: O(n)
Explanation: We use a hashmap to store the mapping of numbers in nums to their indices.The hash map will have n entries, where n is the size of the nums array.Space required is O(n).
Total Space Complexity: O(n+m).
Explanation: We are given two array nums and operations. The size of nums is n, and the size of operations is m.Thus the space required to store the elements in nums is O(n) and space required to store the elements in operations is O(m).
So, the total space complexity will be O(n+m).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given an array of strings words and a string chars.
A string is good if it can be formed by characters from chars(each character can only be used once).
Return the sum of lengths of all good strings in words.
Given an integer array nums return the most frequent even element.
If there is a tie, return the smallest one. If there is no such element, return -1.