#2280

Medium

LeetCode Problem Workspace

Minimum Lines to Represent a Line Chart

Determine the fewest lines needed to accurately connect stock price points in a line chart using array and math reasoning.

array math geometry sorting number theory

Problem Statement

You are given a 2D array stockPrices where stockPrices[i] = [dayi, pricei] represents the stock price on day dayi. The points are plotted on an XY plane with dayi as X and pricei as Y, and adjacent points are connected to form a line chart. Your task is to compute the minimum number of straight lines needed to represent the line chart without altering the order of days.

Return an integer representing the minimum number of lines required. For example, given stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]], the correct output is 3 because three line segments suffice to connect all points with correct slopes.

Examples

Example 1

Input: stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]

Output: 3

The diagram above represents the input, with the X-axis representing the day and Y-axis representing the price. The following 3 lines can be drawn to represent the line chart:

Line 1 (in red) from (1,7) to (4,4) passing through (1,7), (2,6), (3,5), and (4,4).
Line 2 (in blue) from (4,4) to (5,4).
Line 3 (in green) from (5,4) to (8,1) passing through (5,4), (6,3), (7,2), and (8,1). It can be shown that it is not possible to represent the line chart using less than 3 lines.

Example 2

Input: stockPrices = [[3,4],[1,2],[7,8],[2,3]]

Output: 1

As shown in the diagram above, the line chart can be represented with a single line.

Constraints

1 <= stockPrices.length <= 105
stockPrices[i].length == 2
1 <= dayi, pricei <= 109
All dayi are distinct.

Solution Approach

Sort points by day

Arrange stockPrices in increasing order of dayi to ensure the chart progresses sequentially. This step is crucial because collinearity checks require consecutive points in time.

Check slopes between consecutive points

Compute the slope between each pair of consecutive points. Whenever the slope changes, it indicates a new line segment. This allows grouping of points that lie on the same straight line efficiently.

Count distinct line segments

Iterate through all points, tracking slope changes. Increment the line count each time a slope change occurs. The final count is the minimum number of lines needed to represent the chart.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is dominated by sorting, O(n log n), and slope checks take O(n), giving overall O(n log n). Space complexity is O(1) extra if in-place sorting is used.

What Interviewers Usually Probe

Ask why sorting by day is necessary before checking slopes.
Expect candidate to explain slope comparison without floating-point precision errors.
Look for handling of edge cases where multiple points are collinear or duplicate prices exist.

Common Pitfalls or Variants

Common pitfalls

Not sorting points by day before checking slopes, leading to incorrect line counts.
Using floating-point division for slopes without reducing fractions, causing precision errors.
Failing to handle cases where consecutive points have the same price or day order is not guaranteed.

Follow-up variants

Calculate minimum lines if some points can be skipped or ignored to reduce total lines.
Determine the number of lines needed for a 3D line chart instead of 2D.
Optimize for streaming input where points arrive one by one and minimum lines must be updated online.

FAQ

What is the main idea behind the Minimum Lines to Represent a Line Chart problem?

The key is to detect collinear points by checking slopes between consecutive points after sorting by day and counting each slope change as a new line.

Can we use floating-point slopes safely in this problem?

No, using floating-point slopes can cause precision errors; it is safer to compare slopes using cross multiplication of differences.

How does sorting affect the solution?

Sorting by day ensures that consecutive points are checked in chronological order, which is required for correct collinearity grouping.

What is the expected time complexity for this solution?

Sorting takes O(n log n) and slope checks take O(n), so the overall time complexity is O(n log n).

Is this problem only about arrays and math?

Yes, it primarily involves array manipulation to order points and math to calculate slopes, fitting the Array plus Math pattern.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        stockPrices.sort()
        dx, dy = 0, 1
        ans = 0
        for (x, y), (x1, y1) in pairwise(stockPrices):
            dx1, dy1 = x1 - x, y1 - y
            if dy * dx1 != dx * dy1:
                ans += 1
            dx, dy = dx1, dy1
        return ans

Continue Practicing

#2344 minimum deletions to make array divisible #1998 gcd sort of an array #2607 make k subarray sums equal