Maximum Number of Intersections on the Chart

Maximum Number of Intersections on the Chart

What is this problem about?

The Maximum Number of Intersections on the Chart coding problem presents a piecewise linear chart (a sequence of line segments connecting consecutive data points) and asks for the maximum number of times a horizontal line can intersect the chart. Given the y-values at each integer x-coordinate, you want to find the horizontal line y=c that crosses the most segment crossings.

Why is this asked in interviews?

Microsoft and Meta use this problem to test advanced sweep line techniques combined with a Binary Indexed Tree (BIT) for efficient range updates. A horizontal line intersects a segment if the segment's y-range spans across the line. This translates to a difference array or BIT problem: for each segment, increment all y-values in its vertical range. The answer is the maximum frequency across all y-values.

Algorithmic pattern used

Line sweep + Binary Indexed Tree (BIT/Fenwick Tree): For each consecutive pair of points (y1, y2), the horizontal line intersects this segment for all y in [min(y1,y2), max(y1,y2)] (exclusive of endpoints if touching counts differently). Use a difference array or BIT to perform range increment on [min, max], then query the point with maximum value. This is O(n log(max_y)) overall.

A segment tree can also handle this with range updates and global maximum queries.

Example explanation

Y-values: [1, 4, 2, 3].

• Segment 1→4: intersects y=2, y=3 (i.e., y in [1,4] half-open).
• Segment 4→2: intersects y=2, y=3 (y in [2,4]).
• Segment 2→3: intersects y=2 (y in [2,3]).
• Count at y=2: 2 (segments 1→4 and 4→2). Count at y=3: 2. Count at y=2 (segment 2→3): add 1. Total at y=2: 3. Total at y=3: 2.
• Maximum = 3 at y=2.

Common mistakes candidates make

• Counting endpoint touches incorrectly: Whether touching an endpoint counts as an intersection affects the range bounds. Clarify and adjust ranges accordingly.
• Using an array of size max_y naively: If y-values are large, use coordinate compression before building the BIT.
• Off-by-one in range updates: Difference array updates for range [l, r] use diff[l]++, diff[r+1]--; getting this wrong corrupts the count.

Interview preparation tip

For the Array Math Hash Table Sorting Line Sweep Binary Indexed Tree Geometry interview pattern, line sweep + BIT is a standard combination for "how many objects span a given coordinate" problems. Practice the difference array trick first (O(n + max_val)), then upgrade to BIT for query-heavy variants. Coordinate compression is essential when values are large but the problem has a small number of distinct points.