leetcode 1674 | Minimum Moves to Make Array Complementary | Leetcode POTD | Prefix sum | DSA

Añadido: 2026-05-14

[00:00:00]Hello and good morning to everyone. So, today's lead code question is 1674, which is minimum moves to make array complementary. So, basically in this question we are given an integer array nums whose length is n and we are also given an integer limit, right? And in one move, we can replace any integer from nums with another integer between one and limit. And limit is included, right?

[00:00:24]And it is given that array nums is complementary if all indices if all indices i, this sum nums of i plus nums of n minus i minus 1 equals the same number. That means suppose we are given this array 1 2 3 4.

[00:00:41]If we take c, 1 plus 4, 1 plus 4 is the sum is 5.

[00:00:46]2 plus 3, 2 plus 3 again the sum is 5.

[00:00:49]So, for every pair, every pair where nums of i plus nums of n minus i minus 1, the sum of these should be equal for all the pairs. Then the array will be said as complementary, right?

[00:01:05]So, what we have to do is we have to return the minimum number of moves that we require that we require to make our nums as complementary, right? So, let's move to examples.

[00:01:16]So, let's see the first example. In the first example, we are given the array 1 2 4 3 and our limit is 4. That means we can replace any number from 1 to 4, 1 to 4.

[00:01:29]So, see, 3 plus 1, 4.

[00:01:32]And 4 plus 2, the sum is 6. The sum is 6. So, suppose if we replace if we replace >> [clears throat] >> this number, this number 1 with 3, 1 with 3.

[00:01:46]Then 3 plus 3, our sum will be 6. And this sum is also 6. So, to how many moves that we have used to make our array complimentary. So, we just have replaced one number one number. So, the number of moves is one. So, that is our answer.

[00:02:04]So, let's move to the example number two. So, in example number two, we are given this array 1 2 1 2. So, sum of these uh first and last pair is three and second and second uh this is three.

[00:02:15]So, the array is already complimentary.

[00:02:17]So, no need to make any changes or any moves. So, the number of moves that we have done is zero.

[00:02:24]So, let's move to the constraint part.

[00:02:27]So, n which is our nums.length.

[00:02:31]So, n can be up to 10 ^ 5. So, either big O of n solution or n log n solution, right? n squared will give us time limit exceed, right?

[00:02:45]And each element in the nums array and limit can also be up to 10 ^ 5, right?

[00:02:51]Limit can also be up to 10 ^ 5 and it is also given that n, which is the length, is even.

[00:02:59]So, let's move to the approach part.

[00:03:02]So, basically what we have to do is for every pair that is nums of i plus nums of n minus i minus 1, this should be equal to a target value. This should be equal to a target value.

[00:03:14]Now, as we know as we know, we can replace a number from 1 to limit, right? 1 to limit. So, target value target value range can be from 2 to 2 into limit. Suppose we have a pair a, b.

[00:03:32]So, if we replace both a and b with 1 1 with 1 1, then we get we get the sum as two. So, that's the minimum sum, right? Or if we replace both a and b with limit with limit, then our sum will be 2 into limit. So, that's the range that's the range of the sum or we can say that's the range for the target, right? So, our target range target range is from two to two into limit two into limit, right?

[00:04:05]So, if we have to find So, if we take every value as target. If we take every value as target from this range and then then we check the number of moves the number of moves or changes that we have to do done and then take the one with the minimum changes.

[00:04:25]Take the answer with minimum changes.

[00:04:28]So, but the time complexity here is So, how many values we have for target? So, for target we have two into limit values two into limit values. And for checking and for finding the number of changes and for finding the number of changes we take big of n time. So, the total time complexity here is two into limit into n. And as we know, n is lesser than equal to 10 ^ 5. Even limit is lesser than equal to 10 ^ 5. So, in worst case in worst case it will be 10 ^ 10, which is too much and which will give us time limit exceed. So, we can't follow this method. We can't follow this method. So, basically we need a more efficient way.

[00:05:11]We need a more efficient way to calculate to calculate how many moves we require how many moves we require for each target sum.

[00:05:21]Right? Earlier what we were doing is we were taking We were taking a target and then we were finding We were find We were finding moves for that target, right? And but that will take that will take n into limit time n into limit time. So, we have to somehow optimize it, right? So, let's see how we can optimize it. So, first suppose we have a pair a, b where a is nums of i and b is nums of n - i - 1, right? And let's assume a is lesser than or equal to b. Then the sum sum is a + b.

[00:06:00]Now, there are three possibilities for any target. There are three possibilities for any target. So, first possibility is that we need zero moves. That we need zero moves to reach that target. So, if you have 5, 2 then what is the target that we can achieve in zero move? So, basically seven is a target that we can achieve in zero moves because because that is a direct sum without changing without changing any number, we are getting seven. So, seven is the target. Seven is a target basically a + b. That is the sum of the two numbers. So, seven does not require any change.

[00:06:45]Right? So, we can easily reach the target seven, right? So, a + b needs zero moves. So, this is case one. This is case one. So, let's see the case two.

[00:06:56]Case two is we require one move. We require one move to reach the target.

[00:07:02]So, in one move we can either we can either change a or we can either change b, right? Either a or b.

[00:07:10]Right?

[00:07:12]And we can change a or b to any value any value from one to limit, right? We can change from any value one to limit.

[00:07:21]So, if we change only one element and then the achievable targets are So, suppose we change a first. We change a first, then the range for a will be a minimum a can be one, then b will be same. And maximum value for a can be limit.

[00:07:40]So, these are the range.

[00:07:41]These are the range of the sum that we get when we change A. And when we change B, then we get 1 + A because minimum value for B can be 1 and maximum value for B can be limit + A. Right? So, these are the range of the sums that we get when we change A and B. Now, if you combine both, if you combine both the ranges, then from here see one and one is common.

[00:08:08]Now, we have to minimize the left part.

[00:08:11]So, what we have to do? We have to take the minimum of these two. We have to take minimum of A and B. So, we take minimum of A {comma} B for the left range.

[00:08:20]In the right range, we have limit as common. In the right range, we have limit as common.

[00:08:25]And now, for the right range, we have to maximize this range. We have to maximize the right right range. So, we take maximum of A {comma} B.

[00:08:34]Maximum of A {comma} B. So, this is the range. This is the range of the sum.

[00:08:39]This is the range of the sum that for that we require only one move.

[00:08:44]That is we need to change either A or B.

[00:08:47]Right?

[00:08:50]Now, so all the targets, all the targets which are present in this range requires only one move. Now, the case third. So, we have seen zero move case.

[00:09:01]We have seen one move case.

[00:09:04]Now, all the sums, all the sums that are left, means all the remaining target sums will always require two move.

[00:09:11]Right? So, we have to change both the elements to achieve both the elements to achieve the rest of the target sums.

[00:09:18]Right? So, that's is case three. Now, what we do is for every pair, for every pair, we assume that all the sum, all the target sum initially require two moves. Right?

[00:09:30]So, for every target sum, every target sum in the range two to two into limit, two into limit, we assume they all require two moves initially for a pair.

[00:09:42]Then what we do is then we find then we find the range range for one move then we find the range for one move. So, all the elements or all the target sum that are present in this range they'll require only more one move. So, we subtract we subtract minus one we subtract minus one from them because initially we have assumed that they all require two moves. They all require two moves. So, we subtract one from them, right? And then the third case, the exact sum the exact sum that also that also do not require any move. So, that requires zero moves. So, again we subtract minus one for that also, right?

[00:10:23]And what we And to handle to handle these range updates update what we do is we use a difference array.

[00:10:31]We use a difference array. And then once we have calculated the whole difference array, then we use prefix sum to find to find the to find the number of moves for each target sum, right?

[00:10:44]So, to update the ranges efficiently we have used difference array.

[00:10:49]So, we maintain a difference array named as diff, right? And when we apply prefix sum when we apply prefix sum on this it will give us a total moves that we need for every target sum, right?

[00:11:05]So, let's see. So, initially initially all target needs two moves. All target need two moves. And our target range is from two into two two to two into limit, right? So, what we do is we will we will add we will plus two here and then we subtract minus two minus two in the next element that is two into limit plus one, right? So, when we prefix sum when we prefix sum, this two this two will be added to all the numbers in this range, right? To all the numbers in this range.

[00:11:42]Then then we handle the one move range.

[00:11:45]That is those sums those target sums that require one move. So, the range is left is minimum of a {comma} b plus one and the right is maximum of a {comma} b plus limit. So, now for minimum for the left range for the left range, we have as you So, we have assumed that these require two moves, but but these sums these sums require only one move. These sums require only one move, so we reduce the cost by one. We reduce the cost by one, so we we put minus one we put minus one at left range. We put minus one at left range and at right plus one range at right plus one range, we again add one.

[00:12:28]Right? So, when we do prefix sum when we do prefix sum, all the elements all the elements in the range l to r they will be reduced by minus one. They will be reduced by minus one, right?

[00:12:42]Then the third case, the exact sum case.

[00:12:45]That is the sum is equal to a plus b.

[00:12:48]So, for the this point for this point a plus b, we have to reduce we have to reduce the diff diff by again minus one, right? And then s plus one the next element will be added to plus one, right? So, for this point that is a plus b, we again reduce the cost by one. And then what we do is then we take the prefix sum. Then we take the prefix sum over our difference array. And then this will give us the total moves. This will give us the total moves required for every target sum. So, what we do is we'll take the that we'll take the minimum moves. We'll take the minimum move as our answer. So, let's try to understand with the help of an example.

[00:13:34]We have taken the array 2 1 4 and 5. So, this is our array and our limit and our limit is 6, right? So, first pair first pair is 2 {comma} 5. So, we have taken the first pair 2 {comma} 5 and limit is 6.

[00:13:49]So, first we see the case zero moves.

[00:13:53]So, if zero moves means target is is the sum that is 2 {comma} 5. The sum of 2 {comma} 5 is 7. So, 7 needs 7 do not need to change any elements. So, for target sum 7, we do not need to change any element. So, so target is equal to 7 requires zero moves. Then for one move case, for one move case, our range will be 1 plus minimum of A {comma} B and limit plus maximum of A {comma} B. So, 1 plus minimum of 2 {comma} 5 is 2.

[00:14:22]And limit limit is 6 plus maximum of 2 {comma} 5 is 5. So, the range So, the range from 3 to 11 range from 3 to 11.

[00:14:30]So, these target sum require only one move, right? Require only one move.

[00:14:36]Right?

[00:14:37]And the rest of the targets the rest of the targets in the range 2 2 2 2 into limit that is 2 into 2 12 requires two moves.

[00:14:46]So, let's see how will how will handle these ranges using a difference array.

[00:14:51]So, initially we assume all the all the target sums from 2 2 2 12 2 2 12 will require two uh require two changes. So, what we have done is we have put plus two plus two here and minus two at 13 because all the sums from 2 to 12 2 to 12 require two moves two moves, right?

[00:15:16]And then what we have done is then one move range the one move range was from 3 to 11 from 3 to 11. So, we do minus one here.

[00:15:25]And so from 3 to 11. So, 11 is up to here. So, minus one will be up to here. Then, we again have to plus one here because the minus one will be up to 11 only, right? Up to 11 only minus one should be affected. And then, the third one is zero move. So, the zero move element is 2 + 5, that is seven.

[00:15:49]So, at seven we have to again reduce the cost by minus one. And for only seven we have to reduce the cost.

[00:15:55]So, we again have to put plus one at eight, right?

[00:15:59]We have to put plus one at eight.

[00:16:02]So, see. This is our array. This is our array after processing the first pair.

[00:16:07]Now, our next pair is 1 {comma} 4. 1 {comma} 4. So, again all the sum needs two moves. So, we again put plus two at two. So, it will become plus four. And we again put minus two at two into limit plus one. So, it will become minus one. Then, our one move range. Our one move range is one plus minimum of 1 {comma} 4. Minimum 1 {comma} 4 is one. And then, limit plus maximum is four four. So, our limit is two to 10. Two to 10. So, what we do is we minus one at two. We minus one at two. We have put minus one. We have put minus one at two. And we again put 11.

[00:16:47]We put plus one at 11. Plus one at 11 because our range is minus one will be from two to 10 only. So, we again have to put plus one to the next of the elements.

[00:16:59]Right?

[00:17:00]Then, so it will become see here 4 minus one will become three minus one. So, this will be after processing one move. Now, zero move case. That is 1 + 4. 1 + 4 is five. So, at five at five we have to put minus one. So, 2 3 four, five. At five, you have to put minus one and again plus one at six.

[00:17:21]Right? Again plus one at six. So, our array our array difference array will look like this after processing after processing both the pairs.

[00:17:34]So, now the next thing is we apply prefix sum. We apply prefix sum on this difference array. So, we get three here, then three minus one, two here, then again here not two, then two minus one, one here, then one plus one, two here, two minus one, one here, one plus one, two here, then again two, again two, two plus one, three here, three plus one, four here.

[00:17:58]So, this way this way we get we get our our moves for each target. So, for target two, we require three moves. For target three, four, five, six, seven, eight, nine, 10, 11, 12. So, for each target, we we get the number of moves that we need.

[00:18:20]So, the minimum number of moves is one, which is for five and seven. So, for five and seven, we get the minimum number of moves, which is one. So, our answer is one.

[00:18:30]Right? So, let's see.

[00:18:32]Uh initially, our array was 2 1 4 5. And we are getting minimum move for one at target is equal to five. At target is equal to five and seven. So, we see for five. So, we get the first pair 2 {comma} 5. So, if you change five to three, if you change five to three, that means one move, we get our target sum as three as five, sorry. 2 plus 3 is five.

[00:18:55]Then one plus four, same target is five, so no change. So, we see only one move.

[00:19:01]And that is what we get. That is what we get after taking the prefix sum. After taking the prefix sum over the difference array.

[00:19:08]So, let's move to the code part. So, in the code part, we have taken the size of the array and then we have taken a difference array whose size is So, difference array is from two to two into limit. So, size is two into limit plus two we have taken, right? And then we have iterated over all the pairs over all the pairs. So, we have taken from I two zero to N by two because zero then the last element will be occupied with itself only. Then we have taken both the numbers A and B and then we have find the uh range. We have find the range for for one move. That is one plus minimum of A comma B and limit plus maximum of A comma B.

[00:19:51]And then we have find the sum. And now initially we assume that all sum needs two moves. So, our range will be from two into two two to two into limit. So, this range this range will need plus two. Then we added we added two here and then we subtracted two from here so that the rest of the elements rest of the elements won't be added two, right?

[00:20:16]Then one more range. So, one more for one more range we have find the range range is from low to high. So, we subtract minus one at low and then added added again one at high plus one, right?

[00:20:29]And then the third thing is exact zero move. That is for the sum which is A plus B. So, for sum we added we subtracted minus one and then we again added plus one at sum plus one, right?

[00:20:42]So, here up to here our difference array will be formed. Now, after forming the difference array, we have to find the minimum moves. We have to find the minimum moves.

[00:20:54]Right? So, what we do is we find the prefix sum. We take the prefix sum from two to two into limit two to two into limit and then moves moves is equal to we add the previous value. Moves plus equal to difference of target. Difference of target and then we take the minimum answer. We take the minimum minimum of the moves and then store that in the answer and then we return the answer.

[00:21:21]So, I hope I'm able to explain you the solution properly. So, if you like the video, please make sure to like, share, and subscribe the channel. Thank you.