LeetCode

Editorial: LeetCode 1943 Describe the Painting

Editorial: LeetCode 1943 Describe the Painting

https://leetcode.com/problems/describe-the-painting/ from Google

Thinking process:

Looking at the limit of the inputs, looks like we can use sweep line, which is also one of the most popular algorithm in Google’s interview. The concept is easy. We first scan all the inputs to find the left most point and right most point. This is just an optimization. We can sweep the whole range as well (from 1 to 10^5), but it’s slower.

1int start = 1e5, end = 0;
2for (int i=0; i<S; i++) {
3    start = min(start, segments[i][0]);
4    end = max(end, segments[i][1]);
5}

After getting this two points, we allocate points to represent all the points along the line from start to end. For each point, if there’s a segment starting from the point, we add the color. Then we subtract the color at the end of the segment. This is the main idea of the sweep line, where we record some value at the beginning of the segment, and remove the value at the end of the segment. In this way, when we sweep the whole line, we can know if there’s a color on it or not.

1vector<ll> point(end+1);
2vector<bool> isEnd(end+1);
3for (int i=0; i<S; i++) {
4    point[segments[i][0]] += segments[i][2];
5    point[segments[i][1]] -= segments[i][2];
6    isEnd[segments[i][1]] = true;
7}

One tricky thing is the isEnd. Although we only need to output the sum of the colors, we still need to distinguish if they are different colors or not. Since the value of the colors are distinct, we can just use isEnd to know if we need to start a new painting.

After that, we just loop through all the points and check if the current color sum is different or not. If it’s different or isEnd is true, we start a new painting.

Below is the code.

 1class Solution {
 2public:
 3    typedef long long ll;
 4    vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
 5        int S = segments.size();
 6        int start = 1e5, end = 0;
 7        for (int i=0; i<S; i++) {
 8            start = min(start, segments[i][0]);
 9            end = max(end, segments[i][1]);
10        }
11        vector<ll> point(end+1);
12        vector<bool> isEnd(end+1);
13        for (int i=0; i<S; i++) {
14            point[segments[i][0]] += segments[i][2];
15            point[segments[i][1]] -= segments[i][2];
16            isEnd[segments[i][1]] = true;
17        }
18        vector<vector<ll>> ans;
19        int left = 0;
20        ll cur = 0;
21        for (int i=start; i<=end; i++) {
22            if (isEnd[i] or point[i] != 0) {
23                ll nextValue = cur + point[i];
24                if (isEnd[i] or nextValue != cur) {
25                    if (cur) {
26                        ans.push_back({left, i, cur});
27                    }
28                    cur = nextValue;
29                    left = i;
30                }
31            }
32        }
33        return ans;
34    }
35};
comments powered by Disqus