Skip to content

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
}

Comments