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

Predictive analytics: Olympic medal prediction model using Python

by Ashwin Goyal, Product @ HRS Groups, Ex - Udaan, OYO

17 Aug, 2024

01:30 PM

Top Project ideas to ace Amazon SDE interview

by Anubhav Sinha, SDE2 @ Amazon

06 Aug, 2024

01:30 PM

Master PowerBI using T20 World Cup Data

by Ashwin Goyal, Product @ HRS Groups, Ex - Udaan, OYO

09 Aug, 2024

01:30 PM

Projects ideas to get shortlisted for analytical roles at MAANG

by Abhishek Soni, Data Scientist @ Amazon

12 Aug, 2024

01:30 PM

How to clear Google SDE interview?

by Saurav Prateek, SDE2@Google

14 Aug, 2024

01:30 PM

Predictive analytics: Olympic medal prediction model using Python

by Ashwin Goyal, Product @ HRS Groups, Ex - Udaan, OYO