Get the biggest chronological drop, min and max from an array with O(n)

Question

I have written a javascript function for analyzing the biggest drop in an array. But one little issue is still there. As the max value, I always get max value from my hole array and not from my drop.

Example: Array: [100,90,80,120]

The biggest drop would be between 100 and 80. So max must be 100, and min 80. My function always returns the highest value from the whole array. in my case 120

function checkData(data) {
  let max = 0
  let min = 0
  let drop = 0

  for (let i = 0; i < data.length; i++) {
      if (max < data[i]) {
          max = data[i] //?
      } else {
          let tempDrop = max - data[i]
          drop = Math.max(tempDrop, drop)
          min = max - drop
      }
  }
  return [max, min, drop]
}

I want to get the chronological correct biggest delta from left to right

Answer 1

Your loop should keep track of the current drop and compare it to the previous largest drop. You can do this by tracking indexes:

function checkData(data) {
  let bestDropStart = 0
  let bestDropEnd = 0
  let bestDrop = 0
  let currentDropStart = 0
  let currentDropEnd = 0
  let currentDrop = 0
  for (let i = 1; i < data.length; i++) {
    if (data[i] < data[i - 1]) {
      // we are dropping
      currentDropEnd = i
      currentDrop = data[currentDropStart] - data[i]
    } else {
      // the current drop ended; check if it's better
      if (currentDrop > bestDrop) {
        bestDrop = currentDrop
        bestDropStart = currentDropStart
        bestDropEnd = currentDropEnd
      }
      // start a new drop
      currentDropStart = currentDropEnd = i
      currentDrop = 0
    }
  }
  // check for a best drop at end of data
  if (currentDrop > bestDrop) {
    bestDrop = currentDrop
    bestDropStart = currentDropStart
    bestDropEnd = currentDropEnd
  }
  // return the best drop data
  return [data[bestDropStart], data[bestDropEnd], bestDrop]
}

console.log(checkData([100, 90, 80, 120]))
console.log(checkData([100, 90, 80, 120, 30]))
console.log(checkData([70, 100, 90, 80]))
console.log(checkData([100, 90, 80, 120, 30, 50]))

You can also do it by just keeping the start and end values for the current and best drops, but my preference would be to explicitly track the indexes. It just seems clearer (easier to debug and maintain) to me that way.

Answer 2

You need to iterate the array once (O(n)) and keep a running count of min and max values and:

1. Reset it every time the value increases w.r.t. previous value
2. But note them down if the difference is greater than previously noted values

function checkData(array) {
  var currentmax = array[0];
  var currentmin = array[0];
  var overallmax = array[0];
  var overallmin = array[0];
  var i;
  for (i = 1; i < array.length; i++) {
    if (array[i] <= array[i - 1]) {
      // value is same or decreased
      currentmin = array[i];
    } else {
      // check if previous iteration was the largest
      if (currentmax - currentmin > overallmax - overallmin) {
        overallmax = currentmax;
        overallmin = currentmin;
      }
      // restart
      currentmax = array[i];
      currentmin = array[i];
    }
  }
  // check if last iteration was the largest
  if (currentmax - currentmin > overallmax - overallmin) {
    overallmax = currentmax;
    overallmin = currentmin;
  }

  return [overallmax, overallmin, overallmax - overallmin];
}
console.log(checkData([100, 90, 80, 120]));
console.log(checkData([100, 90, 80, 120, 200, 100, 90]));
console.log(checkData([10, 100, 50, 50, 10, 100, 50, 50, 1]));

Answer 3

It sounds like you'd like the returned max and min to be the same ones used in calculating the largest drop rather than the overall max and min. In that case just add an additional variable to store those when drop is updated. Replace

drop = Math.max(tempDrop, drop)

with an if statement (pseudocode):

if current_drop is greater than stored_drop:
  stored_drop = current_drop
  stored_max_min = current max and min

then return the additional stored max and min.

Answer 4

You need to keep track of two things:

• The maximum value you have up to an element i.
• The minimum value you have from an element i to the end of the list.

Then you just need to find the drop for each index and select which one is biggest.

Here is the code:

function maxDrop (data) {
  if (!data || data.length === 0) {
    return;
  }
  const max = [];
  const min = [];
  for (let i = 0; i < data.length; i++) {
    const left = data.slice(0, i);
    const right = data.slice(i, data.length);
    max.push(Math.max.apply(null, left));
    min.push(Math.min.apply(null, right));
  }
  let maxDrop = max[0] - min[0];
  let maxValue = max[0];
  let minValue = min[0];
  for (let j = 0; j < data.length; j++) {
    const drop = max[j] - min[j];
    if (maxDrop < drop) {
      maxDrop = drop;
      maxValue = max[j];
      minValue = min[j];
    }
  }
  return [maxValue, minValue, maxDrop];
}

console.log(maxDrop([100,90,80,120]))
console.log(maxDrop([100,110,120,300,200,70,60,50,90,400]))
console.log(maxDrop([100,90,80,120,30]))

Answer 5

To add one more to the mix.. A possible approach is to create all the drop - ranges first, than get the one with the largest drop

A version with reduce:

function checkData(data) {
let dropInd = 1,
   mx = data.reduce((arr,val, ind) => {
 if(ind && val > data[ind-1])dropInd++;         
 arr[dropInd] = arr[dropInd] || {max:val};
 arr[dropInd].min = val;
 arr[dropInd].drop = arr[dropInd].max - val;
 return arr;
}, []) //after reduce, islands are created based on 'dropInd'  
  .sort((v1,v2)=>v2.drop - v1.drop) //sort by drop descending
  [0]; //the first value now contains the maximum drop  

  return [mx.max,mx.min,mx.drop];
}



console.log(checkData([100, 90, 80, 120]));
console.log(checkData([100, 90, 80, 120, 200, 100 ,90]));
console.log(checkData([200,100, 90, 80, 120,  100 ,90]));
console.log(checkData([200,120,190, 90, 80, 120,  100 ,90]));

Answer 6

This works exactly as intended (as per your expected output), as shown in the following code snippet.

The issue must be in how you are sending your data as an array.

alert(checkData([100, 90, 80, 120]));

function checkData(data) {
  let max = 0
  let min = 0
  let drop = 0

  for (let i = 0; i < data.length; i++) {
    if (max < data[i]) {
      max = data[i] //?
    } else {
      let tempDrop = max - data[i]
      drop = Math.max(tempDrop)
      min = max - drop
    }
  }
  return [max, min, drop]
}

// Output : 120, 80, 20

However, if what you are looking for is a Max, a Min, and then the biggest difference, i.e. between the the max and min, which in your given example would be 40, then you can simply do this.

alert(checkData([100, 90, 80, 120]));

function checkData(data) {

  let max = data.reduce(function(a, b) {
    return Math.max(a, b);
  });
  let min = data.reduce(function(a, b) {
    return Math.min(a, b);
  });

  let drop = max-min;

  return [max, min, drop];
  
}

// Output : 120, 80, 40

I only mention this as I don't know why you've said you expect the biggest difference to be 20, given 100 and 80, when you have 120 and 80 in the same array, meaning the biggest difference is 40.