Posts tagged as “flip”

花花酱 LeetCode 1975. Maximum Matrix Sum

By zxi on December 31, 2021

You are given an n x n integer matrix. You can do the following operation any number of times:

Choose any two adjacent elements of matrix and multiply each of them by -1.

Two elements are considered adjacent if and only if they share a border.

Your goal is to maximize the summation of the matrix’s elements. Return the maximum sum of the matrix’s elements using the operation mentioned above.

Example 1:

Input: matrix = [[1,-1],[-1,1]]
Output: 4
Explanation: We can follow the following steps to reach sum equals 4:
- Multiply the 2 elements in the first row by -1.
- Multiply the 2 elements in the first column by -1.

Example 2:

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
Output: 16
Explanation: We can follow the following step to reach sum equals 16:
- Multiply the 2 last elements in the second row by -1.

Constraints:

n == matrix.length == matrix[i].length
2 <= n <= 250
-10⁵ <= matrix[i][j] <= 10⁵

Solution: Math

Count the number of negative numbers.
1. Even negatives, we can always flip all the negatives to positives. ans = sum(abs(matrix)).
2. Odd negatives, there will be one negative left, we found the smallest abs(element) and let it become negative. ans = sum(abs(matrix))) – 2 * min(abs(matrix))

Time complexity: O(n²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

long long maxMatrixSum(vector<vector<int>>& matrix) {

const int n = matrix.size();

long long ans = 0;

int count = 0;

int lo = INT_MAX;

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j) {

ans += abs(matrix[i][j]);

lo = min(lo, abs(matrix[i][j]));

count += matrix[i][j] < 0;

}

return ans - (count & 1) * 2 * lo;

}

};

花花酱 LeetCode 1529. Bulb Switcher IV

By zxi on July 26, 2020

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

Choose any bulb (index i) of your current configuration.
Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3:

Input: target = "00000"
Output: 0

Example 4:

Input: target = "001011101"
Output: 5

Constraints:

1 <= target.length <= 10^5
target[i] == '0' or target[i] == '1'

Solution: XOR

Flip from left to right, since flipping the a bulb won’t affect anything in the left.
We count how many times flipped so far, and that % 2 will be the state for all the bulb to the right.
If the current bulb’s state != target, we have to flip once.

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

int minFlips(string target) {

int ans = 0;

int cur = 0;

for (char c : target) {

if (c - '0' != cur) {

cur ^= 1;

++ans;

}

return ans;

}

};

花花酱 LeetCode 48. Rotate Image

By zxi on October 2, 2019

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Solution: 2 Passes

First pass: mirror around diagonal
Second pass: mirror around y axis

Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

void rotate(vector<vector<int>>& matrix) {

const int n = matrix.size();

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

swap(matrix[i][j], matrix[j][i]);

for (int i = 0; i < n; ++i)

reverse(begin(matrix[i]), end(matrix[i]));

}

};

花花酱 LeetCode 978. Longest Turbulent Subarray

By zxi on January 20, 2019

A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:

For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1]when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

Input: [4,8,12,16]
Output: 2

Example 3:

Input: [100]
Output: 1

Note:

1 <= A.length <= 40000
0 <= A[i] <= 10^9

Solution: DP

Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua, running time: 120 ms

class Solution {

public:

int maxTurbulenceSize(vector<int>& A) {

vector<int> up(A.size(), 1);

vector<int> down(A.size(), 1);

int ans = 1;

for (int i = 1; i < A.size(); ++i) {

if (A[i] > A[i - 1]) up[i] = down[i - 1] + 1;

if (A[i] < A[i - 1]) down[i] = up[i - 1] + 1;

ans = max(ans, max(up[i], down[i]));

}

return ans;

}

};

花花酱 LeetCode 926. Flip String to Monotone Increasing

By zxi on October 20, 2018

Problem

A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)

We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.

Return the minimum number of flips to make S monotone increasing.

Example 1:

Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.

Note:

1 <= S.length <= 20000
S only consists of '0' and '1' characters.

Solution: DP

l[i] := number of flips to make S[0] ~ S[i] become all 0s.

r[i] := number of flips to make S[i] ~ S[n – 1] become all 1s.

Try all possible break point, S[0] ~ S[i – 1] are all 0s and S[i] ~ S[n-1] are all 1s.

ans = min{l[i – 1] + r[i]}

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int minFlipsMonoIncr(string S) {

const int n = S.size();

vector<int> l(n + 1); // 1 -> 0

vector<int> r(n + 1); // 0 -> 1

l[0] = S[0] - '0';

r[n - 1] = '1' - S[n - 1];

for (int i = 1; i < n; ++i)

l[i] = l[i - 1] + S[i] - '0';

for (int i = n - 2; i >= 0; --i)

r[i] = r[i + 1] + '1' - S[i];

int ans = r[0]; // all 1s.

for (int i = 1; i <= n; ++i)

ans = min(ans, l[i - 1] + r[i]);

return ans;

}

};

C++ v2

// Author: Huahua

class Solution {

public:

int minFlipsMonoIncr(string S) {

const int n = S.length();

vector<vector<int>> dp(n + 1, vector<int>(2));

for (int i = 1; i <= n; ++i) {

if (S[i - 1] == '0') {

dp[i][0] = dp[i - 1][0];

dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1;

} else {

dp[i][0] = dp[i - 1][0] + 1;

dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]);

}

return min(dp[n][0], dp[n][1]);

}

};

C++ v2 / O(1) Space

// Author: Huahua

class Solution {

public:

int minFlipsMonoIncr(string S) {

const int n = S.length();

int dp0 = 0;

int dp1 = 0;

for (int i = 1; i <= n; ++i) {

int tmp0 = dp0 + (S[i - 1] == '1');

dp1 = min(dp0, dp1) + (S[i - 1] == '0');

dp0 = tmp0;

}

return min(dp0, dp1);

}

};