Maximum Number of Intersections on the Chart

Maximum Number of Intersections on the Chart - Problem

Array Hash Table Math Binary Indexed Tree Geometry Line Sweep Sorting Hard

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.

Input & Output

Example 1 — Basic Case

$ Input: y = [1,4,2]

› Output: 2

💡 Note: Chart has points (1,1), (2,4), (3,2). Line segments: (1,1)→(2,4) and (2,4)→(3,2). A horizontal line at y=2.5 intersects both segments, giving maximum 2 intersections.

Example 2 — Single Peak

$ Input: y = [2,1,3]

› Output: 2

💡 Note: Points (1,2), (2,1), (3,3). Segments: (1,2)→(2,1) and (2,1)→(3,3). Horizontal line at y=1.5 intersects both segments.

Example 3 — Monotonic

$ Input: y = [1,2,3,4]

› Output: 3

💡 Note: Points form ascending line. Any horizontal line between y=1.5 and y=3.5 intersects all 3 segments: (1,1)→(2,2), (2,2)→(3,3), (3,3)→(4,4).

Constraints

2 ≤ y.length ≤ 10⁵
1 ≤ y[i] ≤ 10⁸
No two consecutive elements are equal

Visualization

Tap to expand

Understanding the Visualization

Input Chart

Line chart with points connected by segments

Test Horizontal Lines

Find optimal y-coordinate for maximum intersections

Count Intersections

Return maximum number of segments intersected

Key Takeaway

🎯 Key Insight: Use sweep line algorithm to efficiently find the y-coordinate where the most line segments are active simultaneously

Asked in

G Google 15 M Microsoft 12

The key insight is that each line segment contributes exactly one intersection at any y-value within its range. Best approach uses coordinate compression and sweep line to efficiently count active segments. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Coordinate Compression + Sweep Line	O(n log n)	O(n)	Use coordinate compression and sweep line algorithm for efficient counting
Brute Force - Try All Y-Values	O(n²)	O(n)	Check every possible y-coordinate and count intersections

Coordinate Compression + Sweep Line — Algorithm Steps

Create events for each segment's y-range
Sort events by y-coordinate
Sweep through events, tracking active segments
Record maximum active count

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Events

Generate start/end events for each segment's y-range

Sort & Sweep

Sort events by y-coordinate and sweep through them

Track Active

Count active segments at each y-level, record maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int y;
    int delta;
} Event;

int compareEvents(const void* a, const void* b) {
    Event* ea = (Event*)a;
    Event* eb = (Event*)b;
    return ea->y - eb->y;
}

int solution(int* y, int n) {
    if (n <= 1) return 0;
    
    Event events[2000]; // Max 2*n events
    int eventCount = 0;
    
    // Create events for each segment
    for (int i = 0; i < n - 1; i++) {
        int y1 = y[i], y2 = y[i + 1];
        if (y1 != y2) {
            int low = y1 < y2 ? y1 : y2;
            int high = y1 > y2 ? y1 : y2;
            events[eventCount++] = (Event){low, 1};   // Segment starts
            events[eventCount++] = (Event){high, -1}; // Segment ends
        }
    }
    
    // Sort events by y-coordinate
    qsort(events, eventCount, sizeof(Event), compareEvents);
    
    int maxIntersections = 0;
    int activeSegments = 0;
    
    // Sweep through events
    int i = 0;
    while (i < eventCount) {
        int currY = events[i].y;
        
        // Process all events at current y-coordinate
        while (i < eventCount && events[i].y == currY) {
            activeSegments += events[i].delta;
            i++;
        }
        
        // Update maximum
        if (i < eventCount) {
            if (activeSegments > maxIntersections) {
                maxIntersections = activeSegments;
            }
        }
    }
    
    return maxIntersections;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int y[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        y[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(y, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting events dominates the time complexity

⚡ Linearithmic

Space Complexity

O(n)

Storage for events and coordinate compression

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Coordinate Compression + Sweep Line — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler