Welcome to Subscribe On Youtube

3724. Minimum Operations to Transform Array

Description

You are given two integer arrays nums1 of length n and nums2 of length n + 1.

You want to transform nums1 into nums2 using the minimum number of operations.

You may perform the following operations any number of times, each time choosing an index i:

  • Increase nums1[i] by 1.
  • Decrease nums1[i] by 1.
  • Append nums1[i] to the end of the array.

Return the minimum number of operations required to transform nums1 into nums2.

 

Example 1:

Input: nums1 = [2,8], nums2 = [1,7,3]

Output: 4

Explanation:

Step i Operation nums1[i] Updated nums1
1 0 Append - [2, 8, 2]
2 0 Decrement Decreases to 1 [1, 8, 2]
3 1 Decrement Decreases to 7 [1, 7, 2]
4 2 Increment Increases to 3 [1, 7, 3]

Thus, after 4 operations nums1 is transformed into nums2.

Example 2:

Input: nums1 = [1,3,6], nums2 = [2,4,5,3]

Output: 4

Explanation:

Step i Operation nums1[i] Updated nums1
1 1 Append - [1, 3, 6, 3]
2 0 Increment Increases to 2 [2, 3, 6, 3]
3 1 Increment Increases to 4 [2, 4, 6, 3]
4 2 Decrement Decreases to 5 [2, 4, 5, 3]

Thus, after 4 operations nums1 is transformed into nums2.

Example 3:

Input: nums1 = [2], nums2 = [3,4]

Output: 3

Explanation:

Step i Operation nums1[i] Updated nums1
1 0 Increment Increases to 3 [3]
2 0 Append - [3, 3]
3 1 Increment Increases to 4 [3, 4]

Thus, after 3 operations nums1 is transformed into nums2.

 

Constraints:

  • 1 <= n == nums1.length <= 105
  • nums2.length == n + 1
  • 1 <= nums1[i], nums2[i] <= 105

Solutions

Solution 1: Greedy

We define an answer variable $\text{ans}$ to record the minimum number of operations, with an initial value of $1$, representing the operation needed to append the last element to the end of the array.

Then we iterate through the first $n$ elements of the array. For each pair of corresponding elements $(\text{nums1}[i], \text{nums2}[i])$, we calculate their difference and add it to $\text{ans}$.

During the iteration, we also need to check whether $\min(\text{nums1}[i], \text{nums2}[i]) \leq \text{nums2}[n] \leq \max(\text{nums1}[i], \text{nums2}[i])$ holds. If it does, it means we can directly adjust $\text{nums1}[i]$ to reach $\text{nums2}[n]$. Otherwise, we need to record a minimum difference $d$, which represents the minimum number of operations required to adjust some element to $\text{nums2}[n]$.

Finally, if no element satisfying the condition is found after the iteration, we need to add $d$ to $\text{ans}$, indicating that we need extra operations to adjust some element to $\text{nums2}[n]$.

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

  • class Solution {
    public long minOperations(int[] nums1, int[] nums2) {
        long ans = 1;
        int n = nums1.length;
        boolean ok = false;
        int d = 1 << 30;
        for (int i = 0; i < n; ++i) {
            int x = Math.max(nums1[i], nums2[i]);
            int y = Math.min(nums1[i], nums2[i]);
            ans += x - y;
            d = Math.min(d, Math.min(Math.abs(x - nums2[n]), Math.abs(y - nums2[n])));
            ok = ok || (nums2[n] >= y && nums2[n] <= x);
        }
        if (!ok) {
            ans += d;
        }
        return ans;
    }
}


  • class Solution {
public:
    long long minOperations(vector<int>& nums1, vector<int>& nums2) {
        long long ans = 1;
        int n = nums1.size();
        bool ok = false;
        int d = 1 << 30;
        for (int i = 0; i < n; ++i) {
            int x = max(nums1[i], nums2[i]);
            int y = min(nums1[i], nums2[i]);
            ans += x - y;
            d = min(d, min(abs(x - nums2[n]), abs(y - nums2[n])));
            ok = ok || (nums2[n] >= y && nums2[n] <= x);
        }
        if (!ok) {
            ans += d;
        }
        return ans;
    }
};


  • class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 1
        ok = False
        d = inf
        for x, y in zip(nums1, nums2):
            if x < y:
                x, y = y, x
            ans += x - y
            d = min(d, abs(x - nums2[-1]), abs(y - nums2[-1]))
            ok = ok or y <= nums2[-1] <= x
        if not ok:
            ans += d
        return ans


  • func minOperations(nums1 []int, nums2 []int) int64 {
	var ans int64 = 1
	n := len(nums1)
	ok := false
	d := 1 << 30
	for i := 0; i < n; i++ {
		x := max(nums1[i], nums2[i])
		y := min(nums1[i], nums2[i])
		ans += int64(x - y)
		d = min(d, min(abs(x-nums2[n]), abs(y-nums2[n])))
		if nums2[n] >= y && nums2[n] <= x {
			ok = true
		}
	}
	if !ok {
		ans += int64(d)
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}


  • function minOperations(nums1: number[], nums2: number[]): number {
    let ans = 1;
    const n = nums1.length;
    let ok = false;
    let d = 1 << 30;
    for (let i = 0; i < n; ++i) {
        const x = Math.max(nums1[i], nums2[i]);
        const y = Math.min(nums1[i], nums2[i]);
        ans += x - y;
        d = Math.min(d, Math.abs(x - nums2[n]), Math.abs(y - nums2[n]));
        if (nums2[n] >= y && nums2[n] <= x) {
            ok = true;
        }
    }
    if (!ok) {
        ans += d;
    }
    return ans;
}

All Problems

All Solutions