2D server grid update

solution.ts

/**
 * Calculate days required to update all servers
 * 
 * O(rows * columns)
 * 
 * @param rows    rows in grid array
 * @param columns columns in grid array
 * @param grid    servers 2D array
 * 
 * @returns days required to update all servers or -1 if it's not possible
 */
export const calcDaysToUpdate = (rows: number, columns: number, grid: Array<number[]>) => {
  if (rows < 1 || columns < 1) {
    return -1
  }

  let updatedServers = []
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < columns; j++) {
      if (grid[i][j] === 1) {
        updatedServers.push([i, j])
      }
    }
  }

  let totalUpdated = 0 // debug purposes
  let day = 0
  let notUpdated = rows * columns - updatedServers.length

  while (notUpdated > 0 && updatedServers.length > 0) {
    day += 1

    let newUpdateServers: Array<number[]> = []
    updatedServers.forEach(([x, y]) => {
      newUpdateServers.push(...updateNeighbors(rows, columns, grid, x, y))
    })

    totalUpdated += newUpdateServers.length // debug only
    notUpdated -= newUpdateServers.length
    updatedServers = newUpdateServers
  }

  console.log('Updated servers:', totalUpdated, 'Not updated servers:', notUpdated)

  /**
   * -1 if there are not updated servers
   * 0 if there are no not updated servers and no servers were updated
   * otherwise return days spent to update servers
   */
  return notUpdated > 0 ? -1 : day
}

/**
 * Update all not updated adjacent servers that are either
 * on the left, right, above or below a given server.
 * 
 * @param rows      rows in grid array
 * @param columns   columns in grid array
 * @param grid      servers' 2D array
 * @param x         row index
 * @param y         column index
 * 
 * @returns updated cells array
 */
export const updateNeighbors = (rows: number, columns: number, grid: Array<number[]>, x: number, y: number) => {
  let updated = []
  let points = [[x, y - 1], [x, y + 1], [x - 1, y], [x + 1, y]]

  for (let [i, j] of points) {
    if (isInRange(i, rows) && isInRange(j, columns) && grid[i][j] === 0) {
      updated.push([i, j])
      grid[i][j] = 1
    }
  }

  return updated
}

/**
 * is index in range, ex [0..max]
 * 
 * @param index row or column index in grid array
 * @param max   rows or columns of grid array accordingly
 * @param min   grid start index, always 0 in this case
 * 
 * @returns true if index is within range, otherwise false
 */
export const isInRange = (index: number, max: number, min = 0) => {
  return index >= min && index < max
}

task.md

Amazon has a 2D grid of cell towers. All servers need to be updated to the latest software version. Servers that already have the update should not be updated again. Servers are in the form of a 2D array of 0 and 1 where the value 0 represents an out of date server and the value of 1 represents an updated server. In a single day, an updated server can push the update to each of its adjacent out of date servers. An adjacent server is either on the left, right, above or below a given server. Once the server receives the update, it becomes updated and can push the update to its adjacent servers on the following day. Given the 2D array representing the current status of its servers.

Write an algorithm that will determine the minimum number of days required to push the update to all the available servers.

Input The input to the function/method consists of three arguments:

• rows, an integer representing the number of rows in the grid;
• columns, an integer representing the number of columns in the grid;
• grid, an integer array representing the current status of its servers. The value 0 represents an out of date server and the value 1 represents an updated server.

Output Return an integer representing the minimum number of days required to update all the servers in the grid network. Return -1 if all the available servers cannot be updated.

Note Diagonally placed cells are not considered neighbors.

Example Input: rows = 4 columns = 5

[[0, 1, 1, 0, 1],
 [0, 1, 0, 1, 0],
 [0, 0, 0, 0, 1],
 [0, 1, 0, 0, 0]]

Output: 2

Explanation: At the end of day one, the status of the servers :

1, 1, 1, 1, 1
1, 1, 1, 1, 1
0, 1, 0, 1, 1
1, 1, 1, 0, 1

at the end of day two, the status of the servers :

1, 1, 1, 1, 1
1, 1, 1, 1, 1
1, 1, 1, 1, 1
1, 1, 1, 1, 1

By the end of day two, all the servers are up to date.

Assumptions added by Mykola:

• if all servers are already updated - return 0
• if there are no servers (rows or columns) - return -1
• edge cell doesn't update a server on the opposite side ex: [[1, 0, 0, 0]] will be [1, 1, 0, 0] on the first day but not [[1, 1, 0, 1]]

test.ts

import { calcDaysToUpdate, isInRange, updateNeighbors } from '../src/task2Cache'

const getGrid = (x = 0) => ([
  [x, x, x],
  [x, x, x],
  [x, x, x],
])

describe('Update servers in grid', () => {
  describe('calcDaysToUpdate', () => {
    it('use case from task', () => {
      expect(calcDaysToUpdate(4, 5, [
        [0, 1, 1, 0, 1],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 0, 1],
        [0, 1, 0, 0, 0]
      ])).toBe(2)
    })

    it('from the end', () => {
      expect(calcDaysToUpdate(4, 5, [
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1]
      ])).toBe(7)
    })

    it('from the beginning', () => {
      expect(calcDaysToUpdate(5, 5, [
        [1, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0]
      ])).toBe(8)
    })

    it('no cells', () => {
      expect(calcDaysToUpdate(1, 0, [])).toBe(-1)
    })

    it('no rows', () => {
      expect(calcDaysToUpdate(0, 0, [])).toBe(-1)
    })

    it('no update servers', () => {
      expect(calcDaysToUpdate(3, 3, getGrid(0))).toBe(-1)
    })

    it('all servers are up to date', () => {
      expect(calcDaysToUpdate(3, 3, getGrid(1))).toBe(0)
    })

    it('single row', () => {
      expect(calcDaysToUpdate(1, 3, [[1, 0, 0]])).toBe(2)
    })

    it('single column', () => {
      expect(calcDaysToUpdate(3, 1, [[0], [0], [1]])).toBe(2)
    })

    it('1x1 updated', () => {
      expect(calcDaysToUpdate(1, 1, [[1]])).toBe(0)
    })

    it('1x1 not updated', () => {
      expect(calcDaysToUpdate(1, 1, [[0]])).toBe(-1)
    })
  })

  describe('isInRange', () => {
    it('out of max range', () => {
      expect(isInRange(3, 3)).toBe(false)
    })

    it('out of min range', () => {
      expect(isInRange(-1, 1)).toBe(false)
    })

    it('in range (min)', () => {
      expect(isInRange(0, 1)).toBe(true)
    })

    it('in range (any)', () => {
      expect(isInRange(5, 9)).toBe(true)
    })
  })

  describe('updateNeighbors', () => {
    it('update 4', () => {
      const grid = getGrid(0)
      expect(updateNeighbors(3, 3, grid, 1, 1)).toEqual([[1, 0], [1, 2], [0, 1], [2, 1]])

      const resultGrid = getGrid(0)
      resultGrid[0][1] = 1
      resultGrid[1][0] = 1
      resultGrid[1][2] = 1
      resultGrid[2][1] = 1

      expect(grid).toEqual(resultGrid)
    })

    it('update nothing', () => {
      const grid = getGrid(1)
      expect(updateNeighbors(3, 3, grid, 1, 1)).toEqual([])

      const resultGrid = getGrid(1)

      expect(grid).toEqual(resultGrid)
    })

    it('update top left', () => {
      const grid = getGrid(0)
      expect(updateNeighbors(3, 3, grid, 0, 0)).toEqual([[0, 1], [1, 0]])

      const resultGrid = getGrid(0)
      resultGrid[0][1] = 1
      resultGrid[1][0] = 1

      expect(grid).toEqual(resultGrid)
    })

    it('update top right', () => {
      const grid = getGrid(0)
      expect(updateNeighbors(3, 3, grid, 0, 2)).toEqual([[0, 1], [1, 2]])

      const resultGrid = getGrid(0)
      resultGrid[0][1] = 1
      resultGrid[1][2] = 1

      expect(grid).toEqual(resultGrid)
    })

    it('update bottom right', () => {
      const grid = getGrid(0)
      expect(updateNeighbors(3, 3, grid, 2, 2)).toEqual([[2, 1], [1, 2]])

      const resultGrid = getGrid(0)
      resultGrid[1][2] = 1
      resultGrid[2][1] = 1

      expect(grid).toEqual(resultGrid)
    })

    it('update bottom left', () => {
      const grid = getGrid(0)
      expect(updateNeighbors(3, 3, grid, 2, 0)).toEqual([[2, 1], [1, 0]])

      const resultGrid = getGrid(0)
      resultGrid[1][0] = 1
      resultGrid[2][1] = 1

      expect(grid).toEqual(resultGrid)
    })
  })
})