2934. Minimum Operations to Maximize Last Elements in Arrays
Problem Description
You are given two integer arrays nums1
and nums2
, both of the same length n
and indexed starting from zero. You have the ability to perform operations on these arrays, where a single operation consists of swapping the values at the same index i
in both arrays. The goal is to make the last element of each array the maximum value within that respective array. The problem asks to determine the minimum number of such operations required to achieve this goal for both arraysāor to establish that it is impossible to do so, in which case the result should be -1
.
To clarify:
nums1[n - 1]
should be equal to the maximum value innums1
.nums2[n - 1]
should be equal to the maximum value innums2
.
You have to return the smallest number of operations needed to satisfy both conditions or -1
if it's not possible to satisfy them.
Intuition
First, the problem can be approached by considering two cases: swapping or not swapping the values of nums1[n - 1]
and nums2[n - 1]
. For each case, two scenarios can occur for any index i
: either no swap is needed because both elements are already in their correct place according to the maximum value constraint, or a swap is needed to move a larger value to the last index of its respective array.
We can create a helper function f(x, y)
that will count the number of operations (swaps) needed when x
and y
represent the last values of nums1
and nums2
respectively. As we loop through the arrays, if we encounter a pair where neither array can have their last value as the maximum without swapping with the other, we immediately know it is impossible to satisfy the condition, and we can return -1
.
The solution employs a greedy strategy:
- If both values at the current index
i
are less than or equal tox
andy
respectively, no action is needed. - If one value is greater than
x
and can be swapped to be the new last value ofnums1
, and the other is greater thany
and can be swapped to be the new last value ofnums2
, we perform a swap. - If neither of these conditions is satisfied, fulfilling the goal is not possible.
After considering both cases of whether to swap the last elements or not, we'll have two values representing the minimum number of swaps needed for each scenario. If both scenarios return -1
, this means it's impossible to meet the goal for both arrays. Otherwise, we return the smaller number of operations required, bearing in mind that if we did swap the last elements initially, an extra swap (totaling b + 1
) is included in the final count.
Solution Approach
The implementation consists of a helper function f(x, y)
that is responsible for determining the number of swaps required to make x
the last value of nums1
and y
the last value of nums2
. This function iterates through the arrays, excluding their last elements, to check if the current condition meeting criteria is satisfied without swapping or if a swap is needed.
Here are the steps in the algorithm:
- Check each element pair from
nums1
andnums2
(up ton-1
) to see if they already satisfy the condition wherenums1[i] <= x
andnums2[i] <= y
. - If the condition is not satisfied, check if making a swap would satisfy it, which means
nums1[i] <= y
andnums2[i] <= x
after the swap. - If neither the current state nor a swap can satisfy the condition, it means it's impossible to achieve the goal, and
f(x, y)
will return-1
. - If a swap is needed, the count
cnt
is incremented.
Following this, the minOperations()
method calls f(x, y)
twice with different parameters: once where x
and y
are the initial last values of nums1
and nums2
respectively (case 1: no swap for last elements), and then with x
and y
swapped (case 2: with swap for last elements). It stores the results in variables a
and b
.
The final step in the algorithm is to evaluate these two outcomes:
- If both
a
andb
are-1
, it means it's impossible to satisfy the conditions using either case, and the method returns-1
. - If at least one of the cases has a non-
-1
result, the method returns the minimum number of operations needed to satisfy the conditions. Since swapping the last elements counts as an operation, in case 2 (ifb
is not-1
), 1 is added tob
before comparing it toa
.
The implementation makes use of:
- A helper function to encapsulate the logic for checking and counting swaps needed.
- A greedy approach that incrementally solves the problem by deciding the best action (swap or no swap) for each element pair.
- Iterative traversal of both arrays which efficiently enables us to check conditions and count swaps at the same time.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the following arrays:
nums1 = [1,3,5,4]
nums2 = [1,2,3,7]
Both arrays have a length of n = 4
. According to the problem, we want nums1[3]
to be the maximum of nums1
and nums2[3]
to be the maximum of nums2
.
Initially, nums1[3] = 4
, and nums2[3] = 7
. The maximum values of nums1
and nums2
are 5
and 7
, respectively. We need to make 5
the last element of nums1
and keep 7
as the last element of nums2
.
- We start with the helper function
f(x, y)
, withx = 4
andy = 7
, the last elements ofnums1
andnums2
respectively. - Loop through the arrays up to
n-1
(i.e., the third element), checking if a swap is necessary:- Index
0
: Both1
and1
are less than4
and7
. No swap needed. - Index
1
:3
is less than4
, and2
is less than7
. No swap needed. - Index
2
:5
is greater than4
and needs to be the last element ofnums1
, and3
is less than7
, so we can swap5
and4
to satisfy the condition fornums1
. After this swap,nums1
becomes[1,3,4,5]
.
- Index
- Since we were able to make a swap that progresses towards our goal, we increment our count
cnt
by1
. - Now, we call the helper function
f(x, y)
again withx = 7
andy = 4
to see if we should have swapped the last elements initially.- This time, the elements of
nums1
andnums2
at index3
already satisfy the condition. There is no need for any swaps. So in this case, our countcnt
is0
.
- This time, the elements of
Finally, we compare results a
and b
from both cases. Since the result from the second case b
(without any initial swap) is the minimum and is not -1
, we add 1
to b
because of the initial swap we considered. Therefore, b + 1 = 0 + 1 = 1
. However, since we did not need that initial swap, the smallest number of operations needed to satisfy the conditions is actually just b
, which is 0
.
In conclusion, 0
swaps are required to make the last element of each array the maximum value within that respective array. We found that by not performing the swap on the last elements initially, our arrays were already in the desired state. Hence, the smallest number of operations needed is 0
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def min_operations(self, nums1: List[int], nums2: List[int]) -> int:
5 # Define a helper function to calculate the number of operations needed.
6 def calculate_operations(target1: int, target2: int) -> int:
7 operations_count = 0
8 # Iterate through both lists except the last element.
9 for elem1, elem2 in zip(nums1[:-1], nums2[:-1]):
10 # If both elements are less than or equal to their respective targets, no operation is needed.
11 if elem1 <= target1 and elem2 <= target2:
12 continue
13 # If it's impossible to make one less than or equal to the other's target, return -1.
14 if not (elem1 <= target2 and elem2 <= target1):
15 return -1
16 # Otherwise, an operation (swap) is needed.
17 operations_count += 1
18 return operations_count
19
20 # Calculate the operations needed if we consider the last element of nums1 as the target for nums1,
21 # and the last element of nums2 as the target for nums2, and vice-versa.
22 operations_a = calculate_operations(nums1[-1], nums2[-1])
23 operations_b = calculate_operations(nums2[-1], nums1[-1])
24
25 # If both calculations returned -1, there's no solution. Otherwise, take the minimum of the two
26 # In the case where operations_b is not -1, we need to add 1 to it because it symbolizes an extra swap
27 # at the end between the last elements of nums1 and nums2.
28 return -1 if operations_a == operations_b == -1 else min(operations_a, float('inf') if operations_b == -1 else operations_b + 1)
29
30# Example usage:
31# sol = Solution()
32# result = sol.min_operations([1,2,3], [4,5,6])
33# print(result) # Output would depend on the logic provided by the algorithm
34
1class Solution {
2
3 private int length; // Naming 'n' as 'length' for better readability.
4
5 // Method to calculate the minimum operations to make nums1 and nums2 equal.
6 public int minOperations(int[] nums1, int[] nums2) {
7 // Initialize length to be the length of nums1 array (assuming nums1 and nums2 are of same length).
8 length = nums1.length;
9
10 // Calculate the minimum operations required by comparing last elements of both arrays in two ways.
11 int operationsFromNums1 = calculateOperations(nums1, nums2, nums1[length - 1], nums2[length - 1]);
12 int operationsFromNums2 = calculateOperations(nums1, nums2, nums2[length - 1], nums1[length - 1]);
13
14 // If both calculations resulted in -1, return -1, else return the minimum of two calculations.
15 // When comparing operationsFromNums2, we add 1 since we are swapping numbers from the other array.
16 return (operationsFromNums1 == -1 && operationsFromNums2 == -1) ? -1
17 : Math.min(operationsFromNums1, operationsFromNums2 + 1);
18 }
19
20 // Helper method to calculate the operations needed to make each pair of elements in nums1 and nums2 ordered with respect to x and y.
21 private int calculateOperations(int[] nums1, int[] nums2, int x, int y) {
22 int count = 0; // Counter to keep track of the number of operations.
23
24 // Go through each pair of elements up to the second-to-last pair.
25 for (int i = 0; i < length - 1; ++i) {
26 // Continue if both elements are already in the correct order with respect to x and y.
27 if (nums1[i] <= x && nums2[i] <= y) {
28 continue;
29 }
30
31 // If it's not possible to make elements in nums1 and nums2 in order by swapping,
32 // return -1 indicating it's not possible to equalize the arrays.
33 if (!(nums1[i] <= y && nums2[i] <= x)) {
34 return -1;
35 }
36
37 // Otherwise, a swap is required, increment the count of operations.
38 ++count;
39 }
40
41 return count; // Return the total number of operations needed.
42 }
43}
44
1class Solution {
2public:
3 int minOperations(vector<int>& nums1, vector<int>& nums2) {
4 int sizeOfNums = nums1.size(); // Variable name changed from 'n' to 'sizeOfNums' for better readability.
5
6 // Lambda function to calculate the minimum operations required when comparing the elements of nums1 and nums2.
7 auto countMinOperations = [&](int limit1, int limit2) {
8 int count = 0; // Initialize operation counter.
9
10 // Iterate over the elements of the vectors, excluding the last element.
11 for (int i = 0; i < sizeOfNums - 1; ++i) {
12 // If both elements at index i are within the specified limits, no operation is needed.
13 if (nums1[i] <= limit1 && nums2[i] <= limit2) {
14 continue;
15 }
16 // If swapping cannot help to be within limits, operation is not possible.
17 if (!(nums1[i] <= limit2 && nums2[i] <= limit1)) {
18 return -1;
19 }
20 // A swap is counted as an operation.
21 ++count;
22 }
23 return count; // Return the total operations counted.
24 };
25
26 // Use the lambda function to count the operations for the limits determined by the last elements of both vectors.
27 int operationsA = countMinOperations(nums1.back(), nums2.back());
28 int operationsB = countMinOperations(nums2.back(), nums1.back());
29
30 // If both results are -1, return -1 (operation isn't possible). Otherwise, return the minimum of the two, adjusting for the off-by-one.
31 return operationsA + operationsB == -2 ? -1 : min(operationsA, operationsB + 1);
32 }
33};
34
1// Function to find the minimum number of operations to make all elements pair-wise compatible.
2// nums1 and nums2 are arrays we are trying to make compatible through operations.
3function minOperations(nums1: number[], nums2: number[]): number {
4 const arrayLength = nums1.length; // Store the length of the arrays.
5
6 // Helper function to count operations needed to make each pair compatible.
7 // x and y are the target values for nums1 and nums2 to be compatible with.
8 const countOperations = (targetNums1: number, targetNums2: number): number => {
9 let operationCount = 0; // Initialize operation count.
10 for (let i = 0; i < arrayLength - 1; ++i) {
11 // No operation needed if current elements are already less than or equal to targets.
12 if (nums1[i] <= targetNums1 && nums2[i] <= targetNums2) {
13 continue;
14 }
15 // If swapping doesn't make the numbers compatible with the targets, return -1.
16 if (!(nums1[i] <= targetNums2 && nums2[i] <= targetNums1)) {
17 return -1;
18 }
19 operationCount++; // Increment the operation count if we need to swap.
20 }
21 return operationCount; // Return the total number of operations needed.
22 };
23
24 // Call the helper function with the last elements of nums1 and nums2 as targets.
25 const operationsA = countOperations(nums1.at(-1), nums2.at(-1));
26 const operationsB = countOperations(nums2.at(-1), nums1.at(-1));
27
28 // If both cases result in -1, we return -1, meaning it's not possible to make arrays compatible.
29 if (operationsA === -1 && operationsB === -1) {
30 return -1;
31 }
32
33 // If one of the operations counts is -1, return the other one.
34 // Otherwise, return the minimum count of the two operations plus one
35 // (which accounts for the last swap not counted by the helper function).
36 return operationsA === -1 || operationsB === -1 ?
37 Math.max(operationsA, operationsB) :
38 Math.min(operationsA, operationsB + 1);
39}
40
Time and Space Complexity
Time Complexity
The time complexity of the code can be determined by looking at the two main components: the f
function and the calls to this function within minOperations
.
-
Function
f
: This function includes a for-loop that iterates over two arrays (nums1
andnums2
). The loop runs for the length of the arrays minus one (n-1
times) because the[:-1]
slice is used, which excludes the last element of each array. Inside the loop, there is a constant amount of work being done: a series of comparisons and a conditional increment ofcnt
. Therefore, the complexity of thef
function isO(n-1)
which simplifies toO(n)
. -
Calls within
minOperations
: The functionf
is called twice insideminOperations
. Since each call has a time complexity ofO(n)
, and they are not nested, this does not change the overall time complexity of the code, which remainsO(n)
.
Combining the parts, we maintain an overall time complexity of O(n)
for the minOperations
function.
Space Complexity
Analyzing the space complexity, there are no additional data structures that grow with the size of the input being used. The variables cnt
, a
, and b
use a constant amount of space. The slices used in the zip
function in f
do not create new arrays; they just create views of the original arrays, so they don't add to the space complexity.
Therefore, the space complexity is O(1)
, as it does not depend on the size of the input arrays.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!