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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Replace Elements in an Array

Number: 2388

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a 0-indexed array of distinct positive integers, perform a series of operations on the array. For each operation, replace an existing number with a new number that is not currently in the array. Return the final array after all operations.

Key Insights

  • Use a hash map (dictionary) to keep track of each number's index in the array.
  • By mapping the value to its index, we can quickly update the array for each operation in O(1) time.
  • Since each operation guarantees that the new number is not already in the array and that the old number exists, dictionary updates and array replacements are straightforward.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of the array and m is the number of operations. Space Complexity: O(n), due to the hash map used to store indices.

Solution

Maintain a hash map to store the mapping from each number in the array to its current index. For each operation, use the hash map to locate the index of the number to be replaced, then update the array and the hash map accordingly. This simulation of operations guarantees overall efficiency by achieving constant time look-ups and updates.

Code Solutions

# Python solution with detailed comments
class Solution:
    def arrayChange(self, nums, operations):
        # Create a mapping from number to its index in the array
        index_map = {num: i for i, num in enumerate(nums)}
        # Process each operation: [old_val, new_val]
        for old_val, new_val in operations:
            # Find the index of the old value using the map
            idx = index_map.pop(old_val)
            # Replace the element in the array with new_val
            nums[idx] = new_val
            # Map the new value with its index
            index_map[new_val] = idx
        return nums

# Example usage:
# sol = Solution()
# print(sol.arrayChange([1,2,4,6], [[1,3],[4,7],[6,1]]))
← Back to All Questions