Do you think IIT Guwahati certified course can help you in your career?
Introduction
Arrays are one of the most important topics from an interview perspective. Questions related to Arrays are frequently asked in the technical interview of Product-based companies in the initial stages. Therefore it's quite important to have a solid understanding of Arrays and practice questions related to Arrays.
This blog will discuss a commonly asked interview question, the Best time to buy and sell stock, wherein the prices of the stocks will be stored in an array. You need to find the maximum profit possible.
The problem statement on hand says, "You are given an array of integers, prices where prices[i] is the price of a given stock on an ith day. You want to maximize the profit by choosing a single day to buy one stock and a different day to sell that stock. Return the maximum profit you can achieve from this transaction".
The point to consider here is to choose a single day to buy one stock and a single day to sell that stock. And you can’t sell a stock before you buy one.
Let’s look at possible input-output pairs before moving on to the solution.
Input: prices = [7, 1, 5, 4, 3, 6]
Output: 5
Explanation: Purchase stock on day two wherein the price is 1 and sell it on day six wherein the price is 6, profit = 6 - 1 = 5.
Input: prices = [100, 160, 220, 40, 535, 695]
Output: 655
Explanation: Purchase stock on day four wherein the stock price is 40 and sell it on day six wherein the price is 695, profit = 695 - 40 = 655.
If you can't make sense of how we have calculated the profits, you may refer to the following table that calculates the profit when purchasing the stock on day 1.
Stock Purchase Day
Possible selling days
Profit
(Day 2 - Day 1)
Profit
(Day 3 - Day 1)
Profit(Day 4 - Day 1)
Profit(Day 5 - Day 1)
Profit(Day 6 - Day 1)
Day 1
Day 2
Day 3
Day 4
Day 5
Day 6
160 - 100
= 60
220 - 100
=120
40 - 100
= -60
535 - 100
= 435
695 - 100
=595
Input: prices = [100, 90, 80, 70, 34, 20]
Output: 0
Explanation: The stock prices are decreasing every day so that no profit can be earned.
Approach 1: Best time to buy and sell stock
As can be seen from the sample input-output examples, a possible approach would be to buy a stock and sell it on every possible day whenever profitable and keep updating the maximum profit so far.
This will require two nested loops, the outer one will pick up each day, say i, one by one to purchase that stock, and the inner loop will calculate the profit if the stock is sold on each of the possible days.
Algorithm
Initialize maxProfit with 0.
Use two nested loops, the outer one will consider the day in which the stock will be purchased and the inner one will consider the days in which the stock will be sold.
Find the maximum profit by buying and selling at each index. At each iteration, find the profit. Change the value of the maxProfit if the profit obtained is greater than the maxProfit
Return the maximum profit.
Implementation
The implementation of the algorithm is given below:
publicclass Solution {
publicstaticint maxProfit(int[] prices) {
// Brute force approach
int maxProfit = 0;
for(int i = 0; i < prices.length - 1; i++){
for(int j = i + 1; j < prices.length; j++)
{
int profit = prices[j] - prices[i];
maxProfit = Math.max(profit, maxProfit);
}
}
return maxProfit;
}
publicstaticvoid main(String[] args) {
System.out.println("Maximum profit in prices1 array is: ");
int[] prices1 = {7, 1, 5, 4, 3, 6};
System.out.println(maxProfit(prices1));
System.out.println("\nMaximum profit in prices2 array is: ");
int[] prices2 = {100, 160, 220, 40, 535, 695};
System.out.println(maxProfit(prices2));
System.out.println("\nMaximum profit in prices3 array is: ");
int[] prices3 = {100, 90, 80, 70, 34, 20};
System.out.println(maxProfit(prices3));
}
}
The output of the above program is:
Maximum profit in prices1 array is:
5
Maximum profit in prices2 array is:
655
Maximum profit in prices3 array is:
0
Complexity Analysis
The algorithm's time complexity is O(n^2), where n is the number of days.
The space complexity is O(1).
Approach 2: Best time to buy and sell stock
In an interview, it is recommended that if you cannot figure out the correct answer in one go, try to analyze the problem statement and the possible input-output pairs. Figure out how to reduce the computation in the brute force approach and try to eliminate repetitive steps. There are high chances that you will get to the optimized solution.
In the question we are discussing, an important point to notice is the maximum profit on the ith day is:
price of the stock on an ith day - min value of stock till the ith day
Taking an example for understanding, prices[] = {7, 1, 5, 4, 3, 6}
Max profit on Day 3 = Stock price on Day 3 - Minimum of Stock price of Day 1 and Day 2
= 5 - 1 = 4
Max profit on Day 4 = Stock price on Day 4 - Minimum of Stock price of Day 1, Day 2 and Day 3
= 4 - 1 = 3
In general, max profit on Day n = Price of stock on Day n - min(Day 1, Day 2, ………., Day n-1).
Algorithm
Make two variables, maxProfit = 0, to store the maximum profit and minCost = Integer.MAX_VALUE to store the minimum price of stock till the ith day.
Linearly traverse the stock prices array.
Keep track of the minimum element on the left side.
Calculate the profit on an ith day, considering that we are selling the stock on an ith day and purchase the stock at the minimum price of the stock till the ith day. Update the maxProfit value if the profit is greater than the maxProfit.
Return the maxProfit.
Implementation
The implementation of the above algorithm is:
publicclass BestTime{
publicstaticint findMaxProfit(int[] prices)
{
int minCost = Integer.MAX_VALUE;
int profit = 0;
for(int i = 0; i < prices.length; i++)
{
minCost = Math.min(minCost, prices[i]);
profit = Math.max(profit, prices[i] - minCost);
}
return profit;
}
publicstaticvoid main(String[] args) {
System.out.println("Maximum profit in prices1 array is: ");
int[] prices1 = {7, 1, 5, 4, 3, 6};
System.out.println(findMaxProfit(prices1));
System.out.println("\nMaximum profit in prices2 array is: ");
int[] prices2 = {100, 60, 220, 40, 35, 195};
System.out.println(findMaxProfit(prices2));
System.out.println("\nMaximum profit in prices3 array is: ");
int[] prices3 = {100, 45, 0, 7, 34, 20};
System.out.println(findMaxProfit(prices3));
}
}
The output of the above program is:
Maximum profit in prices1 array is:
5
Maximum profit in prices2 array is:
160
Maximum profit in prices3 array is:
34
Complexity Analysis
The time complexity is O(N), as only a single linear traversal of the array is needed.
Variations of the Best time to Buy and Sell Stock Problem
The problem discussed above relies on the thought that you can only buy the stock once and sell it once. There are many possible variations of this problem, some of which are enlisted below:
You can have as many transactions as you want. A transaction denotes buying and selling one share of stock.
The blog discussed an important interview problem, the best time to buy and sell stock. Various approaches along with code in java were discussed. With this done, you may practice more questions related to Arrays.
A common problem faced by all of us is we prepare well, but during online assessments, we are unable to solve the questions on time. To overcome this, Coding Ninjas have come up with an online mock test series. The mock tests for leading companies like Amazon, Microsoft, Google, Adobe, Flipkart, TCS, Wipro, and Accenture are available for free.
Our team of experts has curated and designed these online mock test series to help you prepare better for your coding interview rounds. In this online test series, you will get multiple tests that include the latest coding interview questions. Start preparing for the 2021 Amazon, Microsoft, etc., tech interviews now.
Live masterclass
SDE LinkedIn & Naukri Hacks to Get More Recruiter Calls
by Pranav Malik
18 Apr, 2025
01:30 PM
Microsoft SDE Roadmap: Use AI Tools to Succeed
by Pranav Malik
14 Apr, 2025
01:30 PM
Amazon's expert tips on Non-tech to Data Analytics transition
by Abhishek Soni
15 Apr, 2025
01:30 PM
Crack Big4 Data Analytics interview: Dos & Don'ts
by Alka Pandey
17 Apr, 2025
01:30 PM
High-Paying SDE Role: How to job hunt effectively
by Shantanu Shubham
16 Apr, 2025
01:30 PM
SDE LinkedIn & Naukri Hacks to Get More Recruiter Calls
34+ registered 
