Practice/Meta/Leetcode 3009. Maximum Number of Intersections on the Chart

Leetcode 3009. Maximum Number of Intersections on the Chart

CodingOptional

Problem

You are given a 2D chart where multiple data series are plotted over the same x-coordinates. Each series is represented as a list of y-values, and all series have the same number of data points.

When you connect consecutive points in each series with straight line segments, these segments can intersect with segments from other series between adjacent x-coordinates.

Your task is to count the total number of pairwise intersections that occur between all line segments across all adjacent column pairs.

Two line segments between columns i and i+1 intersect if:

• They belong to different series
• One segment goes from a lower y-value to a higher y-value while the other goes from a higher y-value to a lower y-value (or vice versa)

More formally, for series a and series b, the segments from (i, a[i]) to (i+1, a[i+1]) and from (i, b[i]) to (i+1, b[i+1]) intersect if and only if the relative ordering of their y-values changes between the two columns.

Requirements

1. Count all pairwise intersections between line segments from different series
2. Only consider intersections between adjacent x-coordinates (columns)
3. Return the total count of all such intersections across all adjacent column pairs
4. Handle cases where multiple segments may have the same y-value

Constraints

• 1 ≤ number of series ≤ 1000
• 1 ≤ number of columns ≤ 1000
• 0 ≤ y-values ≤ 10^9
• All series have the same length
• For optimal performance, aim for O(n × m × log(n)) time complexity where n is the number of series and m is the number of columns

Examples

Example 1:

` Input: chart = [[1, 3], [2, 1], [3, 2]] Output: 3 Explanation: Between columns 0 and 1:

• Series 0: (0,1)→(1,3) and Series 1: (0,2)→(1,1) cross (1 < 2 but 3 > 1) Between columns 1 and 2:
• Series 0: (1,3)→(2,2) and Series 1: (1,1)→(2,3) cross
• Series 0: (1,3)→(2,2) and Series 2: (1,2)→(2,3) cross Total crossings: 1 + 2 = 3 `

Example 2:

Input: chart = [[1, 2, 3], [4, 5, 6]] Output: 0 Explanation: Both series are monotonically increasing and maintain their relative order, so no crossings occur.

Example 3:

Input: chart = [[1, 5], [5, 1]] Output: 1 Explanation: The two lines cross exactly once between the two columns as their relative positions swap.