Coding Solution

Stock Exchange Losses – CodinGame solution in C

Mediumrunning maximumsingle passarraysgreedyUpdated
Short answer

Scan the values once, keeping the highest value seen so far. For every new value, the worst loss ending there is value - highestSoFar; keep the minimum of those differences, starting from 0, and print it, which gives a negative number or 0 when prices never go down. The whole solution is O(n) time and O(1) memory.

The problem

You are given the chronological list of n stock values (n up to 100,000, each value a positive integer below 2^31). Find the largest loss an investor could suffer by buying at one moment and selling at a later moment.

The answer is the most negative difference v[j] - v[i] with i < j, printed as a negative integer. If the values never decrease, there is no loss and you must print 0.

Approach, step by step

  1. Reformulate the problemWe want the minimum of v[j] - v[i] over i < j. For a fixed selling day j, the worst buying day is the highest value before it, so we only need the running maximum.
  2. Single passWalk through the values, update maxSoFar = max(maxSoFar, v), and compute v - maxSoFar. Keep the smallest difference seen, initialised to 0.
  3. Print the result as isThe best difference is already negative (or 0), so print it directly. Starting from 0 handles the "no loss" case without a special branch.
  4. Read the values efficientlyAll values are on one line. Splitting the line (or using scanf in a loop in C) is enough; you never need to store the array.

Complexity

TimeO(n)
SpaceO(1)

Each value is read and compared once and only two numbers are kept. The brute-force check of every pair is O(n^2), about 5 * 10^9 comparisons for n = 100,000, which times out.

Solution code

Stock Exchange Losses – C

The C version reads the whole line and splits it with strtok and atoi. Instead of a running max it tracks a "current peak and lowest value since that peak" pair and closes the segment whenever a new peak appears, which is equivalent and correct.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

int main(int argc, char **argv)
{
    // number of stock values
    int N;
    scanf("%d\n", &N);
    
    /* as each stock value is under 2^31 which is roughly 4*10^9,
       15 chars per value is largely enough*/
    char line[15*N];
    fgets(line,15*N,stdin);
    
    /* currentMax and currentMin will store the local minimum and maximum
       stock values, maxLoss will store the maximum loss found yet */
    int stockValue, maxLoss, currentMax, currentMin;
    maxLoss = currentMax = 0;
    currentMin = INT_MAX;
    
    // Uses strtok to read all the stock values
    char *tok;
    tok = strtok(line," ");
    for (int i = 0 ; i < N ; i++) {
        stockValue = atoi(tok);
        
        /* a new peak: the drop measured from the old peak is final, store it and restart from here */
        if (stockValue > currentMax) {
            if (currentMax-currentMin > maxLoss)
                maxLoss = currentMax-currentMin;
            currentMax = currentMin = stockValue;
        } 
        /* still below the current peak: remember the lowest point since that peak */
        else if (stockValue < currentMin)
            currentMin = stockValue;
            
        tok = strtok(NULL," ");
    }
    
    /* the last segment never closed inside the loop, so check it once more */
    if (currentMax-currentMin > maxLoss)
        maxLoss = currentMax-currentMin;
        
    /* maxLoss is a positive drop (0 if none); the expected output is negative */
    printf("%d\n",-maxLoss);
    return EXIT_SUCCESS;
}
            

Common mistakes

Going further

This puzzle is the mirror image of the classic "best time to buy and sell a stock" interview question: there you look for max(v[j] - v[i]) with a running minimum, here you want min(v[j] - v[i]) with a running maximum. Seeing it as a running extreme rather than a search over pairs is the whole trick, and it generalises: the same pattern gives the largest drawdown of a portfolio curve, and with prefix sums it gives the maximum subarray sum (Kadane's algorithm). Overflow is not a concern in this puzzle even with 32-bit ints, because both values are positive and below 2^31, so their difference stays within the int range; it becomes one if you adapt the code to values that can be negative.

FAQ

What do I print if the stock only goes up?

Print 0. Initialising the best difference to 0 gives that result automatically.

Why is the answer not simply the maximum minus the minimum?

Because the sale must happen after the purchase. The minimum can occur before the maximum, in which case that pair is a gain, not a loss.

Do I need 64-bit integers?

No. All values are positive and below 2^31, so any difference fits in a signed 32-bit int.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome