MediumNo. 1943
Describe the Painting — LeetCode 1943 Python Solution
- Pattern
- Prefix Sum
- Topics
- Array, Hash Table, Prefix Sum, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
There is a long and thin painting that can be represented by a number line. The painting was painted with multiple overlapping segments where each segment was painted with a unique color.
Example
- Input
- segments = [[1,4,5],[4,7,7],[1,7,9]]
- Output
- [[1,4,14],[4,7,16]]
- Explanation
- The painting can be described as follows:
Python solution
class Solution:
def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
d = defaultdict(int)
for l, r, c in segments:
d[l] += c
d[r] -= c
s = sorted([[k, v] for k, v in d.items()])
n = len(s)
for i in range(1, n):
s[i][1] += s[i - 1][1]
return [[s[i][0], s[i + 1][0], s[i][1]] for i in range(n - 1) if s[i][1]]Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 1943. Describe the Painting is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2251 | Number of Flowers in Full Bloom | Hard |
| 0049 | Group Anagrams | Medium |
| 0169 | Majority Element | Easy |
| 0217 | Contains Duplicate | Easy |
| 0229 | Majority Element II | Medium |
| 0268 | Missing Number | Easy |
Frequently asked questions
- How hard is LeetCode 1943. Describe the Painting?
LeetCode 1943. Describe the Painting is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1943. Describe the Painting?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1943. Describe the Painting?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1943. Describe the Painting cover?
LeetCode 1943. Describe the Painting is tagged Array, Hash Table, Prefix Sum and Sorting on LeetCode.