Minimum Lines to Represent a Line Chart - Practice Coding Problems

Minimum Lines to Represent a Line Chart - Problem

Array Math Geometry Sorting Number Theory Medium

You are given a 2D integer array stockPrices where stockPrices[i] = [day_i, price_i] indicates the price of the stock on day day_i is price_i.

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.

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

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: All three points lie on the same line with slope -1. From (1,7) to (2,6): slope = (6-7)/(2-1) = -1. From (2,6) to (3,5): slope = (5-6)/(3-2) = -1. Since slopes are the same, only 1 line is needed.

Example 2 — Slope Change

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

› Output: 3

💡 Note: Three different slopes: (1,7)→(2,6) has slope -1, (2,6)→(3,5) has slope -1, but (3,5)→(5,4) has slope -0.5. Since the slope changes twice, we need 3 separate line segments.

Example 3 — Two Points

$ Input: stockPrices = [[3,4],[1,2]]

› Output: 1

💡 Note: Only two points, so exactly one line segment is needed to connect them.

Constraints

1 ≤ stockPrices.length ≤ 10⁵
stockPrices[i].length == 2
1 ≤ day_i, price_i ≤ 10⁹
All day_i are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Points

Stock prices plotted as (day, price) coordinates

Connect Points

Connect adjacent points and identify slope changes

Count Lines

Each slope change requires a new line segment

Key Takeaway

🎯 Key Insight: Count slope changes between consecutive point pairs to find minimum line segments needed

Asked in

M Meta 15 A Amazon 12 G Google 8

The key insight is that we need a new line segment whenever the slope between consecutive points changes. We sort the points by day, then compare slopes using cross multiplication to avoid floating point precision issues. Best approach uses cross multiplication with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Adjacent Pairs	O(n log n)	O(1)	Sort points by day, then compare slopes between consecutive point pairs
Optimized - Cross Multiplication	O(n log n)	O(1)	Use cross multiplication to avoid floating point precision issues

Brute Force - Check All Adjacent Pairs — Algorithm Steps

Sort points by day coordinate
Calculate slope between each adjacent pair
Count when slope changes from previous pair

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Points

Sort by day coordinate

Compare Slopes

Check if slope changes between segments

Count Lines

Increment counter when slope changes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    int *arr1 = *(int**)a;
    int *arr2 = *(int**)b;
    return arr1[0] - arr2[0];
}

int solution(int** stockPrices, int stockPricesSize) {
    if (stockPricesSize <= 2) {
        return stockPricesSize == 2 ? 1 : 0;
    }
    
    // Sort by day
    qsort(stockPrices, stockPricesSize, sizeof(int*), compare);
    
    int lines = 1;
    
    for (int i = 2; i < stockPricesSize; i++) {
        int x1 = stockPrices[i-2][0], y1 = stockPrices[i-2][1];
        int x2 = stockPrices[i-1][0], y2 = stockPrices[i-1][1];
        int x3 = stockPrices[i][0], y3 = stockPrices[i][1];
        
        // Check if slopes are different using cross multiplication
        if ((long long)(y2 - y1) * (x3 - x2) != (long long)(y3 - y2) * (x2 - x1)) {
            lines++;
        }
    }
    
    return lines;
}

int main() {
    // Simple parsing for demonstration
    int** stockPrices = malloc(100 * sizeof(int*));
    for (int i = 0; i < 100; i++) {
        stockPrices[i] = malloc(2 * sizeof(int));
    }
    
    // Read input manually - simplified for demo
    int size = 3;
    stockPrices[0][0] = 1; stockPrices[0][1] = 7;
    stockPrices[1][0] = 2; stockPrices[1][1] = 6;
    stockPrices[2][0] = 3; stockPrices[2][1] = 5;
    
    int result = solution(stockPrices, size);
    printf("%d\n", result);
    
    for (int i = 0; i < 100; i++) {
        free(stockPrices[i]);
    }
    free(stockPrices);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), then O(n) to process pairs

⚡ Linearithmic

Space Complexity

O(1)

Only storing slope variables, sorting is in-place

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Adjacent Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler