LeetCode 2295 - Replace Elements in an Array

The problem asks us to perform a series of replacement operations on an array of distinct integers. Specifically, we have an initial array nums containing n distinct positive integers. We are also given m operations, each consisting of a pair [oldValue, newValue].

leetcodemediumarrayhash-tablesimulation

LeetCode Problem 2295

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Simulation

Solution

Problem Understanding

The problem asks us to perform a series of replacement operations on an array of distinct integers. Specifically, we have an initial array nums containing n distinct positive integers. We are also given m operations, each consisting of a pair [oldValue, newValue]. For each operation, we must locate the element oldValue in the array and replace it with newValue. The constraints guarantee that oldValue always exists in the array at the time of the operation and that newValue is not already present in the array, which simplifies handling duplicates.

The expected output is the final state of the array after applying all operations in order.

Key points from the constraints include the large size limit (n and m up to 10^5) and the requirement that all elements are distinct. This suggests that a naive approach of scanning the array linearly for each replacement (O(n * m)) would be inefficient. Edge cases to consider include minimal arrays (length 1), maximal arrays with consecutive replacements, and sequences where elements are swapped back and forth.

Approaches

Brute Force

A straightforward approach is to iterate through each operation and, for each [oldValue, newValue], scan the array nums to find the index of oldValue and replace it with newValue. This approach guarantees correctness because it directly follows the operation instructions. However, it is inefficient since finding the index requires O(n) for each of the m operations, giving a total time complexity of O(n * m), which is unacceptable for the maximum constraints (n, m <= 10^5).

Optimal

The key insight is to use a hash map (dictionary in Python, map in Go) to track the indices of the elements in nums. With this structure, each replacement operation can be performed in O(1) time by looking up the index of oldValue in the map and updating both the array and the map with newValue. This reduces the overall complexity to O(n + m), as we build the map initially and then perform each operation in constant time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Directly scan array for each replacement
Optimal O(n + m) O(n) Use hash map for fast index lookup and updates

Algorithm Walkthrough

  1. Initialize a hash map value_to_index where the key is the element from nums and the value is its index.

  2. Iterate over the array nums and populate value_to_index so each number points to its index in nums.

  3. For each operation [oldValue, newValue] in operations, do the following:

  4. Retrieve the index of oldValue from value_to_index.

  5. Replace nums[index] with newValue.

  6. Remove oldValue from value_to_index and insert newValue with the same index.

  7. Return the updated nums array.

Why it works: The invariant is that value_to_index always accurately reflects the current position of every number in nums. Since all numbers are distinct and the operations guarantee no duplicates, each replacement can be done in constant time without conflicts.

Python Solution

from typing import List

class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        # Step 1: Build a mapping from value to its index
        value_to_index = {num: i for i, num in enumerate(nums)}
        
        # Step 2: Apply each operation
        for old_value, new_value in operations:
            index = value_to_index.pop(old_value)  # Get index and remove old_value
            nums[index] = new_value               # Update the array
            value_to_index[new_value] = index     # Add new_value to the map
            
        return nums

The implementation first constructs the hash map to enable O(1) lookup of indices. Each operation updates the array and maintains the map in sync. Using pop ensures oldValue is removed while retrieving its index. Finally, the modified array is returned.

Go Solution

func arrayChange(nums []int, operations [][]int) []int {
    // Step 1: Build a map from value to index
    valueToIndex := make(map[int]int, len(nums))
    for i, num := range nums {
        valueToIndex[num] = i
    }
    
    // Step 2: Apply each operation
    for _, op := range operations {
        oldValue, newValue := op[0], op[1]
        index := valueToIndex[oldValue]
        nums[index] = newValue
        delete(valueToIndex, oldValue)
        valueToIndex[newValue] = index
    }
    
    return nums
}

In Go, the map is created with make for efficiency. delete is used to remove the old key. All other steps mirror the Python solution. Slice operations in Go directly modify the array, ensuring the map stays consistent.

Worked Examples

Example 1:

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

Step Operation Array State Map State
0 - [1,2,4,6] {1:0, 2:1, 4:2, 6:3}
1 [1,3] [3,2,4,6] {2:1, 4:2, 6:3, 3:0}
2 [4,7] [3,2,7,6] {2:1, 6:3, 3:0, 7:2}
3 [6,1] [3,2,7,1] {2:1, 3:0, 7:2, 1:3}

Final output: [3,2,7,1]

Example 2:

nums = [1,2], operations = [[1,3],[2,1],[3,2]]

Step Operation Array State Map State
0 - [1,2] {1:0, 2:1}
1 [1,3] [3,2] {2:1, 3:0}
2 [2,1] [3,1] {3:0, 1:1}
3 [3,2] [2,1] {2:0, 1:1}

Final output: [2,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) O(n) to build the initial map, O(1) per operation for m operations
Space O(n) Hash map stores n elements for index lookup

The algorithm scales linearly with the size of the array and number of operations, which is optimal given the constraints.

Test Cases

# Provided examples
assert Solution().arrayChange([1,2,4,6], [[1,3],[4,7],[6,1]]) == [3,2,7,1]  # Example 1
assert Solution().arrayChange([1,2], [[1,3],[2,1],[3,2]]) == [2,1]          # Example 2

# Edge cases
assert Solution().arrayChange([1], [[1,2]]) == [2]                           # Single element array
assert Solution().arrayChange([5,10], [[5,10],[10,5]]) == [10,5]             # Swapping values
assert Solution().arrayChange([1,2,3], [[1,4],[2,5],[3,6]]) == [4,5,6]       # Multiple sequential replacements

# Stress test
nums = list(range(1, 100001))
ops = [[i, i+100001] for i in range(1, 100001)]
assert Solution().arrayChange(nums, ops) == list(range(100002, 200002))      # Large input
Test Why
[1,2,4,6], [[1,3],[4,7],[6,1]] Validates normal sequence of replacements
[1,2], [[1,3],[2,1],[3,2]] Checks chain of swaps and replacements
[1], [[1,2]] Tests single-element array
[5,10], [[5,10],[10,5]] Validates swaps that could confuse naive implementations
[1,2,3], [[1,4],[2,5],[3,6]] Multiple sequential replacements on all elements
large range 1..100000 Stress test to ensure efficiency

Edge Cases

  1. Single Element Array: When nums has only one element, it is important that the code correctly replaces it without trying to access indices outside the array. The hash map handles this naturally.

2