Huahua’s Tech Road

花花酱 LeetCode 2435. Paths in Matrix Whose Sum Is Divisible by K

By zxi on October 10, 2022

You are given a 0-indexed m x n integer matrix grid and an integer k. You are currently at position (0, 0) and you want to reach position (m - 1, n - 1) moving only down or right.

Return the number of paths where the sum of the elements on the path is divisible by k. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output: 2
Explanation: There are two paths where the sum of the elements on the path is divisible by k.
The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3.
The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.

Example 2:

Input: grid = [[0,0]], k = 5
Output: 1
Explanation: The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.

Example 3:

Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
Output: 10
Explanation: Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 5 * 10⁴
1 <= m * n <= 5 * 10⁴
0 <= grid[i][j] <= 100
1 <= k <= 50

Solution: DP

Let dp[i][j][r] := # of paths from (0,0) to (i,j) with path sum % k == r.

init: dp[0][0][grid[0][0] % k] = 1

dp[i][j][(r + grid[i][j]) % k] = dp[i-1][j][r] + dp[i][j-1][r]

ans = dp[m-1][n-1][0]

Time complexity: O(m*n*k)
Space complexity: O(m*n*k) -> O(n*k)

C++

// Author: Huahua

class Solution {

public:

int numberOfPaths(vector<vector<int>>& grid, int k) {

const int kMod = 1e9 + 7;

const int m = grid.size();

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

vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k)));

dp[0][0][grid[0][0] % k] = 1;

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

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

if (i == 0 && j == 0) continue;

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

dp[i][j][(r + grid[i][j]) % k] =

((j ? dp[i][j - 1][r] : 0) + (i ? dp[i - 1][j][r] : 0)) % kMod;

}

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

}

};

花花酱 LeetCode 2420. Find All Good Indices

By zxi on September 26, 2022

You are given a 0-indexed integer array nums of size n and a positive integer k.

We call an index i in the range k <= i < n - k good if the following conditions are satisfied:

The k elements that are just before the index i are in non-increasing order.
The k elements that are just after the index i are in non-decreasing order.

Return an array of all good indices sorted in increasing order.

Example 1:

Input: nums = [2,1,1,1,3,4,1], k = 2
Output: [2,3]
Explanation: There are two good indices in the array:
- Index 2. The subarray [2,1] is in non-increasing order, and the subarray [1,3] is in non-decreasing order.
- Index 3. The subarray [1,1] is in non-increasing order, and the subarray [3,4] is in non-decreasing order.
Note that the index 4 is not good because [4,1] is not non-decreasing.

Example 2:

Input: nums = [2,1,1,2], k = 2
Output: []
Explanation: There are no good indices in this array.

Constraints:

n == nums.length
3 <= n <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n / 2

Solution: Prefix Sum

Let before[i] = length of longest non-increasing subarray ends of nums[i].
Let after[i] = length of longest non-decreasing subarray ends of nums[i].

An index is good if nums[i – 1] >= k and nums[i + k] >= k

Time complexity: O(n + (n – 2*k))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> goodIndices(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> before(n, 1);

vector<int> after(n, 1);

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

if (nums[i] <= nums[i - 1])

before[i] = before[i - 1] + 1;

if (nums[i] >= nums[i - 1])

after[i] = after[i - 1] + 1;

}

vector<int> ans;

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

if (before[i - 1] >= k && after[i + k] >= k)

ans.push_back(i);

}

return ans;

}

};

花花酱 LeetCode 2419. Longest Subarray With Maximum Bitwise AND

By zxi on September 26, 2022

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
The maximum possible bitwise AND of a subarray is 3.
The longest subarray with that value is [3,3], so we return 2.

Example 2:

Input: nums = [1,2,3,4]
Output: 1
Explanation:
The maximum possible bitwise AND of a subarray is 4.
The longest subarray with that value is [4], so we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Solution: Find the largest number

a & b <= a
a & b <= b
if b > a, a & b < b, we choose to start a new sequence of “b” instead of continuing with “ab”

Basically, we find the largest number in the array and count the longest sequence of it. Note, there will be some tricky cases like.
b b b b a b
b a b b b b
We need to return 4 instead of 1.

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

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

int ans = 0;

int best = 0;

for (int i = 0, l = 0; i < nums.size(); ++i) {

if (nums[i] > best) {

best = nums[i];

ans = l = 1;

} else if (nums[i] == best) {

ans = max(ans, ++l);

} else {

l = 0;

}

return ans;

}

};

花花酱 LeetCode 2418. Sort the People

By zxi on September 26, 2022

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.

For each index i, names[i] and heights[i] denote the name and height of the i^th person.

Return names sorted in descending order by the people’s heights.

Example 1:

Input: names = ["Mary","John","Emma"], heights = [180,165,170]
Output: ["Mary","Emma","John"]
Explanation: Mary is the tallest, followed by Emma and John.

Example 2:

Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]
Output: ["Bob","Alice","Bob"]
Explanation: The first Bob is the tallest, followed by Alice and the second Bob.

Constraints:

n == names.length == heights.length
1 <= n <= 10³
1 <= names[i].length <= 20
1 <= heights[i] <= 10⁵
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

Solution: Zip and sort

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

C++

// Author: Huahua

class Solution {

public:

vector<string> sortPeople(vector<string>& names, vector<int>& heights) {

vector<pair<int, string*>> data;

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

data.emplace_back(heights[i], &names[i]);

sort(rbegin(data), rend(data));

vector<string> ans(names.size());

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

ans[i].swap(*data[i].second);

return ans;

}

};

花花酱 LeetCode 2416. Sum of Prefix Scores of Strings

By zxi on September 18, 2022

You are given an array words of size n consisting of non-empty strings.

We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i].

For example, if words = ["a", "ab", "abc", "cab"], then the score of "ab" is 2, since "ab" is a prefix of both "ab" and "abc".

Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].

Note that a string is considered as a prefix of itself.

Example 1:

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.

Example 2:

Input: words = ["abcd"]
Output: [4]
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] consists of lowercase English letters.

Solution: Trie

Insert all the words into a tire whose node val is the number of substrings that have the current prefix.

During query time, sum up the values along the prefix path.

Time complexity: O(sum(len(word))
Space complexity: O(sum(len(word))

C++

// Author: Huahua

struct Trie {

Trie* ch[26] = {};

int cnt = 0;

void insert(string_view s) {

Trie* cur = this;

for (char c : s) {

if (!cur->ch[c - 'a'])

cur->ch[c - 'a'] = new Trie();

cur = cur->ch[c - 'a'];

++cur->cnt;

}

int query(string_view s) {

Trie* cur = this;

int ans = 0;

for (char c : s) {

cur = cur->ch[c - 'a'];

ans += cur->cnt;

}

return ans;

}

};

class Solution {

public:

vector<int> sumPrefixScores(vector<string>& words) {

Trie* root = new Trie();

for (const string& w : words)

root->insert(w);

vector<int> ans;

for (const string& w : words)

ans.push_back(root->query(w));

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2435. Paths in Matrix Whose Sum Is Divisible by K

Solution: DP

C++

花花酱 LeetCode 2420. Find All Good Indices

Solution: Prefix Sum

C++

花花酱 LeetCode 2419. Longest Subarray With Maximum Bitwise AND

Solution: Find the largest number

C++

花花酱 LeetCode 2418. Sort the People

C++

花花酱 LeetCode 2416. Sum of Prefix Scores of Strings

Solution: Trie

C++