Watch 2 video solutions for Maximum Number of Intersections on the Chart, a hard level problem involving Array, Math, Binary Indexed Tree. This walkthrough by Huifeng Guan has 1,128 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a line chart consisting of n points connected by line segments. You are given a 1-indexed integer array y. The kth point has coordinates (k, y[k]). There are no horizontal lines; that is, no two consecutive points have the same y-coordinate.
We can draw an infinitely long horizontal line. Return the maximum number of points of intersection of the line with the chart.
Example 1:
Input: y = [1,2,1,2,1,3,2] Output: 5 Explanation: As you can see in the image above, the line y = 1.5 has 5 intersections with the chart (in red crosses). You can also see the line y = 2 which intersects the chart in 4 points (in red crosses). It can be shown that there is no horizontal line intersecting the chart at more than 5 points. So the answer would be 5.
Example 2:
Input: y = [2,1,3,4,5] Output: 2 Explanation: As you can see in the image above, the line y = 1.5 has 2 intersections with the chart (in red crosses). You can also see the line y = 2 which intersects the chart in 2 points (in red crosses). It can be shown that there is no horizontal line intersecting the chart at more than 2 points. So the answer would be 2.
Constraints:
2 <= y.length <= 1051 <= y[i] <= 109y[i] != y[i + 1] for i in range [1, n - 1]Problem Overview: You are given chart points (i, nums[i]). Consecutive points form line segments. A horizontal line can intersect several of these segments. The task is to find the maximum number of segments a single horizontal line intersects.
The key geometric observation: a segment between (i, a) and (i+1, b) intersects every horizontal line whose y-value lies strictly between min(a,b) and max(a,b). Each segment therefore contributes an interval on the y-axis. The problem becomes finding the maximum overlap among these intervals.
Approach 1: Brute Force Horizontal Sampling (O(n * m) time, O(1) space)
Generate candidate horizontal lines between distinct y-values (for example at half-integers between sorted values). For each candidate line, iterate through all segments and check whether the y-value lies between the segment’s endpoints. Count how many segments intersect that line and track the maximum. This method directly follows the geometric definition but becomes slow when the number of candidate y-values grows.
Approach 2: Sweep Line with Binary Indexed Tree (O(n log n) time, O(n) space)
Convert every segment into an interval (low, high] where low = min(nums[i], nums[i+1]) and high = max(nums[i], nums[i+1]). Any horizontal line with y between these bounds intersects the segment exactly once. The task reduces to computing the maximum number of overlapping intervals.
Because y-values can be large, apply coordinate compression on all interval boundaries. Use a difference array style sweep implemented with a Binary Indexed Tree. Add +1 at the compressed index of low and -1 after high. A prefix sum query at each coordinate gives the number of active segments crossing that horizontal level. Track the maximum prefix value during the sweep.
This approach transforms the geometric intersection problem into a classic overlap-counting problem using arrays and a Fenwick tree. Coordinate compression ensures efficient indexing, while the BIT maintains prefix sums in O(log n). The algorithm scales well even when the chart values are large.
Recommended for interviews: The sweep-line interval approach with a Binary Indexed Tree is what interviewers expect. Explaining the geometric insight (each segment corresponds to a y-interval) demonstrates understanding, and implementing the compressed sweep with O(n log n) complexity shows strong algorithmic skill using tools from geometry and Fenwick trees.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Horizontal Sampling | O(n * m) | O(1) | Small input sizes or when exploring the geometric intuition |
| Sweep Line with Binary Indexed Tree | O(n log n) | O(n) | General case with large value ranges; efficient overlap counting |
| Prefix Difference Array with Compression | O(n log n) | O(n) | Simpler implementation when queries are processed after building events |