A harder/interesting version of Leetcode 3576.

Hello! I was solving this Leetcode problem yesterday.

I'll rewrite the problem statement once again for convenience

Problem Statement

Examples

Constraints

I would suggest you to solve (in your head or code) this before going further

My Submission (C++)

constexpr int N = 100000; int temp[N];

class Solution {
public:
    bool canMakeEqual(const std::vector<int>& nums, int k) {
        int n = nums.size();
        auto check = [&](int t) -> bool {
            int ops = 0;
            std::copy(nums.begin(), nums.end(), temp);
            for (int idx = 0; idx + 1 < n; ++idx) {
                if (temp[idx] == -t) {
                    ++ops;
                    temp[idx + 0] *= -1;
                    temp[idx + 1] *= -1;
                }
            }
            return ops <= k && temp[n - 1] == t;
        };
        return check(-1) || check(+1);
    }
};

Now, lets say I have $$$q$$$ Queries of Type:

$$$1$$$ $$$L$$$ $$$R$$$ $$$k$$$ where-
$$$L$$$ and $$$R$$$ represent the left and rite endpoints of a subarray in $$$nums$$$ inclusive.
$$$k$$$ represents the number of operations that can be used to make the entire subarray equal.

For every query, we need to return $$$true$$$ or $$$false$$$ if we are able to make the entire subarray equal.

Here are my observations and approach:

O(n + qlogn) Approach

Every operation results in flipping of two elements.
So if any subarray $$$[L, R]$$$ has
- Odd number of $$$+1/-1$$$, we can never make the entire subarray containing $$$+1/-1$$$ respectively.

It would be possible to convert the entire subarray to $$$-1$$$ or $$$+1$$$ if there are even occurences of it (despite odd occurences of the other value). We just need to check if the number of operations taken is $$$k$$$ or less.

Now, lets consider a subarray $$$[L, R]$$$ containing an even number of $$$-1$$$'s (lets say 4) at indices $$$p, q, r, s$$$, where $$$p \lt q \lt r \lt s$$$.

The greedy strategy for doing this would be to:

Take adjacent pairs $$$(p, q)$$$, $$$(r, s)$$$
For pair $$$(p, q)$$$
- We would perform the operation on indices $$$[p, p + 1, p + 2, ..., q - 1]$$$. $$$(q - p)$$$ Operations.
For pair $$$(r, s)$$$
- We would perform the operation on indices $$$[r, r + 1, r + 2, ..., s - 1]$$$. $$$(s - r)$$$ Operations.

Now we just need to check if $$$(s - r) + (q - p) ≤ k$$$.

How do I solve this?

Store a prefix sum for $$$+1$$$ and $$$-1$$$ occurences individually, this would help us find out their frequency in a range in $$$O(1)$$$ time. $$$O(n)$$$ processing though.
Have two different std::vector<int>, storing the indices of $$$+1$$$ and $$$-1$$$ occurences. Can be done in $$$O(n)$$$ aswell.
Have a $$$dp[n][2]$$$ for both of the std::vector's.

$$$dp[i][0]$$$: total cost of operations involving indices $$$i, i + 1, ..., n - 1$$$, without considering the pair $$$(i, i + 1)$$$.
$$$dp[i][1]$$$: total cost of operations involving indices $$$i, i + 1, ..., n - 1$$$, considering the pair $$$(i, i + 1)$$$.

$$$dp[i][0]$$$ is nothing but $$$dp[i + 1][1]$$$.
$$$dp[i][1] = v[i + 1] - v[i] + dp[i + 1][0]$$$.

Base Cases:
$$$dp[n - 1][0] = 0. dp[n - 1][1] = 0;$$$
$$$dp[n - 2][0] = 0. dp[n - 2][1] = v[n - 1] - v[n - 2].$$$

Computing this also takes $$$O(n)$$$.

For a query,

$$$O(1)$$$: Find the number of $$$+1$$$'s or $$$-1$$$'s in $$$[L, R]$$$.
$$$O(logn)$$$: In case either of them have an even count, find the left and ritemost indices using binary search over the vectors.
$$$O(1)$$$: prefix sum on respective $$$dp$$$ using the positions of the bounded values found in step above.

Overall compleixity is $$$O(n + qlogn)$$$.

Not completely positive of my approach so would like to hear any corrections, improvements or suggestions.

So far, we've only seen static/immutable arrays. Lets say I also have a query of Type 2, where

$$$2$$$ $$$p$$$ : nums[p] *= -1. (flipping the value at index $$$p$$$).

In this case, how do i device an efficient solution when considering queries of both types? Any Ideas?

Комментарии (6)

Написать комментарий?

happywobbuffet

10 месяцев назад, скрыть # |

Auto comment: topic has been updated by happywobbuffet (previous revision, new revision, compare).

→ Ответить

wddd

← Rev. 2 →

Some observations:

We should handle the two cases ($$$1$$$ and $$$-1$$$) separately.
For one case, we only care the indices of the numbers. For example, if the index array of all $$$1$$$ is $$$[1, 2, 3, 5]$$$, then the total number of operations to turn them to $$$-1$$$ would be $$$3 = - 1 + 2 - 3 + 5$$$. Apparently this is an alternating sum on the index array.
Then with preprocessing of all indices of $$$1$$$ and $$$-1$$$, we can answer each type 1 query in $$$O(1)$$$.
For type 2 query, we are basically inserting/deleting numbers to/from the index array, and the sign of all subsequent numbers in the index array will change for the alternating sum. Naively, this results in $$$O(n)$$$ complexity to process each query. Deepseek suggests we can use SegmentTree or Balanced Binary Search Tree to optimize it and achieve $$$O(logn)$$$ complexity.

10 месяцев назад, скрыть # ^ |

Pretty cool observation!. I just overcomplicated it.

Newtech66

You can view this problem as an instance of Gaussian elimination over $$$GF(2)$$$ (in other words, XOR). First of all, change $$$1 \rightarrow 1$$$ and $$$-1 \rightarrow 0$$$. Now you have a binary string.

For example, let's say initially you have the string $$$abcd$$$. Denote an operation at the $$$i$$$-th index as $$$p_i$$$. Note that operating on an index twice does nothing. So in essence, we have the following equations if we want to make everything equal to $$$0$$$:

$$$ \begin{align*} a + p_0 &\equiv 0 \pmod{2} \\ b + p_0 + p_1 &\equiv 0 \pmod{2} \\ c + p_1 + p_2 &\equiv 0 \pmod{2} \\ d + p_2 &\equiv 0 \pmod{2} \end{align*} $$$

We can further write

$$$ \begin{align*} p_0 &\equiv a \pmod{2} \\ p_0 + p_1 &\equiv b \pmod{2} \\ p_1 + p_2 &\equiv c \pmod{2} \\ p_2 &\equiv d \pmod{2} \end{align*} $$$

Now we can eliminate to get

$$$ \begin{align*} p_0 &\equiv a \pmod{2} \\ p_1 &\equiv a + b \pmod{2} \\ p_2 &\equiv a + b + c \pmod{2} \\ 0 &\equiv a + b + c + d \pmod{2} \end{align*} $$$

This means that, we need to take the prefix XOR, check that the XOR of the whole array is $$$0$$$, and then count the number of $$$1$$$-s in the prefix XOR array and check if it is $$$\leq k$$$.

This isn't the only possibility of course, you can also make everything equal to $$$1$$$. To handle that, you can just flip every bit and run the same procedure. So we'll not talk about this case, but remember to handle it (just make another array and run the procedure on both arrays and check if either one works).

So now you have an $$$O(n + q)$$$ solution to your first variant: You know how to count the number of $$$1$$$-s in the prefix XOR of a subarray $$$[L, R]$$$: maintain a prefix sum of how many $$$1$$$-s are there in the prefix XOR array, and if $$$\text{prefix_XOR}[L-1]$$$ is $$$1$$$, you have $$$R-L+1-\text{count}_1(L, R)$$$ number of $$$1$$$-s (you get the idea). Also remember to check the whole subarray XOR is $$$0$$$.

To solve your variant with type $$$2$$$ updates, I think you can see we need a Fenwick tree now.

very nice approach. took me a while to understand it!

Accepted LC Submission Code (C++)

constexpr int N = 100000; int temp[N], pXor[N], pOne[N];

class Solution {
public:
    bool canMakeEqual(std::vector<int>& nums, int k) {
        int n = nums.size();

        for (int &i: nums) i = (i < 0) ? 0 : 1;

        auto transform = [&](auto &nums, int val) -> void {
            for (int i = 0; i < n; ++i) temp[i] = val ? nums[i] ^ 1 : nums[i];
        };

        auto computexor = [&]() -> void {
            std::partial_sum(temp, temp + n, pXor, [](int a, int b) { return a ^ b; });
        };

        auto computeone = [&]() -> void {
            std::partial_sum(pXor, pXor + n, pOne, [](int a, int b) { return a + b; });
        };

        for (const int val: {0, 1}) {
            transform(nums, val);
            computexor();
            computeone();

            if (pXor[n - 1] == 0) {
                int flips = (n >= 2) ? pOne[n - 2] : 0;
                if (flips <= k) return 1;
            }
        }
        
        return 0;
    }
};

I'm still very new to the realm of Fenwick/Segment Tree like Data Structures, could you help with some hints?

Well, a Fenwick tree can maintain and get prefix sums and prefix XORs across updates. That's all you require right? You can look up how to implement a Fenwick tree here.

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Блог пользователя happywobbuffet