LeetCode 3810 - Minimum Operations to Reach Target Array

We are given two arrays, nums and target, of equal length. The array nums represents the current state, while target represents the desired final state. In one operation, we choose a value x. Then we locate every maximal contiguous segment whose current value is exactly x.

leetcodemediumarrayhash-tablegreedy

LeetCode Problem 3810

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy

Solution

Problem Understanding

We are given two arrays, nums and target, of equal length.

The array nums represents the current state, while target represents the desired final state.

In one operation, we choose a value x. Then we locate every maximal contiguous segment whose current value is exactly x. Every position inside those segments is simultaneously replaced by its corresponding value from target.

The important detail is that the operation is defined by a value, not by indices. When we choose x, every current occurrence of x participates automatically.

We must determine the minimum number of operations needed to transform nums into target.

The constraints are large, up to 10^5 elements, which immediately rules out any expensive simulation. We need an algorithm that is close to linear time.

A key observation is that an operation on value x affects every position currently equal to x. Therefore, the natural unit of work is not a segment or an index, but a value.

Some important edge cases include:

  • Arrays that are already equal, the answer should be 0.
  • Multiple mismatched positions sharing the same original value.
  • Values that appear in both matching and mismatching positions.
  • Cases where updating one value creates new occurrences of another value.

The last case is what makes the problem look more complicated than it actually is.

Approaches

Brute Force

A brute force approach would attempt to simulate the process.

We could repeatedly choose values, update segments, generate new array states, and search for the minimum number of operations. Since every operation changes the array and may create new opportunities for future operations, the state space grows extremely quickly.

Even if we attempted BFS on array states, the number of possible states would be enormous. With n = 10^5, such an approach is completely infeasible.

The brute force method is correct because it explores all possible sequences of operations, but it is far too slow.

Key Insight

Consider a position i.

If nums[i] == target[i], that position already contains the correct value. We never need an operation specifically because of that position.

If nums[i] != target[i], then the value currently stored at that position must eventually be removed. The only operation capable of removing that original value is an operation that chooses

x = nums[i]

Therefore, every distinct value that appears in a mismatched position must be chosen at least once.

Now consider choosing some value x.

When we perform the operation for x, every current occurrence of x is updated to its target value. After that, no position that originally required removing x can ever require another operation on x.

Therefore, one operation is sufficient for each distinct value that appears in a mismatched position.

This gives a remarkably simple answer:

Count how many distinct values appear in nums[i] among all indices where nums[i] != target[i].

That count is both necessary and sufficient.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Simulates all possible operation sequences
Optimal O(n) O(n) Count distinct source values among mismatches

Algorithm Walkthrough

  1. Create an empty hash set.
  2. Iterate through both arrays simultaneously.
  3. For each index i, check whether nums[i] differs from target[i].
  4. If the values are equal, do nothing because that position already matches the target.
  5. If the values are different, insert nums[i] into the hash set.
  6. After processing all indices, return the size of the hash set.

The hash set automatically removes duplicates, so each distinct value is counted exactly once.

Why it works

Every mismatched position containing value v requires at least one operation choosing v, because no other operation can directly remove that value from the position. Therefore every distinct mismatching value contributes at least one required operation.

Conversely, a single operation choosing v updates all current occurrences of v simultaneously. Thus one operation per distinct mismatching value is always sufficient.

Since the lower bound and upper bound are identical, the number of distinct values appearing in mismatched positions is exactly the minimum answer.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums: List[int], target: List[int]) -> int:
        values_to_fix = set()

        for current, desired in zip(nums, target):
            if current != desired:
                values_to_fix.add(current)

        return len(values_to_fix)

The implementation follows the algorithm directly.

A hash set named values_to_fix stores every distinct value that appears in a position where the current array differs from the target array.

We iterate through both arrays simultaneously using zip. Whenever a mismatch is found, we add the current value from nums into the set.

Because sets automatically eliminate duplicates, multiple mismatched positions containing the same value still contribute only one operation.

Finally, the answer is simply the number of distinct values stored in the set.

Go Solution

func minOperations(nums []int, target []int) int {
	valuesToFix := make(map[int]struct{})

	for i := 0; i < len(nums); i++ {
		if nums[i] != target[i] {
			valuesToFix[nums[i]] = struct{}{}
		}
	}

	return len(valuesToFix)
}

The Go implementation uses a map as a hash set.

The keys of the map are the distinct values from nums that appear in mismatched positions. The empty struct is used as the value because it consumes zero storage.

The final answer is the number of keys in the map, obtained with len(valuesToFix).

Worked Examples

Example 1

nums   = [1, 2, 3]
target = [2, 1, 3]
Index nums[i] target[i] Mismatch? Set
0 1 2 Yes {1}
1 2 1 Yes {1, 2}
2 3 3 No {1, 2}

Final answer:

len({1, 2}) = 2

Example 2

nums   = [4, 1, 4]
target = [5, 1, 4]
Index nums[i] target[i] Mismatch? Set
0 4 5 Yes {4}
1 1 1 No {4}
2 4 4 No {4}

Final answer:

len({4}) = 1

Example 3

nums   = [7, 3, 7]
target = [5, 5, 9]
Index nums[i] target[i] Mismatch? Set
0 7 5 Yes {7}
1 3 5 Yes {3, 7}
2 7 9 Yes {3, 7}

Final answer:

len({3, 7}) = 2

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass through the arrays
Space O(n) In the worst case every mismatched value is distinct

The algorithm performs a single linear scan of the input. Every set insertion is expected O(1), so the total running time is O(n).

The set may contain up to n distinct values in the worst case, giving O(n) auxiliary space.

Test Cases

sol = Solution()

assert sol.minOperations([1, 2, 3], [2, 1, 3]) == 2  # Example 1
assert sol.minOperations([4, 1, 4], [5, 1, 4]) == 1  # Example 2
assert sol.minOperations([7, 3, 7], [5, 5, 9]) == 2  # Example 3

assert sol.minOperations([1], [1]) == 0  # Single element already correct
assert sol.minOperations([1], [2]) == 1  # Single mismatch

assert sol.minOperations([5, 5, 5], [1, 2, 3]) == 1  # Same source value everywhere
assert sol.minOperations([1, 2, 3], [1, 2, 3]) == 0  # Arrays already equal

assert sol.minOperations([1, 1, 2, 2], [3, 4, 5, 6]) == 2  # Two distinct source values
assert sol.minOperations([1, 2, 3, 4], [5, 6, 7, 8]) == 4  # Every source value distinct

assert sol.minOperations([10, 20, 10, 20], [1, 2, 3, 4]) == 2  # Repeated mismatching values
assert sol.minOperations([1, 2, 1, 2, 1], [1, 3, 1, 4, 1]) == 1  # Only value 2 must be fixed

Test Summary

Test Why
[1,2,3] → [2,1,3] Example 1
[4,1,4] → [5,1,4] Example 2
[7,3,7] → [5,5,9] Example 3
Single equal element Minimum input size
Single mismatch Smallest nontrivial case
All mismatches share same value One operation fixes all
Arrays already equal Answer is zero
Two repeated source values Distinct-value counting
All values distinct Worst case answer
Repeated mismatching values Duplicate elimination
Only one value mismatches Verify selective counting

Edge Cases

Arrays Already Equal

If every index already satisfies nums[i] == target[i], no operation is needed.

A common bug is accidentally counting values even when they already match. The implementation avoids this by inserting into the set only when a mismatch exists.

Many Mismatches With the Same Value

Consider:

nums   = [5, 5, 5]
target = [1, 2, 3]

Every position is wrong, but all of them contain the same current value. Only one operation choosing 5 is required.

Using a hash set naturally handles this because duplicate values are stored only once.

Mixed Matching and Mismatching Occurrences

Consider:

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

The value 4 appears twice, but only one occurrence is mismatched.

A naive solution might incorrectly count all occurrences of 4. The correct logic only considers positions where nums[i] != target[i], so 4 contributes exactly one operation.

Every Mismatched Position Has a Different Value

Consider:

nums   = [1, 2, 3, 4]
target = [5, 6, 7, 8]

Each mismatched position contains a unique source value. Therefore each value requires its own operation, and the answer equals the number of mismatches.

This represents the worst case for the size of the hash set and confirms the O(n) space bound.