Posts tagged as “sweep line”

花花酱 LeetCode 2251. Number of Flowers in Full Bloom

By zxi on April 27, 2022

You are given a 0-indexed 2D integer array flowers, where flowers[i] = [start_i, end_i] means the i^th flower will be in full bloom from start_i to end_i (inclusive). You are also given a 0-indexed integer array persons of size n, where persons[i] is the time that the i^th person will arrive to see the flowers.

Return an integer array answer of size n, where answer[i] is the number of flowers that are in full bloom when the i^th person arrives.

Example 1:

Input: flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
Output: [1,2,2,2]
Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.

Example 2:

Input: flowers = [[1,10],[3,3]], persons = [3,3,2]
Output: [2,2,1]
Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.

Constraints:

1 <= flowers.length <= 5 * 10⁴
flowers[i].length == 2
1 <= start_i <= end_i <= 10⁹
1 <= persons.length <= 5 * 10⁴
1 <= persons[i] <= 10⁹

Solution: Prefix Sum + Binary Search

Use a treemap to store the counts (ordered by time t), when a flower begins to bloom at start, we increase m[start], when it dies at end, we decrease m[end+1]. prefix_sum[t] indicates the # of blooming flowers at time t.

For each people, use binary search to find the latest # of flowers before his arrival.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {

map<int, int> m{{0, 0}};

for (const auto& f : flowers)

++m[f[0]], --m[f[1] + 1];

int sum = 0;

for (auto& [t, c] : m)

c = sum += c;

vector<int> ans;

for (int t : persons)

ans.push_back(prev(m.upper_bound(t))->second);

return ans;

}

};

花花酱 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 1589. Maximum Sum Obtained of Any Permutation

By zxi on September 19, 2020

We have an array of integers, nums, and an array of requests where requests[i] = [start_i, end_i]. The i^th request asks for the sum of nums[start_i] + nums[start_i + 1] + ... + nums[end_i - 1] + nums[end_i]. Both start_i and end_i are 0-indexed.

Return the maximum total sum of all requests among all permutations of nums.

Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
Output: 19
Explanation: One permutation of nums is [2,1,3,4,5] with the following result: 
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
Total sum: 8 + 3 = 11.
A permutation with a higher total sum is [3,5,4,2,1] with the following result:
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
Total sum: 11 + 8 = 19, which is the best that you can do.

Example 2:

Input: nums = [1,2,3,4,5,6], requests = [[0,1]]
Output: 11
Explanation: A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].

Example 3:

Input: nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
Output: 47
Explanation: A permutation with the max total sum is [4,10,5,3,2,1] with request sums [19,18,10].

Constraints:

n == nums.length
1 <= n <= 10⁵
0 <= nums[i] <= 10⁵
1 <= requests.length <= 10⁵
requests[i].length == 2
0 <= start_i <= end_i < n

Solution: Greedy + Sweep line

Sort the numbers, and sort the frequency of each index, it’s easy to show largest number with largest frequency gives us max sum.

ans = sum(nums[i] * freq[i])

We can use sweep line to compute the frequency of each index in O(n) time and space.

For each request [start, end] : ++freq[start], –freq[end + 1]

Then the prefix sum of freq array is the frequency for each index.

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

C++

class Solution {

public:

int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

vector<long> freq(n);

for (const auto& r : requests) {

++freq[r[0]];

if (r[1] + 1 < n) --freq[r[1] + 1];

}

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

freq[i] += freq[i - 1];

sort(begin(freq), end(freq));

sort(begin(nums), end(nums));

long ans = 0;

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

ans += freq[i] * nums[i];

return ans % kMod;

}

};

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

By zxi on June 23, 2018

Problem

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 10⁴ balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_endbursts by an arrow shot at x if x_start ≤ x ≤ x_end. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Solution: Sweep Line

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

int findMinArrowShots(vector<pair<int, int>>& points) {

if (points.empty()) return 0;

sort(points.begin(), points.end(),

[&](const pair<int,int>& a, const pair<int,int>& b){

return a.second < b.second;

});

int right = points.front().second;

int ans = 1;

for (const auto& point : points) {

if (point.first > right) {

right = point.second;

++ans;

}

return ans;

}

};

Posts tagged as “sweep line”

花花酱 LeetCode 2251. Number of Flowers in Full Bloom

Solution: Prefix Sum + Binary Search

C++

花花酱 LeetCode 1871. Jump Game VII

Solution 1: TreeSet /Dequq + Binary Search

C++/set

C++/deque

Solution 2: Queue

C++/set

花花酱 LeetCode 1589. Maximum Sum Obtained of Any Permutation

Solution: Greedy + Sweep line

C++

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

Problem

Solution: Sweep Line

Related Problems

花花酱 LeetCode 759. Employee Free Time