Huahua’s Tech Road

花花酱 LeetCode 1871. Jump Game VII

By zxi on August 5, 2021

You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:

i + minJump <= j <= min(i + maxJump, s.length - 1), and
s[j] == '0'.

Return true if you can reach index s.length - 1 in s, or false otherwise.

Example 1:

Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3. 
In the second step, move from index 3 to index 5.

Example 2:

Input: s = "01101110", minJump = 2, maxJump = 3
Output: false

Constraints:

2 <= s.length <= 10⁵
s[i] is either '0' or '1'.
s[0] == '0'
1 <= minJump <= maxJump < s.length

Solution 1: TreeSet /Dequq + Binary Search

Maintain a set of reachable indices so far, for each ‘0’ index check whether it can be reached from any of the elements in the set.

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

C++/set

// Author: Huahua, 296 ms, 59.7MB

class Solution {

public:

bool canReach(string s, int minJump, int maxJump) {

if (s.back() != '0') return false;

const int n = s.length();

set<int> seen{0};

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

if (s[i] != '0') continue;

while (!seen.empty() && (*seen.begin()) + maxJump < i)

seen.erase(seen.begin());

auto it = seen.upper_bound(i - minJump);

if (it != seen.begin() && *prev(it) + minJump <= i)

seen.insert(i);

}

return seen.count(n - 1);

}

};

C++/deque

// Author: Huahua, 280 ms, 19MB

class Solution {

public:

bool canReach(string s, int minJump, int maxJump) {

if (s.back() != '0') return false;

const int n = s.length();

deque<int> seen{0};

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

if (s[i] != '0') continue;

while (!seen.empty() && (seen.front()) + maxJump < i)

seen.pop_front();

auto it = upper_bound(begin(seen), end(seen), i - minJump);

if (it != seen.begin() && *prev(it) + minJump <= i)

seen.push_back(i);

}

return seen.back() == n - 1;

}

};

Solution 2: Queue

Same idea, we can replace the deque in sol1 with a queue, and only check the smallest element in the queue.

C++/set

// Author: Huahua, 56ms, 19.2MB

class Solution {

public:

bool canReach(string s, int minJump, int maxJump) {

if (s.back() != '0') return false;

const int n = s.length();

queue<int> q{{0}};

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

if (s[i] != '0') continue;

while (!q.empty() && q.front() + maxJump < i)

q.pop();

if (!q.empty() && q.front() + minJump <= i)

q.push(i);

}

return q.back() == n - 1;

}

};

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

花花酱 LeetCode 1870. Minimum Speed to Arrive on Time

By zxi on August 5, 2021

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the i^th train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

For example, if the 1^st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2^nd train ride at the 2 hour mark.

Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.

Tests are generated such that the answer will not exceed 10⁷ and hour will have at most two digits after the decimal point.

Example 1:

Input: dist = [1,3,2], hour = 6
Output: 1
Explanation: At speed 1:
- The first train ride takes 1/1 = 1 hour.
- Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3 hours.
- Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2/1 = 2 hours.
- You will arrive at exactly the 6 hour mark.

Example 2:

Input: dist = [1,3,2], hour = 2.7
Output: 3
Explanation: At speed 3:
- The first train ride takes 1/3 = 0.33333 hours.
- Since we are not at an integer hour, we wait until the 1 hour mark to depart. The second train ride takes 3/3 = 1 hour.
- Since we are already at an integer hour, we depart immediately at the 2 hour mark. The third train takes 2/3 = 0.66667 hours.
- You will arrive at the 2.66667 hour mark.

Example 3:

Input: dist = [1,3,2], hour = 1.9
Output: -1
Explanation: It is impossible because the earliest the third train can depart is at the 2 hour mark.

Constraints:

n == dist.length
1 <= n <= 10⁵
1 <= dist[i] <= 10⁵
1 <= hour <= 10⁹
There will be at most two digits after the decimal point in hour.

Solution: Binary Search

l = speed_min=1
r = speed_max+1 = 1e7 + 1

Find the min valid speed m such that t(m) <= hour.

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

C++

// Author: Huahua

class Solution {

public:

int minSpeedOnTime(vector<int>& dist, double hour) {

constexpr int kMax = 1e7 + 1;

const int n = dist.size();

int l = 1;

int r = kMax;

while (l < r) {

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

int t = 0;

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

t += (dist[i] + m - 1) / m;

if (t + dist.back() * 1.0 / m <= hour)

r = m;

else

l = m + 1;

}

return l == kMax ? -1 : l;

}

};

花花酱 LeetCode 1869. Longer Contiguous Segments of Ones than Zeros

By zxi on August 5, 2021

Given a binary string s, return true if the longest contiguous segment of 1s is strictly longer than the longest contiguous segment of 0s in s. Return false otherwise.

For example, in s = "110100010" the longest contiguous segment of 1s has length 2, and the longest contiguous segment of 0s has length 3.

Note that if there are no 0s, then the longest contiguous segment of 0s is considered to have length 0. The same applies if there are no 1s.

Example 1:

Input: s = "1101"
Output: true
Explanation:
The longest contiguous segment of 1s has length 2: "1101"
The longest contiguous segment of 0s has length 1: "1101"
The segment of 1s is longer, so return true.

Example 2:

Input: s = "111000"
Output: false
Explanation:
The longest contiguous segment of 1s has length 3: "111000"
The longest contiguous segment of 0s has length 3: "111000"
The segment of 1s is not longer, so return false.

Example 3:

Input: s = "110100010"
Output: false
Explanation:
The longest contiguous segment of 1s has length 2: "110100010"
The longest contiguous segment of 0s has length 3: "110100010"
The segment of 1s is not longer, so return false.

Constraints:

1 <= s.length <= 100
s[i] is either '0' or '1'.

Solution: Brute Force

Write a function count to count longest contiguous segment of m, return count(‘1’) > count(‘0’)

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

C++

// Author: Huahua

class Solution {

public:

bool checkZeroOnes(string s) {

auto count = [&](char m) {

int ans = 0;

int l = 0;

for (char c : s)

if (c != m) l = 0;

else ans = max(ans, ++l);

return ans;

};

return count('1') > count('0');

}

};

花花酱 LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

By zxi on August 4, 2021

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.

For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.

Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.

Example 2:

Input: n = 5, k = 5
Output: 1
Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.

Example 3:

Input: n = 20, k = 11
Output: 647427950
Explanation: There are 647427950 (mod 10⁹+ 7) ways to rearrange the sticks such that exactly 11 sticks are visible.

Constraints:

1 <= n <= 1000
1 <= k <= n

Solution: DP

dp(n, k) = dp(n – 1, k – 1) + (n-1) * dp(n-1, k)

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

C++

// Author: Huahua

class Solution {

public:

int rearrangeSticks(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<long>> dp(n + 1, vector<long>(k + 1));

for (int j = 1; j <= k; ++j) {

dp[j][j] = 1;

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

dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % kMod;

}

return dp[n][k];

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None)

def rearrangeSticks(self, n: int, k: int) -> int:

if k == 0: return 0

if k == n or n <= 2: return 1

return (self.rearrangeSticks(n - 1, k - 1) +

(n - 1) * self.rearrangeSticks(n - 1, k)) % (10**9 + 7)

花花酱 LeetCode 1865. Finding Pairs With a Certain Sum

By zxi on August 4, 2021

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

Add a positive integer to an element of a given index in the array nums2.
Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Example 1:

Input
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
Output
[null, 8, null, 2, 1, null, null, 11]
Explanation
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7); // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4] 
findSumPairs.count(8); // return 2; pairs (5,2), (5,4) make 3 + 5 
findSumPairs.count(4); // return 1; pair (5,0) makes 3 + 1 
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4] 
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4] 
findSumPairs.count(7); // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Constraints:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10⁵
1 <= nums1[i] <= 10⁹
1 <= nums2[i] <= 10⁵
0 <= index < nums2.length
1 <= val <= 10⁵
1 <= tot <= 10⁹
At most 1000 calls are made to add and count each.

Solution: HashTable

Note nums1 and nums2 are unbalanced. Brute force method will take O(m*n) = O(10³*10⁵) = O(10⁸) for each count call which will TLE. We could use a hashtable to store the counts of elements from nums2, and only iterate over nums1 to reduce the time complexity.

Time complexity:

init: O(m) + O(n)
add: O(1)
count: O(m)

Total time is less than O(10⁶)

Space complexity: O(m + n)

C++

// Author: Huahua

class FindSumPairs {

public:

FindSumPairs(vector<int>& nums1,

vector<int>& nums2): nums1_(nums1), nums2_(nums2) {

for (int x : nums2_) ++freq_[x];

}

void add(int index, int val) {

if (--freq_[nums2_[index]] == 0)

freq_.erase(nums2_[index]);

++freq_[nums2_[index] += val];

}

int count(int tot) {

int ans = 0;

for (int a : nums1_) {

auto it = freq_.find(tot - a);

if (it != freq_.end()) ans += it->second;

}

return ans;

}

private:

vector<int> nums1_;

vector<int> nums2_;

unordered_map<int, int> freq_;

};

Python3

# Author: Huahua

class FindSumPairs:

def __init__(self, nums1: List[int], nums2: List[int]):

self.nums1 = nums1

self.nums2 = nums2

self.freq = Counter(nums2)

def add(self, index: int, val: int) -> None:

self.freq.subtract((self.nums2[index],))

self.nums2[index] += val

self.freq.update((self.nums2[index],))

def count(self, tot: int) -> int:

return sum(self.freq[tot - a] for a in self.nums1)

Huahua's Tech Road

花花酱 LeetCode 1871. Jump Game VII

Solution 1: TreeSet /Dequq + Binary Search

C++/set

C++/deque

Solution 2: Queue

C++/set

花花酱 LeetCode 1870. Minimum Speed to Arrive on Time

Solution: Binary Search

C++

花花酱 LeetCode 1869. Longer Contiguous Segments of Ones than Zeros

Solution: Brute Force

C++

花花酱 LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

Solution: DP

C++

Python3

花花酱 LeetCode 1865. Finding Pairs With a Certain Sum

Solution: HashTable

C++

Python3