Leetcode 1674 - Minimum Moves to Make Array Complementary

Subscribe Send me a message home page


Problem Description

Link: Leetcode 1674

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.

analysis.png

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 -----

Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png


Comments