Hello!↵
I was solving this [Leetcode](https://leetcode.com/problems/transform-array-to-all-equal-elements/description/) problem yesterday. ↵
↵
I'll rewrite the problem statement once again for convenience↵
↵
<spoiler summary="Problem Statement">↵
You are given an integer array $nums$ of size $n$ containing only $+1$ and $-1$, and an integer $k$.↵
↵
You can perform the following operation at most $k$ times: <br>↵
$·$ Choose an index $i$ $(0 ≤ i < n - 1)$, and multiply both $nums[i]$ and $nums[i + 1]$ by $-1$.↵
↵
Note that you can choose the same index $i$ more than once in different operations.↵
↵
Return $true$ if it is possible to make all elements of the array equal after at most $k$ operations, and $false$ otherwise.↵
</spoiler>↵
↵
<spoiler summary="Examples">↵
Input: $nums = [1,-1,1,-1,1], k = 3$↵
↵
Output: $true$↵
↵
Explanation:↵
↵
We can make all elements in the array equal in $2$ operations as follows: <br>↵
$·$ Choose index $i = 1$, and multiply both $nums[1]$ and $nums[2]$ by $-1$. Now $nums = [1,1,-1,-1,1]$. <br>↵
$·$ Choose index $i = 2$, and multiply both $nums[2]$ and $nums[3]$ by $-1$. Now $nums = [1,1,1,1,1]$.↵
</spoiler>↵
↵
<spoiler summary="Constraints">↵
$·$ $1 ≤ n ≤ 10^{5}$ <br>↵
$·$ $nums[i]$ is either $-1$ or $+1$. <br>↵
$·$ $1 ≤ k ≤ n$↵
</spoiler>↵
↵
I would suggest you to solve (in your head or code) this before going further↵
↵
<spoiler summary="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);↵
}↵
};↵
~~~~~↵
</spoiler>↵
↵
Now, lets say I have $q$ Queries of Type:↵
↵
- $1$ $L$ $R$ $k$ where- <br>↵
- $L$ and $R$ represent the left and rite endpoints of a subarray in $nums$ inclusive. <br>↵
- $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:↵
↵
<spoiler summary="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 < q < r < s$.↵
↵
The greedy strategy for doing this would be to: <br>↵
↵
- 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)$. <br>↵
$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]$. <br>↵
$dp[i][1] = v[i + 1] - v[i] + dp[i + 1][0]$. ↵
↵
Base Cases: <br>↵
$dp[n - 1][0] = 0. dp[n - 1][1] = 0;$ <br>↵
$dp[n - 2][0] = 0. dp[n - 2][1] = v[n - 1] - v[n - 2].$ <br>↵
↵
Computing this also takes $O(n)$.↵
↵
For a query,↵
↵
- $O(1)$: Find the number of $+1$'s or $-1$'s in $[L, R]$. <br>↵
- $O(logn)$: In case either of them have an even count, find the left and ritemost indices using binary search over the vectors. <br>↵
- $O(1)$: prefix sum on respective $dp$ using the positions of the bounded values found in step above.↵
↵
Overall compleixity is $O(n + qlogn)$.↵
</spoiler>↵
↵
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?↵
↵
[](https://pokemondb.net/pokedex/wobbuffet)↵
↵
↵
↵
I was solving this [Leetcode](https://leetcode.com/problems/transform-array-to-all-equal-elements/description/) problem yesterday. ↵
↵
I'll rewrite the problem statement once again for convenience↵
↵
<spoiler summary="Problem Statement">↵
You are given an integer array $nums$ of size $n$ containing only $+1$ and $-1$, and an integer $k$.↵
↵
You can perform the following operation at most $k$ times: <br>↵
$·$ Choose an index $i$ $(0 ≤ i < n - 1)$, and multiply both $nums[i]$ and $nums[i + 1]$ by $-1$.↵
↵
Note that you can choose the same index $i$ more than once in different operations.↵
↵
Return $true$ if it is possible to make all elements of the array equal after at most $k$ operations, and $false$ otherwise.↵
</spoiler>↵
↵
<spoiler summary="Examples">↵
Input: $nums = [1,-1,1,-1,1], k = 3$↵
↵
Output: $true$↵
↵
Explanation:↵
↵
We can make all elements in the array equal in $2$ operations as follows: <br>↵
$·$ Choose index $i = 1$, and multiply both $nums[1]$ and $nums[2]$ by $-1$. Now $nums = [1,1,-1,-1,1]$. <br>↵
$·$ Choose index $i = 2$, and multiply both $nums[2]$ and $nums[3]$ by $-1$. Now $nums = [1,1,1,1,1]$.↵
</spoiler>↵
↵
<spoiler summary="Constraints">↵
$·$ $1 ≤ n ≤ 10^{5}$ <br>↵
$·$ $nums[i]$ is either $-1$ or $+1$. <br>↵
$·$ $1 ≤ k ≤ n$↵
</spoiler>↵
↵
I would suggest you to solve (in your head or code) this before going further↵
↵
<spoiler summary="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);↵
}↵
};↵
~~~~~↵
</spoiler>↵
↵
Now, lets say I have $q$ Queries of Type:↵
↵
- $1$ $L$ $R$ $k$ where- <br>↵
- $L$ and $R$ represent the left and rite endpoints of a subarray in $nums$ inclusive. <br>↵
- $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:↵
↵
<spoiler summary="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 < q < r < s$.↵
↵
The greedy strategy for doing this would be to: <br>↵
↵
- 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)$. <br>↵
$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]$. <br>↵
$dp[i][1] = v[i + 1] - v[i] + dp[i + 1][0]$. ↵
↵
Base Cases: <br>↵
$dp[n - 1][0] = 0. dp[n - 1][1] = 0;$ <br>↵
$dp[n - 2][0] = 0. dp[n - 2][1] = v[n - 1] - v[n - 2].$ <br>↵
↵
Computing this also takes $O(n)$.↵
↵
For a query,↵
↵
- $O(1)$: Find the number of $+1$'s or $-1$'s in $[L, R]$. <br>↵
- $O(logn)$: In case either of them have an even count, find the left and ritemost indices using binary search over the vectors. <br>↵
- $O(1)$: prefix sum on respective $dp$ using the positions of the bounded values found in step above.↵
↵
Overall compleixity is $O(n + qlogn)$.↵
</spoiler>↵
↵
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?↵
↵
[](https://pokemondb.net/pokedex/wobbuffet)↵
↵
↵
