We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Replace Elements in an Array

Difficulty: Medium

Problem 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 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, and operations[i][1] does not exist in nums. Return the array obtained after applying all the operations.

Key Insights

  • Each operation involves a direct replacement of an existing number with a new number.
  • Since all numbers in nums are distinct, each operation can be performed without worrying about duplicates.
  • The operations can be efficiently processed using a mapping structure to track the replacements.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of nums and m is the number of operations. This accounts for the initial setup and the processing of each operation. Space Complexity: O(n), for storing the initial state of the array and any necessary mappings.

Solution

To solve the problem, we will utilize a dictionary to map the values in the nums array to their respective indices. As we process each operation, we'll directly replace the target value (operations[i][0]) with the new value (operations[i][1]). This approach ensures that the operations are applied in constant time for each replacement since we can directly access the index of the element to be replaced.

Code Solutions

def replaceElements(nums, operations):
    # Create a mapping from number to its index
    index_map = {num: i for i, num in enumerate(nums)}
    
    # Process each operation
    for old_value, new_value in operations:
        # Find the index of the old value
        index = index_map[old_value]
        # Replace the old value with the new value
        nums[index] = new_value
        # Update the index map to reflect the new value
        index_map[new_value] = index
        # Remove the old value from the index map
        del index_map[old_value]
    
    return nums
← Back to All Questions