Instead of checking every buy-sell combination, keep track of the minimum buying price seen so far. For every new price: - Update the minimum price. - Calculate today's possible profit. - Store the maximum profit. This greedy strategy reduces the time complexity from O(n²) to O(n) while using constant extra space.
Problem stats
Before
Check every possible buying day with every possible selling day after it.
For each pair:
1. Buy on day i.
2. Sell on day j where j > i.
3. Calculate the profit.
4. Keep track of the maximum profit found.
Although this approach is simple to understand, it requires checking all pairs, making it inefficient for large inputs.
After
Traverse the array only once while keeping track of the minimum stock price seen so far.
For each day's price:
1. Update the minimum buying price if the current price is lower.
2. Calculate the profit by selling today.
3. Update the maximum profit if the current profit is greater.
This greedy approach finds the answer in a single traversal.
The optimized implementation, ready for interview preparation and quick revision.
Solution.java
1public class Solution {2 3 public int maxProfit(int[] prices) {4 5 int minPrice = Integer.MAX_VALUE;6 int maxProfit = 0;7 8 for (int price : prices) {9 10 if (price < minPrice) {11 minPrice = price;12 } else {13 14 int profit = price - minPrice;15 16 if (profit > maxProfit) {17 maxProfit = profit;18 }19 }20 }21 22 return maxProfit;23 }24 25 public static void main(String[] args) {26 27 Solution solution = new Solution();28 29 int[] prices = {7, 1, 5, 3, 6, 4};30 31 System.out.println(solution.maxProfit(prices));32 }33}Analyze the efficiency of the algorithm by understanding its time and space complexity across different execution scenarios.
Time complexity
Space complexity
By execution case
Best case
O(n)
Average case
O(n)
Worst case
O(n)
This solution achieves a O(n) time complexity while using O(1) extra memory. It is considered the optimal approach for this problem and is suitable for coding interviews as well as competitive programming.
Every coding problem teaches a pattern. Focus on the concepts, avoid common mistakes, and remember the interview-worthy takeaways instead of memorizing code.
The biggest takeaway from this problem.
Instead of checking every buy-sell combination, keep track of the minimum buying price seen so far. For every new price: - Update the minimum price. - Calculate today's possible profit. - Store the maximum profit. This greedy strategy reduces the time complexity from O(n²) to O(n) while using constant extra space.
Explain why the optimized solution works before writing the final code. Interviewers care about your thinking process as much as your implementation.
Avoid jumping directly to coding. Always analyze edge cases, constraints, and the optimal approach before implementation.
Focus on understanding the algorithm's pattern instead of memorizing the code. Once the logic becomes clear, implementing the solution in any programming language becomes much easier.
Every DSA problem introduces a reusable pattern. Instead of remembering the exact solution, remember the thought process that led to it. Over time, these patterns will help you solve new problems much faster and perform better in coding interviews.
Practice consistently and move through the roadmap one problem at a time.
Practice similar problems to strengthen your understanding of the underlying algorithm and improve pattern recognition.