issue #178 of rendezvous with cassidoo

Given a n x m binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area.

by Jesse Rogers

JavaScript

/**
 * @fileoverview Given a n x m binary matrix filled with 0s and 1s,
 * 		find the largest rectangle containing only 1s and return its area.
 */

const DATA = [
  [1, 1, 1, 0, 0, 0, 1],
  [1, 1, 0, 1, 1, 1, 1],
  [0, 1, 0, 1, 1, 0, 1],
  [1, 0, 0, 1, 1, 1, 1]
]

class Inspectangle {

  constructor(_matrix) {
    this.matrix = _matrix
  }

  setMatrix(_matrix) {
    this.matrix = _matrix
  }

  hasRange(_row, _range) {
    for (let i = _range[0]; i <= _range[1]; i++) {
      if (!_row[i]) {
        return false
      }
    }
    return true
  }

  getLargest() {
    try {
      let _result = ''
      // generate a map of common ranges found in each row
      const _rangeMap = this.matrix.reduce((_hashmap, _row, i) => {
        // algo will check row above each time, so
        // just skip first row
        if (i) {
          for (let x = 0; x < _row.length; x++) {
            // allocate a new array for range
            const _range = new Array(2)
            // start evaluation around ON bits
            if (_row[x]) {
              // init range values
              let _end = _range[0] = x
              // find range end
              while (_row[_end] && this.hasRange(this.matrix[i - 1], [x, _end])) {
                _range[1] = _end
                _end++
              }
              // validate range
              if (
                // must have two values
                (!isNaN(_range[0]) && !isNaN(_range[1])) &&
                // range must be > 1
                _range[0] !== _range[1]
              ) {
                // tally in hashmap
                const _key = JSON.stringify(_range)
                _hashmap[_key] = (_hashmap[_key] || 1) + 1
              }
            }
          }
        }
        return _hashmap
      }, {})
      // null check
      if (!_rangeMap) {
      	console.error('Unable to evaluate range map')
				return 0
      }
      // calculate largest area
      _result = Object.keys(_rangeMap).reduce((_output, _key) =>...