LeetCode 2280 - Minimum Lines to Represent a Line Chart

In this problem, we are given a list of stock prices over different days. Each element in stockPrices is a pair: This represents a point on a 2D graph where: - The X-axis is the day - The Y-axis is the stock price on that day The line chart is formed by connecting consecutive…

leetcodemediumarraymathgeometrysortingnumber-theory

LeetCode Problem 2280

Difficulty: 🟡 Medium
Topics: Array, Math, Geometry, Sorting, Number Theory

Solution

Problem Understanding

In this problem, we are given a list of stock prices over different days. Each element in stockPrices is a pair:

[day, price]

This represents a point on a 2D graph where:

  • The X-axis is the day
  • The Y-axis is the stock price on that day

The line chart is formed by connecting consecutive points after sorting them by day.

The task is to determine the minimum number of straight line segments required to represent the entire chart.

The important detail is that consecutive points that lie on the same straight line can be represented by a single segment. Whenever the slope changes, we need to start a new line segment.

For example, suppose the points are:

(1,1), (2,2), (3,3), (4,5)

The first three points all lie on the same line with slope 1, so they can be represented by one segment. The slope changes between (3,3) and (4,5), so we need another line segment. The answer becomes 2.

The input constraints are large:

  • Up to 10^5 points
  • Coordinates up to 10^9

These constraints immediately tell us that:

  • An O(n^2) solution will be too slow
  • We need something close to O(n log n) or O(n)

Another important observation is that the days are not guaranteed to be sorted. Since the chart connects points in chronological order, we must sort the points by day before processing them.

A subtle issue involves comparing slopes. Using floating point division is dangerous because precision errors can cause incorrect comparisons. For example:

1/3 != 2/6 using floating point precision in some cases

Instead, we should compare slopes using cross multiplication:

dy1 / dx1 == dy2 / dx2

becomes

dy1 * dx2 == dy2 * dx1

This avoids precision problems entirely.

Several edge cases are important:

  • If there is only one point, no lines are needed because there is nothing to connect.
  • Multiple consecutive segments may share the same slope and should count as one line.
  • Horizontal lines with slope 0 must be handled correctly.
  • Very large coordinate values require careful handling to avoid overflow in some languages.

Approaches

Brute Force Approach

A brute force solution would first sort the points by day and then repeatedly attempt to extend each line segment as far as possible.

For every starting point, we could compute the slope to the next point and continue checking future points to see whether they lie on the same line. Once the slope changes, we start another segment.

This approach is correct because it explicitly verifies whether every consecutive group of points belongs to the same line. However, repeatedly checking future points causes redundant work.

In the worst case, for each point we may scan many later points, leading to quadratic complexity.

With 10^5 points, an O(n^2) solution is far too slow.

Optimal Approach

The key insight is that we only need to compare consecutive slopes.

After sorting the points:

  • Compute the slope between point i-1 and point i
  • Compute the slope between point i and point i+1
  • If the slopes are the same, the current segment continues
  • If the slopes differ, we must start a new line

Instead of computing slopes using division, we compare them using cross multiplication:

(y2 - y1) * (x3 - x2) == (y3 - y2) * (x2 - x1)

This lets us process the array in a single pass after sorting.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Repeatedly checks whether future points stay on the same line
Optimal O(n log n) O(1) or O(log n) Sort once, then compare consecutive slopes in one pass

Algorithm Walkthrough

  1. Sort the points by day.

The chart connects points chronologically, so we must process the points in increasing order of day. 2. Handle the special case where there is only one point.

If the array length is 1, there are no segments to draw, so return 0. 3. Initialize the answer to 1.

Once we have at least two points, we always need at least one line segment. 4. Iterate through the sorted points starting from index 2.

At each step, compare:

  • The slope between points (i-2) and (i-1)
  • The slope between points (i-1) and i
  1. Compare slopes using cross multiplication.

Suppose:

dx1 = x2 - x1
dy1 = y2 - y1

dx2 = x3 - x2
dy2 = y3 - y2

The slopes are equal if:

dy1 * dx2 == dy2 * dx1

This avoids floating point precision issues. 6. If the slopes differ, increment the answer.

A slope change means the current line segment cannot continue, so we must start a new one. 7. Return the final count.

Why it works

The algorithm maintains the invariant that all consecutive points belonging to the current segment have identical slopes between adjacent pairs.

If two consecutive slopes are equal, then the three involved points are collinear, meaning the current line can continue. If the slopes differ, the current segment must end and a new one must begin.

Because every slope change is detected exactly once, the algorithm produces the minimum number of line segments required.

Python Solution

from typing import List

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        n = len(stockPrices)

        if n == 1:
            return 0

        stockPrices.sort()

        lines = 1

        for i in range(2, n):
            x1, y1 = stockPrices[i - 2]
            x2, y2 = stockPrices[i - 1]
            x3, y3 = stockPrices[i]

            dx1 = x2 - x1
            dy1 = y2 - y1

            dx2 = x3 - x2
            dy2 = y3 - y2

            if dy1 * dx2 != dy2 * dx1:
                lines += 1

        return lines

The implementation begins by checking whether there is only one point. In that situation, no line segments are needed.

Next, the points are sorted by day using:

stockPrices.sort()

Since each entry is [day, price], Python naturally sorts by the day value first.

The variable lines starts at 1 because once there are at least two points, at least one segment is necessary.

The loop begins at index 2 because we compare two consecutive slopes at a time, which requires three points.

Inside the loop:

  • The first segment uses points (i-2) and (i-1)
  • The second segment uses points (i-1) and i

Instead of performing division, the implementation compares slopes using cross multiplication:

dy1 * dx2 != dy2 * dx1

If the equality fails, the slope changed and a new line segment is required.

Finally, the total number of segments is returned.

Go Solution

package main

import "sort"

func minimumLines(stockPrices [][]int) int {
	n := len(stockPrices)

	if n == 1 {
		return 0
	}

	sort.Slice(stockPrices, func(i, j int) bool {
		return stockPrices[i][0] < stockPrices[j][0]
	})

	lines := 1

	for i := 2; i < n; i++ {
		x1, y1 := stockPrices[i-2][0], stockPrices[i-2][1]
		x2, y2 := stockPrices[i-1][0], stockPrices[i-1][1]
		x3, y3 := stockPrices[i][0], stockPrices[i][1]

		dx1 := int64(x2 - x1)
		dy1 := int64(y2 - y1)

		dx2 := int64(x3 - x2)
		dy2 := int64(y3 - y2)

		if dy1*dx2 != dy2*dx1 {
			lines++
		}
	}

	return lines
}

The Go solution follows the same algorithmic structure as the Python implementation.

One important Go-specific detail is the use of int64 during multiplication:

int64(y2 - y1)

Since coordinates can reach 10^9, multiplication may exceed the range of a 32-bit integer. Using int64 prevents overflow during cross multiplication.

The sorting step uses sort.Slice, which sorts the points by day.

Unlike Python, Go does not automatically support arbitrary-size integers, so explicit type conversion is important for correctness.

Worked Examples

Example 1

Input:

[[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]

The array is already sorted.

Step-by-step Trace

i Points Compared Slope 1 Slope 2 Same? Lines
Start First segment - - - 1
2 (1,7)-(2,6), (2,6)-(3,5) -1 -1 Yes 1
3 (2,6)-(3,5), (3,5)-(4,4) -1 -1 Yes 1
4 (3,5)-(4,4), (4,4)-(5,4) -1 0 No 2
5 (4,4)-(5,4), (5,4)-(6,3) 0 -1 No 3
6 (5,4)-(6,3), (6,3)-(7,2) -1 -1 Yes 3
7 (6,3)-(7,2), (7,2)-(8,1) -1 -1 Yes 3

Final answer:

3

Example 2

Input:

[[3,4],[1,2],[7,8],[2,3]]

After sorting:

[[1,2],[2,3],[3,4],[7,8]]

Step-by-step Trace

i Points Compared Cross Multiplication Result Same? Lines
Start First segment - - 1
2 (1,2)-(2,3), (2,3)-(3,4) 1×1 == 1×1 Yes 1
3 (2,3)-(3,4), (3,4)-(7,8) 1×4 == 4×1 Yes 1

All points lie on the same line.

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) or O(log n) Only a few variables are used, excluding sorting overhead

The single traversal after sorting is linear, O(n). However, sorting the points requires O(n log n) time, which becomes the overall complexity.

The algorithm itself uses constant extra space. Depending on the sorting implementation, the language runtime may use additional stack space internally.

Test Cases

from typing import List

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        n = len(stockPrices)

        if n == 1:
            return 0

        stockPrices.sort()

        lines = 1

        for i in range(2, n):
            x1, y1 = stockPrices[i - 2]
            x2, y2 = stockPrices[i - 1]
            x3, y3 = stockPrices[i]

            dx1 = x2 - x1
            dy1 = y2 - y1

            dx2 = x3 - x2
            dy2 = y3 - y2

            if dy1 * dx2 != dy2 * dx1:
                lines += 1

        return lines

sol = Solution()

assert sol.minimumLines([[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]) == 3  # example 1
assert sol.minimumLines([[3,4],[1,2],[7,8],[2,3]]) == 1  # example 2

assert sol.minimumLines([[1,1]]) == 0  # single point
assert sol.minimumLines([[1,1],[2,2]]) == 1  # exactly one segment
assert sol.minimumLines([[1,1],[2,2],[3,3]]) == 1  # all collinear
assert sol.minimumLines([[1,1],[2,2],[3,4]]) == 2  # one slope change
assert sol.minimumLines([[1,5],[2,5],[3,5]]) == 1  # horizontal line
assert sol.minimumLines([[5,5],[1,1],[3,3]]) == 1  # unsorted input
assert sol.minimumLines([[1,1],[2,3],[3,5],[4,7]]) == 1  # constant slope
assert sol.minimumLines([[1,1],[2,2],[3,1],[4,2],[5,1]]) == 4  # alternating slopes
assert sol.minimumLines([[1,10**9],[2,10**9-1],[3,10**9-2]]) == 1  # large values

Test Case Summary

Test Why
Example 1 Verifies multiple slope changes
Example 2 Verifies all points on one line
Single point Tests minimum input size
Two points Ensures one segment is counted correctly
All collinear Verifies continuous slope reuse
One slope change Tests segment increment logic
Horizontal line Ensures zero slope works correctly
Unsorted input Verifies sorting step
Constant slope Confirms repeated equal slopes
Alternating slopes Tests repeated segment creation
Large coordinates Verifies overflow-safe comparisons

Edge Cases

Single Point

If there is only one point, there are no adjacent points to connect. A common mistake is returning 1 because developers think at least one segment is needed. However, a single point requires zero lines. The implementation handles this immediately with:

if n == 1:
    return 0

Unsorted Input

The input days are distinct but not guaranteed to be sorted. If we process the points in their original order, the constructed chart would be incorrect because the problem defines adjacency chronologically. The implementation avoids this issue by sorting the array before any slope calculations.

Floating Point Precision Errors

Using floating point division for slope comparison can lead to incorrect results due to rounding issues. For example:

1/3 and 2/6

may not compare exactly equal in floating point arithmetic.

The implementation avoids division entirely and instead compares slopes using cross multiplication:

dy1 * dx2 == dy2 * dx1

This guarantees mathematically exact comparisons.

Large Coordinate Values

Coordinates can be as large as 10^9. When multiplying differences, the result can exceed 32-bit integer limits.

In Python, integers automatically expand, so overflow is not an issue. In Go, however, explicit int64 conversion is necessary to safely handle multiplication without overflow.