[Challenge] Maximize Stock Trading Profit

Events & Challenges
1

Code Challenge #8: May 31, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reportedly asked in interviews at Google:

Basic Difficulty

Given the daily values of a stock, write a program that will find how you can gain the most with a single buy-sell trade.

You may assume …

  • Your function should be called bestDays and take one array of integers as an input.
  • Daily stock values will be represented in an array of integers (arr[]) representing the stock price at the beginning or “opening bell” of each day.
  • You may use the following as a test array, from day 0 through day 7: {17, 11, 60, 25, 150, 75, 31, 120}. In this case, purchasing on day one and selling on day four would yield the most profit.
  • bestDays analyses historical data and returns when one should have bought and sold to maximize profit, it is not designed to predict the future. If you do manage to write a program that accurately predicts future stock market trends, congratulations, you’ll be very very rich.
  • You are required to buy and sell only once.
  • For the sake of this exercise, you will only ever be purchasing, owning, or selling one share.
  • bestDays should return the day on which one should buy a share, followed by the day on which one should sell a share, as integers.
Find out more about basic challenges.

Intermediate difficulty

Given the daily values of a stock over a number of days n, write a program that will find how you can gain the most with a combination of buy-sell trades.

  • You can only make one transaction per day, and new transactions can take place only after the previous transaction is complete (e.g. buy :arrow_forward: sell :arrow_forward: buy :arrow_forward: sell). For example, if you sold on day 3 you could not also buy on day 3, you would have to wait until day 4 or later to purchase again.
  • You may use the following as a test array, from day 0 through day 7: {90, 170, 250, 300, 30, 525, 685, 90}. In this case, purchasing on day zero and selling on day three, then buying again on day four before selling on day six would yield the most profit.

Your function should be called bestDays and take one array of integers as an input. bestDays should output a 2D array of the form [[buyDay1, sellDay1],[buyDay2, sellDay2], ..... , [buyDayN, sellDayN]], where buyDayX and sellDayX are integers corresponding to the days in the input array.

Find out more about intermediate challenges.

Hard Difficulty

Solve the basic and intermediate versions of this challenge as efficiently as possible.

Find out more about hard challenges and Big O

The Winner

Congratulations to @arthgw for submitting the fastest-running entry that produced good outputs!

The challenge may already have a winner, but you are more than welcome to challenge yourself! Scroll down and reply to this thread with your code to participate! Don’t just submit your code, remember to explain your solution, too! If you want your entry to be considered under our “best code” assessment, you must include a link to your code running on repl.it and abide by our other simple rules.

The fine print:

Click the links to find out more about:

tip: if you include the repl.it URL to your code on its own line, it will embed in your post!

1 Like
2

Hi @danieloduffy,

For the solutions, are we required to perform a buy and a sell? For example, if arr is [5, 4, 3, 2, 1], the best strategy would be to not buy and sell at all.

Note that this uses the word allowed, rather than required …

You are allowed to buy and sell only once.

4 Likes
3

I’d say yes, you must make a transaction, and thus in this case your function should seek to minimize your losses.

4 Likes
4

here’s my solution to the basic challenge on repl: https://repl.it/IZiV/0

& here’s the code

function bestDays(days){
  let daysCopy = days.map((day)=>{
    return day
  }).sort((a, b)=>{
    return a - b
  })
  return [days.indexOf(daysCopy[0]), days.indexOf(daysCopy[daysCopy.length - 1])]
}
5

Here’s my solution to the intermediate challenge: https://repl.it/IZmr/1
Here’s the code:

function bestDays(days){
  let answer = []
  let daysCopy = days.map((day)=>{return day}).sort((a,b)=>{return b-a})
  days.map((day)=>{
    if(daysCopy.length > 1){
      answer.push([days.indexOf(daysCopy.pop()), days.indexOf(daysCopy.shift())])
    }
  })
  return answer
}

just realized my solution could require a time machine, yeah, stay tuned

6

Python 3, basic challenge. A simple loop through the list that collects all stock returns wherever a later day’s price is greater than an earlier days. One (rather inevitable, I guess) optimization is that I only look at days after the current day being checked, so the comparisons decrease as the week progresses. I wonder if anyone can tell me what the O() value would be, since technically it’s less than O(n^2) but more than O(n)… Something like O(n!)?
https://repl.it/I12j/0

7 
def bestDays(list1):
    a=b=list1[0]
    loca=locb=0
    for i in range(1,len(list1)):
        if list1[i]<a:
            a=list1[i]
            loca=i
        elif list1[i]>b:
            b=list1[i]
            locb=i
    profit=b-a
    buyOn=loca
    sellOn=locb
    print "Profit = ", profit, "\n Buy On = ",buyOn,"\n Sell on = ",sellOn

list1=list(input("Enter list"))
bestDays(list1)

I did it with Python 2.7
Basically there are 4 variables, 2 to store the greatest and least value and 2 to store the location in the list. Then the for loop is used to traverse the list and find the greatest and least values and their index location, and this in the printed out.

8

Basic Difficulty

All code is explained in the repl

https://repl.it/I0BZ/1

1 Like
9

Thanks, Daniel. Let’s hope for a bull market. :smiley:

3 Likes
10

Heres my code for the basic challenge before I start on the intermediate! (Written in Python)

def bestDays(stock):
    lowest = stock[0]
    lday = 0
    highest = stock[0]
    hday = 0
    for i in range(len(stock)):
        if stock[i] <= lowest:
            lowest = stock[i]
            lday = i
        if stock[i] >= highest:
            highest = stock[i]
            hday = i
    print('Buy on day ' + str(lday) + ' and sell on day ' + str(hday) + '.')

First time doing anything in python (or really any coding in general, to be honest) in many months, so I was quite a bit rusty, but I got it done!

Edit: I just noticed mine could return a sell first, buy later deal, so I’ll have to go back and fix that!

11

What exactly is this function supposed to return? is the an int with highest profit? Return nothing but print a statement along the lines of “if you buy on x day and sell on y date, you will maximize your profit and make z dollars?” Or something completely different?
Thanks!

12

For intermediate difficulty:

Your function should be called bestDays and take one array of integers as an input. bestDays should output a 2D array of the form [[buyDay1, sellDay1],[buyDay2, sellDay2], ..... , [buyDayN, sellDayN]], where buyDayX and sellDayX are integers corresponding to the days in the input array.

The basic difficulty should just return [buyDay1, sellDay1].

2 Likes
13

Basic

(Intermediate is below)
Here’s the repl.it link to my solution to the basic problem in Python3: https://repl.it/I0SC/1

The algorithm keeps track of the smallest value encountered so far (minSoFar) and its index (minSoFarInd), as well as the indices of the days on which to buy (absMinInd) and sell (absMaxInd), and the largest value gained thus far (maxDiff).

It goes sequentially through the array; if it encounters a new minimum value, it updates minSoFar and minSoFarInd to reflect this. Otherwise, it checks if selling a stock bought at the price minSoFar on day minSoFarInd and selling on the current day would result in a gain larger than the largest gain found so far. If the gain is larger, then it updates the maximum gain in maxDiff, and updates the indices of the days on which to buy and sell.

Here’s the code itself:

def bestDays(arr):
  '''Solves the basic challenge'''
  minSoFar = arr[0]
  minSoFarInd = 0
  absMinInd = 0
  absMaxInd = 0
  maxDiff = -999999999
  for (pos, val) in enumerate(arr):
    if val < minSoFar:
      minSoFar = val
      minSoFarInd = pos
    elif val - minSoFar > maxDiff:
      maxDiff = val - minSoFar
      absMinInd = minSoFarInd
      absMaxInd = pos
  return (absMinInd, absMaxInd)

Intermediate

Repl.it for the intermediate solution: https://repl.it/I0Zu/1

Explanation:
The algorithm starts by discarding arrays of length < 2 since these violate the challenges rules (must buy and sell, but not on the same day).

The algorithm uses the function findSeqs(arr) to generate an array of indices of the stocks, where alternating indices represent peaks and troughs of the stock price; in other words, the index of the end of a contiguous decreasing sequence of values (trough), followed by the index of the end of a contiguous increasing sequence of values (peak), followed by index of the end of a decreasing sequence, … Note that the last value in the array is always the end of either an increasing or decreasing sequence, and it is added as such.

If the sequence of troughs and peaks has length exactly 1, then the values are a constantly decreasing sequence, so the smallest negative difference is found in order to minimize loss by checking every neighbouring pair of values to find the closest pair. The smallest pair will always be neighbouring because if a ≤ b ≤ c then a - b ≥ a - c.

Otherwise, if there are multiple peaks and troughs, the sequence is truncated by at most 1 so that it becomes even; this is because if it has an odd length, then the last index is the bottom of a trough, so any buying and selling after the last peak will always be a net loss. Finally, the list of indices is divided into an array of [trough, peak] pairs and this array is returned.

Quick proof that it is always most profitable to sell on a peak and buy on a trough: let a be a peak and b be any value in the increasing sequence peaking at a; let c be the purchasing price. a is the peak, so a ≥ b; thus a - c ≥ b - c, and so the gain of selling at the peak is higher than anywhere in the sequence. Similarly, let c be the selling price and a be a trough and b be any value in the decreasing sequence for which a is the trough. a ≤ b so c - a ≥ c - b, and so selling at the trough will always result in a higher value.

Quick proof sketch that it is most profitable to sell on alternating peaks and troughs. Suppose we have t0, p0, t1, p1, where ti is a trough and pi is a peak, and a higher value of i means that the peak or trough occurs later. It is clear that buying at a peak or selling at a trough is never profitable, so ignore those cases. Then the only possibilities are buying at t0 and selling at p1 or buying at both troughs and selling at both peaks. But p0 - t0 + p1 - t1 = (p1 - t0) + (p0 - t1). Since t1 is the trough directly following p0, we have p0 > t1, and so p0 - t1 > 0. From this we can conclude that (p1 - t0) + (p0 - t1) > (p1 - t0) + 0.
Thus selling at alternating peaks is more profitable than any other pattern of buys and sells for sequences of length 2.

Assume for induction purposes that selling at alternating peaks and troughs is maximally profitable for a sequence of peaks and troughs of length k, i.e. for the sequence t1, p1, t2, p2, …, tk, pk, buying at a trough and selling at the next peak is more profitable than any alternative/subsequence. of length at most k. Consider a sequence of length k+1: t1, p1, t2, p2, …, tk, pk, tk+1, pk+1. We know by assumption that p1 - t1 + p2 - t2 + … + pk - tk is maximally profitable for length k. We also know that pk+1 > tk+1 which means pk+1 - tk+1 > 0. Putting this together, p1 - t1 + p2 - t2 + … + pk - tk + pk+1 - tk+1 > p1 - t1 + p2 - t2 + … + pk - tk + 0, hence it is greater than any possible peak/trough sum of length k or less; and since it is clearly the only choice of length k+1 for this sequence, it must be the maximum.
So by induction, selling at alternating peaks and troughs is the most profitable, and the algorithm is correct

The code:

def findSeqs(arr):
    '''Returns an array of positions where even positions are the end of decreasing sequences and odd positions are the 
end of increasing sequences'''
  indices = [] 
  decreasing = True
  prev = arr[0]
  for (pos, val) in enumerate(arr):
    if pos == 0:
      continue
    if (decreasing and val > prev) or (not decreasing and val < prev):
      decreasing = not decreasing
      indices.append(pos - 1) # previous day is end of sequence
    else:
      prev = val
  # the last element hasn't been added; it is always the end of an increasing or decreasing sequences
  indices.append(len(arr) - 1)
  return indices

def bestDays(arr):
  if len(arr) < 2: # cannot buy and sell on same day so this is unsupported
    return []
  seqs = findSeqs(arr)
  if len(seqs) == 1: # the array is constantly decreasing; minimize loss 
    prev = arr[1]
    ind = 1
    maxDiff = arr[1] - arr[0]
    for (pos, val) in enumerate(arr):
      if pos == 0 or pos == 1:
        continue
      if val - prev > maxDiff:
        maxDiff = val - prev
        ind = pos
      prev = val
    return [[ind - 1, ind]]
  
  if len(seqs) % 2 == 1: # ends on a decreasing sequence
    seqs = seqs[:len(seqs)-1]
  
  # then just sell at the peaks and buy at the troughs
  days = []
  for i in range(1, len(seqs), 2):
    days.append([seqs[i-1], seqs[i]])
  return days

Hard

Both the basic and intermediate algorithms are O(n) where n is the length of the given array. I assume this cannot be improved upon because you need to look at every element at least once in order to know if it would be better to buy/sell on that day.

Edit: Fixed market crash issue. Thanks to @b-twin for the heads up! :smile:

5 Likes
14

Note that your solution can return sell first and buy later.

function bestDays(days){
  var maxDiff = -Infinity;
  var buyDay = 0, sellDay = 0;
  for (var i=days.length-1; i>0; i--) {
    for (var j=i-1; j>=0; j--) {
      if (days[i]-days[j]>maxDiff) {
        maxDiff = days[i]-days[j];
        buyDay=j;
        sellDay=i;
      }
    }
  }
  return `Buy at day ${buyDay} and sell at day ${sellDay}`;
}

Maybe not the best solution, but it works for the Basic Difficulty

2 Likes
15

I noticed that, went back to fix it, got distracted :anguished:

17

@danieloduffy there is a mistake with the example for the intermediate challenge. Only 7 values are given and the given solution has days indexed from 0 to 7 (eight days in total).

2 Likes
18

Javascript: https://repl.it/I0TY/7

19

hi! this looked like fun, so i gave it a shot. here’s my working code:

https://repl.it/I0Op/2

my code is fairly verbose compared to the other solutions submitted, but that’s ok. instead of going for the quickest win, i wanted to build/work with a data model that made sense to me, so this is why my functions turn an array of integers into structured trades (for the basic challenge) and trade combos (for the intermediate challenge). each trade consists of a buy (with day and price), a sell (also day and price), and a profitLoss (diff between sell and buy). and then each combo consists of an array of chronological trades and a totalProfit from those trades.

i also thought it would be more practical (and easier to test/debug) if my functions returned a sorted list of all possible trades/combos instead of just returning the best or max profit. this lets the consumer see the different options, which could be useful when multiple options result in the same profit (in which case the consumer might prefer the shortest or earliest trade or the max profit combo with fewest number of required trades).

at any rate, my basic challenge solution uses a double iteration approach to putting together all possible trades, starting with each day you could buy on and iterating from there for each possible subsequent sell. once all possible trades are determined, we just sort them by (1) max profit desc, (2) shortest time, and (3) earliest time.

my intermediate challenge solution builds on top of that to iterate over all possible trades (which are unique), adding each individual trade as its own possible combo, and combining trades as long as they (1) don’t overlap with any other trades in that combo and (2) actually increase the total profit for the combo. once all the combos are determined, i simply make sure that each combo’s trades are in chronological order and then sort all combos by max profit desc and fewest number of trades (gotta watch out for those commission fees, after all!).

i also throw in a couple type safety checks, ignoring or coercing unexpected data types (i.e. non-array or non-number params), just out of habit. so that’s basically it. enjoy!

1 Like
20

  • I used Java programming to solve the Basic Difficulty. My program does work but I really need your comments for improvement.

  • I have 2 static methods. bestDay(int array) and main method. The method bestDay will return an array that contains 2 days to sell and buy, which gives the user most gain or least lose - if the stock market goes sour.

  • I use linear search for the input array to find the days. If the diff > max value then store the days in array and assign max to diff. However, if the diff < 0, then assign min value to diff and use min as reference variable to compare with diff if there are more than 1 diff < 0.

  • count variable is used to keep track of number of times diff < 0. If count > 1, then compare diff with min.
    package stockTrading;

    public class BestDay {

    public static int bestDay(int stockPrices){
    int arr = new int[2];
    int diff = 0; // Differences between stock prices of 2 days
    int max = 0; // Store the most gain among 8 days
    int min = 0; // Store the least lose among 8 days
    int count = 0; // Count number of times diff <= 0

      for(int i = 0; i < stockPrices.length - 1; i++){
  	for(int j = i + 1; j < stockPrices.length; j++){
  		diff = stockPrices[j] - stockPrices[i];
  		
  		if(diff > max){
  			max = diff;
  			arr[0] = i;
  			arr[1] = j;
  		}
  		else if(diff <= 0 && max == 0){ // If diff is negative and max  value has not changed
  			count++;
  			if(count == 1){ // assign min to diff
  				min = diff;
  				arr[0] = i;
  				arr[1] = j;
  			}
  			else if(count > 1){
  				if(diff >= min){
  					min = diff;
  					arr[0] = i;
  					arr[1] = j;
  				}
  			}
  		}
  		
  	
  	}
  }
  
  return arr;

    }

    public static void main(String args){
    //int stockPrices = {17, 11, 60, 25, 150, 75, 31, 120};
    int stockPrices = {8,5,4,2,0};
    long startTime = System.currentTimeMillis();
    int days = bestDay(stockPrices);
    long endTime = System.currentTimeMillis();

      double diff = (startTime - endTime) / 1e6;
  
  	System.out.println("Day1 = " + days[0] + ", Day2 = " + days[1]);
  	System.out.println("Time differences = " + diff);

    }
    }

1 Like
21

Here’s my solution to the basic problem in Python 2: https://repl.it/I0YW
It iterates through every buy-day, then iterates through every possible sell-day, and computes the maximal difference between the two using the variable ‘max_value’. It runs in O(n^2) time because it passes through each value in the array passed as a parameter on average n/2 times.

Here’s my solution to the intermediate problem, also in Python 2: https://repl.it/I021/0
It finds every point where selling will gain more money than holding on (i.e. the points where we already own a share and the current price is higher than the next day’s price), and the points where buying will be efficient (i.e. the points where we don’t own a share and the current price is lower than the next day’s price). Despite its use of a nested loop, it runs in O(n) time because it passes through every value in the array passed as a parameter exactly once.

This is my first time participating in the Codecademy challenges. If anyone has any comments or feedback, I’d love to hear it!

2 Likes