Amount of New Area Painted Each Day solution and explanation
Google
8 more videos on this problem
AMOUNT OF NEW AREA PAINTED EACH DAY | LEETCODE # 2158 | PYTHON SIMPLE SOLUTIONCracking FAANG · 15:52 · 5K views
Leetcode 2158 - Amount of New Area Painted Each DayEmerald Bay · 13:12 · 1K views
2158. Amount of New Area Painted Each Day (Leetcode Hard)Programming Live with Larry · 15:03 · 942 views
Leetcode 2158DailyLeetcode · 13:42 · 432 views
Leetcode 2158: Amount of new area painted each day JS solutionJack Chen · 4:34 · 124 views
南湾提款机 leetcode 2158夏天 · 56:40 · 71 views
leetcode 2158 Amount of New Area Painted Each Day step by stepSharda Learning Center · 8:45 · 36 views
Leetcode 2158 amount of new area painted each dayb1ank · 9:21 · 23 views
LeetCode 2158: Amount of New Area Painted Each DayAlitaCode · 27:36 · 4 views
The problem
There is a long and thin painting that can be represented by a number line. You are given a 0-indexed 2D integer array paint of length n, where paint[i] = [starti, endi]. This means that on the ith day you need to paint the area between starti and endi.
Painting the same area multiple times will create an uneven painting so you only want to paint each area of the painting at most once.
Return an integer array worklog of length n, where worklog[i] is the amount of new area that you painted on the ith day.
Example 1:
Input: paint = [[1,4],[4,7],[5,8]] Output: [3,3,1] Explanation: On day 0, paint everything between 1 and 4. The amount of new area painted on day 0 is 4 - 1 = 3. On day 1, paint everything between 4 and 7. The amount of new area painted on day 1 is 7 - 4 = 3. On day 2, paint everything between 7 and 8. Everything between 5 and 7 was already painted on day 1. The amount of new area painted on day 2 is 8 - 7 = 1.
Example 2:
Input: paint = [[1,4],[5,8],[4,7]] Output: [3,3,1] Explanation: On day 0, paint everything between 1 and 4. The amount of new area painted on day 0 is 4 - 1 = 3. On day 1, paint everything between 5 and 8. The amount of new area painted on day 1 is 8 - 5 = 3. On day 2, paint everything between 4 and 5. Everything between 5 and 7 was already painted on day 1. The amount of new area painted on day 2 is 5 - 4 = 1.
Example 3:
Input: paint = [[1,5],[2,4]] Output: [4,0] Explanation: On day 0, paint everything between 1 and 5. The amount of new area painted on day 0 is 5 - 1 = 4. On day 1, paint nothing because everything between 2 and 4 was already painted on day 0. The amount of new area painted on day 1 is 0.
Constraints:
1 <= paint.length <= 105paint[i].length == 20 <= starti < endi <= 5 * 104
Approach overview
Problem Overview: Each day you paint an interval [start, end) on a long wall. Some sections may already be painted from previous days. For every day, return how much new area gets painted that wasn’t covered before.
Approach 1: Direct Simulation with Painted Array (Brute Force) (Time: O(n * R), Space: O(R))
Track every painted unit using a boolean array representing the wall. For each day’s interval, iterate from start to end - 1. If a position is not painted yet, mark it painted and increase the count for that day. This approach is simple but inefficient when intervals are large because you repeatedly scan already-painted cells. It works only when the coordinate range is small.
Approach 2: Ordered Set / Interval Merging (Time: O(n log n), Space: O(n))
Store previously painted segments in an ordered structure such as a TreeMap, TreeSet, or balanced BST. For a new interval, locate overlapping segments using ordered lookups. Skip regions that are already painted and count only the uncovered parts. Merge overlapping intervals afterward to maintain a disjoint set of painted segments. Each operation involves logarithmic searches and merges, giving overall O(n log n) complexity. This method relies on interval management and ordered traversal, commonly implemented using an Ordered Set.
Approach 3: Segment Tree with Lazy Propagation (Time: O(n log R), Space: O(R))
Model the wall as a range and build a Segment Tree where each node tracks how much of its interval is already painted. For each day, query how many cells are currently painted inside [start, end), then update the segment tree to mark the entire range as painted. The difference between interval length and already-painted cells gives the new area for that day. This structure efficiently supports range queries and updates on large coordinate ranges.
Recommended for interviews: The ordered interval approach is usually the cleanest solution. It shows you understand interval merging, logarithmic lookups, and efficient state tracking using data structures like arrays and ordered maps. Brute force demonstrates the baseline idea, but the ordered structure or segment tree solution shows the optimization interviewers expect.
Solution
class Node:
def __init__(self, l, r):
self.left = None
self.right = None
self.l = l
self.r = r
self.mid = (l + r) >> 1
self.v = 0
self.add = 0
class SegmentTree:
def __init__(self):
self.root = Node(1, 10**5 + 10)
def modify(self, l, r, v, node=None):
if l > r:
return
if node is None:
node = self.root
if node.l >= l and node.r <= r:
node.v = node.r - node.l + 1
node.add = v
return
self.pushdown(node)
if l <= node.mid:
self.modify(l, r, v, node.left)
if r > node.mid:
self.modify(l, r, v, node.right)
self.pushup(node)
def query(self, l, r, node=None):
if l > r:
return 0
if node is None:
node = self.root
if node.l >= l and node.r <= r:
return node.v
self.pushdown(node)
v = 0
if l <= node.mid:
v += self.query(l, r, node.left)
if r > node.mid:
v += self.query(l, r, node.right)
return v
def pushup(self, node):
node.v = node.left.v + node.right.v
def pushdown(self, node):
if node.left is None:
node.left = Node(node.l, node.mid)
if node.right is None:
node.right = Node(node.mid + 1, node.r)
if node.add:
left, right = node.left, node.right
left.v = left.r - left.l + 1
right.v = right.r - right.l + 1
left.add = node.add
right.add = node.add
node.add = 0
class Solution:
def amountPainted(self, paint: List[List[int]]) -> List[int]:
tree = SegmentTree()
ans = []
for i, (start, end) in enumerate(paint):
l, r = start + 1, end
v = tree.query(l, r)
ans.append(r - l + 1 - v)
tree.modify(l, r, 1)
return ansclass Node {
Node left;
Node right;
int l;
int r;
int mid;
int v;
int add;
public Node(int l, int r) {
this.l = l;
this.r = r;
this.mid = (l + r) >> 1;
}
}
class SegmentTree {
private Node root = new Node(1, 100010);
public SegmentTree() {
}
public void modify(int l, int r, int v) {
modify(l, r, v, root);
}
public void modify(int l, int r, int v, Node node) {
if (l > r) {
return;
}
if (node.l >= l && node.r <= r) {
node.v = node.r - node.l + 1;
node.add = v;
return;
}
pushdown(node);
if (l <= node.mid) {
modify(l, r, v, node.left);
}
if (r > node.mid) {
modify(l, r, v, node.right);
}
pushup(node);
}
public int query(int l, int r) {
return query(l, r, root);
}
public int query(int l, int r, Node node) {
if (l > r) {
return 0;
}
if (node.l >= l && node.r <= r) {
return node.v;
}
pushdown(node);
int v = 0;
if (l <= node.mid) {
v += query(l, r, node.left);
}
if (r > node.mid) {
v += query(l, r, node.right);
}
return v;
}
public void pushup(Node node) {
node.v = node.left.v + node.right.v;
}
public void pushdown(Node node) {
if (node.left == null) {
node.left = new Node(node.l, node.mid);
}
if (node.right == null) {
node.right = new Node(node.mid + 1, node.r);
}
if (node.add != 0) {
Node left = node.left, right = node.right;
left.add = node.add;
right.add = node.add;
left.v = left.r - left.l + 1;
right.v = right.r - right.l + 1;
node.add = 0;
}
}
}
class Solution {
public int[] amountPainted(int[][] paint) {
SegmentTree tree = new SegmentTree();
int n = paint.length;
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int l = paint[i][0] + 1;
int r = paint[i][1];
int v = tree.query(l, r);
ans[i] = r - l + 1 - v;
tree.modify(l, r, 1);
}
return ans;
}
}class Node {
public:
Node* left;
Node* right;
int l;
int r;
int mid;
int v;
int add;
Node(int l, int r) {
this->l = l;
this->r = r;
this->mid = (l + r) >> 1;
this->left = this->right = nullptr;
v = add = 0;
}
};
class SegmentTree {
private:
Node* root;
public:
SegmentTree() {
root = new Node(1, 100010);
}
void modify(int l, int r, int v) {
modify(l, r, v, root);
}
void modify(int l, int r, int v, Node* node) {
if (l > r) return;
if (node->l >= l && node->r <= r) {
node->v = node->r - node->l + 1;
node->add = v;
return;
}
pushdown(node);
if (l <= node->mid) modify(l, r, v, node->left);
if (r > node->mid) modify(l, r, v, node->right);
pushup(node);
}
int query(int l, int r) {
return query(l, r, root);
}
int query(int l, int r, Node* node) {
if (l > r) return 0;
if (node->l >= l && node->r <= r) return node->v;
pushdown(node);
int v = 0;
if (l <= node->mid) v += query(l, r, node->left);
if (r > node->mid) v += query(l, r, node->right);
return v;
}
void pushup(Node* node) {
node->v = node->left->v + node->right->v;
}
void pushdown(Node* node) {
if (!node->left) node->left = new Node(node->l, node->mid);
if (!node->right) node->right = new Node(node->mid + 1, node->r);
if (node->add) {
Node* left = node->left;
Node* right = node->right;
left->v = left->r - left->l + 1;
right->v = right->r - right->l + 1;
left->add = node->add;
right->add = node->add;
node->add = 0;
}
}
};
class Solution {
public:
vector<int> amountPainted(vector<vector<int>>& paint) {
int n = paint.size();
vector<int> ans(n);
SegmentTree* tree = new SegmentTree();
for (int i = 0; i < n; ++i) {
int l = paint[i][0] + 1;
int r = paint[i][1];
int v = tree->query(l, r);
ans[i] = r - l + 1 - v;
tree->modify(l, r, 1);
}
return ans;
}
};Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation with Painted Array | O(n * R) | O(R) | When coordinate range is very small and implementation simplicity matters |
| Ordered Set / Interval Merging | O(n log n) | O(n) | General case where intervals overlap frequently and efficient merging is required |
| Segment Tree with Lazy Propagation | O(n log R) | O(R) | When the coordinate range is large and many range queries/updates are needed |
Frequently asked questions
Is Amount of New Area Painted Each Day easy or hard?
Amount of New Area Painted Each Day is classified as a Hard problem because it requires efficient handling of overlapping intervals and large ranges. A naive simulation fails due to repeated work, so optimized data structures such as ordered sets or segment trees are required.
Amount of New Area Painted Each Day Python/Java solution
Python solutions typically use sorted structures or dictionaries with interval merging logic, while Java implementations often rely on TreeMap or TreeSet for ordered interval management. Both achieve O(n log n) complexity with careful overlap handling.
How to solve Amount of New Area Painted Each Day in O(n)?
An O(n) style solution can be achieved using a skip or next-pointer technique that jumps over already painted cells. Instead of revisiting painted positions, the algorithm links each painted index to the next unpainted index, similar to path compression. This ensures each position is processed at most once.
What is the best approach for Amount of New Area Painted Each Day?
The most practical solution uses an ordered set or balanced map to track disjoint painted intervals. For each new interval, you find overlapping segments, count only the uncovered parts, and merge intervals. This runs in O(n log n) time and O(n) space, which is efficient for large input sizes.
Is Amount of New Area Painted Each Day asked at Google/Amazon/Meta?
Interval tracking and range update problems like this appear in interviews at large tech companies including Google, Amazon, and Meta. The problem tests knowledge of interval merging, ordered maps, and advanced structures like segment trees.
What data structure is used in Amount of New Area Painted Each Day?
Common implementations use ordered sets or balanced binary search trees to store disjoint intervals. Some solutions also use segment trees for efficient range queries and updates. Both approaches manage overlapping intervals efficiently.
What is the time complexity of Amount of New Area Painted Each Day?
The optimal interval-merging or ordered set approach runs in O(n log n) time because each interval insertion and overlap lookup requires logarithmic operations. Space complexity is O(n) for storing disjoint painted intervals. Segment tree implementations typically run in O(n log R).