Huahua’s Tech Road

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

};

花花酱 LeetCode 2101. Detonate the Maximum Bombs

By zxi on December 12, 2021

You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.

The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [x_i, y_i, r_i]. x_i and y_i denote the X-coordinate and Y-coordinate of the location of the i^th bomb, whereas r_i denotes the radius of its range.

You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

Example 1:

Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation:
The above figure shows the positions and ranges of the 2 bombs.
If we detonate the left bomb, the right bomb will not be affected.
But if we detonate the right bomb, both bombs will be detonated.
So the maximum bombs that can be detonated is max(1, 2) = 2.

Example 2:

Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation:
Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.

Example 3:

Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output: 5
Explanation:
The best bomb to detonate is bomb 0 because:
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
Thus all 5 bombs are detonated.

Constraints:

1 <= bombs.length <= 100
bombs[i].length == 3
1 <= x_i, y_i, r_i <= 10⁵

Solution: Simulation w/ BFS

Enumerate the bomb to detonate, and simulate the process using BFS.

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

C++

// Author: Huahua

class Solution {

public:

int maximumDetonation(vector<vector<int>>& bombs) {

const int n = bombs.size();

auto check = [&](int i, int j) -> bool {

long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];

long x2 = bombs[j][0], y2 = bombs[j][1], r2 = bombs[j][2];

return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r1 * r1);

};

int ans = 0;

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

int count = 0;

queue<int> q{{s}};

vector<int> seen(n);

seen[s] = 1;

while (!q.empty()) {

++count;

int i = q.front(); q.pop();

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

if (check(i, j) && !seen[j]++)

q.push(j);

}

ans = max(ans, count);

}

return ans;

}

};

花花酱 LeetCode 2100. Find Good Days to Rob the Bank

By zxi on December 12, 2021

You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the i^th day. The days are numbered starting from 0. You are also given an integer time.

The i^th day is a good day to rob the bank if:

There are at least time days before and after the i^th day,
The number of guards at the bank for the time days before i are non-increasing, and
The number of guards at the bank for the time days after i are non-decreasing.

More formally, this means day i is a good day to rob the bank if and only if security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

Return a list of all days (0-indexed) that are good days to rob the bank. The order that the days are returned in does not matter.

Example 1:

Input: security = [5,3,3,3,5,6,2], time = 2
Output: [2,3]
Explanation:
On day 2, we have security[0] >= security[1] >= security[2] <= security[3] <= security[4].
On day 3, we have security[1] >= security[2] >= security[3] <= security[4] <= security[5].
No other days satisfy this condition, so days 2 and 3 are the only good days to rob the bank.

Example 2:

Input: security = [1,1,1,1,1], time = 0
Output: [0,1,2,3,4]
Explanation:
Since time equals 0, every day is a good day to rob the bank, so return every day.

Example 3:

Input: security = [1,2,3,4,5,6], time = 2
Output: []
Explanation:
No day has 2 days before it that have a non-increasing number of guards.
Thus, no day is a good day to rob the bank, so return an empty list.

Example 4:

Input: security = [1], time = 5
Output: []
Explanation:
No day has 5 days before and after it.
Thus, no day is a good day to rob the bank, so return an empty list.

Constraints:

1 <= security.length <= 10⁵
0 <= security[i], time <= 10⁵

Solution: Pre-Processing

Pre-compute the non-increasing days at days[i] and the non-decreasing days at days[i] using prefix and suffix arrays.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> goodDaysToRobBank(vector<int>& security, int time) {

const int n = security.size();

vector<int> before(n);

vector<int> after(n);

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

before[i] = security[i - 1] >= security[i] ? before[i - 1] + 1 : 0;

for (int i = n - 2; i >= 0; --i)

after[i] = security[i + 1] >= security[i] ? after[i + 1] + 1 : 0;

vector<int> ans;

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

if (before[i] >= time && after[i] >= time)

ans.push_back(i);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2104. Sum of Subarray Ranges

Problem

Solution 0: Brute force [TLE]

Solution 1: Prefix min/max

C++

Solution 2: Monotonic stack

C++

花花酱 LeetCode 2103. Rings and Rods

Solution: Hashset

C++

花花酱 LeetCode 2102. Sequentially Ordinal Rank Tracker

Solution: TreeSet w/ Iterator

C++

花花酱 LeetCode 2101. Detonate the Maximum Bombs

Solution: Simulation w/ BFS

C++

花花酱 LeetCode 2100. Find Good Days to Rob the Bank

Solution: Pre-Processing

C++