Posts tagged as “medium”

花花酱 LeetCode 1492. The kth Factor of n

By zxi on June 27, 2020

Given two positive integers n and k.

A factor of an integer n is defined as an integer i where n % i == 0.

Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.

Example 1:

Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Example 2:

Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.

Example 3:

Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.

Example 4:

Input: n = 1, k = 1
Output: 1
Explanation: Factors list is [1], the 1st factor is 1.

Example 5:

Input: n = 1000, k = 3
Output: 4
Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000].

Constraints:

1 <= k <= n <= 1000

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int kthFactor(int n, int k) {

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

if (n % i == 0 && --k == 0) return i;

return -1;

}

};

花花酱 LeetCode 1488. Avoid Flood in The City

By zxi on June 20, 2020

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.

Given an integer array rains where:

rains[i] > 0 means there will be rains over the rains[i] lake.
rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

ans.length == rains.length
ans[i] == -1 if rains[i] > 0.
ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.

Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

Example 3:

Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.

Example 4:

Input: rains = [69,0,0,0,69]
Output: [-1,69,1,1,-1]
Explanation: Any solution on one of the forms [-1,69,x,y,-1], [-1,x,69,y,-1] or [-1,x,y,69,-1] is acceptable where 1 <= x,y <= 10^9

Example 5:

Input: rains = [10,20,20]
Output: []
Explanation: It will rain over lake 20 two consecutive days. There is no chance to dry any lake.

Constraints:

1 <= rains.length <= 10^5
0 <= rains[i] <= 10^9

Solution: Binary Search

Store the days we can dry a lake in a treeset.
Store the last day when a lake becomes full in a hashtable.
Whenever we encounter a full lake, try to find the first available day that we can dry it. If no such day, return no answer.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> avoidFlood(vector<int>& rains) {

const int n = rains.size();

vector<int> ans(n, -1);

unordered_map<int, int> full; // lake -> day

set<int> dry; // days we can dry lakes.

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

const int lake = rains[i];

if (lake > 0) {

if (full.count(lake)) {

// Find the first day we can dry it.

auto it = dry.upper_bound(full[lake]);

if (it == end(dry)) return {};

ans[*it] = lake;

dry.erase(it);

}

full[lake] = i;

} else {

dry.insert(i);

ans[i] = 1;

}

return ans;

}

};

花花酱 LeetCode 1482. Minimum Number of Days to Make m Bouquets

By zxi on June 14, 2020

Given an integer array bloomDay, an integer m and an integer k.

We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example 1:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

Example 2:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.

Example 3:

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here's the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.

Example 4:

Input: bloomDay = [1000000000,1000000000], m = 1, k = 1
Output: 1000000000
Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.

Example 5:

Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
Output: 9

Constraints:

bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n

Solution: Binary Search

Find the smallest day D that we can make at least m bouquets using binary search.

at a given day, we can check how many bouquets we can make in O(n)

Time complexity: O(nlog(max(days))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minDays(vector<int>& bloomDay, int m, int k) {

const auto [lo, hi] = minmax_element(begin(bloomDay), end(bloomDay));

const int kInf = *hi + 1;

int l = *lo;

int r = kInf;

// Return the number of bouquets we can get at day D.

auto getBouquets = [&](int D) {

int ans = 0;

int cur = 0;

for (int d : bloomDay) {

if (d > D) {

cur = 0;

} else if (++cur == k) {

++ans;

cur = 0;

}

return ans;

};

while (l < r) {

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

// Find smallest day that bouquets >= m.

if (getBouquets(mid) >= m)

r = mid;

else

l = mid + 1;

}

return l >= kInf ? -1 : l;

}

};

花花酱 LeetCode 1481. Least Number of Unique Integers after K Removals

By zxi on June 14, 2020

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

Solution: Greedy

Count the frequency of each unique number. Sort by frequency, remove items with lowest frequency first.

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

C++

// Author: Huahua

class Solution {

public:

int findLeastNumOfUniqueInts(vector<int>& arr, int k) {

unordered_map<int, int> c;

for (int x : arr) ++c[x];

vector<int> m; // freq

for (const auto [x, f] : c)

m.push_back(f);

sort(begin(m), end(m));

int ans = m.size();

int i = 0;

while (k--) {

if (--m[i] == 0) {

++i;

--ans;

}

return ans;

}

};

花花酱 LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

By zxi on June 13, 2020

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

Example 4:

Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.

Example 5:

Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 1000
1 <= target <= 10^8

Solution: Sliding Window + Best so far

Use a sliding window to maintain a subarray whose sum is <= target
When the sum of the sliding window equals to target, we found a subarray [s, e]
Update ans with it’s length + shortest subarray which ends before s.
We can use an array to store the shortest subarray which ends before s.

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

C++

// Author: Huahua

class Solution {

public:

int minSumOfLengths(vector<int>& arr, int target) {

constexpr int kInf = 1e9;

const int n = arr.size();

// min_lens[i] := min length of a valid subarray ends or before i.

vector<int> min_lens(n, kInf);

int ans = kInf;

int sum = 0;

int s = 0;

int min_len = kInf;

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

sum += arr[e];

while (sum > target) sum -= arr[s++];

if (sum == target) {

const int cur_len = e - s + 1;

if (s > 0 && min_lens[s - 1] != kInf)

ans = min(ans, cur_len + min_lens[s - 1]);

min_len = min(min_len, cur_len);

}

min_lens[e] = min_len;

}

return ans >= kInf ? -1 : ans;

}

};