[Javascript] Line Sweep
Solution: Line Sweep\n\nUse line sweep to get range updates in O(1) time, accumulating them with prefix sum at the end to get the actual values.\n\nSplit the ho
**Solution: Line Sweep**\n\nUse line sweep to get range updates in `O(1)` time, accumulating them with prefix sum at the end to get the actual values.\n\nSplit the houses into three segments: \n  1. The left part (nodes outside of the loop, on the left)\n  2. The loop (nodes in (`x`, `y`))\n  3. The right part (nodes outside of the loop on the right)\n\nThree scenarios to cover:\n  1. From the left:\n    Left nodes -> other left nodes\n    Left nodes -> right nodes\n  2. From the loop:\n    Loop nodes -> left nodes\n    Loop nodes -> other loop nodes\n    Loop nodes -> right nodes\n  3. From the right:\n    Right nodes -> other right nodes\n    (right -> left was covered from the left side already)\n\nTime Complexity: `O(n)`\nSpace Complexity: `O(n)`\n```\nvar countOfPairs = function(n, x, y) {\n  if (x > y) {\n    let temp = x;\n    x = y, y = temp;\n  }\n  let loopSize = y - x + 1;\n  let sum = Array(n + 1).fill(0);\n  if (y - x <= 1) {\n    for (let node = 1; node < n; node++) {\n      sum[1] += 2;\n      sum[n - node + 1] -= 2;\n    }\n  } else {\n    let rightNodes = n - y;\n    for (let left = 1; left < x; left++) {\n      // left node -> other left nodes\n      // distance from node `left` to every other left node where node > `left`\n      let remainingNodesLeft = x - left - 1;\n      sum[1] += 2;\n      sum[remainingNodesLeft + 1] -= 2;\n      \n      // left node -> all right nodes\n      // distance from:\n        // left -> last left node (x - left - 1)\n        // last left node -> loop start -> loop end -> first right node (3)\n      let distToLastLeftNode = Math.max(0, x - left - 1);\n      let startDistToRight = 3 + distToLastLeftNode;\n      sum[startDistToRight] += 2;\n      sum[startDistToRight + rightNodes] -= 2;\n    }\n    \n    // right nodes -> other right nodes\n    // same calculation, distance from current node to all other right nodes where node > right\n    for (let right = y + 1; right < n; right++) {\n      let remainingNodesRight = n - right;\n      sum[1] += 2;\n      sum[remainingNodesRight + 1] -= 2;\n    }\n    \n    // loop nodes\n    let leftNodes = x - 1;\n    for (let node = x; node <= y; node++) {\n      // loop nodes -> other loop nodes\n      // visualize a circle, the distances from one node to other nodes are consistent no matter which node we start from in the circle\n      // if the loop size is odd, count every pair of symmetrical nodes in the circle, starting from node\n      // if the loop size is even, there will be one node left at the end instead of a pair\n      if (loopSize % 2 === 1) {\n        sum[1] += 2;\n        sum[Math.floor(loopSize / 2) + 1] -= 2;\n      } else {\n        sum[1] += 2;\n        sum[loopSize / 2]--;\n        sum[(loopSize / 2) + 1]--;\n      }\n      \n      // loop nodes -> left nodes\n      // find the shortest distance to get to the loop start node, then get the distances to other left nodes from there\n      let distToLeft = 1 + Math.min(node - x, y - node + 1);\n      sum[distToLeft] += 2;\n      sum[distToLeft + leftNodes] -= 2;\n      \n      // loop nodes -> right nodes\n      // find the shortest distance to get to the loop end node, then get the distances to other right nodes from there\n      let distToRight = 1 + Math.min(y - node, node - x + 1);\n      sum[distToRight] += 2;\n      sum[distToRight + rightNodes] -= 2;\n    }\n  }\n    \n  // accumulate end values using prefix sum\n  for (let i = 1; i <= n; i++) {\n    sum[i] += sum[i - 1];\n  }\n  sum.shift();\n  if (sum.length > n) sum.pop();\n  return sum;\n};\n```
['JavaScript']