Is Maximum Number of Intersections on the Chart easy or hard?

Maximum Number of Intersections on the Chart is classified as Hard because it requires recognizing a geometric transformation into interval overlap counting. Implementing coordinate compression and a Binary Indexed Tree correctly also increases the difficulty compared with standard array problems.

Maximum Number of Intersections on the Chart Python/Java solution

Python, Java, C++, and Go implementations typically follow the same structure: build intervals from adjacent points, compress coordinates, apply range updates using a Fenwick tree or difference array, and compute the maximum prefix sum representing the maximum intersections.

How to solve Maximum Number of Intersections on the Chart in O(n log n)?

Transform every segment between (i, nums[i]) and (i+1, nums[i+1]) into an interval (min, max] on the y-axis. Compress all unique y-values, then perform a sweep line using a difference update (+1 at start, -1 after end). Use a Binary Indexed Tree to maintain prefix sums and track the maximum overlap while scanning.

What is the best approach for Maximum Number of Intersections on the Chart?

The most efficient approach converts each chart segment into a vertical interval on the y-axis and computes the maximum overlap. Using coordinate compression and a Binary Indexed Tree (Fenwick Tree) allows prefix sum updates and queries in O(log n). The full algorithm runs in O(n log n) time with O(n) space.

Is Maximum Number of Intersections on the Chart asked at Google/Amazon/Meta?

Problems combining geometry, sweep line techniques, and Fenwick trees are common in interviews at companies like Google, Amazon, and Meta. Variants of interval overlap and line intersection counting frequently appear in senior-level algorithm rounds.

What data structure is used in Maximum Number of Intersections on the Chart?

The optimal implementation uses a Binary Indexed Tree (Fenwick Tree) together with coordinate compression. This structure efficiently maintains prefix sums while processing interval start and end events during the sweep.

What is the time complexity of Maximum Number of Intersections on the Chart?

The optimal solution runs in O(n log n) time. Each adjacent pair of points creates an interval, and updates are processed using a Binary Indexed Tree after coordinate compression. The space complexity is O(n) for storing compressed coordinates and Fenwick tree data.

Description Hints 5 Solution Video 25:57

3009. Maximum Number of Intersections on the Chart

Hard45.5% acceptance1 companyPremium elsewhere, free here

There is a line chart consisting of n points connected by line segments. You are given a 1-indexed integer array y. The k^th 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 <= 10⁵
1 <= y[i] <= 10⁹
y[i] != y[i + 1] for i in range [1, n - 1]

Asked at 1 company

Microsoft

Topics

Hints open one at a time

Hint 1

We move a horizontal line from the bottom of the chart to the top.

Hint 2

For each point we reach, the number of intersections might change, so we have to count it.

Hint 3

If a point we just reached is lower than its previous/next point, the number of intersections increases.

Hint 4

If a point we just reached is higher than its previous/next point, the number of intersections decreases.

Hint 5

There is also another solution using Fenwick Tree.

25:57

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,1,2,1,3,2]

Input

[2,1,3,4,5]

Your code is saved on this device.Solution