Minimum Operations to Maximize Last Elements in Arrays

Problem

You are given two 0-indexed integer arrays, nums1 and nums2, both having length n.

You are allowed to perform a series of operations (possibly none).

In an operation, you select an index i in the range [0, n - 1] and swap the values of nums1[i] and nums2[i].

Your task is to find the minimum number of operations required to satisfy the following conditions:

nums1[n - 1] is equal to the maximum value among all elements of nums1, i.e., nums1[n - 1] = max(nums1[0], nums1[1], ..., nums1[n - 1]).
nums2[n - 1] is equal to the maximum value among all elements of nums2, i.e., nums2[n - 1] = max(nums2[0], nums2[1], ..., nums2[n - 1]).

Return an integer denoting theminimum number of operations needed to meet both conditions, or-1 if it isimpossible to satisfy both conditions.

Examples

Example 1

1
2
3
4
5
6
7


Input: nums1 = [1,2,7], nums2 = [4,5,3]
Output: 1
Explanation: In this example, an operation can be performed using index i = 2.
When nums1[2] and nums2[2] are swapped, nums1 becomes [1,2,3] and nums2 becomes [4,5,7].
Both conditions are now satisfied.
It can be shown that the minimum number of operations needed to be performed is 1.
So, the answer is 1.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: nums1 = [2,3,4,5,9], nums2 = [8,8,4,4,4]
Output: 2
Explanation: In this example, the following operations can be performed:
First operation using index i = 4.
When nums1[4] and nums2[4] are swapped, nums1 becomes [2,3,4,5,4], and nums2 becomes [8,8,4,4,9].
Another operation using index i = 3.
When nums1[3] and nums2[3] are swapped, nums1 becomes [2,3,4,4,4], and nums2 becomes [8,8,4,5,9].
Both conditions are now satisfied.
It can be shown that the minimum number of operations needed to be performed is 2.
So, the answer is 2.   

Example 3

1
2
3
4


Input: nums1 = [1,5,4], nums2 = [2,5,3]
Output: -1
Explanation: In this example, it is not possible to satisfy both conditions. 
So, the answer is -1.

Constraints

1 <= n == nums1.length == nums2.length <= 1000
1 <= nums1[i] <= 10^9
1 <= nums2[i] <= 10^9

Solution

Method 1 – Enumeration & Greedy

Intuition

To satisfy both conditions, we need to make the last element of each array the maximum in its array. Swapping at index i only affects nums1[i] and nums2[i], so we can enumerate all possible swap combinations for the last index and check if the conditions can be met with minimum swaps.

Approach

Find the maximum values in nums1 and nums2.
For each possible way to make nums1[n-1] and nums2[n-1] their respective maximums (by swapping or not), count the minimum swaps needed.
For each possibility, check if swapping at some indices can achieve both conditions.
If impossible, return -1.
Edge case: If both arrays already satisfy the condition, return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
    int minOperations(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int ma = *max_element(a.begin(), a.end());
        int mb = *max_element(b.begin(), b.end());
        int ans = INT_MAX;
        for (int swap_last = 0; swap_last < 2; ++swap_last) {
            int x = a[n-1], y = b[n-1];
            if (swap_last) swap(x, y);
            if (x != ma && y != mb) continue;
            int cnt = swap_last;
            for (int i = 0; i < n-1; ++i) {
                bool need_a = (a[i] == ma && x != ma);
                bool need_b = (b[i] == mb && y != mb);
                if (need_a && need_b) cnt = INT_MAX;
                else if (need_a || need_b) cnt++;
            }
            ans = min(ans, cnt);
        }
        return ans == INT_MAX ? -1 : 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
27
28
29
30
31
32
33
34
35


func minOperations(a, b []int) int {
    n := len(a)
    ma, mb := a[0], b[0]
    for i := 1; i < n; i++ {
        if a[i] > ma { ma = a[i] }
        if b[i] > mb { mb = b[i] }
    }
    ans := 1 << 30
    for swapLast := 0; swapLast < 2; swapLast++ {
        x, y := a[n-1], b[n-1]
        if swapLast == 1 {
            x, y = y, x
        }
        if x != ma && y != mb {
            continue
        }
        cnt := swapLast
        for i := 0; i < n-1; i++ {
            needA := a[i] == ma && x != ma
            needB := b[i] == mb && y != mb
            if needA && needB {
                cnt = 1 << 30
            } else if needA || needB {
                cnt++
            }
        }
        if cnt < ans {
            ans = cnt
        }
    }
    if ans == 1<<30 {
        return -1
    }
    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


class Solution {
    public int minOperations(int[] a, int[] b) {
        int n = a.length;
        int ma = Arrays.stream(a).max().getAsInt();
        int mb = Arrays.stream(b).max().getAsInt();
        int ans = Integer.MAX_VALUE;
        for (int swapLast = 0; swapLast < 2; swapLast++) {
            int x = a[n-1], y = b[n-1];
            if (swapLast == 1) {
                int tmp = x; x = y; y = tmp;
            }
            if (x != ma && y != mb) continue;
            int cnt = swapLast;
            for (int i = 0; i < n-1; i++) {
                boolean needA = (a[i] == ma && x != ma);
                boolean needB = (b[i] == mb && y != mb);
                if (needA && needB) cnt = Integer.MAX_VALUE;
                else if (needA || needB) cnt++;
            }
            ans = Math.min(ans, cnt);
        }
        return ans == Integer.MAX_VALUE ? -1 : 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


class Solution {
    fun minOperations(a: IntArray, b: IntArray): Int {
        val n = a.size
        val ma = a.maxOrNull()!!
        val mb = b.maxOrNull()!!
        var ans = Int.MAX_VALUE
        for (swapLast in 0..1) {
            var x = a[n-1]
            var y = b[n-1]
            if (swapLast == 1) {
                val tmp = x; x = y; y = tmp
            }
            if (x != ma && y != mb) continue
            var cnt = swapLast
            for (i in 0 until n-1) {
                val needA = (a[i] == ma && x != ma)
                val needB = (b[i] == mb && y != mb)
                if (needA && needB) cnt = Int.MAX_VALUE
                else if (needA || needB) cnt++
            }
            ans = minOf(ans, cnt)
        }
        return if (ans == Int.MAX_VALUE) -1 else ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def minOperations(self, a: list[int], b: list[int]) -> int:
        n = len(a)
        ma, mb = max(a), max(b)
        ans = float('inf')
        for swap_last in [0, 1]:
            x, y = a[-1], b[-1]
            if swap_last:
                x, y = y, x
            if x != ma and y != mb:
                continue
            cnt = swap_last
            for i in range(n-1):
                need_a = a[i] == ma and x != ma
                need_b = b[i] == mb and y != mb
                if need_a and need_b:
                    cnt = float('inf')
                elif need_a or need_b:
                    cnt += 1
            ans = min(ans, cnt)
        return -1 if ans == float('inf') else 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


impl Solution {
    pub fn min_operations(a: Vec<i32>, b: Vec<i32>) -> i32 {
        let n = a.len();
        let ma = *a.iter().max().unwrap();
        let mb = *b.iter().max().unwrap();
        let mut ans = i32::MAX;
        for swap_last in 0..2 {
            let (mut x, mut y) = (a[n-1], b[n-1]);
            if swap_last == 1 {
                let tmp = x; x = y; y = tmp;
            }
            if x != ma && y != mb { continue; }
            let mut cnt = swap_last;
            for i in 0..n-1 {
                let need_a = a[i] == ma && x != ma;
                let need_b = b[i] == mb && y != mb;
                if need_a && need_b { cnt = i32::MAX; }
                else if need_a || need_b { cnt += 1; }
            }
            ans = ans.min(cnt);
        }
        if ans == i32::MAX { -1 } else { ans }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
    minOperations(a: number[], b: number[]): number {
        const n = a.length;
        const ma = Math.max(...a);
        const mb = Math.max(...b);
        let ans = Number.MAX_SAFE_INTEGER;
        for (let swapLast = 0; swapLast < 2; swapLast++) {
            let x = a[n-1], y = b[n-1];
            if (swapLast) [x, y] = [y, x];
            if (x !== ma && y !== mb) continue;
            let cnt = swapLast;
            for (let i = 0; i < n-1; i++) {
                const needA = a[i] === ma && x !== ma;
                const needB = b[i] === mb && y !== mb;
                if (needA && needB) cnt = Number.MAX_SAFE_INTEGER;
                else if (needA || needB) cnt++;
            }
            ans = Math.min(ans, cnt);
        }
        return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
    }
}

Complexity

⏰ Time complexity: O(n) — We scan both arrays and check all possible swap scenarios for the last index, and for each, scan the rest of the array.
🧺 Space complexity: O(1) — Only a few variables are used for counting and tracking, no extra space proportional to n.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Enumeration & Greedy#

Intuition#

Approach#

Code#

Complexity#