LeetCode Problem 2934

Difficulty: 🟡 Medium
Topics: Array, Enumeration

Solution

LeetCode 2934 - Minimum Operations to Maximize Last Elements in Arrays

Problem Understanding

You are given two arrays, nums1 and nums2, both of the same length n. For every index i, you may optionally swap the pair (nums1[i], nums2[i]). Each swap counts as one operation.

Your goal is to make the last element of each array become the maximum element within that array:

• nums1[n - 1] must be the largest value in nums1
• nums2[n - 1] must be the largest value in nums2

You need to determine the minimum number of swaps required to satisfy both conditions simultaneously. If it is impossible, return -1.

The important detail is that swaps are only allowed between corresponding positions. You cannot rearrange elements arbitrarily. At every index, you only have two choices:

• Keep (nums1[i], nums2[i]) as is
• Swap them

The constraints are relatively small:

• n <= 1000

This means an O(n) or O(n^2) solution is perfectly acceptable. However, brute force over all swap combinations would still be exponential and infeasible.

Another key observation is that only the final elements matter as target maximums. Once we decide what the final pair (nums1[n - 1], nums2[n - 1]) should be, every earlier position becomes an independent validation problem.

Several edge cases are important:

• Arrays of length 1, where the conditions are automatically satisfied
• Situations where swapping the last index is required
• Situations where neither configuration works
• Cases where some indices are forced to swap to satisfy bounds
• Duplicate values, where equality with the maximum is allowed

The problem guarantees valid integer inputs and equal array lengths.

Approaches

Brute Force Approach

A straightforward approach is to try every possible subset of indices to swap.

For each index, there are two choices:

• Do not swap
• Swap

This creates 2^n possible configurations. For every configuration, we can construct the resulting arrays and verify whether the last element of each array is the maximum within that array.

This approach is correct because it exhaustively checks every possible valid sequence of operations. However, it is far too slow.

With n = 1000, the number of configurations becomes astronomically large.

Key Insight for the Optimal Solution

The critical observation is that the only values that matter globally are the final elements:

• nums1[n - 1]
• nums2[n - 1]

There are only two possibilities:

1. Keep the last pair unchanged
2. Swap the last pair

Once this decision is fixed, every earlier index becomes independent.

Suppose the target final values are:

• max1 = nums1[n - 1]
• max2 = nums2[n - 1]

Then for every index i < n - 1, we need:

• Either (nums1[i] <= max1 and nums2[i] <= max2)
• Or after swapping:

(nums2[i] <= max1 and nums1[i] <= max2)

If neither condition holds, the configuration is impossible.

If both conditions hold, we choose the cheaper option. If only one holds, that choice becomes forced.

Since there are only two global scenarios, the solution becomes linear.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n)	O(n)	Tries every swap combination
Optimal	O(n)	O(1)	Evaluates only two possible final states

Algorithm Walkthrough

1. First, define a helper function that computes the minimum operations needed assuming the final elements are fixed.
2. Inside this helper, let:

• target1 = nums1[n - 1]
• target2 = nums2[n - 1]

These are the maximum values we want every earlier element to stay below or equal to. 3. Traverse every index i from 0 to n - 2. 4. For each index, evaluate two possibilities:

• Keep the pair unchanged
• Swap the pair

5. The current pair can remain unchanged if:

nums1[i] <= target1
AND
nums2[i] <= target2

6. The current pair can be swapped if:

nums2[i] <= target1
AND
nums1[i] <= target2

7. Handle the four cases:

• Neither works, return impossible
• Only keep works, continue
• Only swap works, increment swap count
• Both work, choose not swapping because it costs fewer operations

8. Run this logic twice:

• Scenario 1: keep the last pair unchanged
• Scenario 2: swap the last pair

9. In scenario 2, add one extra operation because swapping the last pair itself costs one operation.
10. Return the minimum valid answer between the two scenarios. If neither works, return -1.

Why it works

The final elements completely determine the allowed upper bounds for every earlier position. Since each index interacts only with the chosen target maxima, decisions at different indices become independent.

By checking both possible final configurations, we exhaust all valid global arrangements. The greedy choice at each position is optimal because swapping at one index does not affect feasibility at any other index.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)

        def solve(target1: int, target2: int) -> int:
            operations = 0

            for i in range(n - 1):
                keep_valid = nums1[i] <= target1 and nums2[i] <= target2
                swap_valid = nums2[i] <= target1 and nums1[i] <= target2

                if not keep_valid and not swap_valid:
                    return float('inf')

                if not keep_valid:
                    operations += 1

            return operations

        option1 = solve(nums1[-1], nums2[-1])

        option2 = solve(nums2[-1], nums1[-1])
        if option2 != float('inf'):
            option2 += 1

        answer = min(option1, option2)

        return -1 if answer == float('inf') else answer

The implementation starts by defining a helper function solve. This function assumes the final target values are already fixed.

For every earlier index, the code checks whether the current pair can remain unchanged or must be swapped. If neither configuration satisfies the constraints, the helper immediately returns infinity to indicate impossibility.

The helper counts only forced swaps. Whenever both configurations are valid, the algorithm prefers not swapping because that minimizes operations.

The main function evaluates two scenarios:

• Keep the last pair as is
• Swap the last pair

The second scenario includes one extra operation because the last index itself must be swapped.

Finally, the minimum feasible answer is returned.

Go Solution

func minOperations(nums1 []int, nums2 []int) int {
	n := len(nums1)
	const INF = int(1e9)

	solve := func(target1 int, target2 int) int {
		operations := 0

		for i := 0; i < n-1; i++ {
			keepValid := nums1[i] <= target1 && nums2[i] <= target2
			swapValid := nums2[i] <= target1 && nums1[i] <= target2

			if !keepValid && !swapValid {
				return INF
			}

			if !keepValid {
				operations++
			}
		}

		return operations
	}

	option1 := solve(nums1[n-1], nums2[n-1])

	option2 := solve(nums2[n-1], nums1[n-1])
	if option2 != INF {
		option2++
	}

	answer := option1
	if option2 < answer {
		answer = option2
	}

	if answer == INF {
		return -1
	}

	return answer
}

The Go implementation follows the same logic as the Python version. Since Go does not have built in infinity values for integers, a large sentinel value INF is used instead.

Slices are used directly without additional memory allocation. Integer overflow is not a concern because the operation count is at most n.

Worked Examples

Example 1

nums1 = [1,2,7]
nums2 = [4,5,3]

Scenario 1: Keep last pair

Targets:

target1 = 7
target2 = 3

Index	Pair	Keep Valid	Swap Valid	Decision	Operations
0	(1,4)	No	Yes	Swap	1
1	(2,5)	No	Yes	Swap	2

Result: 2 operations

Scenario 2: Swap last pair

After swapping last index:

target1 = 3
target2 = 7

Extra operation for swapping last index:

operations = 1

Index	Pair	Keep Valid	Swap Valid	Decision	Operations
0	(1,4)	Yes	No	Keep	1
1	(2,5)	Yes	No	Keep	1

Result: 1 operation

Final answer:

1

Example 2

nums1 = [2,3,4,5,9]
nums2 = [8,8,4,4,4]

Scenario 1: Keep last pair

Targets:

target1 = 9
target2 = 4

Index	Pair	Keep Valid	Swap Valid	Decision	Operations
0	(2,8)	No	Yes	Swap	1
1	(3,8)	No	Yes	Swap	2
2	(4,4)	Yes	Yes	Keep	2
3	(5,4)	Yes	No	Keep	2

Result: 2 operations

Scenario 2: Swap last pair

Targets:

target1 = 4
target2 = 9

Index	Pair	Keep Valid	Swap Valid	Decision
3	(5,4)	No	No	Impossible

Result: impossible

Final answer:

2

Example 3

nums1 = [1,5,4]
nums2 = [2,5,3]

Scenario 1

Targets:

target1 = 4
target2 = 3

Index 1:

(5,5)

• Keep invalid
• Swap invalid

Impossible.

Scenario 2

Targets:

target1 = 3
target2 = 4

Again:

(5,5)

• Keep invalid
• Swap invalid

Impossible.

Final answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Two linear scans across the arrays
Space	O(1)	Only a few variables are used

The algorithm performs exactly two passes through the arrays, one for each possible final configuration. No auxiliary data structures proportional to input size are required.

Test Cases

from typing import List

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)

        def solve(target1: int, target2: int) -> int:
            operations = 0

            for i in range(n - 1):
                keep_valid = nums1[i] <= target1 and nums2[i] <= target2
                swap_valid = nums2[i] <= target1 and nums1[i] <= target2

                if not keep_valid and not swap_valid:
                    return float('inf')

                if not keep_valid:
                    operations += 1

            return operations

        option1 = solve(nums1[-1], nums2[-1])

        option2 = solve(nums2[-1], nums1[-1])
        if option2 != float('inf'):
            option2 += 1

        answer = min(option1, option2)

        return -1 if answer == float('inf') else answer

solver = Solution()

assert solver.minOperations([1,2,7], [4,5,3]) == 1  # example 1
assert solver.minOperations([2,3,4,5,9], [8,8,4,4,4]) == 2  # example 2
assert solver.minOperations([1,5,4], [2,5,3]) == -1  # example 3

assert solver.minOperations([1], [1]) == 0  # single element arrays
assert solver.minOperations([5,1], [1,5]) == 0  # already valid
assert solver.minOperations([1,5], [5,1]) == 1  # swap last element
assert solver.minOperations([3,4], [5,2]) == 1  # forced swap
assert solver.minOperations([10,1,1], [1,10,1]) == -1  # impossible case
assert solver.minOperations([4,4,4], [4,4,4]) == 0  # all equal values
assert solver.minOperations([1,2,3], [3,2,1]) == 1  # one beneficial swap

Test	Why
[1,2,7], [4,5,3]	Validates swapping the last pair
[2,3,4,5,9], [8,8,4,4,4]	Tests multiple swaps
[1,5,4], [2,5,3]	Tests impossible configuration
[1], [1]	Smallest possible input
[5,1], [1,5]	Already satisfies conditions
[1,5], [5,1]	Requires swapping the final index
[3,4], [5,2]	Tests forced swap logic
[10,1,1], [1,10,1]	Neither configuration works
[4,4,4], [4,4,4]	Duplicate maximum values
[1,2,3], [3,2,1]	Mixed keep and swap decisions

Edge Cases

One important edge case is arrays of length 1. In this situation, the only element is automatically the maximum element of its array. No swaps are required. The implementation handles this naturally because the loop over n - 1 elements becomes empty.

Another critical edge case occurs when the only valid solution requires swapping the last index itself. Many incorrect implementations forget to evaluate this scenario separately. The algorithm explicitly tests both possible target configurations, ensuring such cases are handled correctly.

A third important edge case is when some earlier index cannot satisfy the constraints in either orientation. For example, both the original pair and swapped pair may exceed the allowed target maxima. The helper function immediately detects this and returns impossibility, preventing invalid solutions from being counted.

Duplicate values are also important. The condition requires the last element to equal the maximum, not strictly exceed all others. The implementation correctly uses <= comparisons, allowing equal maximum values throughout the arrays.