Welcome to Subscribe On Youtube

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

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.

  • 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();
    }
}


  • 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();
    }
};


  • 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)


  • 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)
}


  • 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;
}

All Problems

All Solutions