We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Maximize Last Elements in Arrays

Number: 3190

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two 0-indexed integer arrays nums1 and nums2 of the same length n, you can perform operations where you choose an index i (0 ≤ i < n) and swap nums1[i] with nums2[i]. The goal is to achieve that:

  1. The last element of nums1 equals the maximum value in the final nums1.
  2. The last element of nums2 equals the maximum value in the final nums2. Return the minimum number of swap operations needed to meet both conditions, or -1 if impossible.

Key Insights

  • At each index i you decide whether to swap or not; the decision is independent across indices.
  • The final arrays are determined by: for each i, if not swapped, final value is the original value; if swapped, it takes the value from the other array.
  • The last element’s swap decision (at i = n-1) is fixed by the condition: you have two cases to consider.
    • Case 1: Do not swap the last element. In this case, target1 = nums1[n-1] should be the maximum for nums1 and target2 = nums2[n-1] should be the maximum for nums2.
    • Case 2: Swap the last element. In this case, target1 = nums2[n-1] should be the maximum for nums1 and target2 = nums1[n-1] should be the maximum for nums2.
  • For each other index 0 ≤ i < n-1, choose the swap decision (if available) that keeps the final value at index i less than or equal to the corresponding target and minimizes the swap count.

Space and Time Complexity

Time Complexity: O(n) – The solution processes each element once. Space Complexity: O(1) – Only constant extra space is used.

Solution

We consider two cases based on the action taken at the last index:

  1. Do not swap at the last index:
    • Set targetA = nums1[n-1] and targetB = nums2[n-1].
    • For each index i from 0 to n-2, determine if the original assignment (no swap) satisfies nums1[i] ≤ targetA and nums2[i] ≤ targetB.
    • If not, check if swapping yields nums2[i] ≤ targetA and nums1[i] ≤ targetB.
    • If neither works for any index, case 1 fails.
  2. Swap at the last index:
    • Set targetA = nums2[n-1] and targetB = nums1[n-1].
    • For each index i from 0 to n-2, apply similar checks as above.
    • Add one swap for the last index. Return the minimum operation count among the two valid cases (or -1 if both fail).

The main trick is in breaking the problem into two independent cases and evaluating the feasibility for each index without needing dynamic programming—the decision is local and independent.

Code Solutions

# Python solution for the problem

def minimumOperations(nums1, nums2):
    n = len(nums1)
    
    def compute_ops(swap_last):
        # Determine target values based on whether last element is swapped or not.
        if swap_last:
            targetA, targetB = nums2[n - 1], nums1[n - 1]
            ops = 1  # because we swapped the last element
        else:
            targetA, targetB = nums1[n - 1], nums2[n - 1]
            ops = 0
        
        # Process every index from 0 to n-2
        for i in range(n - 1):
            # If no swap works, then check if a swap is required
            no_swap_valid = (nums1[i] <= targetA and nums2[i] <= targetB)
            swap_valid = (nums2[i] <= targetA and nums1[i] <= targetB)
            # If at least one is valid, choose the one with fewer operations
            if no_swap_valid:
                continue  # do nothing, zero cost for not swapping
            elif swap_valid:
                ops += 1  # swap at index i
            else:
                return float('inf')  # impossible for this configuration
        return ops

    # Check both configurations: not swapping last index and swapping last index.
    candidate1 = compute_ops(swap_last=False)
    candidate2 = compute_ops(swap_last=True)
    
    answer = min(candidate1, candidate2)
    return answer if answer != float('inf') else -1

# Example usage:
#print(minimumOperations([1,2,7], [4,5,3]))  # Expected output: 1
← Back to All Questions