Efficient JS solution (Beat 100% both time and memory)
\n\n# Intuition\nFirst BFS, then BFS, and BFS right after that. Finally, BFS.\n*Edit: I forgot that we also need BFS.\n\n# Complexity\n- Time complexity: O((mn)
![image.png](https://assets.leetcode.com/users/images/493ed78a-e2d2-42ae-af85-71868c93ddda_1695554753.422481.png)\n\n# Intuition\nFirst BFS, then BFS, and BFS right after that. Finally, BFS.\n*Edit: I forgot that we also need BFS.\n\n# Complexity\n- Time complexity: $$O((mn)^2)$$\n- Space complexity: $$O(mn)$$\n\n# Code\n```js\n/**\n * @template TItem\n */\nclass CircularQueue {\n  /**\n   * @param {number} capacity\n   */\n  constructor(capacity) {\n    /**\n     * @private\n     * @type {number}\n     */\n    this._capacity = capacity;\n    /**\n     * @private\n     * @type {number}\n     */\n    this._size = 0;\n    /**\n     * @private\n     * @type {number}\n     */\n    this._bottom = 0;\n\n    /**\n     * @private\n     * @type {TItem[]}\n     */\n    this._data = Array(capacity).fill(undefined);\n  }\n\n  /**\n   * @private\n   * @param {number} index\n   * @returns {number}\n   */\n  _getCircularIndex(index) {\n    const result = index % this._capacity;\n    if (result < 0) result += this._capacity;\n    return result;\n  }\n\n  get capacity() {\n    return this._capacity;\n  }\n\n  get size() {\n    return this._size;\n  }\n\n  get nextItem() {\n    return this._size ? this._data[this._bottom] : undefined;\n  }\n\n  get lastItem() {\n    return this._size\n      ? this._data[this._getCircularIndex(this._bottom + this._size - 1)]\n      : undefined;\n  }\n\n  /**\n   * @param  {...TItem} items\n   */\n  enqueue(...items) {\n    if (this._size + items.length > this._capacity)\n      throw new Error("Queue capacity exceeded.");\n\n    let queueIndex = (this._bottom + this._size) % this._capacity;\n    this._size += items.length;\n    for (let i = 0; i < items.length; i++) {\n      this._data[queueIndex] = items[i];\n      queueIndex = (queueIndex + 1) % this._capacity;\n    }\n  }\n\n  /**\n   * @returns {TItem | undefined}\n   */\n  dequeue() {\n    if (!this._size) return undefined;\n\n    const result = this._data[this._bottom];\n    this._bottom = (this._bottom + 1) % this._capacity;\n    this._size--;\n\n    return result;\n  }\n\n  clear() {\n    this._size = 0;\n  }\n}\n\nconst qr = new CircularQueue(2500);\nconst qc = new CircularQueue(2500);\n\nconst threats = [];\nconst fences = [];\nfunction initLabel(x) {\n  while (x >= threats.length) {\n    threats.push(0);\n    fences.push(0);\n  }\n  threats[x] = 0;\n  fences[x] = 0;\n}\n\nconst DIR_R = [0, 0, 1, -1];\nconst DIR_C = [1, -1, 0, 0];\n\n/**\n * guideline:\n * &7\n * 0: uninfected and not (yet) threaten\n * 1: infected but unvisited\n * 2: infected and visited\n * 3: uninfected and threaten\n * 4: locked up\n * >>3\n * label\n */\n\n/**\n * @param {number[][]} isInfected\n * @return {number}\n */\nvar containVirus = function (isInfected) {\n  let n = isInfected[0].length;\n  let m = isInfected.length;\n  let label = 0;\n  let res = 0;\n\n  function bfs(ir, ic, label) {\n    qr.enqueue(ir);\n    qc.enqueue(ic);\n    let labelState = (label << 3) | 2;\n    isInfected[ir][ic] = labelState;\n    initLabel(label);\n\n    while (qr.size) {\n      let r = qr.dequeue();\n      let c = qc.dequeue();\n\n      for (let i = 0; i < 4; i++) {\n        let rr = r + DIR_R[i];\n        let cc = c + DIR_C[i];\n        let state = isInfected[rr]?.[cc];\n        if (state == undefined) continue;\n\n        switch (state & 7) {\n          case 0: {\n            isInfected[rr][cc] = (label << 3) | 3;\n            fences[label]++;\n            threats[label]++;\n            break;\n          }\n          case 1: {\n            qr.enqueue(rr);\n            qc.enqueue(cc);\n            isInfected[rr][cc] = labelState;\n            break;\n          }\n          case 3: {\n            fences[label]++;\n            if ((state >> 3) != label) {\n              threats[label]++;\n              isInfected[rr][cc] = (label << 3) | 3;\n            }\n            break;\n          }\n        }\n      }\n    }\n  }\n\n  function isStillThreaten(r, c, lockedLabel) {\n    for (let i = 0; i < 4; i++) {\n      let rr = r + DIR_R[i];\n      let cc = c + DIR_C[i];\n      let state = isInfected[rr]?.[cc];\n      if ((state & 7) == 2 && (state >> 3) != lockedLabel) return true;\n    }\n  }\n\n  while (true) {\n    label = 0;\n    let lockedLabel = 0;\n\n    for (let r = 0; r < m; r++) {\n      for (let c = 0; c < n; c++) {\n        if (isInfected[r][c] == 1) {\n          bfs(r, c, label);\n          if (threats[label] > threats[lockedLabel]) lockedLabel = label;\n          label++;\n        }\n      }\n    }\n\n    if (!label) return res;\n\n    res += fences[lockedLabel];\n\n    for (let r = 0; r < m; r++) {\n      for (let c = 0; c < n; c++) {\n        if ((isInfected[r][c] & 7) == 3) {\n          if (isStillThreaten(r, c, lockedLabel)) isInfected[r][c] = 1;\n          else isInfected[r][c] = 0;\n        }\n      }\n    }\n\n    for (let r = 0; r < m; r++) {\n      for (let c = 0; c < n; c++) {\n        let state = isInfected[r][c];\n        if ((state & 7) == 2) {\n          if ((state >> 3) == lockedLabel) isInfected[r][c] = 4;\n          else isInfected[r][c] = 1;\n        }\n      }\n    }\n  }\n};\n```
['Breadth-First Search', 'Queue', 'JavaScript']