We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Lines to Represent a Line Chart

Difficulty: Medium

Problem Description

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.

Key Insights

  • The line connecting two points is determined by their slopes.
  • If three consecutive points are collinear, they can be represented by a single line.
  • The number of lines increases whenever the slope between two consecutive points changes.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the points based on the day. Space Complexity: O(1) - only a few variables are used for calculations.

Solution

To solve the problem, we will first sort the stockPrices based on the day. Then, we will iterate through the sorted list and calculate the slope between consecutive points. If the slope changes, we increment our line count. The slope between two points (x1, y1) and (x2, y2) can be calculated using the formula (y2 - y1) / (x2 - x1). We must be cautious with integer division to avoid precision issues.

Code Solutions

def minimum_lines(stockPrices):
    if len(stockPrices) <= 1:
        return 0
    
    # Sort the stockPrices based on the day
    stockPrices.sort()
    
    lines = 0
    previous_slope = float('inf')
    
    for i in range(1, len(stockPrices) - 1):
        x1, y1 = stockPrices[i - 1]
        x2, y2 = stockPrices[i]
        x3, y3 = stockPrices[i + 1]
        
        # Calculate the slope between (x1, y1) and (x2, y2)
        current_slope = (y2 - y1) * (x3 - x2) - (y3 - y2) * (x2 - x1)
        
        # If current slope is not equal to previous slope, we need a new line
        if current_slope != 0:
            lines += 1
        
    return lines + 1  # Add one for the last segment
← Back to All Questions