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 days, resulting in O(n squared) time complexity, which is inefficient for large datasets often handled at Amazon scale. Instead, I propose a single-pass algorithm. We initialize two variables: minPrice set to infinity and maxProfit set to zero. As we iterate through the prices array, for each day's price, we first check if it is lower than our current minPrice; if so, we update minPrice. Then, we calculate the potential profit by subtracting minPrice from the current price. If this calculated profit exceeds our recorded maxProfit, we update maxProfit. This ensures that at any point, we are comparing the current price against the lowest historical price available up to that moment. For example, with prices [7, 1, 5, 3, 6, 4], the algorithm identifies 1 as the min, calculates profits like 5-1=4, 6-1=5, and correctly returns 5. This approach runs in O(n) time since we traverse the list once, and uses O(1) space, meeting the strict efficiency requirements typical of Amazon technical interviews.
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
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.