Minimum Operations to Maximize Last Elements in Arrays

Med

#2614Time: 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`.

Patterns

Enumeration

Data structures

Array

Prompt

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] <= 10⁹
1 <= nums2[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    int minSwaps = Integer.MAX_VALUE;3 4    public int minimumOperations(int[] nums1, int[] nums2) {5        // This is a conceptual implementation. It will be too slow for the given constraints.6        solve(0, 0, nums1, nums2);7        return minSwaps == Integer.MAX_VALUE ? -1 : minSwaps;8    }9 10    private void solve(int index, int currentSwaps, int[] nums1, int[] nums2) {11        if (index == nums1.length) {12            if (isValid(nums1, nums2)) {13                minSwaps = Math.min(minSwaps, currentSwaps);14            }15            return;16        }17 18        // Case 1: Don't swap at the current index19        solve(index + 1, currentSwaps, nums1, nums2);20 21        // Case 2: Swap at the current index22        swap(nums1, nums2, index);23        solve(index + 1, currentSwaps + 1, nums1, nums2);24        swap(nums1, nums2, index); // Backtrack to restore the arrays25    }26 27    private void swap(int[] nums1, int[] nums2, int i) {28        int temp = nums1[i];29        nums1[i] = nums2[i];30        nums2[i] = temp;31    }32 33    private boolean isValid(int[] nums1, int[] nums2) {34        int n = nums1.length;35        int max1 = nums1[n - 1];36        int max2 = nums2[n - 1];37        for (int i = 0; i < n; i++) {38            if (nums1[i] > max1 || nums2[i] > max2) {39                return false;40            }41        }42        return true;43    }44}

Complexity

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`.

Trade-offs

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

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.

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.

Walkthrough

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.

1class Solution {2    public int minimumOperations(int[] nums1, int[] nums2) {3        int n = nums1.length;4 5        // Case 1: We don't swap the last elements.6        // The target maximums are the original last elements.7        int swaps1 = countSwaps(nums1[n - 1], nums2[n - 1], nums1, nums2);8 9        // Case 2: We swap the last elements.10        // The target maximums are the swapped last elements.11        int swaps2 = countSwaps(nums2[n - 1], nums1[n - 1], nums1, nums2);12        if (swaps2 != Integer.MAX_VALUE) {13            swaps2++; // Add 1 for the swap at the last position itself.14        }15 16        int result = Math.min(swaps1, swaps2);17 18        return result == Integer.MAX_VALUE ? -1 : result;19    }20 21    // Helper function to calculate swaps for given target maximums.22    private int countSwaps(int max1, int max2, int[] nums1, int[] nums2) {23        int n = nums1.length;24        int swaps = 0;25        for (int i = 0; i < n - 1; i++) {26            int n1 = nums1[i];27            int n2 = nums2[i];28 29            boolean isOriginalValid = (n1 <= max1 && n2 <= max2);30            boolean isSwappedValid = (n2 <= max1 && n1 <= max2);31 32            if (!isOriginalValid && !isSwappedValid) {33                return Integer.MAX_VALUE; // This scenario is impossible.34            } else if (!isOriginalValid) {35                swaps++; // We are forced to swap.36            }37        }38        return swaps;39    }40}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int n;4public5  int minOperations(int[] nums1, int[] nums2) {6    n = nums1.length;7    int a = f(nums1, nums2, nums1[n - 1], nums2[n - 1]);8    int b = f(nums1, nums2, nums2[n - 1], nums1[n - 1]);9    return a + b == -2 ? -1 : Math.min(a, b + 1);10  }11private12  int f(int[] nums1, int[] nums2, int x, int y) {13    int cnt = 0;14    for (int i = 0; i < n - 1; ++i) {15      if (nums1[i] <= x && nums2[i] <= y) {16        continue;17      }18      if (!(nums1[i] <= y && nums2[i] <= x)) {19        return -1;20      }21      ++cnt;22    }23    return cnt;24  }25}

1class Solution {2public:3  int minOperations(vector<int> &nums1, vector<int> &nums2) {4    int n = nums1.size();5    auto f = [&](int x, int y) {6      int cnt = 0;7      for (int i = 0; i < n - 1; ++i) {8        if (nums1[i] <= x && nums2[i] <= y) {9          continue;10        }11        if (!(nums1[i] <= y && nums2[i] <= x)) {12          return -1;13        }14        ++cnt;15      }16      return cnt;17    };18    int a = f(nums1.back(), nums2.back());19    int b = f(nums2.back(), nums1.back());20    return a + b == -2 ? -1 : min(a, b + 1);21  }22};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem