You are given two integer arrays nums and target, each of length n. Here, nums[i] represents the current value at index i, while target[i] represents the desired value at index i. Your goal is to transform nums into target.

To achieve this, you may perform the following operation any number of times (including zero):

• Choose an integer value x.
• Find all maximal contiguous segments where every element equals x. A segment is maximal if it cannot be extended further to the left or right while keeping all values equal to x. In other words, you locate every run of consecutive positions whose value is exactly x.
• For each such segment [l, r], simultaneously update every position in that range to its corresponding target value:
  • nums[l] = target[l], nums[l + 1] = target[l + 1], ..., nums[r] = target[r].

The key idea here is that a single operation, fixed on a chosen value x, affects all maximal segments equal to x at once. Each position within those segments is rewritten to match its own target value in one step.

Your task is to return the minimum number of operations required to make nums exactly equal to target.

In essence, for every index i where nums[i] already equals target[i], no change is needed. For every index i where nums[i] differs from target[i], that current value nums[i] must be "processed" through an operation. Since choosing a value x handles all positions holding that value together, you only need to account for each distinct original value that needs changing, giving you the minimum operation count.

Let's think about what each operation really accomplishes. When we choose a value x, every position currently holding x gets rewritten to its own target value in a single step. This means one operation can "fix" many positions at once, as long as they all share the same current value x.

The first observation is that any index i where nums[i] == target[i] is already correct, so it never needs to be touched. We can completely ignore these positions.

Now focus on the indices where nums[i] != target[i]. Each such position must be changed at some point, and the only way to change a position is to choose its current value x = nums[i] in an operation. Here is the crucial insight: all positions that share the same current value can be handled together in one operation. So if multiple indices need changing and they all hold the same value, a single choice of x covers them all.

This naturally leads us to count by distinct values. Suppose two indices both have nums[i] = 5 and both need changing. Picking x = 5 once rewrites both of them simultaneously, no matter how far apart they are. Therefore, the number of operations is not the number of mismatched positions, but the number of distinct values among the mismatched positions.

You might worry that rewriting one segment could create new values that then need further operations, making the counting more complicated. However, the answer simply equals the number of distinct original nums[i] values where nums[i] != target[i]. Each distinct "wrong" value contributes exactly one operation, and there is no way to do better, since two different values can never be fixed by a single choice of x.

So the entire problem reduces to: collect all values nums[i] for which nums[i] != target[i], store them in a set to remove duplicates, and the size of that set is the minimum number of operations.

Pattern Learn more about Greedy patterns.

Solution 1: Hash Table

Following directly from the intuition, our task reduces to counting the number of distinct values among the positions where nums[i] differs from target[i]. A hash table (or more precisely, a hash set) is the perfect data structure for this, because it automatically removes duplicates and lets us query its size in constant time.

The implementation can be broken down into a few simple steps:

1. Iterate over the two arrays in parallel. We pair up nums[i] and target[i] for every index i. In Python, zip(nums, target) gives us these pairs (x, y) where x = nums[i] and y = target[i].

2. Filter the mismatched positions. For each pair (x, y), we only care about it when x != y, meaning the current value does not yet match the desired value. Positions where x == y are already correct and are skipped.

3. Collect the distinct current values into a set. For every mismatched pair, we insert the current value x into a set s. Because a set discards duplicates, all positions sharing the same value x collapse into a single entry. This mirrors the fact that one operation on value x fixes all of them at once.

4. Return the size of the set. The final answer is len(s), which is the number of distinct "wrong" values, and therefore the minimum number of operations.

The whole logic is captured neatly by a set comprehension:

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)

Complexity Analysis:

• Time complexity: O(n), where n is the length of the arrays. We make a single pass over both arrays, and each insertion into the hash set takes average O(1) time.
• Space complexity: O(n) in the worst case, since the set may store up to n distinct values when every position is mismatched and holds a unique value.