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

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