Day 51 of My DSA Problem Solving

Q1 :- Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Input: nums = [1,3,5,6], target = 5  
Output: 2

Input: nums = [1,3,5,6], target = 2  
Output: 1

Input: nums = [1,3,5,6], target = 7  
Output: 4

Input: nums = [1,3,5,6], target = 0  
Output: 0

Input: nums = [1], target = 0  
Output: 0

➡️ Solution

Approach

1. Initialize two pointers:

   • Create two variables, left and right, to represent the current search boundaries.
   • Set left = 0 and right = nums.length - 1.

2. Run a loop while left <= right:

   • This loop helps to narrow down the search space until the correct position is found.

3. Find the middle index:

   • Calculate mid = Math.floor((left + right) / 2) to get the midpoint of the current range.

4. Compare nums[mid] with target:

   • If nums[mid] === target: return mid (target found).
   • If nums[mid] < target: move the left pointer to mid + 1 (search right half).
   • Else: move the right pointer to mid - 1 (search left half).

5. Return left:

   • If the loop ends without finding the target, left will be at the position where the target should be inserted.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0
    let right = nums.length - 1;


  while(left <= right){
    let mid = Math.floor((left + right) / 2)

    if(nums[mid] === target){
      return mid
    }else if(nums[mid] < target){
      left = mid + 1
    }else{
      right = mid - 1
    }

  }
   return left

};

Q2 :- Sqrt(x)

Implement the function mySqrt(x) that computes and returns the integer part of the square root of a non-negative integer x.

• The returned integer should be the greatest integer r such that r * r <= x.
• Do not use any built-in exponent functions like Math.sqrt().

Input: x = 8
Output: 2

Input: x = 4
Output: 2

➡️ Solution

Approach

1. Handle Edge Case:

   • If x is 0, return 0 immediately since the square root of 0 is 0.

2. Initialize Search Range:

   • Set left = 0 and right = x. The square root of x will always lie within this range.

3. Binary Search Loop:

   • While left <= right:
     • Compute mid = Math.floor((left + right) / 2).
     • If mid * mid === x, return mid (exact square root found).
     • If mid * mid < x, move the left boundary to mid + 1 to search in the right half.
     • If mid * mid > x, move the right boundary to mid - 1 to search in the left half.

4. Return Result:

   • If the loop ends without finding an exact square root, return right, which will be the greatest integer r such that r * r <= x.

Time and Space Complexity

• Time Complexity: O(log x) — efficient due to binary search.
• Space Complexity: O(1) — constant space usage.

This method avoids using built-in functions and works efficiently even for large inputs.

Code

/**
 * @param {number} x
 * @return {number}
 */


var mySqrt = function(x) {
if (x === 0) return 0;
let left = 0;
let right = x


while(left <= right){

let mid = Math.floor((left + right) / 2)

if(mid * mid == x){
  return mid
}else if(mid * mid < x){
  left = mid + 1
}else{
  right = mid - 1
}

}

return right;

};

Comments

[Neha Sharma]

good work