AI solution for JavaScript Coding Question on BFE.dev
103. implement Math.sqrt()

One possible solution for mySqrt() is to use binary search to find the integer square root.

function mySqrt(x) {
  // Special case
  if (x === 0) return 0;
  // Binary search for integer square root
  let left = 1, right = x;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (mid * mid === x) return mid;
    if (mid * mid < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  // Return the floor of the last mid
  return right;
}

The time complexity of this solution is O(log x) and the space complexity is O(1), as we only use a few constant variables.

This solution is already optimal in terms of time complexity, but there is a way to improve the space complexity. Instead of using the left and right variables to track the range of possible square roots, we can simply define two pointers and update them until they meet:

function mySqrt(x) {
  // Special case
  if (x === 0) return 0;
  // Binary search for integer square root with two pointers
  let lo = 1, hi = x;
  while (lo < hi) {
    let mid = Math.floor((lo + hi) / 2);
    if (mid * mid === x) return mid;
    if (mid * mid < x) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  // Return the floor of the last mid
  return lo * lo > x ? lo - 1 : lo;
}

This solution still has a time complexity of O(log x), but the space complexity is now O(1).