You are given two integer arrays: nums1 with length n and nums2 with length n + 1. Notice that nums2 is exactly one element longer than nums1.

Your goal is to transform nums1 so that it becomes identical to nums2, using as few operations as possible.

In each operation, you pick an index i of nums1 and do one of the following:

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

Each of these counts as a single operation.

Return the minimum total number of operations needed.

A few key points to understand the problem:

1. Since nums2 has one more element than nums1, you must use the append operation at least once to make the lengths match. The appended value is a copy of some existing element nums1[i].

2. The first n positions of nums1 must end up equal to the first n elements of nums2. Changing nums1[i] to nums2[i] costs exactly |nums1[i] - nums2[i]| operations (each step of +1 or -1 is one operation).

3. The appended element must eventually equal nums2[n] (the last element of nums2). You can be clever here: while adjusting nums1[i] from its original value toward nums2[i], if the value nums2[n] lies between nums1[i] and nums2[i], you can append a copy at the exact moment the element passes through nums2[n] — costing only 1 extra operation for the append itself.

4. If no element's adjustment path passes through nums2[n], you must pay extra: the smallest gap d between nums2[n] and any value on the boundary of some element's path (either its starting value nums1[i] or its target nums2[i]), plus the 1 operation for the append.

Example:

Suppose nums1 = [3] and nums2 = [5, 4].

• Adjusting 3 → 5 costs 2 operations. Along the way, the value passes through 4, so when it reaches 4, append a copy (cost 1), then continue to 5 (total: 2 + 1 = 3 operations).

The answer is the minimum number of such operations over all possible strategies.

Let's start by figuring out what costs are unavoidable, and then think about where we have freedom to save operations.

The unavoidable part. The first n elements of nums1 must match the first n elements of nums2. The only way to change a value is by +1 or -1 steps, so each pair costs exactly |nums1[i] - nums2[i]| operations — there's no way around it. Also, since nums2 is one element longer, we must perform at least one append, which costs 1 operation. So a hard lower bound on the answer is:

sum(|nums1[i] - nums2[i]|) + 1

The interesting part: where does the appended element come from? The appended value is a snapshot of some nums1[i] at the moment we copy it, and it must end up equal to nums2[n] (the last element of nums2). The key insight is that elements don't jump — they move one step at a time, so as nums1[i] travels from its original value to nums2[i], it passes through every integer in between.

This gives us a free ride: if nums2[n] lies inside the interval [min(nums1[i], nums2[i]), max(nums1[i], nums2[i])] for any index i, we can pause that element's journey exactly when it equals nums2[n], append it (cost 1, already counted), and continue. The appended copy is already correct — zero extra cost beyond the lower bound.

When no path passes through nums2[n]. If nums2[n] falls outside every element's travel interval, we have to make a detour. Take some element, walk it to nums2[n], append, then walk it back to where it needs to go. The detour costs 2 × (distance overshot) — but wait, we can be smarter: we only need to move the element to nums2[n] before appending or after copying, and the cheapest detour is measured from whichever endpoint of an element's interval is closest to nums2[n]. Actually, thinking carefully: we can append a copy at any point during the journey, then keep adjusting the appended element separately. So the extra cost is just the minimal distance:

d = min over all i of min(|nums1[i] - nums2[n]|, |nums2[i] - nums2[n]|)

We move the appended copy from the nearest reachable value to nums2[n], paying d extra operations.

Putting it together. The answer is:

• sum of |nums1[i] - nums2[i]| (mandatory adjustments)
• + 1 (mandatory append)
• + d only if no element's path already covers nums2[n].

This explains the greedy one-pass structure: as we zip through the pairs, we accumulate the differences, check the "covers nums2[n]" condition (y <= nums2[-1] <= x after ordering the pair), and track the fallback distance d in case the condition never holds.

Pattern Learn more about Greedy patterns.

The implementation is a single greedy pass over the paired elements of nums1 and nums2, tracking three things along the way: the accumulated adjustment cost, whether a "free" append point exists, and the cheapest fallback distance.

Step 1: Initialize the answer with the mandatory append.

ans = 1
ok = False
d = inf

• ans = 1 accounts for the one append operation we must always perform (since nums2 is one element longer than nums1).
• ok is a flag indicating whether some element's adjustment path passes through nums2[-1] (the target value of the appended element).
• d tracks the minimum extra distance needed if no such path exists, initialized to infinity.

Step 2: Iterate over each pair (nums1[i], nums2[i]).

for x, y in zip(nums1, nums2):
    if x < y:
        x, y = y, x

We normalize each pair so that x is the larger value and y is the smaller. After the swap, the element's travel interval is simply [y, x], which simplifies the checks below.

Step 3: Accumulate the mandatory adjustment cost.

    ans += x - y

Since x >= y after normalization, x - y equals |nums1[i] - nums2[i]| — the unavoidable cost of adjusting nums1[i] to nums2[i].

Step 4: Track the fallback distance.

    d = min(d, abs(x - nums2[-1]), abs(y - nums2[-1]))

If we end up needing a detour, the cheapest one starts from whichever interval endpoint (the original value or the target value) is closest to nums2[-1]. We keep the global minimum of these distances across all indices.

Step 5: Check for a free append point.

    ok = ok or y <= nums2[-1] <= x

If nums2[-1] lies within the interval [y, x], then while adjusting this element step by step, its value will pass through nums2[-1] exactly. At that moment we append a copy — the copy is already correct, costing nothing beyond the 1 already counted. Once ok becomes True, it stays True.

Step 6: Pay the detour if necessary.

if not ok:
    ans += d
return ans

If no element's path covers nums2[-1], we append a copy from the nearest reachable value and adjust the copy itself by d steps to reach nums2[-1].

Worked trace. Take nums1 = [3], nums2 = [5, 4]:

• Start: ans = 1, ok = False, d = inf.
• Pair (3, 5) → normalized to x = 5, y = 3. Then ans = 1 + 2 = 3, d = min(inf, |5-4|, |3-4|) = 1, and since 3 <= 4 <= 5, ok = True.
• ok is True, so no extra cost. Return 3.

Complexity Analysis.

• Time complexity: O(n) — a single pass through the n paired elements, with constant work per pair.
• Space complexity: O(1) — only a fixed number of scalar variables (ans, ok, d) are used, regardless of input size.