Minimum Lines to Represent a Line Chart solution and explanation
Google
9 more videos on this problem
Minimum Lines to Represent a Line Chart | Leetcode 2280 | Arrays | Contest 294 🔥🔥Coding Decoded · 10:41 · 1K views
Weekly Contest 294 | 2280. Minimum Lines to Represent a Line ChartcodingMohan · 7:41 · 586 views
2280. Minimum Lines to Represent a Line Chart | Leetcode weekly 294 | Leetcode MediumBinaryMagic · 15:42 · 510 views
Leetcode 2280. Min Lines to Represent Line Chart | EasyThinkCode · 5:45 · 468 views
Minimum Lines to Represent a Line Chart - Leetcode Weekly 294 | Hitesh TripathiCoding Talkies | Newton School · 11:28 · 444 views
2280. Minimum Lines to Represent a Line Chart (Leetcode Medium)Programming Live with Larry · 6:49 · 354 views
Minimum Lines to Represent a Line Chart(Leetcode Weekly 294)Soumya Bhattacharjee · 3:20 · 306 views
Leetcode Weekly Contest 294 | PROBLEM 2278 , 2279 , 2280 | MATHS | GEOMETRYcode Explainer · 17:22 · 303 views
2280 Minimum Lines to Represent a Line Chart | Zero to FAANG | Weekly 294 | Leetcode | WE2Programmers Zone · 17:23 · 290 views
【每日一题】LeetCode 2280. Minimum Lines to Represent a Line ChartHuifeng Guan · 12:35 · 260 views
The problem
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 <= 105stockPrices[i].length == 21 <= dayi, pricei <= 109- All
dayiare 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.
class Solution:
def minimumLines(self, stockPrices: List[List[int]]) -> int:
if len(stockPrices) <= 1:
return 0
stockPrices.sort()
lines = 1
for i in range(2, len(stockPrices)):
x1, y1 = stockPrices[i-2]
x2, y2 = stockPrices[i-1]
x3, y3 = stockPrices[i]
if (y3-y2) * (x2-x1) != (y2-y1) * (x3-x2):
lines += 1
return linesimport java.util.Arrays;
class Solution {
public int minimumLines(int[][] stockPrices) {
if (stockPrices.length <= 1) return 0;
Arrays.sort(stockPrices, (a, b) -> Integer.compare(a[0], b[0]));
int lines = 1;
for (int i = 2; i < stockPrices.length; i++) {
long x1 = stockPrices[i-2][0], y1 = stockPrices[i-2][1];
long x2 = stockPrices[i-1][0], y2 = stockPrices[i-1][1];
long x3 = stockPrices[i][0], y3 = stockPrices[i][1];
if((y3-y2)*(x2-x1) != (y2-y1)*(x3-x2)) {
lines++;
}
}
return lines;
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
static bool compare(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
int minLines(vector<vector<int>>& stockPrices) {
if (stockPrices.size() <= 1) return 0;
sort(stockPrices.begin(), stockPrices.end(), compare);
int lines = 1;
for (int i = 2; i < stockPrices.size(); i++) {
long long x1 = stockPrices[i-2][0], y1 = stockPrices[i-2][1];
long long x2 = stockPrices[i-1][0], y2 = stockPrices[i-1][1];
long long x3 = stockPrices[i][0], y3 = stockPrices[i][1];
if((y3-y2)*(x2-x1) != (y2-y1)*(x3-x2)) {
lines++;
}
}
return lines;
}
};function minimumLines(stockPrices) {
if (stockPrices.length <= 1) return 0;
stockPrices.sort((a, b) => a[0] - b[0]);
let lines = 1;
for (let i = 2; i < stockPrices.length; i++) {
const [x1, y1] = stockPrices[i-2];
const [x2, y2] = stockPrices[i-1];
const [x3, y3] = stockPrices[i];
if ((y3-y2) * (x2-x1) !== (y2-y1) * (x3-x2)) {
lines++;
}
}
return lines;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
int *pointA = *(int **)a;
int *pointB = *(int **)b;
return pointA[0] - pointB[0];
}
int minLines(int stockPrices[][2], int stockPricesSize) {
if (stockPricesSize <= 1) return 0;
qsort(stockPrices, stockPricesSize, sizeof(stockPrices[0]), compare);
int lines = 1;
for (int i = 2; i < stockPricesSize; i++) {
long long x1 = stockPrices[i-2][0], y1 = stockPrices[i-2][1];
long long x2 = stockPrices[i-1][0], y2 = stockPrices[i-1][1];
long long x3 = stockPrices[i][0], y3 = stockPrices[i][1];
// Check for collinearity using cross product: (y3-y2)*(x2-x1) != (y2-y1)*(x3-x2)
if((y3-y2)*(x2-x1) != (y2-y1)*(x3-x2)) {
lines++;
}
}
return lines;
}using System;
public class Solution {
public int MinimumLines(int[][] stockPrices) {
if (stockPrices.Length <= 1) return 0;
Array.Sort(stockPrices, (a, b) => a[0].CompareTo(b[0]));
int lines = 1;
for (int i = 2; i < stockPrices.Length; i++) {
long x1 = stockPrices[i-2][0], y1 = stockPrices[i-2][1];
long x2 = stockPrices[i-1][0], y2 = stockPrices[i-1][1];
long x3 = stockPrices[i][0], y3 = stockPrices[i][1];
if((y3-y2)*(x2-x1) != (y2-y1)*(x3-x2)) {
lines++;
}
}
return lines;
}
}The Python solution involves sorting the days of stock prices and comparing slope values calculated by differences. Integer arithmetic ensures precision handling without any issues related to floating-point inaccuracies during slope comparison.
Time Complexity: O(n log n), due to sorting operations.
Space Complexity: O(1), as the sort is done in place.
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.
class Solution:
def minimumLines(self, stockPrices: List[List[int]]) -> int:
if len(stockPrices) <= 1:
return 0
stockPrices.sort()
lines = len(stockPrices) - 1
for i in range(2, len(stockPrices)):
if (stockPrices[i][1] - stockPrices[i-1][1]) * (stockPrices[i-1][0] - stockPrices[i-2][0]) == \
(stockPrices[i-1][1] - stockPrices[i-2][1]) * (stockPrices[i][0] - stockPrices[i-1][0]):
lines -= 1
return linesimport java.util.Arrays;
class Solution {
public int minimumLines(int[][] stockPrices) {
if (stockPrices.length <= 1) return 0;
Arrays.sort(stockPrices, (a, b) -> Integer.compare(a[0], b[0]));
int lines = stockPrices.length - 1;
for (int i = 2; i < stockPrices.length; i++) {
if ((long)(stockPrices[i][1] - stockPrices[i-1][1]) * (stockPrices[i-1][0] - stockPrices[i-2][0]) ==
(long)(stockPrices[i-1][1] - stockPrices[i-2][1]) * (stockPrices[i][0] - stockPrices[i-1][0])) {
lines--;
}
}
return lines;
}
}#include <vector>
#include <algorithm>
using namespace std;
int minimumLines(vector<vector<int>>& stockPrices) {
if (stockPrices.size() <= 1) return 0;
sort(stockPrices.begin(), stockPrices.end());
int lines = stockPrices.size() - 1;
for (size_t i = 2; i < stockPrices.size(); ++i) {
if ((long long)(stockPrices[i][1] - stockPrices[i-1][1]) * (stockPrices[i-1][0] - stockPrices[i-2][0]) ==
(long long)(stockPrices[i-1][1] - stockPrices[i-2][1]) * (stockPrices[i][0] - stockPrices[i-1][0])) {
--lines;
}
}
return lines;
}function minimumLines(stockPrices) {
if (stockPrices.length <= 1) return 0;
stockPrices.sort((a, b) => a[0] - b[0]);
let lines = stockPrices.length - 1;
for (let i = 2; i < stockPrices.length; i++) {
const [x1, y1] = stockPrices[i-2];
const [x2, y2] = stockPrices[i-1];
const [x3, y3] = stockPrices[i];
if ((y3-y2) * (x2-x1) === (y2-y1) * (x3-x2)) {
lines--;
}
}
return lines;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int minimumLines(int stockPrices[][2], int stockPricesSize) {
if (stockPricesSize <= 1) return 0;
qsort(stockPrices, stockPricesSize, sizeof(stockPrices[0]), compare);
int lines = stockPricesSize - 1;
for (int i = 2; i < stockPricesSize; i++) {
if ((long)((stockPrices[i][1] - stockPrices[i-1][1]) * (stockPrices[i-1][0] - stockPrices[i-2][0])) ==
(long)((stockPrices[i-1][1] - stockPrices[i-2][1]) * (stockPrices[i][0] - stockPrices[i-1][0]))) {
lines--;
}
}
return lines;
}using System;
public class Solution {
public int MinimumLines(int[][] stockPrices) {
if (stockPrices.Length <= 1) return 0;
Array.Sort(stockPrices, (a,b) => a[0].CompareTo(b[0]));
int lines = stockPrices.Length - 1;
for (int i = 2; i < stockPrices.Length; i++) {
if ((long)(stockPrices[i][1] - stockPrices[i-1][1]) * (stockPrices[i-1][0] - stockPrices[i-2][0]) ==
(long)(stockPrices[i-1][1] - stockPrices[i-2][1]) * (stockPrices[i][0] - stockPrices[i-1][0])) {
lines--;
}
}
return lines;
}
}The Python version addresses the problem iteratively, adjusting downward the attempted maximal line count by catching similarity in directional transitions, with inline calculation, ensuring continuity-based reduction of lines counted.
Time Complexity: O(n log n), resulting from sorting needs.
Space Complexity: O(1), achieved by immediate modification.
Approach 3: Default Approach
function minimumLines(stockPrices: number[][]): number {
const n = stockPrices.length;
stockPrices.sort((a, b) => a[0] - b[0]);
let ans = 0;
let pre = [BigInt(0), BigInt(0)];
for (let i = 1; i < n; i++) {
const [x1, y1] = stockPrices[i - 1];
const [x2, y2] = stockPrices[i];
const dx = BigInt(x2 - x1),
dy = BigInt(y2 - y1);
if (i == 1 || dx * pre[1] !== dy * pre[0]) ans++;
pre = [dx, dy];
}
return ans;
}func minimumLines(stockPrices [][]int) int {
ans := 0
sort.Slice(stockPrices, func(i, j int) bool { return stockPrices[i][0] < stockPrices[j][0] })
for i, dx, dy := 1, 0, 1; i < len(stockPrices); i++ {
x, y := stockPrices[i-1][0], stockPrices[i-1][1]
x1, y1 := stockPrices[i][0], stockPrices[i][1]
dx1, dy1 := x1-x, y1-y
if dy*dx1 != dx*dy1 {
ans++
}
dx, dy = dx1, dy1
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Slopes and Collinearity | Time Complexity: O(n log n), due to sorting operations. |
| Approach 2: Incremental Line Count with Direct Comparison | Time Complexity: O(n log n), resulting from sorting needs. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Slopes and Collinearity | O(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 Comparison | O(n log n) | O(1) | Preferred interview solution after sorting; simple linear pass and easy slope checks |
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.