Posts tagged as “medium”

花花酱 LeetCode 1504. Count Submatrices With All Ones

By zxi on July 5, 2020

Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.

Example 1:

Input: mat = [[1,0,1],
              [1,1,0],
              [1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

Example 2:

Input: mat = [[0,1,1,0],
              [0,1,1,1],
              [1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

Example 3:

Input: mat = [[1,1,1,1,1,1]]
Output: 21

Example 4:

Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5

Constraints:

1 <= rows <= 150
1 <= columns <= 150
0 <= mat[i][j] <= 1

Solution 1: Brute Force w/ Pruning

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

C++

// Author: Huahua

class Solution {

public:

int numSubmat(vector<vector<int>>& mat) {

const int R = mat.size();

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

// # of sub matrices with top-left at (sr, sc)

auto subMats = [&](int sr, int sc) {

int max_c = C;

int count = 0;

for (int r = sr; r < R; ++r)

for (int c = sc; c < max_c; ++c)

if (mat[r][c]) {

++count;

} else {

max_c = c;

}

return count;

};

int ans = 0;

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

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

ans += subMats(r, c);

return ans;

}

};

花花酱 LeetCode 1503. Last Moment Before All Ants Fall Out of a Plank

By zxi on July 5, 2020

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank.

Example 1:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
Note that the last moment when an ant was on the plank is t = 4 second, after that it falls imediately out of the plank. (i.e. We can say that at t = 4.0000000001, there is no ants on the plank).

Example 2:

Input: n = 7, left = [], right = [0,1,2,3,4,5,6,7]
Output: 7
Explanation: All ants are going to the right, the ant at index 0 needs 7 seconds to fall.

Example 3:

Input: n = 7, left = [0,1,2,3,4,5,6,7], right = []
Output: 7
Explanation: All ants are going to the left, the ant at index 7 needs 7 seconds to fall.

Example 4:

Input: n = 9, left = [5], right = [4]
Output: 5
Explanation: At t = 1 second, both ants will be at the same intial position but with different direction.

Example 5:

Input: n = 6, left = [6], right = [0]
Output: 6

Constraints:

1 <= n <= 10^4
0 <= left.length <= n + 1
0 <= left[i] <= n
0 <= right.length <= n + 1
0 <= right[i] <= n
1 <= left.length + right.length <= n + 1
All values of left and right are unique, and each value can appear only in one of the two arrays.

Solution: Keep Walking

When two ants A –> and <– B meet at some point, they change directions <– A B –>, we can swap the ids of the ants as <– B A–>, so it’s the same as walking individually and passed by. Then we just need to find the max/min of the left/right arrays.

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

C++

// Author: Huahua

class Solution {

public:

int getLastMoment(int n, vector<int>& left, vector<int>& right) {

const int t1 = left.empty() ? 0 : *max_element(cbegin(left), cend(left));

const int t2 = right.empty() ? 0 : n - *min_element(cbegin(right), cend(right));

return max(t1, t2);

}

};

Java

// Author: Huahua

class Solution {

public int getLastMoment(int n, int[] left, int[] right) {

int t1 = left.length == 0 ? 0 : Arrays.stream(left).max().getAsInt();

int t2 = right.length == 0 ? 0 : n - Arrays.stream(right).min().getAsInt();

return Math.max(t1, t2);

}

Python3

# Author: Huahua

class Solution:

def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:

t1 = max(left) if left else 0

t2 = n - min(right) if right else 0

return max(t1, t2)

花花酱 LeetCode 1498. Number of Subsequences That Satisfy the Given Sum Condition

By zxi on June 28, 2020

Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6

Solution: Two Pointers

Since order of the elements in the subsequence doesn’t matter, we can sort the input array.
Very similar to two sum, we use two pointers (i, j) to maintain a window, s.t. nums[i] +nums[j] <= target.
Then fix nums[i], any subset of (nums[i+1~j]) gives us a valid subsequence, thus we have 2^(j-(i+1)+1) = 2^(j-i) valid subsequence for window (i, j).

Time complexity: O(nlogn) // Sort
Space complexity: O(n) // need to precompute 2^n % kMod.

C++

// Author: Huahua

class Solution {

public:

int numSubseq(vector<int>& nums, int target) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

vector<int> p(n + 1, 1);

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

p[i] = (p[i - 1] << 1) % kMod;

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

int ans = 0;

for (int i = 0, j = n - 1; i <= j; ++i) {

while (i <= j && nums[i] + nums[j] > target) --j;

if (i > j) continue;

// In subarray nums[i~j]:

// min = nums[i], max = nums[j]

// nums[i] + nums[j] <= target

// {nums[i], (j - i - 1 + 1 values)}

// Any subset of the right part gives a valid subsequence

// in the original array. And There are 2^(j - i) ones.

ans = (ans + p[j - i]) % kMod;

}

return ans;

}

};

花花酱 LeetCode 1497. Check If Array Pairs Are Divisible by k

By zxi on June 28, 2020

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return True If you can find a way to do that or False otherwise.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Example 2:

Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).

Example 3:

Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

Example 4:

Input: arr = [-10,10], k = 2
Output: true

Example 5:

Input: arr = [-1,1,-2,2,-3,3,-4,4], k = 3
Output: true

Constraints:

arr.length == n
1 <= n <= 10^5
n is even.
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5

Solution: Mod and Count

Count the frequency of (x % k + k) % k.
f[0] should be even (zero is also even)
f[1] = f[k -1] ((1 + k – 1) % k == 0)
f[2] = f[k -2] ((2 + k – 2) % k == 0)
…
Time complexity: O(n)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

bool canArrange(vector<int>& arr, int k) {

vector<int> f(k);

for (int x : arr) ++f[(x % k + k) % k];

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

if (f[i] != f[k - i]) return false;

return f[0] % 2 == 0;

}

};

花花酱 LeetCode 1493. Longest Subarray of 1’s After Deleting One Element

By zxi on June 27, 2020

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1’s in the resulting array.

Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Example 4:

Input: nums = [1,1,0,0,1,1,1,0,1]
Output: 4

Example 5:

Input: nums = [0,0,0]
Output: 0

Constraints:

1 <= nums.length <= 10^5
nums[i] is either 0 or 1.

Solution 1: DP

Preprocess:
l[i] := longest 1s from left side ends with nums[i], l[i] = nums[i] + nums[i] * l[i – 1]
r[i] := longest 1s from right side ends with nums[i], r[i] = nums[i] + nums[i] * r[i + 1]

Use each node as a bridge (ignored), the total number of consecutive 1s = l[i – 1] + r[i + 1].

ans = max{l[i-1] + r[i +1]}
Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

vector<int> l(n);

vector<int> r(n);

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

l[i] = (i > 0 ? l[i - 1] * nums[i] : 0) + nums[i];

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

r[i] = (i < n - 1 ? r[i + 1] * nums[i] : 0) + nums[i];

int ans = 0;

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

ans = max(ans, (i > 0 ? l[i - 1] : 0) +

(i < n - 1 ? r[i + 1] : 0));

return ans;

}

};

Solution 2: DP

dp[i][0] := longest subarray ends with nums[i] has no ones.
dp[i][0] := longest subarray ends with nums[i] has 1 one.
if nums[i] == 1:
dp[i][0] = dp[i – 1][0] + 1
dp[i][1] = dp[i – 1][1] + 1
if nums[i] == 0:
dp[i][0] = 0
dp[i][1] = dp[i – 1][0] + 1
Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

// dp[i][0] := longest subarray ends with nums[i-1] has no zeros.

// dp[i][0] := longest subarray ends with nums[i-1] has 1 zero.

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

int ans = 0;

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

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

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

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

} else {

dp[i][0] = 0;

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

}

ans = max({ans, dp[i][0] - 1, dp[i][1] - 1});

}

return ans;

}

};

Solution 3: Sliding Window

Maintain a sliding window l ~ r s.t sum(num[l~r]) >= r – l. There can be at most one 0 in the window.
ans = max{r – l} for all valid windows.

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

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

int sum = 0; // sum of nums[l~r].

for (int l = 0, r = 0; r < n; ++r) {

sum += nums[r];

// Maintain sum >= r - l, at most 1 zero.

while (l < r && sum < r - l)

sum -= nums[l++];

ans = max(ans, r - l);

}

return ans;

}

};