Minimum Operations to Maximize Last Elements in Arrays - Solution & Explanation

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