Replace Elements in an Array

MEDIUM

Description

You are given a 0-indexed array nums that consists of n distinct positive integers. Apply m operations to this array, where in the i^th operation you replace the number operations[i][0] with operations[i][1].

It is guaranteed that in the i^th 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 <= 10⁵
All the values of nums are distinct.
operations[i].length == 2
1 <= nums[i], operations[i][0], operations[i][1] <= 10⁶
operations[i][0] will exist in nums when applying the i^th operation.
operations[i][1] will not exist in nums when applying the i^th operation.

Approaches

Checkout 2 different approaches to solve Replace Elements in an Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Linear Scan

This approach directly simulates the process described in the problem. For each operation, it iterates through the entire nums array to find the element that needs to be replaced and then updates it. This is the most straightforward but also the least efficient method.

Algorithm

Iterate through each operation [old_val, new_val] in the operations array.
For each operation, perform a linear scan on the nums array from index i = 0 to n-1.
If nums[i] is equal to old_val, update nums[i] to new_val.
Since all elements in nums are distinct, you can break the inner loop after finding and replacing the element.
After all m operations are processed, return the modified nums array.

The algorithm iterates through each operation provided in the operations array. For a given operation [old_val, new_val], it performs a linear scan on the nums array from beginning to end. When it finds an element nums[i] that matches old_val, it replaces this element with new_val. Because the problem guarantees that elements are distinct, the inner loop can be terminated as soon as the element is found and replaced. This process is repeated for all m operations.

class Solution {
    public int[] replaceElements(int[] nums, int[][] operations) {
        for (int[] op : operations) {
            int oldVal = op[0];
            int newVal = op[1];
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == oldVal) {
                    nums[i] = newVal;
                    break; // Elements are distinct, so we can stop searching.
                }
            }
        }
        return nums;
    }
}

Complexity Analysis

Time Complexity: O(n * m), where `n` is the length of `nums` and `m` is the number of operations. For each of the `m` operations, we may have to scan the entire `nums` array of size `n` in the worst case.Space Complexity: O(1), as we are modifying the input array in-place and not using any additional data structures that scale with the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Space-efficient, as it uses constant extra space, O(1), by modifying the array in-place.

Cons:

Extremely inefficient for large inputs, with a quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Replace Elements in an Array. Click on different languages to view the code.

class Solution {
public
  int[] arrayChange(int[] nums, int[][] operations) {
    Map<Integer, Integer> d = new HashMap<>();
    for (int i = 0; i < nums.length; ++i) {
      d.put(nums[i], i);
    }
    for (var op : operations) {
      int a = op[0], b = op[1];
      nums[d.get(a)] = b;
      d.put(b, d.get(a));
    }
    return nums;
  }
}

Video Solution

Watch the video walkthrough for Replace Elements in an Array

Data Structures:

ArrayHash Table