Skip to main content
Talentd

Minimum Lines to Represent a Line Chart - Solution & Explanation

MediumArrayMathGeometrySorting13 min readAsked at: Google
Practice this problem

Problem Statement

You are given a 2D integer array stockPrices where stockPrices[i] = [dayi, pricei] indicates the price of the stock on day dayi is pricei. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:

Return the minimum number of lines needed to represent the line chart.

 

Example 1:

Input: stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
Output: 3
Explanation:
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
Explanation:
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.

Approach Overview

Problem Overview: You receive stock prices as [day, price] points. After sorting by day, the chart connects points with straight segments. The goal is to compute the minimum number of straight lines needed so consecutive points that share the same slope belong to the same segment.

Approach 1: Using Slopes and Collinearity (O(n log n) time, O(1) space)

First sort the points by day using a standard sorting step. Then iterate through the array and compute the slope between consecutive points. If three consecutive points are collinear, they belong to the same line segment, so you continue without increasing the line count. Instead of floating-point division, compare slopes using cross multiplication: (y2 - y1) * (x3 - x2) == (y3 - y2) * (x2 - x1). This avoids precision issues and relies purely on integer arithmetic from math and geometry. Every time the slope changes, increment the line counter.

Approach 2: Incremental Line Count with Direct Comparison (O(n log n) time, O(1) space)

This approach focuses on counting line segments as you traverse the sorted array. After sorting by day, start with one line segment between the first two points. For each new point, compare the slope of the last segment with the slope formed by the current pair. If the slopes differ, a new line segment must start, so increment the count. The comparison again uses cross multiplication instead of division. The logic is simple: iterate once, compute slope relationships, and maintain a running count of segments.

Recommended for interviews: The incremental slope comparison approach is typically expected. It shows you understand how to detect collinearity without floating-point errors and how sorting enables a single linear pass. Interviewers usually look for the O(n log n) solution (due to sorting) with constant extra space and integer slope comparison.

Approach 1: Approach 1: Using Slopes and Collinearity

To determine the minimum number of lines needed, we can utilize the concept of slopes between two points.
The slope between two points (x1, y1) and (x2, y2) is (y2-y1)/(x2-x1).
By calculating slopes between consecutive points and checking for changes in the slope, we can count the number of distinct lines required.

This C solution sorts the given points based on the day, then calculates consecutive slopes to check if they are collinear. Using integer arithmetic to avoid precision issues with floating-point division, this implementation compares the slopes of each triplet of points to ascertain changes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), dominated by the sorting step.
Space Complexity: O(1), as sorting is in-place.

Try this approach in the editor →

Approach 2: Approach 2: Incremental Line Count with Direct Comparison

In this approach, we directly compare consecutive points to form lines when a change in direction is detected. By storing the direction differences using primitive comparisons, we adjust and increment a line counter whenever a shift occurs in the plotting direction of consecutive stock points.

This C solution takes the approach of starting with the maximum possible lines (n-1) and reduces them as coinciding slope patterns are identified between consecutive stock prices. Uses simple subtraction and multiplication for calculations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), dictated by the sorting requirement.
Space Complexity: O(1), as no additional space is utilized outside of input modification.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Slopes and Collinearity

Time Complexity: O(n log n), dominated by the sorting step.
Space Complexity: O(1), as sorting is in-place.

Approach 2: Incremental Line Count with Direct Comparison

Time Complexity: O(n log n), dictated by the sorting requirement.
Space Complexity: O(1), as no additional space is utilized outside of input modification.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Using Slopes and CollinearityO(n log n)O(1)General case when points are unsorted and you need accurate slope comparison without floating-point errors
Incremental Line Count with Direct ComparisonO(n log n)O(1)Preferred interview solution after sorting; simple linear pass and easy slope checks

Video Solution

Minimum Lines to Represent a Line Chart | Leetcode 2280 | Arrays | Contest 294 🔥🔥 • Coding Decoded • 1,313 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Lines to Represent a Line Chart easy or hard?
The problem is rated Medium because the logic is simple but requires careful handling of slopes and integer arithmetic. Avoiding floating-point precision issues with cross multiplication is the key insight. Once the points are sorted, the rest of the solution is a straightforward linear scan.
Minimum Lines to Represent a Line Chart Python/Java solution
Python and Java solutions both follow the same idea: sort the points by day, then iterate once while comparing slopes using cross multiplication. Each time the slope changes, increment the line count. The implementation uses simple arithmetic and runs in O(n log n) time.
How to solve Minimum Lines to Represent a Line Chart in O(n)?
An O(n) traversal is possible after the input is sorted by day. During the pass, compare slopes of consecutive segments using cross multiplication. If the slopes differ, increment the line count. Since the sorting step is usually required for unsorted input, the complete solution remains O(n log n) overall.
What is the best approach for Minimum Lines to Represent a Line Chart?
The optimal approach sorts the points by day and compares slopes between consecutive segments. If two adjacent segments share the same slope, the points are collinear and belong to the same line. Cross multiplication is used instead of floating-point division to avoid precision errors. The overall complexity is O(n log n) time due to sorting and O(1) extra space.
Is Minimum Lines to Represent a Line Chart asked at Google/Amazon/Meta?
This type of slope comparison and collinearity problem appears in interviews at companies that emphasize algorithmic reasoning, including Google, Amazon, and fintech firms. The problem tests sorting, geometry intuition, and careful integer arithmetic handling.
What data structure is used in Minimum Lines to Represent a Line Chart?
The main data structure is an array of points representing day and price pairs. After sorting the array, the algorithm processes it sequentially while comparing slopes derived from adjacent elements. No additional complex data structures are required.
What is the time complexity of Minimum Lines to Represent a Line Chart?
The dominant cost is sorting the points by day, which takes O(n log n). After sorting, the algorithm performs a single linear pass to compare slopes between consecutive points, which is O(n). The total complexity is therefore O(n log n) time with O(1) additional space.

Ready to solve this problem?

Practice Minimum Lines to Represent a Line Chart with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Points on a Line

Next

Minimum Number of Lines to Cover Points