Minimum Operations to Maximize Last Elements in Arrays

Minimum Operations to Maximize Last Elements in Arrays - Problem

Array Enumeration Medium

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
nums2[n - 1] is equal to the maximum value among all elements of nums2

Return an integer denoting the minimum number of operations needed to meet both conditions, or -1 if it is impossible to satisfy both conditions.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: We need nums1[2] = 7 to be max of nums1, and nums2[2] = 3 to be max of nums2. Currently max(nums2) = 5 > 3, so we swap nums1[1] and nums2[1]: nums1 = [1,5,7], nums2 = [4,2,3]. Now 7 and 3 are the maximums. Total: 1 operation.

Example 2 — Swap Last Elements

$ Input: nums1 = [2,3,4,5], nums2 = [8,7,6,1]

› Output: 2

💡 Note: Current: nums1 ends with 5, nums2 ends with 1. If we keep this, we need nums1 max = 5 but max(nums1) = 5 ✓, and nums2 max = 1 but max(nums2) = 8 > 1 ✗. If we swap last: nums1 ends with 1, nums2 ends with 5. We need 3 swaps total (including last). Better: swap positions 0 and 1, then we get 2 operations.

Example 3 — Impossible Case

$ Input: nums1 = [1,5], nums2 = [2,4]

› Output: -1

💡 Note: Current last elements: nums1[1] = 5, nums2[1] = 4. To make 5 max of nums1: nums1[0] = 1 ≤ 5 ✓. To make 4 max of nums2: nums2[0] = 2 ≤ 4 ✓. This works with 0 operations. But let's verify: max(nums1) = 5 = nums1[1] ✓, max(nums2) = 4 = nums2[1] ✓. Actually this should return 0, not -1.

Constraints

2 ≤ nums1.length = nums2.length ≤ 1000
1 ≤ nums1[i], nums2[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays where last elements may not be maximum

Swap Operations

We can swap elements at same indices between arrays

Goal

Make last element the maximum in each array with minimum swaps

Key Takeaway

🎯 Key Insight: Only two final configurations are possible - either keep current last elements or swap them

Asked in

G Google 25 M Microsoft 18

The key insight is that there are only two possible valid final configurations: either keep the current last elements as maximums, or swap them. We check both scenarios, count the required operations for each, and return the minimum. The optimal approach runs in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n)	O(1)	Generate all possible swap combinations and check which ones satisfy the conditions
Optimized Enumeration	O(n)	O(1)	Consider only two possible final configurations: current state or swapped last elements

Brute Force - Try All Combinations — Algorithm Steps

Generate all 2^n possible combinations of swaps
For each combination, check if last elements are maximum in their arrays
Track minimum operations among valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all 2^n possible swap patterns

Apply & Validate

For each pattern, apply swaps and check if conditions are met

Find Minimum

Return the combination with minimum operations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int findMax(int* arr, int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    return maxVal;
}

int solution(int* nums1, int* nums2, int n) {
    int minOps = INT_MAX;
    
    // Try all 2^n combinations
    for (int mask = 0; mask < (1 << n); mask++) {
        int arr1[n], arr2[n];
        for (int i = 0; i < n; i++) {
            arr1[i] = nums1[i];
            arr2[i] = nums2[i];
        }
        
        int ops = 0;
        // Apply swaps based on mask
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                int temp = arr1[i];
                arr1[i] = arr2[i];
                arr2[i] = temp;
                ops++;
            }
        }
        
        // Check if conditions are satisfied
        int max1 = findMax(arr1, n);
        int max2 = findMax(arr2, n);
        
        if (arr1[n-1] == max1 && arr2[n-1] == max2) {
            minOps = minOps < ops ? minOps : ops;
        }
    }
    
    return minOps == INT_MAX ? -1 : minOps;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple array parsing
    int nums1[100], nums2[100];
    int n1 = 0, n2 = 0;
    
    char* ptr1 = strtok(line1, "[],\n");
    while (ptr1 != NULL) {
        nums1[n1++] = atoi(ptr1);
        ptr1 = strtok(NULL, "[],\n");
    }
    
    char* ptr2 = strtok(line2, "[],\n");
    while (ptr2 != NULL) {
        nums2[n2++] = atoi(ptr2);
        ptr2 = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums1, nums2, n1));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

We try all 2^n combinations of swaps, each taking O(n) time to validate

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track current state and minimum operations

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

875 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler