# Minimum Operations to Maximize Last Elements in Arrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-maximize-last-elements-in-arrays)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-maximize-last-elements-in-arrays
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## 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 the **minimum** number of operations needed to meet **both** conditions_, _or_ `-1` _if it is **impossible** to satisfy both conditions._

**Example 1:**

**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:**

**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:**

**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] <= 109`
* `1 <= nums2[i] <= 109`

# Approaches
## Brute Force with Recursion
This approach explores every possible combination of swaps. For each index from 0 to n-1, we have two choices: either swap `nums1[i]` and `nums2[i]` or not. This creates a decision tree of depth `n`, leading to `2^n` possible final configurations of the arrays. For each configuration, we check if it satisfies the given conditions and keep track of the minimum number of swaps required.
**Time:** O(n * 2^n) - There are `2^n` possible swap configurations. For each configuration, we perform a validation check which takes O(n) time to iterate through the arrays and find the maximums. · **Space:** O(n) - The space complexity is determined by the maximum depth of the recursion stack, which is `n`.
**Pros:** Guaranteed to find the correct answer if it runs to completion.; Conceptually simple to understand as it checks every possibility.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (`n` up to 1000).
### Explanation
We can implement this using a recursive function that tries both possibilities (swapping and not swapping) at each index. The function builds up a path in the decision tree. When it reaches a leaf (a full configuration of the arrays), it checks if the configuration is valid. If it is, it compares the number of swaps used to reach this state with the minimum found so far and updates it if necessary.

```java
class Solution {
    int minSwaps = Integer.MAX_VALUE;

    public int minimumOperations(int[] nums1, int[] nums2) {
        // This is a conceptual implementation. It will be too slow for the given constraints.
        solve(0, 0, nums1, nums2);
        return minSwaps == Integer.MAX_VALUE ? -1 : minSwaps;
    }

    private void solve(int index, int currentSwaps, int[] nums1, int[] nums2) {
        if (index == nums1.length) {
            if (isValid(nums1, nums2)) {
                minSwaps = Math.min(minSwaps, currentSwaps);
            }
            return;
        }

        // Case 1: Don't swap at the current index
        solve(index + 1, currentSwaps, nums1, nums2);

        // Case 2: Swap at the current index
        swap(nums1, nums2, index);
        solve(index + 1, currentSwaps + 1, nums1, nums2);
        swap(nums1, nums2, index); // Backtrack to restore the arrays
    }

    private void swap(int[] nums1, int[] nums2, int i) {
        int temp = nums1[i];
        nums1[i] = nums2[i];
        nums2[i] = temp;
    }

    private boolean isValid(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int max1 = nums1[n - 1];
        int max2 = nums2[n - 1];
        for (int i = 0; i < n; i++) {
            if (nums1[i] > max1 || nums2[i] > max2) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Create a recursive helper function `solve(index, currentSwaps, nums1, nums2)`.
- **Base Case:** When `index` reaches the end of the arrays (`index == n`), we have a complete configuration.
  - Check if the current configuration is valid: `nums1[n-1]` must be the maximum of `nums1`, and `nums2[n-1]` must be the maximum of `nums2`.
  - If valid, update a global minimum swaps variable with `currentSwaps`.
  - Return.
- **Recursive Step:** For the current `index`:
  1.  **Don't Swap:** Make a recursive call `solve(index + 1, currentSwaps, nums1, nums2)`.
  2.  **Swap:** Swap `nums1[index]` and `nums2[index]`. Make a recursive call `solve(index + 1, currentSwaps + 1, nums1, nums2)`. After the call returns, swap back the elements to restore the state for other recursive branches (this is called backtracking).
- The initial call is `solve(0, 0, nums1, nums2)`. The final answer is the global minimum swaps found. If no valid configuration is found, the minimum will remain at its initial large value, indicating impossibility.

## Greedy Two-Case Analysis
This approach is based on a key observation: the final values at the last index, `nums1[n-1]` and `nums2[n-1]`, must be the maximums of their respective arrays. These final values must originate from the initial pair `(nums1[n-1], nums2[n-1])`. This leaves only two possibilities for the target maximums: either `(nums1[n-1], nums2[n-1])` or, after one swap, `(nums2[n-1], nums1[n-1])`. We can calculate the minimum swaps required for each of these two scenarios and take the overall minimum.
**Time:** O(n) - We iterate through the arrays a constant number of times (twice in the provided implementation, once for each case). · **Space:** O(1) - We only use a constant amount of extra space for variables.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for the given constraints.; Simple to implement once the core logic is understood.
**Cons:** Requires a specific insight into the problem structure, which might not be immediately obvious.
### Explanation
We can implement this by creating a helper function that calculates the number of swaps for a given pair of target maximums. We then call this helper for our two main cases.

**Case 1: No swap at `nums[n-1]`**
We calculate the swaps needed, assuming `nums1[n-1]` and `nums2[n-1]` are the final maximums.

**Case 2: Swap at `nums[n-1]`**
We calculate the swaps needed, assuming `nums2[n-1]` and `nums1[n-1]` are the final maximums. We add 1 to this result to account for the swap at the last index itself.

The final result is the minimum of these two cases. If a case is impossible (i.e., for some index `i`, neither the original nor the swapped pair fits under the target maximums), we can treat its cost as infinity.

```java
class Solution {
    public int minimumOperations(int[] nums1, int[] nums2) {
        int n = nums1.length;

        // Case 1: We don't swap the last elements.
        // The target maximums are the original last elements.
        int swaps1 = countSwaps(nums1[n - 1], nums2[n - 1], nums1, nums2);

        // Case 2: We swap the last elements.
        // The target maximums are the swapped last elements.
        int swaps2 = countSwaps(nums2[n - 1], nums1[n - 1], nums1, nums2);
        if (swaps2 != Integer.MAX_VALUE) {
            swaps2++; // Add 1 for the swap at the last position itself.
        }

        int result = Math.min(swaps1, swaps2);

        return result == Integer.MAX_VALUE ? -1 : result;
    }

    // Helper function to calculate swaps for given target maximums.
    private int countSwaps(int max1, int max2, int[] nums1, int[] nums2) {
        int n = nums1.length;
        int swaps = 0;
        for (int i = 0; i < n - 1; i++) {
            int n1 = nums1[i];
            int n2 = nums2[i];

            boolean isOriginalValid = (n1 <= max1 && n2 <= max2);
            boolean isSwappedValid = (n2 <= max1 && n1 <= max2);

            if (!isOriginalValid && !isSwappedValid) {
                return Integer.MAX_VALUE; // This scenario is impossible.
            } else if (!isOriginalValid) {
                swaps++; // We are forced to swap.
            }
        }
        return swaps;
    }
}
```
### Algorithm
- The core idea is that the final maximums for `nums1` and `nums2` must be chosen from the pair `(nums1[n-1], nums2[n-1])`. This gives two scenarios.
- **Scenario 1: No swap at the last index.**
  - The target maximums are `target1 = nums1[n-1]` and `target2 = nums2[n-1]`.
  - Calculate the swaps needed for indices `0` to `n-2` to satisfy `nums1[i] <= target1` and `nums2[i] <= target2`. Let this be `cost1`.
- **Scenario 2: Swap at the last index.**
  - This costs 1 swap initially.
  - The target maximums are `target1 = nums2[n-1]` and `target2 = nums1[n-1]`.
  - Calculate the swaps needed for indices `0` to `n-2`. Let this be `cost2`. The total cost for this scenario is `1 + cost2`.
- For each index `i < n-1` in the calculation:
  - If `nums1[i]` and `nums2[i]` already satisfy the target conditions, 0 swaps are needed for this index.
  - If not, check if swapping them (`nums2[i]`, `nums1[i]`) satisfies the conditions. If yes, 1 swap is needed.
  - If neither configuration works, the entire scenario is impossible.
- The final answer is the minimum of the costs from the two scenarios. If both scenarios are impossible, return -1.

# Solutions
### Java

```java
class Solution {
private
  int n;
public
  int minOperations(int[] nums1, int[] nums2) {
    n = nums1.length;
    int a = f(nums1, nums2, nums1[n - 1], nums2[n - 1]);
    int b = f(nums1, nums2, nums2[n - 1], nums1[n - 1]);
    return a + b == -2 ? -1 : Math.min(a, b + 1);
  }
private
  int f(int[] nums1, int[] nums2, int x, int y) {
    int cnt = 0;
    for (int i = 0; i < n - 1; ++i) {
      if (nums1[i] <= x && nums2[i] <= y) {
        continue;
      }
      if (!(nums1[i] <= y && nums2[i] <= x)) {
        return -1;
      }
      ++cnt;
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums1, vector<int> &nums2) {
    int n = nums1.size();
    auto f = [&](int x, int y) {
      int cnt = 0;
      for (int i = 0; i < n - 1; ++i) {
        if (nums1[i] <= x && nums2[i] <= y) {
          continue;
        }
        if (!(nums1[i] <= y && nums2[i] <= x)) {
          return -1;
        }
        ++cnt;
      }
      return cnt;
    };
    int a = f(nums1.back(), nums2.back());
    int b = f(nums2.back(), nums1.back());
    return a + b == -2 ? -1 : min(a, b + 1);
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int: def f(x: int, y: int) -> int: cnt = 0 for a, b in zip(nums1[: - 1], nums2[: - 1]): if a <= x and b <= y: continue if not (a <= y and b <= x): return - 1 cnt += 1 return cnt a, b = f(nums1[- 1], nums2[- 1]), f(nums2[- 1], nums1[- 1]) return - 1 if a + b == - 2 else min(a, b + 1)

```