Problem

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.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

OR

Given an array of stock prices, where the increasing indexes of the array signify the increase in time. Return a good time to buy and sell such that profit is maximized. You are allowed to transact only once.

OR

Given an array A[], write an algorithm to find Maximum difference between two elements where larger element appears after the smaller element or in other words find A[i] and A[j] such that A[j]-A[i] is maximum where j > i.

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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input:
prices = [7,6,4,3,1]
Output:
 0
Explanation: In this case, no transactions are done and the max profit = 0.

Solution

Video explanation

Here is the video explaining below few methods in detail. Please check it out:

Method 1: Brute Force

This problem can be easily solved using two nested loops. Take each element at a time and compare it with all the other elements and keep the track of the maximum difference elements where larger element appears after the smaller element.

Code

Java
class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0; // Initialise maximum profit
        
        // Loop through all buy-sell pairs
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                ans = Math.max(ans, prices[j] - prices[i]); // Update maximum profit
            }
        }
        
        return ans;
    }
}
Python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans: int = 0  # Initialise maximum profit
        
        # Loop through all buy-sell pairs
        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                ans = max(ans, prices[j] - prices[i])  # Update maximum profit
                
        return ans

Complexity

  • ⏰ Time complexity: O(n^2), because we use two nested loops to check every pair of buying and selling days.
  • 🧺 Space complexity: O(1) as no additional data structures are used.

Method 2 - Greedy

The optimal solution leverages the idea of keeping track of the minimum price encountered so far and calculating the maximum profit along the way. This avoids the need to compare every pair of days explicitly, making the algorithm much more efficient.

Approach

  1. Initialise Variables:
    • min_price to store the minimum stock price encountered so far (initialised to infinity).
    • ans to store the maximum profit (initialised to 0).
  2. Iterate Through Prices:
    • At each day:
      • Check and update min_price if the current prices[i] is lower than the current min_price.
      • Calculate the profit for selling on the current day: profit = prices[i] - min_price.
      • Update ans if the calculated profit is greater than the current ans.
  3. Return the Result:
    • After iterating through all days, return the value of ans.

Code

Java
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE; // Start with the largest possible value
        int ans = 0; // Initialise maximum profit
        
        for (int p : prices) {
            if (p < minPrice) {
                minPrice = p; // Update the minimum price
            } else if (p - minPrice > ans) {
                ans = p - minPrice; // Update the maximum profit
            }
        }
        
        return ans;
    }
}
Python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price: int = float('inf')  # Start with the largest possible value
        ans: int = 0  # Initialise maximum profit
        
        for p in prices:
            if p < min_price:
                min_price = p  # Update the minimum price
            elif p - min_price > ans:
                ans = p - min_price  # Update the maximum profit
        
        return ans

Method 3 - Divide and Conquer

  • We need to find the two elements A[i] and A[j] so that A[j] – A[i] is maximum and j > i

  • Divide the input array into 2 parts, left Half and right half.

  • We have divided the problem in 2 parts. Now we can conclude that for answer-

    • Both indexes i and j are in the left half of the array.
    • Both indexes i and j are in the right half of the array.
    • Index i is in left half and index j is in right half of the array.

  • Solve the above 3 sub problems recursively and final answer will the maximum of these 3 sub problems.

This solution is very much similar to Merge sort.

Complexity

Time complexity is O(nlogn).

Code

Java
public int maxProfit(int[] prices) {
	return maxProfit(prices, 0, prices.length - 1);
}

private int maxProfit(int[] prices, int start, int end) {
	if (start >= end) {
		return -1;
	}
	int mid = start + (end - start) / 2;
	
	int leftDiff = maxProfit(prices, start, mid);
	int rightDiff = maxProfit(prices, mid + 1, end);
	
	int minLeft = getMin(prices, start, mid);
	int maxRight = getMax(prices, mid, end);
	
	int centerDiff = maxRight - minLeft;
	
	return Math.max(centerDiff, Math.max(leftDiff, rightDiff));
}

public int getMin(int[] nums, int i, int j) {
	int min = nums[i];
	for (int k = i + 1; k<= j; k++) {
		if (nums[k]<min)
			min = nums[k];
	}
	return min;
}
public int getMax(int[] nums, int i, int j) {
	int max = nums[i];
	for (int k = i + 1; k<= j; k++) {
		if (nums[k] > max)
			max = nums[k];
	}
	return max;
}

Method 4 - Kadane - Tracking Diff with Min Element so Far

In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:

  1. Maximum difference found so far (max_diff).
  2. Minimum number visited so far (min_element)

Code

Java
public int maxProfit(int prices[]) {
	int maxProfit = Integer.MIN_VALUE;
	int minElement = prices[0];
	int i;
	for (i = 1; i<prices.length; i++) {
		if (prices[i] - minElement > max_diff)
			maxProfit = prices[i] - minElement;
		if (prices[i]<minElement)
			minElement = prices[i];
	}
	return maxProfit;
}

Removing if condition:

public int maxProfit(int[] prices) {
	if (prices == null || prices.length<= 1) {
		return 0;
	}

	int min = prices[0]; // min so far
	int ans = 0;

	for (int i = 1; i<prices.length; i++) {
		ans = Math.max(result, prices[i] - min);
		min = Math.min(min, prices[i]);
	}

	return ans;
}

Complexity

Time Complexity: O(n), Auxiliary Space: O(1)

Method 5 - Kadane - Tracking Diff with Max Element so Far

Previous solution was on min_so_far, now we have max_so_far.

  • Traverse the array from right to left.
  • Maintain 2 variables – maxDifference (this will be our final answer), and max_so_far(maximum element we encounter while traversing the array)
  • During iteration, every element has 2 choices
    • Either current element is the maximum element among elements which are iterated, if yes then max_so_far = current element.
    • OR current element is less than the max_so_far. If yes then update the maxDifference = max_so_far – current element.
  • Once the iteration is done, return maxDifference.

Complexity

Time complexity: O(n), Space complexity: O(1)

Code

Java
 public static int maxDifference(int[] A) {
 	int size = A.length;
 	int maxDiff = -1;
 	int max_so_far = A[size - 1]; //assign the last element
 	for (int i = size - 2; i > 0; i--) {
 		if (max_so_far<A[i])
 			max_so_far = A[i];
 		else if (max_so_far > A[i])
 			maxDiff = Math.max(maxDiff, max_so_far - A[i]);
 	}
 	return maxDiff;
 }

Complexity

Time Complexity: O(n), Auxiliary Space: O(1)

Method 6 - Dynamic Programming - Max Sum Subarray

First find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now this problems turns into finding the maximum sum subarray of this difference array.

Code

Java
int maxProfit(int prices[],) {
	// Create a diff array of size n-1. The array will 
	// hold the difference of adjacent elements
	int diff[] = new int[n - 1];
	for (int i = 0; i<n - 1; i++) {
		diff[i] = arr[i + 1] - arr[i];
	}

	// Now find the maximum sum subarray in diff array
	int maxDiff = diff[0];
	for (int i = 1; i<n - 1; i++) {
		if (diff[i - 1] > 0) {
			diff[i] += diff[i - 1];
		}
		if (maxDiff<diff[i]) {
			maxDiff = diff[i];
		}
	}
	return maxDiff;
}

Method 7 - 2 Pointer Approach

Code

Java
int maxProfit(int arr[]) {
	int l = 0, r = 1; // left buy, right sell
	int maxProfit = 0;
	while(r < arr.length) {
		// is profitable transaction?
		if(price[l] < price[r]){
			int profit = price[r] - price[l]
			maxProfit = Math.max(profit, maxProfit);
		}else {
			l = r;
		}
		r++;
	}
}

Complexity

Time Complexity: O(n), Auxiliary Space: O(1)