Best Time to Buy and Sell Stock (I)
You are given an array of prices where `prices[i]` is the price of a given stock on the $i$-th day. Find the maximum profit you can achieve. Solve in $O(n)$.
Why Interviewers Ask This
Amazon interviewers use this problem to assess your ability to optimize for time complexity while maintaining code clarity. They specifically evaluate whether you can identify that a single pass solution is superior to nested loops, reflecting their 'Bias for Action' and focus on efficient resource usage in high-scale systems.
How to Answer This Question
1. Clarify constraints: Confirm if multiple transactions are allowed (they are not here) and if short selling is permitted (no). 2. Define the goal: Maximize profit from one buy followed by one sell where buy date < sell date. 3. Propose the brute force: Briefly mention O(n^2) nested loops to show baseline understanding, then immediately pivot to the optimal approach. 4. Explain the single-pass logic: Iterate through the array once, tracking the minimum price seen so far. For each day, calculate potential profit by subtracting the min price from current price. 5. Update global maximum: Compare current potential profit with the running maximum and update if higher. 6. Handle edge cases: Mention empty arrays or single-element lists returning zero. 7. Analyze complexity: Explicitly state O(n) time and O(1) space, aligning with Amazon's expectation for scalable solutions.
Key Points to Cover
- Explicitly stating the O(n) time complexity requirement upfront
- Demonstrating the transition from brute force to optimized single-pass logic
- Correctly handling the constraint that buying must precede selling
- Using clear variable names like minPrice and maxProfit for readability
- Briefly analyzing space complexity to show full algorithmic awareness
Sample Answer
To solve this efficiently, I would first clarify that we are looking for the maximum profit from a single transaction, meaning we must buy before we sell. A naive approach using two nested loops would check every pair of…
Common Mistakes to Avoid
- Attempting to find the absolute minimum and maximum values in the array without checking their indices, leading to invalid buy-before-sell scenarios
- Ignoring edge cases such as an empty array or a strictly decreasing price sequence where profit is zero
- Implementing a nested loop solution that results in O(n^2) complexity despite the O(n) requirement
- Failing to explain the thought process behind why tracking the running minimum is sufficient for finding the global maximum profit
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.