Posts tagged as “medium”

花花酱 LeetCode 1904. The Number of Full Rounds You Have Played

By zxi on August 15, 2021

A new online video game has been released, and in this video game, there are 15-minute rounds scheduled every quarter-hour period. This means that at HH:00, HH:15, HH:30 and HH:45, a new round starts, where HH represents an integer number from 00 to 23. A 24-hour clock is used, so the earliest time in the day is 00:00 and the latest is 23:59.

Given two strings startTime and finishTime in the format "HH:MM" representing the exact time you started and finished playing the game, respectively, calculate the number of full rounds that you played during your game session.

For example, if startTime = "05:20" and finishTime = "05:59" this means you played only one full round from 05:30 to 05:45. You did not play the full round from 05:15 to 05:30 because you started after the round began, and you did not play the full round from 05:45 to 06:00 because you stopped before the round ended.

If finishTime is earlier than startTime, this means you have played overnight (from startTime to the midnight and from midnight to finishTime).

Return the number of full rounds that you have played if you had started playing at startTime and finished at finishTime.

Example 1:

Input: startTime = "12:01", finishTime = "12:44"
Output: 1
Explanation: You played one full round from 12:15 to 12:30.
You did not play the full round from 12:00 to 12:15 because you started playing at 12:01 after it began.
You did not play the full round from 12:30 to 12:45 because you stopped playing at 12:44 before it ended.

Example 2:

Input: startTime = "20:00", finishTime = "06:00"
Output: 40
Explanation: You played 16 full rounds from 20:00 to 00:00 and 24 full rounds from 00:00 to 06:00.
16 + 24 = 40.

Example 3:

Input: startTime = "00:00", finishTime = "23:59"
Output: 95
Explanation: You played 4 full rounds each hour except for the last hour where you played 3 full rounds.

Constraints:

startTime and finishTime are in the format HH:MM.
00 <= HH <= 23
00 <= MM <= 59
startTime and finishTime are not equal.

Solution: String / Simple math

ans = max(0, floor(end / 15) – ceil(start / 15))

Tips:

Write a reusable function to parse time to minutes.
a / b for floor, (a + b – 1) / b for ceil

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

C++

// Author: Huahua

class Solution {

public:

int numberOfRounds(string startTime, string finishTime) {

auto parseTime = [](string t) {

return ((t[0] - '0') * 10 + (t[1] - '0')) * 60 + (t[3] - '0') * 10 + t[4] - '0';

};

int m1 = parseTime(startTime);

int m2 = parseTime(finishTime);

if (m2 < m1) m2 += 24 * 60;

return max(0, m2 / 15 - (m1 + 14) / 15);

}

};

花花酱 LeetCode 1899. Merge Triplets to Form Target Triplet

By zxi on August 11, 2021

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [a_i, b_i, c_i] describes the i^th triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.

To obtain target, you may apply the following operation on triplets any number of times (possibly zero):

Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)].
- For example, if triplets[i] = [2, 5, 3] and triplets[j] = [1, 7, 5], triplets[j] will be updated to [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5].

Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

Example 1:

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.

Example 2:

Input: triplets = [[1,3,4],[2,5,8]], target = [2,5,8]
Output: true
Explanation: The target triplet [2,5,8] is already an element of triplets.

Example 3:

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]].
- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]].
The target triplet [5,5,5] is now an element of triplets.

Example 4:

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.

Constraints:

1 <= triplets.length <= 10⁵
triplets[i].length == target.length == 3
1 <= a_i, b_i, c_i, x, y, z <= 1000

Solution: Greedy

Exclude those bad ones (whose values are greater than x, y, z), check the max value for each dimension or whether there is x, y, z for each dimension.

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

C++

// Author: Huahua

class Solution {

public:

bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& t) {

vector<int> ans(3);

for (const auto& c : triplets)

if (c[0] <= t[0] && c[1] <= t[1] && c[2] <= t[2])

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

ans[i] |= c[i] == t[i];

return ans[0] && ans[1] && ans[2];

}

};

花花酱 LeetCode 1898. Maximum Number of Removable Characters

By zxi on August 11, 2021

You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).

You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.

Return the maximum k you can choose such that p is still a subsequence of s after the removals.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example 1:

Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb".
"ab" is a subsequence of "accb".
If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.

Example 2:

Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1
Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd".
"abcd" is a subsequence of "abcddddd".

Example 3:

Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0
Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.

Constraints:

1 <= p.length <= s.length <= 10⁵
0 <= removable.length < s.length
0 <= removable[i] < s.length
p is a subsequence of s.
s and p both consist of lowercase English letters.
The elements in removable are distinct.

Solution: Binary Search + Two Pointers

If we don’t remove any thing, p is a subseq of s, as we keep removing, at some point L, p is no longer a subseq of s. e.g [0:True, 1: True, …, L – 1: True, L: False, L+1: False, …, m:False], this array is monotonic. We can use binary search to find the smallest L such that p is no long a subseq of s. Ans = L – 1.

For each guess, we can use two pointers to check whether p is subseq of removed(s) in O(n).

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

C++

// Author: Huahua

class Solution {

public:

int maximumRemovals(string s, string p, vector<int>& removable) {

const int n = s.length();

const int t = p.length();

const int m = removable.size();

int l = 0;

int r = m + 1;

vector<int> idx(n, INT_MAX);

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

idx[removable[i]] = i;

while (l < r) {

int mid = l + (r - l) / 2;

int j = 0;

for (int i = 0; i < n && j < t; ++i)

if (idx[i] >= mid && s[i] == p[j]) ++j;

if (j != t)

r = mid;

else

l = mid + 1;

}

// l is the smallest number s.t. p is no longer a subseq of s.

return l - 1;

}

};

花花酱 LeetCode 1895. Largest Magic Square

By zxi on August 9, 2021

A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal. The integers in the magic square do not have to be distinct. Every 1 x 1 grid is trivially a magic square.

Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.

Example 1:

Input: grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
Output: 3
Explanation: The largest magic square has a size of 3.
Every row sum, column sum, and diagonal sum of this magic square is equal to 12.
- Row sums: 5+1+6 = 5+4+3 = 2+7+3 = 12
- Column sums: 5+5+2 = 1+4+7 = 6+3+3 = 12
- Diagonal sums: 5+4+3 = 6+4+2 = 12

Example 2:

Input: grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
Output: 2

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10⁶

Solution: Brute Force w/ Prefix Sum

Compute the prefix sum for each row and each column.

And check all possible squares.

Time complexity: O(m*n*min(m,n)²)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

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

const int m = grid.size();

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

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

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

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

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

rows[i][j + 1] = rows[i][j] + grid[i][j];

cols[j][i + 1] = cols[j][i] + grid[i][j];

}

for (int k = min(m, n); k >= 2; --k)

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

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

vector<int> s;

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

s.push_back(rows[i + r][j + k] - rows[i + r][j]);

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

s.push_back(cols[j + c][i + k] - cols[j + c][i]);

int d1 = 0;

int d2 = 0;

for (int d = 0; d < k; ++d) {

d1 += grid[i + d][j + d];

d2 += grid[i + d][j + k - d - 1];

}

s.push_back(d1);

s.push_back(d2);

if (count(begin(s), end(s), s[0]) == s.size()) return k;

}

return 1;

}

};

花花酱 LeetCode 1894. Find the Student that Will Replace the Chalk

By zxi on August 9, 2021

There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with the student number 0, then the student number 1, and so on until the teacher reaches the student number n - 1. After that, the teacher will restart the process, starting with the student number 0 again.

You are given a 0-indexed integer array chalk and an integer k. There are initially k pieces of chalk. When the student number i is given a problem to solve, they will use chalk[i] pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less than chalk[i], then the student number i will be asked to replace the chalk.

Return the index of the student that will replace the chalk.

Example 1:

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.

Example 2:

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.

Constraints:

chalk.length == n
1 <= n <= 10⁵
1 <= chalk[i] <= 10⁵
1 <= k <= 10⁹

Solution: Math

Sum up all the students. k %= sum to skip all the middle rounds.

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

C++

// Author: Huahua

class Solution {

public:

int chalkReplacer(vector<int>& chalk, int k) {

long sum = accumulate(begin(chalk), end(chalk), 0L);

k %= sum;

for (size_t i = 0; i < chalk.size(); ++i)

if ((k -= chalk[i]) < 0) return i;

return -1;

}

};