Huahua’s Tech Road

花花酱 LeetCode 2441. Largest Positive Integer That Exists With Its Negative

By zxi on October 15, 2022

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

Example 1:

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the only valid k we can find in the array.

Example 2:

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3:

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no a single valid k, we return -1.

Constraints:

1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
nums[i] != 0

Solution 1: Hashtable

We can do in one pass by checking whether -x in the hashtable and update ans with abs(x) if so.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

unordered_set<int> s;

int ans = -1;

for (int x : nums) {

if (abs(x) > ans && s.count(-x))

ans = abs(x);

s.insert(x);

}

return ans;

}

};

Solution 2: Sorting

Sort the array by abs(x) in descending order.

[-1,10,6,7,-7,1] becomes = [-1, 1, 6, -7, 7, 10]

Check whether arr[i] = -arr[i-1].

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

sort(begin(nums), end(nums), [](int a, int b){

return abs(a) == abs(b) ? a < b : abs(a) > abs(b);

});

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

if (nums[i] == -nums[i - 1]) return nums[i];

return -1;

}

};

Solution 3: Two Pointers

Sort the array.

Let sum = nums[i] + nums[j], sum == 0, we find one pair, if sum < 0, ++i else –j.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxK(vector<int>& nums) {

sort(begin(nums), end(nums));

int ans = -1;

for (int i = 0, j = nums.size() - 1; i < j; ) {

const int s = nums[i] + nums[j];

if (s == 0) {

ans = max(ans, nums[j]);

++i, --j;

} else if (s < 0) {

++i;

} else {

--j;

}

return ans;

}

};

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 2441. Largest Positive Integer That Exists With Its Negative

Solution 1: Hashtable

C++

Solution 2: Sorting

C++

Solution 3: Two Pointers

C++

花花酱 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++