Skip to content

Instantly share code, notes, and snippets.

@GlenDC
Last active February 13, 2017 15:50
Show Gist options
  • Save GlenDC/f2d9c8653f6a59e297684d3c7d195ed5 to your computer and use it in GitHub Desktop.
Save GlenDC/f2d9c8653f6a59e297684d3c7d195ed5 to your computer and use it in GitHub Desktop.
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]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment