Skip to content

3009. Maximum Number of Intersections on the Chart 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int maxIntersectionCount(vector<int>& y) {
    const int n = y.size();
    int ans = 0;
    int intersectionCount = 0;
    map<int, int> line;

    for (int i = 1; i < n; ++i) {
      const int start = 2 * y[i - 1];
      const int end = 2 * y[i] + (i == n - 1 ? 0 : y[i] > y[i - 1] ? -1 : 1);
      ++line[min(start, end)];
      --line[max(start, end) + 1];
    }

    for (const auto& [_, count] : line) {
      intersectionCount += count;
      ans = max(ans, intersectionCount);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int maxIntersectionCount(int[] y) {
    final int n = y.length;
    int ans = 0;
    int intersectionCount = 0;
    TreeMap<Integer, Integer> line = new TreeMap<>();

    for (int i = 1; i < n; ++i) {
      final int start = 2 * y[i - 1];
      final int end = 2 * y[i] + (i == n - 1 ? 0 : y[i] > y[i - 1] ? -1 : 1);
      line.merge(Math.min(start, end), 1, Integer::sum);
      line.merge(Math.max(start, end) + 1, -1, Integer::sum);
    }

    for (final int count : line.values()) {
      intersectionCount += count;
      ans = Math.max(ans, intersectionCount);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def maxIntersectionCount(self, y: list[int]) -> int:
    ans = 0
    intersectionCount = 0
    line = collections.Counter()

    for i, (a, b) in enumerate(itertools.pairwise(y)):
      start = 2 * a
      end = 2 * b + (0 if i == len(y) - 2 else -1 if b > a else 1)
      line[min(start, end)] += 1
      line[max(start, end) + 1] -= 1

    for count in sorted(line):
      intersectionCount += line[count]
      ans = max(ans, intersectionCount)

    return ans