LeetCode 1943: Describe the Painting Solution

Master LeetCode problem 1943 (Describe the Painting), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1943. Describe the Painting

Medium

Array Hash Table Sorting Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can iterate through the given segments and maintain a mapping of start points and end points to their corresponding colors. We can then merge overlapping segments and calculate the sum of mixed colors for each non-overlapping segment. Finally, we construct the painting based on these non-overlapping segments.

Initialize an empty hashmap to store the mapping of start and end points to colors.
Iterate through the segments and update the mapping with the corresponding colors.
Sort the unique start and end points in ascending order.
Initialize variables for the current colors and their sums.
Iterate through the sorted points and update the current colors and sums accordingly.
Generate the non-overlapping segments with their mixed color sums.
Return the resulting painting.

Time Complexity: O(nlogn) where n is the number of segments. Space Complexity: O(n) for storing the mapping and non-overlapping segments.

Solution Code

import java.util.*;

class Solution {
    public int[][] describePainting(int[][] segments) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] segment : segments) {
            map.put(segment[0], map.getOrDefault(segment[0], 0) + segment[2]);
            map.put(segment[1], map.getOrDefault(segment[1], 0) - segment[2]);
        }

        List<Integer> points = new ArrayList<>(map.keySet());
        Collections.sort(points);

        int currentSum = 0;
        int currentColor = 0;
        List<int[]> result = new ArrayList<>();

        for (int i = 0; i < points.size(); i++) {
            int point = points.get(i);
            if (currentColor > 0) {
                result.add(new int[]{points.get(i - 1), point, currentSum});
            }
            currentSum += map.get(point);
            currentColor = currentSum > 0 ? currentSum : 0;
        }

        return result.toArray(new int[0][]);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1943 (Describe the Painting)?

This page provides optimized solutions for LeetCode problem 1943 (Describe the Painting) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1943 (Describe the Painting)?

The time complexity for LeetCode 1943 (Describe the Painting) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1943 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1943 in Java, C++, or Python.

Back to LeetCode Solutions