[Javascript] BFS & Cycle Counting Explained
Solution: BFS & Cycle Counting\n\nBFS level-by-level and get minimum swaps for the node values at each level.\n\nHow to calculate the minimum swaps to sort an a
**Solution: BFS & Cycle Counting**\n\nBFS level-by-level and get minimum swaps for the node values at each level.\n\nHow to calculate the minimum swaps to sort an array:\n  1. Get the index of each number in its sorted position (store in a hashmap `indexes`)\n  2. For each `nums[i]`, store the number we need to swap with to place `nums[i]` in its sorted position (store in a hashmap `next`)\n  3. Find the size of each cycle.\n  4. Get the total sum of each (`cycle size - 1`).\n\nWhy sum of (`cycle size - 1`) is correct:\n*   If cycle size = `1`, we don\'t need any swaps.\n*   If cycle size = `2`, we only need 1 swap.\n*   If cycle size = `3`, we need 2 swaps.\n\n  --- **Main Proof** ---\n*   Starting from the smallest number in the cycle, swap each `nums[i]` (where `nums[i]` is in the cycle) into its sorted position.\n*   Since the number is now in the correct position, it is no longer in the cycle and this leaves us with a cycle of size (`n - 1`), where `n = the previous size of the cycle`.\n\t*   The edge from `nums[i]` -> correct position is now replaced with a new edge coming from the number we swapped with.\n\n`n = number of nodes in the tree`\nTime Complexity: `O(n log(n))` 1581ms\nSpace Complexity: `O(n)` 129MB\n```\nvar minimumOperations = function(root) {\n  let queue = [root], ans = 0;\n  while (queue.length)  {\n    let next = [];\n    ans += minSwaps(queue.map(node => node.val));\n    while (queue.length) {\n      let node = queue.shift();\n      if (node.left) next.push(node.left);\n      if (node.right) next.push(node.right);\n    }\n    queue = next;\n  } \n  return ans;\n};\n\nfunction minSwaps(nums) {\n  let sorted = [...nums].sort((a, b) => a - b);\n  let indexes = sorted.reduce((memo, num, idx) => {\n    memo[num] = idx;\n    return memo;\n  }, {});\n\n  let next = {};\n  for (let num of nums) {\n    next[num] = nums[indexes[num]];\n  }\n\n  let seen = new Set(), ans = 0;\n  for (let num of nums) {\n    let cycleSize = 0, node = num;\n    while (!seen.has(node)) {\n      seen.add(node);\n      node = next[node];\n      cycleSize++;\n    }\n    ans += Math.max(0, cycleSize - 1);\n  }\n  return ans;\n}\n```
['JavaScript']