## CodinGame - Solution in Javascript to Stock Exchange Losses Problem

This is a Javascript implementation for a solution to the CodinGame Stock Exchange Losses problem.

The post is the fourth in a series that I started with the goal of testing the feasibility of solving CodinGame challenges in Javascript. You can also check out the third and second solutions that I posted earlier.

var n = readline(); var prices = []; // prices array will hold price values prices = readline().split(' '); // read stock prices // this is javascript // so we have to make sure the prices are interpreted as integers for(var i = 0; i < prices.length; i++) prices[i] = parseInt(prices[i]); var localMinIdx = 0; var localMaxIdx = 0; var globalMinIdx = localMinIdx; var globalMaxIdx = globalMinIdx; // check all prices, looking for new local maximal difference for (var i = 0; i < prices.length; i++) { // if a lower price is found than the global minimum so far if(prices[i] < prices[globalMinIdx]) { // update the global minimum globalMinIdx = i; } // if the new price is larger than the current local maximum price if(prices[i] > prices[localMaxIdx]) { // start a new local min/max sequence localMaxIdx = i; localMinIdx = i; } // if the new price is lower than the current local minimum price else if(prices[i] < prices[localMinIdx]) { // update the local minimum price localMinIdx = i; // and compare the local difference to the global difference so far var localDelta = prices[localMaxIdx] - prices[localMinIdx]; var globalDelta = prices[globalMaxIdx] - prices[globalMinIdx]; if(localDelta > globalDelta) { // the local difference is larger than the global difference // so make this the new global benchmark difference globalMinIdx = localMinIdx; globalMaxIdx = localMaxIdx; } } } // the maximum loss is the negative global delta var maxLoss = prices[globalMinIdx] - prices[globalMaxIdx]; print(maxLoss);

There is a naive O(n^2) solution to this problem which compares each element to all subsequent elements keeping track of the global minimum (maximal difference) found. This is trivial to implement using two nested for loops

var maxLoss = 0; for (var i = 0; i < prices.length; i++) { var min = prices[i]; for (var j = i + 1; j < prices.length; j++) { if(prices[j] < min) { min = prices[j]; } } if(maxLoss > (min - prices[i])) { maxLoss = (min - prices[i]); } } // the desired result is the value of maxLoss

However, this algorithm is sub-optimal and it's quadratic performance characteristics start to take a toll on larger sequences.

In contrast with the trivial O(n^2) implementation, the algorithm I gave in the complete solution computes the result in linear time by keeping track of two differences: a local difference which is updated whenever a new larger price is detected, and a global difference which is the largest (maximal) difference for all prices so far

The original problem statement can be found on the CodinGame website.