Welcome to Subscribe On Youtube

3009. Maximum Number of Intersections on the Chart

Description

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.

 

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 <= 105
  • 1 <= y[i] <= 109
  • y[i] != y[i + 1] for i in range [1, n - 1]

Solutions

Solution 1

  • 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;
    }
}


  • class Solution {
public:
    int maxIntersectionCount(vector<int>& y) {
        int n = y.size();
        map<int, int> line;
        for (int i = 1; i < n; ++i) {
            int start = 2 * y[i - 1];
            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];
        }
        int ans = 0, intersection = 0;
        for (auto& [_, count] : line) {
            intersection += count;
            ans = max(ans, intersection);
        }
        return ans;
    }
};


  • class Solution:
    def maxIntersectionCount(self, y: List[int]) -> int:
        n = len(y)
        line = defaultdict(int)
        for i in range(1, n):
            start = 2 * y[i - 1]
            end = 2 * y[i] + (0 if i == n - 1 else (-1 if y[i] > y[i - 1] else 1))
            line[min(start, end)] += 1
            line[max(start, end) + 1] -= 1
        ans = intersection = 0
        for _, count in sorted(line.items()):
            intersection += count
            ans = max(ans, intersection)
        return ans


  • func maxIntersectionCount(y []int) (ans int) {
	n := len(y)
	line := map[int]int{}
	for i := 1; i < n; i++ {
		start := 2 * y[i-1]
		end := 2 * y[i]
		if i != n-1 {
			if y[i] > y[i-1] {
				end--
			} else {
				end++
			}
		}
		a, b := min(start, end), max(start, end)
		line[a]++
		line[b+1]--
	}
	keys := make([]int, 0, len(line))
	for k := range line {
		keys = append(keys, k)
	}
	sort.Ints(keys)
	intersection := 0
	for _, k := range keys {
		intersection += line[k]
		if ans < intersection {
			ans = intersection
		}
	}
	return
}

All Problems

All Solutions