Huahua’s Tech Road

花花酱 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 2105. Watering Plants II

By zxi on December 12, 2021

Problem

Solution: Simulation w/ Two Pointers

Simulate the watering process.

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

C++

// Author: Huahua

class Solution {

public:

int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {

const int n = plants.size();

int ans = 0;

for (int l = 0, r = n - 1, A = capacityA, B = capacityB; l <= r; ++l, --r) {

if (l == r)

return ans += max(A, B) < plants[l];

if ((A -= plants[l]) < 0)

A = capacityA - plants[l], ++ans;

if ((B -= plants[r]) < 0)

B = capacityB - plants[r], ++ans;

}

return ans;

}

};

花花酱 LeetCode 2104. Sum of Subarray Ranges

By zxi on December 12, 2021

Problem

Solution 0: Brute force [TLE]

Enumerate all subarrays, for each one, find min and max.

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

Solution 1: Prefix min/max

We can use prefix technique to extend the array while keep tracking the min/max of the subarray.

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

C++

// Author: Huahua

class Solution {

public:

long long subArrayRanges(vector<int>& nums) {

const int n = nums.size();

long long ans = 0;

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

int lo = nums[i];

int hi = nums[i];

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

lo = min(lo, nums[j]);

hi = max(hi, nums[j]);

ans += (hi - lo);

}

return ans;

}

};

Solution 2: Monotonic stack

This problem can be reduced to 花花酱 LeetCode 907. Sum of Subarray Minimums

Just need to run twice one for sum of mins and another for sum of maxs.

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

C++

// Author: Huahua

class Solution {

public:

long long subArrayRanges(vector<int>& nums) {

const int n = nums.size();

auto sumOf = [&](function<bool(int, int)> op) {

long long ans = 0;

stack<int> s;

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

while (!s.empty() and (i == n or op(nums[s.top()], nums[i]))) {

long long k = s.top(); s.pop();

long long j = s.empty() ? -1 : s.top();

ans += nums[k] * (i - k) * (k - j);

}

s.push(i);

}

return ans;

};

return sumOf(less<int>()) - sumOf(greater<int>());

}

};

花花酱 LeetCode 2103. Rings and Rods

By zxi on December 12, 2021

Problem

Solution: Hashset

Use 10 hashsets to track the status of each rod, check whether it contains three unique elements (R,G,B).

Time complexity: O(n)
Space complexity: O(10*3)

C++

// Author: Huahua

class Solution {

public:

int countPoints(string rings) {

constexpr int kRods = 10;

vector<unordered_set<char>> s(kRods);

for (int i = 0; i < rings.size(); i += 2)

s[rings[i + 1] - '0'].insert(rings[i]);

int ans = 0;

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

if (s[i].size() == 3)

++ans;

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);

};

Huahua's Tech Road

Solution 1: Range sum query

C++

Solution 2: Sliding Window

C++

C++

Solution 0: Brute force [TLE]

Solution 1: Prefix min/max

C++

Solution 2: Monotonic stack

C++

Solution: Hashset

C++

Solution: TreeSet w/ Iterator

C++