CodinGame - Solution in Javascript to Stock Exchange Losses Problem

Print

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.

is the founder of Donaq, a software development consulting company with a focus on mobility. You can find Mike on Google+ and on LinkedIn.
Design copyright (c) Miky Dinescu