Replace Elements in an Array — Editorial

Opening the reading…

Intuitionthe array position does not change, only the value stored there

Each operation identifies a value, not an index. Searching the whole array for that value would work, but repeating that search for up to m operations can revisit the same positions many times. The useful fact is that every value is distinct, so each value has exactly one current position that can be stored directly.

Build a map from each current value to its index. For an operation old -> new, read old's position, write new into that array slot, then move the map entry from old to new. The map must describe the array after every operation, because a later operation may refer to a value that was introduced earlier.

Approachkeep the array and the value-to-index map synchronized

Create an empty hash map from each value in nums to its index, because the map turns a value lookup into an expected constant-time operation.

Insert every initial nums[i] with index i, so the map describes the array before the first operation.

For each operation, read oldVal and newVal and obtain the position stored at oldVal, because the operation names the value and not its location.

Write newVal into nums[pos], because the replacement affects the array slot where oldVal currently lives.

Set the map entry for newVal to pos, so later operations can find the newly introduced value at its current position.

Erase oldVal from the map, because leaving it there would make the map claim that a value still exists after it has been replaced.

Return nums after all operations, because each update was applied directly to the required output array in the given order.

Complexityexpected bounds for hash-table operations

MEASURE	BOUND	WHY
Time	O(n + m) expected	Building the map processes each of the n initial values once. Each of the m operations performs a constant number of expected constant-time hash-table actions and one array write, so no operation scans the array. With adversarial hash collisions, a hash-table action can degrade to O(n), making the worst-case time O(nm).
Space	O(n) extra	The map contains one entry per current array value, and the temporary operation references use constant additional space. The returned nums array is required output and is excluded. The extra space remains O(n) for every input arrangement because replacements preserve the number of array elements.

n is the array length and m is the number of operations. The time bound assumes expected constant-time unordered_map lookup, insertion and erasure.

Annotated solutionC++ · direct simulation with a value-to-index hash map

CPPBuild the index map once, then update the array and map for each replacement.

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
        unordered_map<int, int> index;

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            index[nums[i]] = i;
        }

        for (const vector<int>& operation : operations) {
            int oldValue = operation[0];
            int newValue = operation[1];
            int position = index[oldValue];

            nums[position] = newValue;
            index[newValue] = position;
            index.erase(oldValue);
        }

        return nums;
    }
};

The three update lines are one indivisible operation. The array changes first, the new value receives the old value's position, and the old value is removed. Updating only the array makes the current result look correct but leaves later lookups stale; updating only the map creates a map that no longer describes nums.