Best Time To Buy And Sell Stock Solution for Accenture

Company: Accenture · Difficulty: Easy · Topics: Array, Dynamic Programming

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Key Understanding:

• You can only buy once and sell once
• You must buy before you sell
• You want to maximize the difference (sell price - buy price)
• If no profit is possible, return 0
• The array represents daily stock prices in chronological order

Examples

Example 1:

Input: prices = [7,1,5,3,6,4]

Output: 5

Explanation:

• Buy on day 2 (price = 1) and sell on day 5 (price = 6)
• Profit = 6 - 1 = 5
• This is the maximum possible profit
• Visual representation: [7,1,5,3,6,4] → Buy at 1, Sell at 6

Example 2:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation:

• The price continuously decreases
• No profit is possible (buying high, selling low)
• Best strategy is to not make any transaction
• Visual representation: [7,6,4,3,1] → All prices are decreasing

Example 3:

Input: prices = [1,2,3,4,5]

Output: 4

Explanation:

• Buy on day 1 (price = 1) and sell on day 5 (price = 5)
• Profit = 5 - 1 = 4
• Visual representation: [1,2,3,4,5] → Buy at 1, Sell at 5

Example 4:

Input: prices = [3,2,6,5,0,3]

Output: 4

Explanation:

• Buy on day 2 (price = 2) and sell on day 3 (price = 6)
• Profit = 6 - 2 = 4
• Visual representation: [3,2,6,5,0,3] → Buy at 2, Sell at 6

Intuition

The key insight is that we need to find the maximum difference between any two prices, where the selling price comes after the buying price. We can track the minimum price seen so far and calculate potential profits.

Core Concept:

• For each day, we can either:

1. Buy the stock (if it's the lowest price seen so far)

2. Sell the stock (if it gives us maximum profit)

3. Do nothing

Why One Pass Works:

• We don't need to look back at previous prices
• We only need to track the minimum price seen so far
• For each current price, we calculate potential profit
• We update our answer if we find a better profit

Mathematical Insight:

• If we buy at price[i] and sell at price[j], profit = price[j] - price[i]
• To maximize profit, we want to minimize price[i] and maximize price[j]
• Since we can't predict future prices, we track the minimum price seen so far

Approach

Approach 1: One Pass (Optimal)

Algorithm:

1. Initialize minPrice to the first price and maxProfit to 0

2. Iterate through prices starting from the second element

3. For each price:

• Update minPrice if current price is lower
• Calculate potential profit (current price - minPrice)
• Update maxProfit if potential profit is higher

4. Return maxProfit

Why This Works:

• We track the minimum price seen so far
• For each current price, we calculate what profit we would get if we sold now
• We update our answer if we find a better profit
• This ensures we find the maximum possible profit

Complexity Analysis:

• Time: O(n) - Single pass through the array
• Space: O(1) - Only constant variables needed

Approach 2: Two Pass (Finding Future Max)

Algorithm:

1. For each day, find the maximum price in the future

2. Calculate potential profit for each day

3. Return maximum profit

Why This Works:

• For each buying day, we find the best selling day in the future
• This gives us the maximum profit possible from each buying point

Complexity Analysis:

• Time: O(n²) - For each day, we scan future days
• Space: O(1) - Only constant variables needed

Approach 3: Brute Force

Algorithm:

1. Check all possible buy-sell pairs

2. Calculate profit for each pair

3. Return maximum profit

Why This Works:

• We try every possible combination of buy and sell days
• This guarantees we find the optimal solution

Complexity Analysis:

• Time: O(n²) - We check all possible pairs
• Space: O(1) - Only constant variables needed

Dry Run

Let's trace through Example 1: prices = [7,1,5,3,6,4]

One Pass Approach:

Step 1: Initialize

• minPrice = 7 (first price)
• maxProfit = 0

Step 2: Process each price

• i=1, price=1:
• minPrice = min(7,1) = 1
• maxProfit = max(0,1-1) = 0
• i=2, price=5:
• minPrice = 1 (unchanged)
• maxProfit = max(0,5-1) = 4
• i=3, price=3:
• minPrice = 1 (unchanged)
• maxProfit = max(4,3-1) = 4
• i=4, price=6:
• minPrice = 1 (unchanged)
• maxProfit = max(4,6-1) = 5
• i=5, price=4:
• minPrice = 1 (unchanged)
• maxProfit = max(5,4-1) = 5

Step 3: Return maxProfit = 5

Two Pass Approach:

Step 1: For each day, find future maximum

• Day 0: Future max = 6 (at day 4)
• Day 1: Future max = 6 (at day 4)
• Day 2: Future max = 6 (at day 4)
• Day 3: Future max = 6 (at day 4)
• Day 4: Future max = 4 (at day 5)
• Day 5: No future days

Step 2: Calculate profits

• Day 0: 6-7 = -1
• Day 1: 6-1 = 5
• Day 2: 6-5 = 1
• Day 3: 6-3 = 3
• Day 4: 4-6 = -2
• Day 5: No profit possible

Step 3: Return max profit = 5

Key Insights

1. Single Pass Efficiency: We don't need to look back or forward, just track minimum

2. Greedy Nature: We always want to buy at the lowest price seen so far

3. No Need for History: We only need the minimum price, not all previous prices

4. Early Termination: If we find a profit, we can continue to look for better

5. Edge Case Handling: If no profit is possible, return 0

Edge Cases

1. Single Element: Array with one price, return 0 (can't buy and sell)

2. Decreasing Prices: All prices decrease, return 0

3. Increasing Prices: All prices increase, buy first, sell last

4. Same Prices: All prices are same, return 0

5. Large Arrays: Algorithm handles large arrays efficiently

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: One Pass (Optimal)

Time Complexity: O(n) - We traverse the array once

Space Complexity: O(1) - We use only constant extra space

Advantages:

• Most efficient solution
• Single pass through array
• Constant space usage
• Simple and intuitive

Disadvantages:

• None for this problem

Solution 2: Two Pass

Time Complexity: O(n²) - We check future prices for each day

Space Complexity: O(1) - We use only constant extra space

Advantages:

• More intuitive approach
• Easy to understand

Disadvantages:

• Less efficient
• Higher time complexity

Solution 3: Brute Force

Time Complexity: O(n²) - We check all possible pairs

Space Complexity: O(1) - We use only constant extra space

Advantages:

• Guarantees optimal solution
• Easy to implement

Disadvantages:

• Least efficient
• Not suitable for large arrays

More Accenture coding questions