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 <= 10001 <= nums1[i] <= 1091 <= nums2[i] <= 109Problem Overview: You are given two arrays of equal length. At any index i, you can swap nums1[i] with nums2[i]. The goal is to make the last element of each array the maximum element within that array using the minimum number of swaps.
The constraint that swaps are only allowed at the same index changes how you reason about the problem. Instead of freely rearranging values, you must decide for each index whether the pair should stay as is or be swapped. The final values at nums1[n-1] and nums2[n-1] become the target maximums, so every earlier element must be less than or equal to those values.
Approach 1: Greedy Swapping Approach (O(n) time, O(1) space)
The greedy strategy checks whether each index already satisfies the constraint relative to the final elements. For a pair (nums1[i], nums2[i]), at least one orientation must keep both values less than or equal to the final targets (nums1[n-1], nums2[n-1]). If the current orientation violates the rule but swapping fixes it, perform a swap and increment the operation count.
A practical implementation evaluates two scenarios: keep the last pair as is, or swap the last pair first. Each scenario sets different target maximums for the arrays. Then iterate from index 0 to n-2, checking whether the pair fits the constraint directly, requires a swap, or is impossible. If neither orientation works, the configuration is invalid. The minimum valid swap count across both scenarios is the answer.
This works because each index decision is independent once the final maximum values are fixed. The algorithm performs a single pass over the arrays and uses only constant extra memory. It relies on simple comparisons and conditional swaps, making it ideal for problems focused on array traversal and enumeration of possibilities.
Approach 2: Priority Queue Approach (O(n log n) time, O(n) space)
A less direct strategy pushes candidate elements into a priority queue while tracking which pairs violate the maximum constraint. The heap helps identify the largest conflicting elements that must be swapped to maintain valid ordering relative to the final targets.
During iteration, insert elements that exceed the allowed maximum into the priority queue. When a violation occurs, swap the pair that best restores the ordering and update the heap. This approach effectively manages conflicting elements dynamically but introduces extra overhead from heap operations.
The priority queue version is useful when extending the logic to more complex constraints or when you want a structured way to always resolve the largest violation first. However, the additional log n factor and memory overhead make it less efficient than the greedy method for this specific problem.
Recommended for interviews: The greedy enumeration approach is the expected solution. It shows you understand how fixing the final targets simplifies the problem and allows a linear scan. Mentioning both scenarios for the last pair demonstrates careful edge‑case handling. The priority queue version is usually unnecessary but can illustrate alternative thinking when discussing tradeoffs.
This approach involves identifying the maximum elements in both arrays and strategically swapping elements to ensure that the maximum elements are positioned at the last index of each array, aiming for the least number of swaps. We focus on swapping to achieve the maximum elements move to the end positions of nums1 and nums2, respectively.
This C implementation scans through the arrays to identify candidates for swapping to improve the last indices' values. The function counts the minimal swaps to achieve the condition if possible, or returns -1 otherwise.
Time Complexity: O(n), as it requires a linear scan through both arrays.
Space Complexity: O(1), as it uses only constant extra space.
We use a priority queue (max-heap) to extract maximum elements from both arrays and compute possible pairings for swaps. This approach will improve efficiency by focusing directly on maximizing elements and attempting the critical swap actions first.
C++ implementation utilizes dual priority queues; from each queue, it retrieves the maximum current value and attempts a swap if beneficial. Adjustments on priority happen until max conditions are met or deemed impossible.
Time Complexity: O(n log n), as insertions and removals from the priority queue are logarithmic in nature due to sorting.
Space Complexity: O(n), because of the priority queue storage requirement for elements.
We can discuss two cases:
nums1[n - 1] and nums2[n - 1]nums1[n - 1] and nums2[n - 1]For each case, we denote the last values of the arrays nums1 and nums2 as x and y, respectively. Then we traverse the first n - 1 values of the arrays nums1 and nums2, and use a variable cnt to record the number of swaps. If nums1[i] leq x and nums2[i] leq y, then no swap is needed. Otherwise, if nums1[i] leq y and nums2[i] leq x, then a swap is needed. If neither condition is met, return -1. Finally, return cnt.
We denote the number of swaps in the two cases as a and b, respectively. If a + b = -2, then it is impossible to satisfy both conditions, so return -1. Otherwise, return min(a, b + 1).
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Swapping Approach | Time Complexity: O(n), as it requires a linear scan through both arrays. |
| Priority Queue Approach | Time Complexity: O(n log n), as insertions and removals from the priority queue are logarithmic in nature due to sorting. |
| Case Discussion + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Swapping Approach | O(n) | O(1) | Best general solution. Single pass after fixing the final targets. |
| Priority Queue Approach | O(n log n) | O(n) | Useful when managing dynamic conflicts or extending to more complex ordering constraints. |
2934. Minimum Operations to Maximize Last Elements in Arrays | Weekly 371 • Tech Courses • 516 views views
Watch 3 more video solutions →Practice Minimum Operations to Maximize Last Elements in Arrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor