Minimum Moves to Make Array Complementary | LeetCode 1674 - Python

Añadido: 2026-05-20

[00:00:00]Hello everyone. I'm Paul and this is problem 1,674.

[00:00:04]Minimum moves to make array complementary. This is a medium problem that might be very tricky. So, next I will show you how to solve it step by step. We are given an integer array nums of even length and an integer limit. So, let's say that we're given this input and we have to return the minimum number of moves to make nums complementary.

[00:00:26]Here is the requirement for a complementary array. For all indices, nums at the current index plus nums at the opposite index equals the same number. For example, in this array, if we do 1 + 4, we get 5 and 2 + 3 is also 5. Even that in both cases we get 5, this is a complementary array. So, we need to get the minimum number of moves to make nums complementary.

[00:00:54]Here, if we do 1 + 3, the result is 4. 2 + 4 is 6. These two numbers are different, so we need to use one or more moves. Here, we can replace this four with a two because two is in between one and the limit. Here, the limit is four.

[00:01:12]Which means that now we can do 1 + 3.

[00:01:15]This is 4 and 2 + 2 is 4 also. Now, these two numbers are equal and the minimum number of moves that we need to use in order to reach this is one. So, the result here is one.

[00:01:30]The main observation to solve this problem is here. What if we take this pair, 1 3? Let's say that we use zero operations. The total sum that we can get in this scenario is 1 + 3, which is 4. So, now we are here in this scenario.

[00:01:45]We take left plus right. We don't change anything. Here, we use zero moves. As you can see, here m is equal to zero.

[00:01:55]Now, what's the minimum possible number that we can get? Well, we can replace this with the minimum possible number, so this stays at one. We replace this with one, and we do 1 + 1, this is equal to two. Now, we are in this scenario. In order to do this, we need to use two operations. So, here we use two operations in this scenario.

[00:02:18]Now, what's the maximum possible number that we can get? Well, we can replace this number with the limit, this is four. We do the same with this number, and 4 + 4 is equal to eight. This is the same as limit * 2, so now we are in this scenario, and we need two operations to reach this. So, here the number of moves is two.

[00:02:41]Now, what if we want to use only one move? What's the minimum possible sum that we can get? Well, we can replace the maximum number between one and three with the minimum possible number, which is one, so now we are using only one operation, and we do 1 + 1, which is equal to two. Now, we are in this scenario. We are taking the minimum number between one and three plus one because of this operation. Now, we are here, and in this scenario, we use one move.

[00:03:11]Now, what if we use one operation, but we want to get the maximum possible sum?

[00:03:16]Well, we can do something very similar.

[00:03:18]We take the maximum number between one and three, which is three, plus the limit, which means that we replace this number with the limit four.

[00:03:28]4 + 3 is seven. So, now we are here. We take the maximum between left and right plus the limit, and here we are using one operation.

[00:03:39]And as you can see here, we have ranges.

[00:03:41]This means that anything that goes in between two and the minimum between left and right plus one requires two moves.

[00:03:49]Anything that goes in between the minimum between left and right plus one and left and right requires one move and so on. These are the four possible ranges. So, we know that the target to get the minimum number of moves in order to make this array complementary is somewhere in this line. So, we can perform this into an array and fill the corresponding moves at each index.

[00:04:17]For example, let's say that we take the same here one three. What if the current target is something in between two and four? Let's say that it's three. We know that this requires only one move and this makes sense because we can replace this three with a two. Now we are changing only one element and we do one plus two. This is equal to three. So, we require only one move. And let's say that we pick something in between four and seven. Let's say that we pick six for example. Well, we can change only one element. We can replace this with three and now we do three plus three.

[00:04:54]This is equal to six. Finally, let's say that we pick something that's on the edge. Let's say that we pick seven. We can do three plus four. Now we are changing only one element and four plus three is equal to seven and we require only one move to do this.

[00:05:11]So, now we know how this array works, but the question is how can we build it?

[00:05:16]And for this you should be familiar with something called difference array. So, let's see how this works. Let's say that we have this array and we are trying to add a one to everything in this range and everything in this range. As you can see here, we have overlapping ranges.

[00:05:34]The result should be 0 1 1 2 1. Now the question is how can we get this?

[00:05:42]Well, for this we can build a difference array where every value is zero initially. And now we can go through these indices from left to right. First, we are here and this is not the starting point of a range. So, the effect at this point is zero. We can just continue with the next index. Next, we are here and this is a starting point of this range, which means that from here to the right, we need to add one to every index. So, we can store this starting point of the effect here in the difference array. We can add one.

[00:06:15]Next, we are here and this is not the starting point of any effect. As you can see, this index is in between left and right bounds of this range. So, we can just continue with the next index and keep zero. Next, we are here and from here to the right, we start the effect of this range. And how do we start this effect? Well, we can add one here in the difference array.

[00:06:40]Next, we continue and we know that from here to the right, we need to remove the effect of this range. So, if here we start the effect with one, how do we remove it? Well, we can subtract one, so this is now minus one. Now, with this difference array, we can build a prefix sum array. And remember how we do this.

[00:07:03]We are storing the accumulated sum at every index. First, we are here, the sum is zero. Next, we are here, so we do 1 + 0. Next here, 0 + 1 is 1. Here, 1 + 1 is 2. And here, 2 + -1 is 1.

[00:07:21]Now, this is the final array. For example, if we look at the index zero, the result is zero. For indices 1 and 2, the results are 1 and 1. Here, we have overlapping ranges and remember that we need to add one to this index for every range. So, the result is two.

[00:07:38]Next here, the result is one. We have only one range.

[00:07:42]So, this is it and by doing this, we are solving the problem in big O of n time complexity. So, even with overlapping ranges, this is very efficient. Now, going back to the problem, we can have a difference array corresponding to this line and now we can iterate pair by pair. We start with one free. And let's say that we start with two moves. We start by replacing these two numbers with one and one. What are the corresponding effects at each point in the line? Well, if we start from two moves, we know that at the minimum between left and right plus one, meaning at two, meaning here, we need to remove the effect of one of the moves. So, here we subtract one.

[00:08:29]Next, here at left plus right, meaning index four, we need to subtract the effect of another move. So, we go to index four and replace this with minus one.

[00:08:41]Now, what happens here at left plus right plus one? Well, now we are in this range. We are using one move. So, we should add this move. We go to index five now, here, and add one move.

[00:08:57]And what happens here at the maximum between left and right plus the limit plus one? Well, now we are at index eight and from here to the right, we need to add the effect of a new move.

[00:09:10]So, we replace this with one. Now, we are looking at this pair, two and four, and we do the same. We start from two moves. And what are the corresponding effects at each point? Well, here, we are in this range. We are using only one move. So, we should subtract one move.

[00:09:29]We go to the minimum between left and right plus one, meaning three. We go here and replace this with minus one.

[00:09:37]Next here at six, we should subtract the effect of another move. So, we go here and subtract one.

[00:09:45]Next at left plus right plus one from here to the right, we need to add the effect of a new move. So, we go to seven and add one. And finally here, meaning nine, we need to add the effect of a new move. So, here we add one. Now, we can continue with either a prefix sum array or a variable current. In the code, we'll use current for simplicity, but here I will show you the prefix sum approach with an array because of learning purposes. So, we start from the maximum possible number of moves, which means we replace every number here. So, we need four moves as a maximum n moves.

[00:10:29]Here, n is four, so we start with four.

[00:10:32]And now we build a prefix sum array as usual. We do 4 + 0, then 4 + -1, 3 + -1, 2 + -1, 1 + 1, 2 + -1, 1 + 1, 2 + 1, and 3 + 1.

[00:10:52]So, now where do we have the minimum number of moves to make nums complementary? Well, we have them either here or here. The result is the minimum number in this array, which is one. And just to be clear, this means that we can pick either four or six as targets. If we pick four, we can replace this with two, and now we do 1 + 3, which is equal to four. 2 + 2 + 2 is equal to four, also. And if we pick six, we replace this with three, and we can do 3 + 3, which is equal to six, and 2 + 4 is also equal to six. So, these are the two valid scenarios. This is the final result.

[00:11:35]Overall time complexity here is big O of N plus L. Why? Well, because we are going through N divided by two pairs, so we can say that this is overall N. And then this array these two arrays have a size of roughly two times limit. So, we can say that this is overall L. Overall time complexity is N plus L. And overall space complexity is big O of L because of this difference array. So, with this in mind, now let's go with the code.

[00:12:07]First, N is the length of nums and we need a difference array. This is an array with zero times and here we take two times limit plus two.

[00:12:19]Now, we can say for every index in range and we are going through every pair, so we can take N divided by two. Here we need to round down this number.

[00:12:29]Every time we have a left and right.

[00:12:31]Left is equal to nums I and right is the number at the opposite index. So, right is equal to nums at N minus one minus I.

[00:12:43]Now, we can set the corresponding effects. So, difference at and here we take the minimum between left and right plus one. Here we need to subtract one move. Then we go to difference at left plus right and subtract another move.

[00:13:01]Then we go to difference at left plus right plus one. And here we add one move. And finally, we go to difference at the maximum between left and right plus the limit plus one. And here we need to add one move. So, these are the four effects. Now, with this we can build our result. We can say that result and current are initially in n and we start from the maximum possible number of moves. And now we say for I in range and we go from two to two times limit plus one.

[00:13:42]Every time we add to current, this is our prefix sum basically. We add difference I. And every time the result is the minimum between what we already have in the result and current. And finally we can return result.

[00:14:00]So, this is the entire code. Let's submit this and see if it works.

[00:14:05]Here we have an extra F. So, let's remove this and try again. As you can see this works and it's very efficient.

[00:14:11]So, if you found this useful, please drop a like, subscribe, and see you in the next one. Bye-bye.