Posts tagged as “hard”

花花酱 LeetCode 2106. Maximum Fruits Harvested After at Most K Steps

By zxi on December 12, 2021

Problem

Solution 1: Range sum query

Assuming we can collect fruits in range [l, r], we need a fast query to compute the sum of those fruits.

Given startPos and k, we have four options:
1. move i steps to the left
2. move i steps to the left and k – i steps to the right.
3. move i steps to the right
4. move i steps to the right and k – i steps to the left.

We enumerate i steps and calculate maximum range [l, r] covered by each option, and collect all the fruit in that range.

Time complexity: O(m + k)
Space complexity: O(m)
where m = max(max(pos), startPos)

C++

// Author: Huahua

class Solution {

public:

int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {

const int m = max(startPos, (*max_element(begin(fruits), end(fruits)))[0]);

vector<int> sums(m + 2);

for (int i = 0, j = 0; i <= m; ++i) {

sums[i + 1] += sums[i];

while (j < fruits.size() && fruits[j][0] == i)

sums[i + 1] += fruits[j++][1];

}

int ans = 0;

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

if (startPos - s >= 0) {

int l = startPos - s;

int r = min(max(startPos, l + (k - s)), m);

ans = max(ans, sums[r + 1] - sums[l]);

}

if (startPos + s <= m) {

int r = startPos + s;

int l = max(0, min(startPos, r - (k - s)));

ans = max(ans, sums[r + 1] - sums[l]);

}

return ans;

}

};

Solution 2: Sliding Window

Maintain a window [l, r] such that the steps to cover [l, r] from startPos is less or equal to k.

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

C++

// Author: Huahua

class Solution {

public:

int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {

auto steps = [&](int l, int r) {

if (r <= startPos)

return startPos - l;

else if (l >= startPos)

return r - startPos;

else

return min(startPos + r - 2 * l, 2 * r - startPos - l);

};

int ans = 0;

for (int r = 0, l = 0, cur = 0; r < fruits.size(); ++r) {

cur += fruits[r][1];

while (l <= r && steps(fruits[l][0], fruits[r][0]) > k)

cur -= fruits[l++][1];

ans = max(ans, cur);

}

return ans;

}

};

花花酱 LeetCode 2102. Sequentially Ordinal Rank Tracker

By zxi on December 12, 2021

A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

Adding scenic locations, one at a time.
Querying the i^th best location of all locations already added, where i is the number of times the system has been queried (including the current query).
- For example, when the system is queried for the 4^th time, it returns the 4^th best location of all locations already added.

Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:

SORTracker() Initializes the tracker system.
void add(string name, int score) Adds a scenic location with name and score to the system.
string get() Queries and returns the i^th best location, where i is the number of times this method has been invoked (including this invocation).

Example 1:

Input

["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]

[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]

Output

[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

Explanation

SORTracker tracker = new SORTracker(); // Initialize the tracker system.

tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.

tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.

tracker.get(); // The sorted locations, from best to worst, are: branford, bradford.

// Note that branford precedes bradford due to its higher score (3 > 2).

// This is the 1st time get() is called, so return the best location: "branford".

tracker.add("alps", 2); // Add location with name="alps" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford.

// Note that alps precedes bradford even though they have the same score (2).

// This is because "alps" is lexicographically smaller than "bradford".

// Return the 2nd best location "alps", as it is the 2nd time get() is called.

tracker.add("orland", 2); // Add location with name="orland" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford, orland.

// Return "bradford", as it is the 3rd time get() is called.

tracker.add("orlando", 3); // Add location with name="orlando" and score=3 to the system.

tracker.get(); // Sorted locations: branford, orlando, alps, bradford, orland.

// Return "bradford".

tracker.add("alpine", 2); // Add location with name="alpine" and score=2 to the system.

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "bradford".

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "orland".

Constraints:

name consists of lowercase English letters, and is unique among all locations.
1 <= name.length <= 10
1 <= score <= 10⁵
At any time, the number of calls to get does not exceed the number of calls to add.
At most 4 * 10⁴ calls in total will be made to add and get.

Solution: TreeSet w/ Iterator

Use a treeset to store all the entries and use a iterator that points to the entry to return. When inserting a new entry into the tree, if it’s higher than the current element then let the iterator go backward one step.

Time complexity: add O(logn) / get O(1)

C++

// Author: Huahua

class SORTracker {

public:

SORTracker() {}

void add(string name, int score) {

if (*s.emplace(-score, name).first < *cit) --cit;

}

string get() {

return (cit++)->second;

}

private:

set<pair<int, string>> s;

// Note: cit points to begin(s) after first insertion.

set<pair<int, string>>::const_iterator cit = end(s);

};

花花酱 LeetCode 76. Minimum Window Substring

By zxi on November 29, 2021

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10⁵
s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Solution: Hashtable + Two Pointers

Use a hashtable to store the freq of characters we need to match for t.

Use (i, j) to track a subarray that contains all the chars in t.

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

C++

// Author: Huahua

class Solution {

public:

string minWindow(string s, string t) {

const int n = s.length();

const int m = t.length();

vector<int> freq(128);

for (char c : t) ++freq[c];

int start = 0;

int l = INT_MAX;

for (int i = 0, j = 0, left = m; j < n; ++j) {

if (--freq[s[j]] >= 0) --left;

while (left == 0) {

if (j - i + 1 < l) {

l = j - i + 1;

start = i;

}

if (++freq[s[i++]] == 1) ++left;

}

return l == INT_MAX ? "" : s.substr(start, l);

}

};

花花酱 LeetCode 123. Best Time to Buy and Sell Stock III

By zxi on November 28, 2021

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Example 4:

Input: prices = [1]
Output: 0

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

Solution: DP

A special case of 花花酱 LeetCode 188. Best Time to Buy and Sell Stock IV where k = 2.

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

C++

// Author: Huahua

class Solution {

public:

int maxProfit(vector<int>& prices) {

constexpr int k = 2;

const int n = prices.size();

vector<int> balance(k + 1, INT_MIN);

vector<int> profit(k + 1, 0);

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

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

balance[j] = max(balance[j], profit[j - 1] - prices[i]);

profit[j] = max(profit[j], balance[j] + prices[i]);

}

return profit[k];

}

};

花花酱 LeetCode 2092. Find All People With Secret

By zxi on November 28, 2021

You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [x_i, y_i, time_i] indicates that person x_i and person y_i have a meeting at time_i. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person x_i has the secret at time_i, then they will share the secret with person y_i, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.

Example 1:

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Example 2:

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.

Example 3:

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3.
Note that person 2 can share the secret at the same time as receiving it.
At time 2, person 3 shares the secret with person 4.
Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

Example 4:

Input: n = 6, meetings = [[0,2,1],[1,3,1],[4,5,1]], firstPerson = 1
Output: [0,1,2,3]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 0 shares the secret with person 2, and person 1 shares the secret with person 3.
Thus, people 0, 1, 2, and 3 know the secret after all the meetings.

Constraints:

2 <= n <= 10⁵
1 <= meetings.length <= 10⁵
meetings[i].length == 3
0 <= x_i, y_i<= n - 1
x_i != y_i
1 <= time_i <= 10⁵
1 <= firstPerson <= n - 1

Solution: Union Find

Sorting meetings by time.

At each time stamp, union people who meet.
Key step: “un-union” people if they DO NOT connected to 0 / known the secret after each timestamp.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {

map<int, vector<pair<int, int>>> events;

for (const auto& m : meetings)

events[m[2]].emplace_back(m[0], m[1]);

vector<int> p(n);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return p[x] == x ? x : (p[x] = find(p[x]));

};

p[firstPerson] = 0;

for (const auto& [t, s] : events) {

for (const auto [u, v] : s)

p[find(u)] = find(v);

for (const auto [u, v] : s) {

if (find(u) != find(0)) p[u] = u;

if (find(v) != find(0)) p[v] = v;

}

vector<int> ans;

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

if (find(i) == find(0)) ans.push_back(i);

return ans;

}

};

Posts tagged as “hard”

花花酱 LeetCode 2106. Maximum Fruits Harvested After at Most K Steps

Problem

Solution 1: Range sum query

C++

Solution 2: Sliding Window

C++

花花酱 LeetCode 2102. Sequentially Ordinal Rank Tracker

Solution: TreeSet w/ Iterator

C++

花花酱 LeetCode 76. Minimum Window Substring

Solution: Hashtable + Two Pointers

C++

花花酱 LeetCode 123. Best Time to Buy and Sell Stock III

Solution: DP

C++

花花酱 LeetCode 2092. Find All People With Secret

Solution: Union Find

C++

Related Problems