981. Time Based Key-Value Store

Link: https://leetcode.com/problems/time-based-key-value-store/

Description: Create a time-based key-value store.

Solution:

We can use a binary search to find the value of the largest timestamp that is smaller than the given timestamp. We can store the key-value pairs in an object where the key is the key and the value is an array of [timestamp, value]. We can use the binary search to find the value of the largest timestamp that is smaller than the given timestamp because the timestamps always increase. If the timestamp is earlier than all timestamps, we can return an empty string. Otherwise, we can return the value of the largest timestamp that is smaller than the given timestamp.

var TimeMap = function () {
  this.store = {} // key: string, value: array of [timestamp, value]
}

/**
 * @param {string} key
 * @param {string} value
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function (key, value, timestamp) {
  if (this.store[key] === undefined) {
    this.store[key] = []
  }
  this.store[key].push([timestamp, value])
}

/**
 * @param {string} key
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function (key, timestamp) {
  if (!this.store[key]) return ''

  let pairs = this.store[key]

  let left = 0
  let right = pairs.length - 1

  while (left <= right) {
    const m = left + Math.floor((right - left) / 2)

    if (pairs[m][0] === timestamp) {
      return pairs[m][1]
    } else if (pairs[m][0] > timestamp) {
      right = m - 1
    } else {
      left = m + 1
    }
  }
  // If the timestamp is earlier than all timestamps, return ""
  // Otherwise, return the value of the largest timestamp that is smaller than the given timestamp
  return right >= 0 ? pairs[right][1] : ''
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */