How to efficiently track rolling min / max values in a frequently updated sliding array

Question

Consider the following javascript data structure:

let sensors = { 
  sensor1: {
    min: 1.00,
    max: 9.00,
    data: [
      {
        timestamp: 1517760374400,
        value: 1.00
      },
      {
        timestamp: 1517760374500,
        value: 2.00
      },
      {
        timestamp: 1517760374600,
        value: 9.00
      },
      {
        timestamp: 1517760374700,
        value: 1.00
      },
      {
        timestamp: 1517760374800,
        value: 3.00
      },
      {
        timestamp: 1517760374900,
        value: 1.00
      },
      {
        timestamp: 1517760375000,
        value: 9.00
      },
      {
        timestamp: 1517760375100,
        value: 8.00
      },
    ]
  },
  // sensor2, sensor3, etc...
}

Imagine there could be thousands of timestamped data for each sensor.

Initially you can easily set a min / max value, every time an object is added by checking if it is bigger or smaller than the current max

But the tricky part and my question is this:

What is the size of the array is limited - in this case we would set it to a length of 8.

Whenever a new item after item 8 is added (the limit is reached), the 1st item will be removed, and the nth item will be pushed into the end of the array.

The problem is that there can be more items with the same value, and even if there isn't we have no way of knowing which min / max is next without iterating the entire array once again

This is supposed to be scalable to thousands of array items, and is to be run roughly every second with ideally - as low cpu utilization as possible - I don't really think looping over thousands of items every second will be effecient enough.

Do you see another other ways of keeping track of min / max values of an array which is changing like this ever second?

Answer 1

Data structure:

• Queue size of N to store N item.

• Min / Max Heap to track the min / max item.

• A hash map to track the frequency of each item.

When you there is a coming data, update the frequency of the new item, if not there in the heap, add it.

When you need to pop an item, decrease the frequency, while frequency of head == 0, remove from the heap.

Head of the heap is the solution.

Pseudo code:

const swap = (data, i, j) => {
  let temp = data[i];
  data[i] = data[j];
  data[j] = temp;
}

class Heap {
  constructor() {
    this.data = [];
    this.inHeap = {};
    this.size = 0;
  }
  
  head() {
    return this.data[0];
  }
  // add item O(logN);
  add(number) {
  
    if (!this.inHeap[number]) {
      this.data[this.size++] = number;
      let current = this.size - 1;

      while (current > 0) {
        if (this.data[current >> 1] < this.data[current]) {
          swap(this.data, current >> 1, current);
          current >>= 1;
        } else {
          break;
        }
      }
      this.inHeap[number] = true;
    }
    
  }
  // remove head O(logN);
  remove() {
    this.size--;
    delete this.inHeap[this.data[0]];
    this.data[0] = this.data[this.size];

    let current = 0;
    while (current * 2 + 1 < this.size) {
      let next = current * 2 + 1;
      if (current * 2 + 2 < this.size && this.data[current * 2 + 2] > this.data[current * 2 + 1]) {
        next = current * 2 + 2;
      } 
      
      if (this.data[current] < this.data[next]) {
        swap(this.data, current, next);
        current = next;
      } else {
        break;
      }
    }
    
  }
}

class Queue {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.size = 0;
    this.data = [];
    this.head = -1;
  }
  
  // add a number and return the removed item if any
  add(number) {
    let next = (this.head + 1) % this.maxSize;
    let removedItem = this.data[next];
    this.data[next] = number;
    this.head = next;
    
    if (removedItem === undefined) {
      this.size++;
    }
    
    return removedItem;
  }
  
  get(i) {
    return this.data[(this.head - this.size + 1 + i + this.maxSize ) % this.maxSize];
  }
}

class Solution {
  constructor(n) {
    this.n = n;
    this.queue = new Queue(this.n);
    this.heap = new Heap();
    this.frequency = {};
  }
  add(number) {
    let removedItem = this.queue.add(number);
    
    if (!this.frequency[number]) {
      this.frequency[number] = 1;
      this.heap.add(number);
    } else {
      this.frequency[number]++;
    }
    
    if (removedItem !== undefined) {
      this.frequency[removedItem]--;
      
      if (!this.frequency[removedItem]) {
        delete this.frequency[removedItem];
      }
      
      // remove head if frequency is zero
      while (!this.frequency[this.heap.head()]) {
        this.heap.remove();
      }
    }
  }
  
  size() {
    return this.queue.size;
  }
  
  get(i) {
    return this.queue.get(i);
  }
  
  max() {
    return this.heap.head();
  }
}

/*** use of solution here!! **/
let solution = new Solution(3);
let numberInput = document.getElementById("number");
let data = document.getElementById("data");
let maxResult = document.getElementById("max");
let heapData = document.getElementById("heap");
let queueData = document.getElementById("queue");
let frequencyData = document.getElementById("frequency");

function addNumber() {
  let value = parseInt(numberInput.value);
  
  if (isNaN(value)) {
    alert("Please input a number!");
  } else {
    solution.add(value);
  }
  
  maxResult.innerHTML = "Max: " + solution.max();
  
  // gather data
  let dataString = "";
  for (let i = 0; i < solution.size(); i++) {
    dataString += " " + solution.get(i);
  }
  
  data.innerHTML = "Data: " + dataString;
  heapData.innerHTML = "Heap: " + JSON.stringify(solution.heap.data.slice(0, solution.heap.size));
  queueData.innerHTML = "Queue: " + JSON.stringify(solution.queue);
  frequencyData.innerHTML = "Frequency: " + JSON.stringify(solution.frequency);
  
  numberInput.value = parseInt(Math.random() * 1000);
}

.input {
  display: flex;
}

.input input {
  width: 200px;
  padding: 5px 10px;
  outline: none;
}

.input button {
  padding: 5px 10px;
  border: 1px solid light gray;
}

div {
  padding: 5px 10px;
}

<div class="input">
  <input type="text" id="number" />
  <button onClick="addNumber()">Add</button>
</div>
<div class="result">
  <div class="data" id="data">
    Data: 
  </div>
  <div class="max" id="max">
    Max: undefined!
  </div>
</div>
<div class="debug">
  <div>
    <code class="data" id="heap">
      Heap:
    </code>
  </div>
  <div>
    <code class="max" id="queue">
    Queue:
    </code>
  </div>
  <div>
    <code class="max" id="frequency">
      Frequency:
    </code>
  </div>
</div>

Answer 2

Sounds fun. I think that you're going to run into a problem where you just don't know a priori whether a value is going to be an extreme (max/min) value in the future.

My thought would be to add an expiration counter to your current max & min values. This counter decrements each time you don't replace your rolling min/max. It is reset to 8 when it is updated with a new, fresh value. Min and max obviously have separate counters.

Now you only have to loop through your values if a counter decrements to 0 and your min/max value becomes stale (it is no longer in your list). If, for example, your min counter expires, you now have to identify the remaining minimum that is currently in your list of 8. In this case, you'll reset the expiration counter to match the number of iterations until that new min value gets removed from the list (8 - it's index).

That might save you some CPU cycles!