# Leetcode 1674 - Minimum Moves to Make Array Complementary

#### Problem Description

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

Return the minimum number of moves required to make nums complementary.

Example 1:

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.


Example 2:

Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.


Example 3:

Input: nums = [1,2,1,2], limit = 2
Output: 0
Explanation: nums is already complementary.


#### Solution

Let's call the sum of any pair (A[i], A[A.size() - 1 - i]) the target value. Given a pair (a, b) with $$\leq$$ b, if the target value is a + b, then we don't need to modify this pair and it contributes zero to the final cost. It's obvious that the maximum contribution of a pair is two. So we just need to figure out when the cost is one. We observe that with one change the lower bound of a + b is a + 1 and upper bound of a + b is b + limit. Therefore is $$a + 1 \leq \textrm{target} \leq b + limit$$, then the cost contribution of the pair (a, b) is one.

Now we can see that three values are important: (1) a + 1 (2) a + b and (3) limit + b. For this problem, we can view them as a segment with three points. We will call them left point, middle point and right point.

We will use the first example in the problem description to explain the solution.

#### Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Point {
public:
int coordinate;
int typeId;

Point(int coordinate, int typeId): coordinate(coordinate), typeId(typeId) {}
};

class Solution {

public:
vector<Point> points;

int minMoves(vector<int>& nums, int limit) {

if (nums.empty()) {
return 0;
}

this->constructSegmentsAndPoints(nums, limit);

int cost = static_cast<int>(nums.size());
int result = cost;

size_t k = 0;

while ( k < this->points.size() ) {
size_t k_copied = k;

int compensate = 0;

// k will always increase by at least 1 in the inner while block
while (k < this->points.size() && this->points.at(k).coordinate == this->points.at(k_copied).coordinate) {
const auto& p = this->points.at(k);

if (p.typeId == 0) {
--cost;
} else if (p.typeId == 1) {
--cost;
++compensate;
} else {
++compensate;
}
++k;
}

result = min(result, cost);
cost += compensate;
}

return result;
}

void constructSegmentsAndPoints(const vector<int>& nums, int limit) {
for (size_t i = 0; i < nums.size() / 2; ++i) {
int a = min(nums[i], nums[nums.size() - 1 - i]);
int b = max(nums[i], nums[nums.size() - 1 - i]);

this->points.emplace_back(a + b, 1);
this->points.emplace_back(a + 1, 0);

if (a != limit) {
this->points.emplace_back(b + limit, 2);
}
}

sort(this->points.begin(), this->points.end(), [](const Point& p1, const Point& p2) { return p1.coordinate < p2.coordinate; });
}
};


----- END -----

Welcome to join reddit self-learning community.

Want some fun stuff?