Posts tagged as “O(mn)”

花花酱 LeetCode 1639. Number of Ways to Form a Target String Given a Dictionary

By zxi on October 31, 2020

You are given a list of strings of the same length words and a string target.

Your task is to form target using the given words under the following rules:

target should be formed from left to right.
To form the i^th character (0-indexed) of target, you can choose the k^th character of the j^th string in words if target[i] = words[j][k].
Once you use the k^th character of the j^th string of words, you can no longer use the x^th character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.
Repeat the process until you form the string target.

Notice that you can use multiple characters from the same string in words provided the conditions above are met.

Return the number of ways to form target from words. Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

Example 2:

Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

Example 3:

Input: words = ["abcd"], target = "abcd"
Output: 1

Example 4:

Input: words = ["abab","baba","abba","baab"], target = "abba"
Output: 16

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 1000
All strings in words have the same length.
1 <= target.length <= 1000
words[i] and target contain only lowercase English letters.

Solution: DP

dp[i][j] := # of ways to form target[0~j] where the j-th letter is from the i-th column of words.
count[i][j] := # of words that have word[i] == target[j]

dp[i][j] = dp[i-1][j-1] * count[i][j]

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

C++

class Solution {

public:

int numWays(vector<string>& words, string target) {

constexpr int kMod = 1e9 + 7;

const int n = target.length();

const int m = words[0].length();

vector<long> dp(n); // dp[j] = # of ways to form t[0~j]

for (int i = 0; i < m; ++i) {

vector<int> count(26);

for (const string& word: words)

++count[word[i] - 'a'];

for (int j = min(i, n - 1); j >= 0; --j)

dp[j] = (dp[j] + (j > 0 ? dp[j - 1] : 1) *

count[target[j] - 'a']) % kMod;

}

return dp[n - 1];

}

};

花花酱 LeetCode 1391. Check if There is a Valid Path in a Grid

By zxi on March 22, 2020

Given a m x ngrid. Each cell of the grid represents a street. The street of grid[i][j] can be:

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true

Example 5:

Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

Solution: BFS

Need to check both sides (x, y) -> (tx, ty) and (tx, ty) -> (x, y) to make sure a path exist.

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

bool hasValidPath(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<int> dirs{0, -1, 0, 1, 0}; // [up, left, down, right]

vector<set<int>> rules{

{1, 3}, {0, 2}, {1, 2},

{2, 3}, {0, 1}, {0, 3}};

queue<int> q{{0}};

vector<int> seen(m * n);

seen[0] = 1;

while (!q.empty()) {

int cx = q.front() % n;

int cy = q.front() / n;

q.pop();

if (cx == n - 1 && cy == m - 1) return true;

for (int d : rules[grid[cy][cx] - 1]) {

int x = cx + dirs[d];

int y = cy + dirs[d + 1];

int key = y * n + x;

if (x < 0 || x >= n || y < 0 || y >= m || seen[key]

|| !rules[grid[y][x] - 1].count((d + 2) % 4)) continue;

seen[key] = 1;

q.push(key);

}

return false;

}

};

花花酱 LeetCode 1380. Lucky Numbers in a Matrix

By zxi on March 15, 2020

Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column

Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 3:

Input: matrix = [[7,8],[1,2]]
Output: [7]

Constraints:

m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5.
All elements in the matrix are distinct.

Solution: Pre-processing

Two pass. First pass, record the min val of each row, and max val of each column.
Second pass, identify lucky numbers.

Time complexity: O(m * n)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> luckyNumbers (vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

vector<int> rows(m, INT_MAX);

vector<int> cols(n, INT_MIN);

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

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

rows[i] = min(rows[i], matrix[i][j]);

cols[j] = max(cols[j], matrix[i][j]);

}

vector<int> ans;

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

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

if (matrix[i][j] == rows[i] &&

matrix[i][j] == cols[j])

ans.push_back(matrix[i][j]);

return ans;

}

};

花花酱 LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid

By zxi on February 29, 2020

Given a m x ngrid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some invalid signs on the cells of the grid which points outside the grid.

You will initially start at the upper left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path doesn’t have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.

Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).

Example 3:

Input: grid = [[1,2],[4,3]]
Output: 1

Example 4:

Input: grid = [[2,2,2],[2,2,2]]
Output: 3

Example 5:

Input: grid = [[4]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100

Solution 1: Lazy BFS (fake DP)

dp[i][j] := min steps to reach (i, j)

Time complexity: O((m+n)*m*n)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int minCost(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2));

dp[0][0] = 0;

auto solve = [&](int x, int y) {

int& v = dp[y][x];

if (x > 0) v = min(v, dp[y][x - 1] + (grid[y][x - 1] != 1));

if (y > 0) v = min(v, dp[y - 1][x] + (grid[y - 1][x] != 3));

if (x < n - 1) v = min(v, dp[y][x + 1] + (grid[y][x + 1] != 2));

if (y < m - 1) v = min(v, dp[y + 1][x] + (grid[y + 1][x] != 4));

};

// At most m + n steps to propagate the results to (m - 1, n -1).

for (int k = 0; k <= (m + n); ++k) {

for (int y = 0; y < m; ++y)

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

solve(x, y);

for (int y = m - 1; y >= 0; --y)

for (int x = n - 1; x >= 0; --x)

solve(x, y);

}

return dp[m - 1][n - 1];

}

};

C++

// Author: Huahua, 88 ms / 22.9 MB

class Solution {

public:

int minCost(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2));

dp[0][0] = 0;

while (true) {

auto prev(dp);

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

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

if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (grid[i - 1][j] != 3));

if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (grid[i][j - 1] != 1));

}

for (int i = m - 1; i >= 0; --i)

for (int j = n - 1; j >= 0; --j) {

if (i != m - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + (grid[i + 1][j] != 4));

if (j != n - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + (grid[i][j + 1] != 2));

}

if (prev == dp) break; // optimal solution obtained.

}

return dp[m - 1][n - 1];

}

};

Solution 2: 0-1 BFS

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int minCost(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

deque<pair<int, int>> q{{0, 0}};

vector<char> seen(m * n);

vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

while (!q.empty()) {

auto [p, cost] = q.front(); q.pop_front();

int x = p % n, y = p / n;

if (x == n - 1 && y == m - 1) return cost;

if (seen[p]++) continue;

for (int i = 0; i < 4; ++i) {

int tx = x + dirs[i][0], ty = y + dirs[i][1];

int tp = ty * n + tx;

if (tx < 0 || ty < 0 || tx >= n || ty >= m || seen[tp]) continue;

if (grid[y][x] == i + 1)

q.emplace_front(tp, cost);

else

q.emplace_back(tp, cost + 1);

}

return -1;

}

};

花花酱 LeetCode 1314. Matrix Block Sum

By zxi on January 11, 2020

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n, K <= 100
1 <= mat[i][j] <= 100

Solution: 2D range query

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

// Author: Huahua, 20 ms

class Solution {

public:

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {

const int n = mat.size();

const int m = mat[0].size();

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

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

for (int x = 1; x <= m; ++x)

dp[y][x] = dp[y - 1][x] + dp[y][x - 1] + mat[y - 1][x - 1] - dp[y - 1][x - 1];

auto ans = mat;

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

for (int x = 1; x <= m; ++x) {

int x1 = max(1, x - K);

int x2 = min(m, x + K);

int y1 = max(1, y - K);

int y2 = min(n, y + K);

ans[y - 1][x - 1] = dp[y2][x2] - dp[y1 - 1][x2] - dp[y2][x1 - 1] + dp[y1 - 1][x1 - 1];

}

return ans;

}

};