We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Intersections on the Chart

Number: 3315

Difficulty: Hard

Paid? Yes

Companies: Microsoft, Meta

Problem Description

Given an array y representing the y‐coordinates of n points (with x‑coordinates 1, 2, …, n) that are connected sequentially by line segments (with no horizontal segments), an infinitely long horizontal line is drawn. The task is to choose a y = c such that the line “cuts” the chart at as many points as possible. In other words, for each segment connecting (i, y[i]) and (i+1, y[i+1]), if c lies strictly between y[i] and y[i+1], then it counts as an intersection. Return the maximum intersection count that can be attained by any horizontal line.

Key Insights

  • The chart is formed by connecting consecutive points; each segment is strictly monotonic (since no two consecutive points share the same y‐value).
  • Every segment creates an open interval (min(y[i], y[i+1]), max(y[i], y[i+1])). A horizontal line at c will intersect the segment if and only if c lies strictly in that interval.
  • The problem reduces to choosing a c that lies in as many of these open intervals as possible.
  • This is analogous to the “maximum overlapping intervals” problem. We can use a sweep line algorithm.
  • By processing “start” events (the lower y of the segment) and “end” events (the higher y of the segment) carefully (remembering that endpoints are not included), we can find the maximum count of intervals overlapping any gap between distinct endpoints.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting of 2*(n-1) events. Space Complexity: O(n) for storing the events.

Solution

We first convert each segment connecting consecutive points into an interval (a, b) where a = min(y[i], y[i+1]) and b = max(y[i], y[i+1]). A horizontal line crosses the segment if its y = c satisfies a < c < b.

We then create two kinds of events:

  • A “start” event at a indicating that for any candidate c > a, this segment will count.
  • An “end” event at b indicating that for any candidate c ≥ b, this segment no longer counts.

We sort these events by coordinate. When processing events at the same coordinate, we subtract (process end events) before adding (process start events) because endpoints are not included in the open interval. As we sweep through the events, the maximum active count (active intervals that cover a gap between two event coordinates) corresponds to the maximum intersections with the chart.

Code Solutions

# Python solution for Maximum Number of Intersections on the Chart

class Solution:
    def maximumIntersection(self, y):
        # List to hold events: each event is (coordinate, type)
        # type: -1 for an end event, +1 for a start event.
        events = []
        
        n = len(y)
        # Create events for each segment between y[i] and y[i+1]
        for i in range(n - 1):
            a = min(y[i], y[i + 1])
            b = max(y[i], y[i + 1])
            events.append((a, +1))  # start event; interval (a, b) becomes active after a
            events.append((b, -1))  # end event; interval (a, b) stops being active at b
            
        # Sort events by coordinate; if coordinates tie, process end (-1) events first
        events.sort(key=lambda x: (x[0], x[1]))
        
        active = 0       # current count of active intervals
        max_active = 0   # maximum count of active intervals found
        prev_coordinate = None
        
        i = 0
        while i < len(events):
            current_coordinate = events[i][0]
            # If there is a gap between previous coordinate and current,
            # any candidate c in that gap will have count = active.
            if prev_coordinate is not None and prev_coordinate < current_coordinate:
                max_active = max(max_active, active)
            
            # Process all events with the same coordinate.
            # End events (-1) should be processed before start events (+1).
            end_events = 0
            start_events = 0
            while i < len(events) and events[i][0] == current_coordinate:
                if events[i][1] == -1:
                    end_events += 1
                else:
                    start_events += 1
                i += 1
            # Remove those intervals that end at this coordinate.
            active -= end_events
            # Then add intervals that start at this coordinate.
            active += start_events
            prev_coordinate = current_coordinate
        
        return max_active

# Example usage
sol = Solution()
print(sol.maximumIntersection([1,2,1,2,1,3,2]))  # Output: 5
print(sol.maximumIntersection([2,1,3,4,5]))        # Output: 2
← Back to All Questions