Skip to content

3810. Minimum Operations to Reach Target Array

Description

You are given two integer arrays nums and target, each of length n, where nums[i] is the current value at index i and target[i] is the desired value at index i.

You may perform the following operation any number of times (including zero):

  • Choose an integer value x
  • Find all maximal contiguous segments where nums[i] == x (a segment is maximal if it cannot be extended to the left or right while keeping all values equal to x)
  • For each such segment [l, r], update simultaneously:
    • nums[l] = target[l], nums[l + 1] = target[l + 1], ..., nums[r] = target[r]

Return the minimum number of operations required to make nums equal to target.

 

Example 1:

Input: nums = [1,2,3], target = [2,1,3]

Output: 2

Explanation:​​​​​​​

  • Choose x = 1: maximal segment [0, 0] updated -> nums becomes [2, 2, 3]
  • Choose x = 2: maximal segment [0, 1] updated (nums[0] stays 2, nums[1] becomes 1) -> nums becomes [2, 1, 3]
  • Thus, 2 operations are required to convert nums to target.​​​​​​​​​​​​​​

Example 2:

Input: nums = [4,1,4], target = [5,1,4]

Output: 1

Explanation:

  • Choose x = 4: maximal segments [0, 0] and [2, 2] updated (nums[2] stays 4) -> nums becomes [5, 1, 4]
  • Thus, 1 operation is required to convert nums to target.

Example 3:

Input: nums = [7,3,7], target = [5,5,9]

Output: 2

Explanation:

  • Choose x = 7: maximal segments [0, 0] and [2, 2] updated -> nums becomes [5, 3, 9]
  • Choose x = 3: maximal segment [1, 1] updated -> nums becomes [5, 5, 9]
  • Thus, 2 operations are required to convert nums to target.

 

Constraints:

  • 1 <= n == nums.length == target.length <= 105
  • 1 <= nums[i], target[i] <= 105

Solutions

Solution 1: Hash Table

Thinking

One operation replaces every maximal run of a value \(x\) with the corresponding \(\textit{target}\) entries. \(n \le 10^5\), so simulating rewrites would rescan the array.

All runs of \(x\) change together, so each mismatched \(x\) needs one operation regardless of how many runs it has.

Already matching positions do not count. The answer is the number of distinct \(nums[i]\) that still differ from the target.

A set of those original values has size equal to the minimum number of operations.

According to the problem description, we only need to count the number of distinct \(\text{nums}[i]\) where \(\text{nums}[i] \ne \text{target}[i]\). Therefore, we can use a hash table to store these distinct \(\text{nums}[i]\) and finally return the size of the hash table.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

1
2
3
4
class Solution:
    def minOperations(self, nums: List[int], target: List[int]) -> int:
        s = {x for x, y in zip(nums, target) if x != y}
        return len(s)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int minOperations(int[] nums, int[] target) {
        Set<Integer> s = new HashSet<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != target[i]) {
                s.add(nums[i]);
            }
        }
        return s.size();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int minOperations(vector<int>& nums, vector<int>& target) {
        unordered_set<int> s;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != target[i]) {
                s.insert(nums[i]);
            }
        }
        return s.size();
    }
};

1
2
3
4
5
6
7
8
9
func minOperations(nums []int, target []int) int {
    s := make(map[int]struct{})
    for i := 0; i < len(nums); i++ {
        if nums[i] != target[i] {
            s[nums[i]] = struct{}{}
        }
    }
    return len(s)
}

1
2
3
4
5
6
7
8
9
function minOperations(nums: number[], target: number[]): number {
    const s = new Set<number>();
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== target[i]) {
            s.add(nums[i]);
        }
    }
    return s.size;
}

Comments