Bird
Raised Fist0

The following code attempts to implement the peak-valley approach but contains a subtle bug. Identify the line causing incorrect profit calculation.

medium🐞 Bug Identification Q14 of Q15
Greedy Algorithms - Best Time to Buy and Sell Stock II
The following code attempts to implement the peak-valley approach but contains a subtle bug. Identify the line causing incorrect profit calculation.
def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] > prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] < prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit
ALine with 'while i < n - 1 and prices[i] < prices[i + 1]:'
BLine with 'valley = prices[i]'
CLine with 'while i < n - 1 and prices[i] > prices[i + 1]:'
DLine with 'profit += peak - valley'
Step-by-Step Solution
Solution:
  1. Step 1: Compare with correct condition

    The correct condition should be prices[i] >= prices[i + 1] to skip equal or descending prices.
  2. Step 2: Identify bug impact

    Using strict '>' misses equal prices, causing incorrect valley selection and possibly negative profit.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Changing '>' to '>=' fixes edge cases with flat prices [OK]
Quick Trick: Check comparison operators in loops for off-by-one errors [OK]
Common Mistakes:
MISTAKES
  • Using strict inequalities causing missed equal prices
  • Adding negative differences to profit
  • Off-by-one errors causing index out of range
Trap Explanation:
PITFALL
  • Strict inequality looks correct but fails on equal adjacent prices, a subtle edge case.
Interviewer Note:
CONTEXT
  • Tests attention to detail and handling of edge cases in greedy loops.
Master "Best Time to Buy and Sell Stock II" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Greedy Algorithms Quizzes