Posts tagged as “hard”

花花酱 LeetCode 1001. Grid Illumination

By zxi on February 24, 2019

On a N x N grid of cells, each cell (x, y) with 0 <= x < N and 0 <= y < N has a lamp.

Initially, some number of lamps are on. lamps[i] tells us the location of the i-th lamp that is on. Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).

For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.

After each query (x, y) [in the order given by queries], we turn off any lamps that are at cell (x, y) or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y).)

Return an array of answers. Each value answer[i] should be equal to the answer of the i-th query queries[i].

Example 1:

Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: 
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
Then the query at [1, 1] returns 1 because the cell is lit.  After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
Before performing the second query we have only the lamp [4,4] on.  Now the query at [1,0] returns 0, because the cell is no longer lit.

Note:

1 <= N <= 10^9
0 <= lamps.length <= 20000
0 <= queries.length <= 20000
lamps[i].length == queries[i].length == 2

Solution: HashTable

use lx, ly, lp, lq to track the # of lamps that covers each row, col, diagonal, antidiagonal

Time complexity: O(|L| + |Q|)
Space complexity: O(|L|)

C++

// Author: Huahua, running time: 460 ms, 82.2 MB

class Solution {

public:

vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {

unordered_set<long> s;

unordered_map<int, int> lx, ly, lp, lq;

for (const auto& lamp : lamps) {

const int x = lamp[0];

const int y = lamp[1];

s.insert(static_cast<long>(x) << 32 | y);

++lx[x];

++ly[y];

++lp[x + y];

++lq[x - y];

}

vector<int> ans;

for (const auto& query : queries) {

const int x = query[0];

const int y = query[1];

if (lx.count(x) || ly.count(y) || lp.count(x + y) || lq.count(x - y)) {

ans.push_back(1);

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty) {

if (tx < 0 || tx >= N || ty < 0 || ty >= N) continue;

const long key = static_cast<long>(tx) << 32 | ty;

if (!s.count(key)) continue;

s.erase(key);

if (--lx[tx] == 0) lx.erase(tx);

if (--ly[ty] == 0) ly.erase(ty);

if (--lp[tx + ty] == 0) lp.erase(tx + ty);

if (--lq[tx - ty] == 0) lq.erase(tx - ty);

}

} else {

ans.push_back(0);

}

return ans;

}

};

C++ v2

// Author: Huahua, running time: 444 ms, 82.2 MB

class Solution {

public:

vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {

unordered_set<long> s;

unordered_map<int, int> lx, ly, lp, lq;

for (const auto& lamp : lamps) {

const int x = lamp[0];

const int y = lamp[1];

s.insert(static_cast<long>(x) << 32 | y);

++lx[x];

++ly[y];

++lp[x + y];

++lq[x - y];

}

vector<int> ans;

auto dec = [](unordered_map<int, int>& m, int key) {

auto it = m.find(key);

if (it->second == 1)

m.erase(it);

else

--it->second;

};

for (const auto& query : queries) {

const int x = query[0];

const int y = query[1];

if (lx.count(x) || ly.count(y) || lp.count(x + y) || lq.count(x - y)) {

ans.push_back(1);

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty) {

if (tx < 0 || tx >= N || ty < 0 || ty >= N) continue;

const long key = static_cast<long>(tx) << 32 | ty;

auto it = s.find(key);

if (it == s.end()) continue;

s.erase(it);

dec(lx, tx);

dec(ly, ty);

dec(lp, tx + ty);

dec(lq, tx - ty);

}

} else {

ans.push_back(0);

}

return ans;

}

};

花花酱 LeetCode 995. Minimum Number of K Consecutive Bit Flips

By zxi on February 17, 2019

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

Example 1:

Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].

Example 2:

Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].

Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

Note:

1 <= A.length <= 30000
1 <= K <= A.length

Solution: Greedy

From left most, if there is a 0, that bit must be flipped since the right ones won’t affect left ones.

Time complexity: O(nk) -> O(k)
Space complexity: O(1)

C++ / O(nk)

// Author: Huahua, running time: 5172 ms, 16.4 MB

class Solution {

public:

int minKBitFlips(vector<int>& A, int K) {

int ans = 0;

for (int i = 0; i <= A.size() - K; ++i) {

if (A[i] == 1) continue;

++ans;

for (int j = 0; j < K; ++j)

A[i + j] ^= 1;

}

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

if (A[i] == 0) return -1;

return ans;

}

};

C++ / O(n)

// Author: Huahua, running time: 100 ms, 19.6 MB

class Solution {

public:

int minKBitFlips(vector<int>& A, int K) {

vector<int> flipped(A.size());

int ans = 0;

int flip = 0;

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

if (i >= K) flip ^= flipped[i - K];

if ((A[i] ^ flip) == 0) {

if (i + K > A.size()) return -1;

++ans;

flip ^= 1;

flipped[i] = 1;

}

return ans;

}

};

花花酱 LeetCode 992. Subarrays with K Different Integers

By zxi on February 10, 2019

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Note:

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

Solution: Two pointers + indirection

Let f(x) denote the number of subarrays with x or less distinct numbers.
ans = f(K) – f(K-1)
It takes O(n) Time and O(n) Space to compute f(x)

C++

// Author: Huahua

// vector: 56 ms, 10.1 MB

// Hashtable: 126 ms, 25 MB

class Solution {

public:

int subarraysWithKDistinct(vector<int>& A, int K) {

// Returns the number of subarrays with k or less distinct numbers.

auto subarrys = [&A](int k) {

vector<int> count(A.size() + 1);

int ans = 0;

int i = 0;

for (int j = 0; j < A.size(); ++j) {

if (count[A[j]]++ == 0)

--k;

while (k < 0)

if (--count[A[i++]] == 0) ++k;

ans += j - i + 1;

}

return ans;

};

return subarrys(K) - subarrys(K - 1);

}

};

花花酱 LeetCode 982. Triples with Bitwise AND Equal To Zero

By zxi on January 26, 2019

Given an array of integers A, find the number of triples of indices (i, j, k) such that:

0 <= i < A.length
0 <= j < A.length
0 <= k < A.length
A[i] & A[j] & A[k] == 0, where & represents the bitwise-AND operator.

Example 1:

Input: [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

Note:

1 <= A.length <= 1000
0 <= A[i] < 2^16

Solution: Counting

Time complexity: O(n^2 + n * max(A))
Space complexity: O(max(A))

C++

// Author: Huahua, running time: 60 ms

class Solution {

public:

int countTriplets(vector<int>& A) {

const int n = *max_element(begin(A), end(A));

vector<int> count(n + 1);

for (int a: A)

for (int b: A)

++count[a & b];

int ans = 0;

for (int a : A)

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

if ((a & i) == 0) ans += count[i];

return ans;

}

};

花花酱 LeetCode 85. Maximal Rectangle

By zxi on January 26, 2019

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Solution: DP

Time complexity: O(m^2*n)
Space complexity: O(mn)

dp[i][j] := max length of all 1 sequence ends with col j, at the i-th row.
transition:
dp[i][j] = 0 if matrix[i][j] == ‘0’
= dp[i][j-1] + 1 if matrix[i][j] == ‘1’

C++

class Solution {

public:

int maximalRectangle(vector<vector<char> > &matrix) {

int r = matrix.size();

if (r == 0) return 0;

int c = matrix[0].size();

// dp[i][j] := max len of all 1s ends with col j at row i.

vector<vector<int>> dp(r, vector<int>(c));

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

for (int j = 0; j < c; ++j)

dp[i][j] = (matrix[i][j] == '1') ? (j == 0 ? 1 : dp[i][j - 1] + 1) : 0;

int ans = 0;

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

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

int len = INT_MAX;

for (int k = i; k < r; k++) {

len = min(len, dp[k][j]);

if (len == 0) break;

ans = max(len * (k - i + 1), ans);

}

return ans;

}

};

Posts tagged as “hard”

花花酱 LeetCode 1001. Grid Illumination

Solution: HashTable

C++

C++ v2

花花酱 LeetCode 995. Minimum Number of K Consecutive Bit Flips

Solution: Greedy

C++ / O(nk)

C++ / O(n)

花花酱 LeetCode 992. Subarrays with K Different Integers

Solution: Two pointers + indirection

C++

Related Problems

花花酱 LeetCode 982. Triples with Bitwise AND Equal To Zero

Solution: Counting

C++

花花酱 LeetCode 85. Maximal Rectangle

Solution: DP

C++