Next Greater Numbers

The objective is to write a function that takes an array of integers and calculates for each of them the distance to the next greater value, or -1 if there isn't any.

For example, given the array, [13, 25, 10, 5, 8, 2, 20], the return value would be [1, -1, 4, 1, 2, 1, -1]. Working our way from left to right, the next number greater than 13 is 1 hop away, there is no number greater than 25, the next number greater than 10 is 4 hops away, and so on. Note that this necessarily means the last value in the result is -1 since there is no next number that is greater.

It might be tempting at first glance to traverse the array from left to right, checking each following value against the current one, but that would lead to a solution with an O(n²) worst case runtime. To do better we make use of information we generate as we traverse through the array backwards. Instead of incrementing our counter by one each time as we search for the next greater value, we can check the corresponding value in the result array and see how many hops to a value that exceeds it. We can then hop to that value directly and check again. If we reach a -1 along the way we can stop, since this indicates there is no greater value ahead.

This solution saves us hops since we don't repeat unnecessary traversals. In fact, in the worst case—an ever decreasing set of values—we only perform one check for each value, leading to linear runtime.

The visualization here shows randomly chosen array values on a line chart. The solid red dot is the one for which we're calculating an output value. The red circle is the value being compared. Notice how the circle hops around and stops after very few hops—often after only one.

<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
  font-family: sans-serif;
  background: white;
  width: 860px;
  margin: 0 auto;
}

.axis path,
.axis line {
  fill: none;
  stroke: #333;
  shape-rendering: crispEdges;
}

.axis text {
  font-size: 10px;
  fill: #333;
}

.line {
  fill: none;
  stroke: steelblue;
  stroke-width: 1.5px;
}

.point circle {
  fill: steelblue;
  stroke: white;
  stroke-width: 3px;
}

.point text {
  font-size: 12px;
}

.point.active circle {
  fill: orangered;
}

.point.active text {
  fill: orangered;
  font-size: 16px;
  font-weight: bold;
}

.focus {
  fill: none;
  stroke: orangered;
  stroke-width: 2px;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>
var margins = {top: 50, right: 50, bottom: 50, left: 70},
    width = 860 - margins.left - margins.right,
    height = 400 - margins.top - margins.bottom;

var xScale = d3.scale.linear()
    .range([0, width]);

var yScale = d3.scale.linear()
    .range([height, 0]);

var yAxis = d3.svg.axis()
    .scale(yScale)
    .orient('left')
    .ticks(10);

var line = d3.svg.line()
    .x(function(d) { return xScale(d.id); })
    .y(function(d) { return yScale(d.value); });

var svg = d3.select('body').append('svg')
    .attr('width', width + margins.left + margins.right)
    .attr('height', height + margins.top + margins.bottom)
  .append('g')
    .attr('transform', 'translate(' + [margins.left, margins.top] + ')');

var gyAxis = svg.append('g')
    .attr('class', 'axis')
    .attr('transform', 'translate(-20,0)');

var path = svg.append('path')
    .attr('class', 'line');

var focus = svg.append('circle')
    .attr('class', 'focus');

var points;

function draw(data) {
  data = data.map(function(d, i) { return {value: d, hops: NaN, id: i}; });
  data[data.length-1].hops = -1;

xScale.domain([0, data.length-1]);
  yScale.domain(d3.extent(data, function(d) { return d.value; }));
  gyAxis.call(yAxis);

path.datum(data).transition()
      .duration(800)
      .attr('d', line);

points = svg.selectAll('.point')
      .data(data);

pointsEnter = points.enter().append('g')
      .attr('class', 'point')
      .attr('transform', function(d) {
        return 'translate(' + [xScale(d.id), yScale(d.value)] + ')';
      });

pointsEnter.append('circle')
      .attr('r', 6);

pointsEnter.append('text')
      .attr('dx', 3)
      .attr('dy', -8);

points.transition()
      .duration(800)
      .attr('transform', function(d) {
        return 'translate(' + [xScale(d.id), yScale(d.value)] + ')';
      });

points.select('text')
      .text(function(d) { return d.hops || ''; });

points.exit()
      .remove();
}

function setFocus(id, isTransition) {
  if (!id) { focus.transition().attr('r', 0); return; }
  var point = points.filter(compare(id)).datum();
  (isTransition ? focus.transition() : focus)
      .attr('cx', xScale(id))
      .attr('cy', yScale(point.value))
      .attr('r', 8);
}

function setActive(id) {
  var isActive = compare(id);
  points
    .classed('active', isActive)
  .select('circle')
    .transition()
    .attr('r', function(d) { return isActive(d) ? 8 : 6; });
}

function setLabel(id, label) {
  points.filter(compare(id)).select('text').text(label);
}

function compare(id) {
  return function (d) { return d.id === id; };
}

function nextPeaks(data, onComplete) {
  var result = [-1];
  var frame = 0;
  for (var i = data.length-2; i >= 0; i--) {
    var j = 0;
    delay(setActive, frame, i);
    delay(setFocus, frame, i+j+1);
    delay(setLabel, frame, i, 1);
    while (data[i+j+1] <= data[i] && result[j] !== -1) {
      j += result[j];
      frame++;
      delay(setFocus, frame, i+j+1, true);
      delay(setLabel, frame, i, j+1);
    }

result.unshift(data[i] > data[i+j+1] ? -1 : j+1);
    delay(setLabel, frame++, i, result[0]);
  }

delay(function() {
    setActive();
    setFocus();
    if (onComplete) { onComplete(); }
  }, frame);
}

function delay(fn, sec) {
  var args = Array.prototype.slice.call(arguments, 2);
  return setTimeout(fn.bind.apply(fn, [null].concat(args)), sec*1000);
}

(function go() {
  var data = d3.range(15).map(function() {
    return Math.floor(Math.random() * 40);
  });

draw(data);
  delay(nextPeaks, 1, data, delay.bind(null, go, 2));
})();
</script>
</body>

https://d3js.org/d3.v3.min.js