max_difference.js

var _ = require("lodash");
var assert = require('assert');

// maxDifferenceOriginal computes the max difference z = x - y,
// where x.index > z.index, and `!EwA(w != z ^ w > z)`
// input: {a: 'input array containing all numbers'}
function maxDifferenceOriginal(a) {
    // can only work with arrays
    if(!_.isArray(a)) {
        return -1;
    }

    // make sure all elements of the given array are numbers
    a = _.filter(a, _.isNumber);
    // a difference requires at least 2 numbers
    if(a.length < 2) {
        return -1;
    }
    
    // in order to optimize the more probable cases,
    // we sort the array from low to high,
    // however in order to do this, we'll have to store the index,
    // alongside the value.

    // store index, as we want to take that into account
    index = 0;
    a = _.map(a, function(elem) {
        elem = {v: elem, i: index};
        index++;
        return elem;
    });
    // sort it from lowest value to highest value;
    a = _.sortBy(a, function(elem) { return elem.v; });
    
    // no we can go through the array,
    // with the worst time complexity = `n*log(n)`
    var min, max;
    for(var upper = a.length - 1; upper >= 0; upper--) {
        max = a[upper];
        for(var lower = 0; lower < upper; lower++) {
            min = a[lower];
            if(max.i > min.i && max.v >= min.v) {
                return max.v - min.v;
            }
        }
    }
    
    return -1;
}

// maxDifference computes the max difference z = x - y,
// where x.index > z.index, and `!EwA(w != z ^ w > z)`
// input: {a: 'input array containing all numbers'}
//
// NOTE: the isArray check (a) and filter (b)
//       could be prevented if using for example TypeScript
function maxDifference(a) {
    // can only work with arrays (a)
    if(!_.isArray(a)) {
        return -1;
    }

    // make sure all elements of the given array are numbers (b)
    a = _.filter(a, _.isNumber);
    // a difference requires at least 2 numbers
    if(a.length < 2) {
        return -1;
    }

    result = {
        prevMax: null,
        prevMin: null,
        min: Number.MAX_VALUE,
        max: null,
    }

    result = _.reduce(a, function(acc, elem) {
        // a new min value always override the last found maxValue,
        // however we do want to store the prevMin and/or prevMax values
        // in case our new min value has no matching max value
        if(elem < acc.min) {
            if(acc.min !== Number.MAX_VALUE &&
                (_.isNull(acc.prevMin) || acc.prevMin < acc.min)) {
                acc.prevMin = acc.min;
            }
            if(!_.isNull(acc.max) && 
                (_.isNull(acc.prevMax) || acc.max-acc.prevMin > acc.prevMax-acc.prevMin)) {
                acc.prevMax = acc.max;
                acc.prevMin = acc.min;
            }

            acc.min = elem;
            acc.max = null;
        // no new min value found, so we'll try to use it as a new max value
        } else if(elem >= acc.min) {
            // if no max value has been found yet, we'll store it as the first max value,
            // if one has been found we want to make sure its bigger than the previous one
            if(_.isNull(acc.max) || elem > acc.max) {
                if(acc.max > acc.prevMax) {
                    acc.prevMax = acc.max;
                }
                acc.max = elem;
            // else we might override the previous max value
            } else if(elem > acc.prevMax) {
                acc.prevMax = elem;
            }
        }

        return acc;
    }, result);

    if(!_.isNull(result.max)) {
        if(!_.isNull(result.prevMax) && !_.isNull(result.prevMin)) {
            // both pairs exist, so we'll return the biggest diff of the 2
            return _.max([
                result.prevMax - result.prevMin,
                result.max - result.min,
            ]);
        }

        // only the current max and min pair is possible
        // and thus is the biggest
        return result.max - result.min;
    }

    // only the previous pair exists, so we'll return that,
    // this could happen in case we found a new min value,
    // that didn't match with another max value further down the road.
    if(!_.isNull(result.prevMax) && !_.isNull(result.prevMin)) {
        return result.prevMax - result.prevMin;
    }

    return -1;
}

////////////////
// UNIT TESTS //
////////////////

// example unit tests
assert.equal(8, maxDifference([2, 3, 10, 2, 4, 8, 1]));
assert.equal(2, maxDifference([7, 9, 5, 6, 3, 2]));
assert.equal(-1, maxDifference([10, 8, 7, 6, 5]));

// can only work with array
assert.equal(-1, maxDifference(null));
assert.equal(-1, maxDifference("foo"));
assert.equal(-1, maxDifference(_.isFunction));

// non-numbers are filtered out
assert.equal(-1, maxDifference([1,"foo"]));
assert.equal(2, maxDifference([1,"foo", 3]));
// contains enough numeric elements,
// but no max difference possible
assert.equal(-1, maxDifference([3,"foo", 1, "bar"]));

// require at least 2 elements
assert.equal(-1, maxDifference([]));
assert.equal(-1, maxDifference([1]));

// perfect max difference
assert.equal(1, maxDifference([1,2]));
assert.equal(5, maxDifference([1,2,3,4,5,6]));
assert.equal(0, maxDifference([1,1,1,1,1,1]));
assert.equal(9, maxDifference([-10, -8, -6, -4, -2, -1]));

// no max difference possible
assert.equal(-1, maxDifference([2, 1]));
assert.equal(-1, maxDifference([6, 5, 4, 3, 2, 1]));
assert.equal(-1, maxDifference([10, 8, 6, 4, 2, 0]));
assert.equal(-1, maxDifference([-1, -5, -10]));

// other valid arrays
assert.equal(2, maxDifference([10, 3, 5, 2]));
assert.equal(6, maxDifference([10, 3, 5, 2, 8, 1, 2]));
assert.equal(8, maxDifference([10, 3, 5, 2, 8, 2, 10]));
assert.equal(8, maxDifference([2, 8, 10, 3, 4, 5]));
assert.equal(7, maxDifference([1,8,3,4,5,6]));
assert.equal(5, maxDifference([2,1,3,4,5,6]));