Topics
Binary Search

Binary Search (opens in a new tab)

  • Binary search is a search algorithm that finds the position of a target value within a sorted array
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let left = 0, right = nums.length - 1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return -1;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Valid Perfect Square (opens in a new tab)

  • Naive approach would be start half the number now multiply each number by itself and check if it match with target
  • As the array is already sorted Binary search can be modified to reduce the time complexity
/**
 * @param {number} num
 * @return {boolean}
 */
var validPerfectSquare = function (num) {
  if (num == 1) return true;
 
  let left = 0,
    right = Math.floor(num / 2);
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (mid * mid === num) {
      return true;
    }
 
    if (mid * mid < num) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return false;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Search Insert Position (opens in a new tab)

  • Naive approach would be start from left side of the array and insert at a point where you find the first match or next higher number. This approach works very well for small arrays.
  • As the array is already sorted Binary search can be modified to reduce the time complexity
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0, right = nums.length - 1;
  let ans = nums.length;
 
  if (target > nums.at(-1)) {
    // if target is greater than the last element
    return ans;
  }
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2); // obtain the mid value
 
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] >= target) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Find Smallest Letter Greater Than Target (opens in a new tab)

  • Binary search technique is used to find the smallest letter greater than the target
  • If the target is greater than the last element or smaller than the first element, return the first element
/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function (letters, target) {
  let left = 0, right = letters.length - 1;
  let ans = 0;
 
  // if target is beyond the limits of letters
  if (target < letters[0] || letters.at(-1) < target) {
    return letters[ans];
  }
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (target < letters[mid]) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return letters[ans];
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Sqrt(x) (opens in a new tab)

  • Use binary search technique to with a range from 0 to x
  • Use the mid value to check if mid * mid is less than or equal to x
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  let left = 0, right = x, ans;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const square = mid * mid;
 
    if (square <= x) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return ans;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Find First and Last Position of Element in Sorted Array (opens in a new tab)

  • Use binary search technique to find the first & last position of the target element
  • Modify the conditional logic accordingly to find the first & last position of the target
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // if target is beyond the limits of nums
  if (target > nums.at(-1) || target < nums[0]) {
    return [-1, -1];
  }
 
  const firstPos = getFirstPos(nums, target);
  if (firstPos === -1) {
    // if start position is not present, it means the number itself is not present
    return [-1, -1];
  }
  const lastPos = getLastPos(nums, target, firstPos);
 
  return [firstPos, lastPos];
};
 
function getFirstPos(nums, target) {
  let left = 0, right = nums.length - 1;
  let firstPos = -1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    if (nums[mid] === target) {
      firstPos = mid;
      right = mid - 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return firstPos;
}
 
function getLastPos(nums, target, firstPos) {
  let left = firstPos, right = nums.length - 1;
  let lastPos = -1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    if (nums[mid] === target) {
      lastPos = mid;
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return lastPos;
}
Complexity
  • Time: O(log(n))
  • Space: O(1)

Search in Rotated Sorted Array (opens in a new tab)

  • Find which half is sorted and check if the target is within the sorted half
  • If the target is within the sorted half, update the search range accordingly
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let left = 0, right = nums.length - 1;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[mid] === target) {
      return mid;
    }
 
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
 
  return -1;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Find Minimum in Rotated Sorted Array (opens in a new tab)

  • Find which half is sorted and store the minimum value
  • Explore the unsorted half till completion
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let left = 0, right = nums.length - 1, min = Infinity;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[left] <= nums[mid]) {
      min = Math.min(min, nums[left]);
      left = mid + 1;
    } else {
      min = Math.min(min, nums[mid]);
      right = mid - 1;
    }
  }
 
  return min;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Search in Rotated Sorted Array II (opens in a new tab)

  • Find which half is sorted and check if the target is within the sorted half
  • If the target is within the sorted half, update the search range accordingly
  • If left, mid, and right are the same, move the left and right pointers
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
  let left = 0, right = nums.length - 1;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[mid] === target) {
      return true;
    }
 
    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      left += 1;
      right -= 1;
    } else if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
 
  return false;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Find Minimum in Rotated Sorted Array II (opens in a new tab)

  • Find which half is sorted and store the minimum value
  • Explore the unsorted half till completion
  • If left, mid, and right are the same, move the left and right pointers
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let left = 0, right = nums.length - 1;
  let min = Infinity;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      min = Math.min(min, nums[mid]);
      left += 1;
      right -= 1;
    } else if (nums[left] <= nums[mid]) {
      min = Math.min(min, nums[left]);
      left = mid + 1;
    } else {
      min = Math.min(min, nums[mid]);
      right = mid - 1;
    }
  }
 
  return min;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Find Peak Element (opens in a new tab)

  • Use binary search to find if mid is a peak. If mid is not a peak, move towards the direction of the greater element
  • If mid ends at the first or last element, consider it as a peak
/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function (nums) {
  let left = 0, right = nums.length - 1, mid;
 
  while (left <= right) {
    mid = left + Math.floor((right - left) / 2);
 
    if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
      return mid;
    }
 
    if (nums[mid - 1] > nums[mid]) {
      right = mid - 1;
    } else if (nums[mid] < nums[mid + 1]) {
      left = mid + 1;
    } else {
      // edge case where mid is the first/last element
      return mid;
    }
  }
 
  return mid;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Kth Missing Positive Number (opens in a new tab)

  • Find the index of the lower bound of the missing number using binary search
  • Return the missing number by adding the k to the index
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findKthPositive = function (arr, k) {
  let left = 0, right = arr.length - 1;
  let ans = arr.length;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const missingCount = arr[mid] - (mid + 1);
 
    // find smallest index of missing number greater than k
    if (k <= missingCount) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans + k; // arr[ans] + k - (arr[ans] - (ans + 1)) = kth missing number
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Koko Eating Bananas (opens in a new tab)

  • Use binary search to find the if mid is the minimum eating time
  • If time is less than or equal to h, update the answer and move towards the left
  • If time is greater than h, move towards the right
/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
  let max = Math.max(...piles); // max possible count of bananas eaten per hour
  let left = 0, right = max, ans;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const time = piles.reduce((acc, bananas) => acc + Math.ceil(bananas / mid), 0);
 
    if (time <= h) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
Complexity
  • Time: O(n log(Max(piles)))
  • Space: O(1)

Minimum Number of Days to Make m Bouquets (opens in a new tab)

  • Use binary search to find the if mid is the days to make m bouquets
  • If bouquets are greater than or equal to m, update the answer and move towards the left
  • If bouquets are less than m, move towards the right
/**
 * @param {number[]} bloomDay
 * @param {number} m
 * @param {number} k
 * @return {number}
 */
var minDays = function (bloomDay, m, k) {
  if (m * k > bloomDay.length) {
    return -1;
  }
 
  let max = Math.max(...bloomDay); // max possible days
  let left = 0, right = max, ans;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const bouquets = getBouquets(bloomDay, mid, m, k);
 
    if (bouquets >= m) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
 
function getBouquets(bloomDay, mid, m, k) {
  let bouquets = 0, flowers = 0;
  
  for (let i = 0; i < bloomDay.length; i++) {
    // add flowers to bouquet if bloomed or reset
    flowers = bloomDay[i] <= mid ? flowers + 1 : 0
 
    // if enough flowers in a bouquet
    if (flowers === k) {
      bouquets += 1;
      flowers = 0;
    }
 
    // if enough bouquets
    if (bouquets === m) {
      break;
    }
  }
 
  return bouquets;
}
Complexity
  • Time: O(n log(Max(days)))
  • Space: O(1)

Find the Smallest Divisor Given a Threshold (opens in a new tab)

  • Use binary search to find the divisor if it satisfies the threshold
  • If sum is mo than threshold, move towards the right else move towards the left
/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function (nums, threshold) {
  const max = Math.max(...nums);
  let left = 1, right = max, ans;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const sum = divisorSum(nums, mid);
 
    if (sum <= threshold) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
 
function divisorSum(nums, div) {
  let sum = 0;
  for (const val of nums) {
    sum += Math.ceil(val / div);
  }
  return sum;
}
Complexity
  • Time: O(n log(Max(nums)))
  • Space: O(1)

Capacity To Ship Packages Within D Days (opens in a new tab)

  • Use binary search to find the capacity with min & max as the max weight & total weight respectively
  • If the days to ship is less than or equal to the given days, move towards the left else move towards the right
/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function (weights, days) {
  const [totalWeight, maxWeight] = getTotalAndMax(weights);
  let left = maxWeight, right = totalWeight;
  let ans = totalWeight;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const daysToShip = getDaysToShip(weights, mid);
 
    if (daysToShip <= days) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
 
function getTotalAndMax(arr) {
  let sum = 0, max = 0;
 
  for (const item of arr) {
    sum += item;
    if (max < item) {
      max = item;
    }
  }
 
  return [sum, max];
}
 
function getDaysToShip(weights, shipCapacity) {
  let days = 1, capacity = 0;
  for (const weight of weights) {
    if (capacity + weight > shipCapacity) {
      days += 1;
      capacity = 0;
    }
 
    capacity += weight;
  }
 
  return days;
}
Complexity
  • Time: O(n log(Sum(weights)))
  • Space: O(1)

Magnetic Force Between Two Balls (opens in a new tab)

  • Using binary search, set the left as 1 and right as the maximum distance between the balls
  • Check if the placements are possible with the given distance and continue till you find the maximum distance
  • Popularly known as the Aggressive Cows (opens in a new tab) problem
/**
 * @param {number[]} position
 * @param {number} m
 * @return {number}
 */
var maxDistance = function (positions, m) {
  positions.sort((a, b) => a - b);
  let left = 1,
    right = positions.at(-1) - positions.at(0);
 
  // placed in the 2 extreme end of the array
  if (m === 2) {
    return right;
  }
 
  let ans;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const isPossible = checkPlacements(positions, m, mid);
 
    if (isPossible) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return ans;
};
 
function checkPlacements(arr, m, distance) {
  let prev = arr[0],
    count = 1;
 
  for (let i = 1; i < arr.length; i++) {
    // if the gap is maintained
    if (arr[i] - prev >= distance) {
      count += 1;
      prev = arr[i];
    }
 
    // if placements are complete
    if (count === m) {
      return true;
    }
  }
 
  return false;
}
Complexity
  • Time: O(n log(n))
  • Space: O(1)

Split Array Largest Sum (opens in a new tab)

  • Use binary searach with min & max as max & sum of the array
  • Check if the sum can be split into k subarrays for mid value
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var splitArray = function (nums, k) {
  const [sum, max] = getTotalAndMax(nums);
  if (k === nums.length) {
    return max;
  }
 
  if (k === 1) {
    return sum;
  }
 
  let left = max,
    right = sum,
    ans = 0;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const canFit = checkFitment(nums, k, mid);
 
    if (canFit) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
 
function checkFitment(nums, k, limit) {
  let sum = 0,
    count = 1;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    if (sum > limit) {
      count += 1;
      sum = nums[i];
 
      if (count > k) {
        return false;
      }
    }
  }
 
  return true;
}
 
function getTotalAndMax(arr) {
  let sum = 0,
    max = 0;
 
  for (const item of arr) {
    sum += item;
    if (max < item) {
      max = item;
    }
  }
 
  return [sum, max];
}
Complexity
  • Time: O(n log(sum - max))
  • Space: O(1)

Minimize Max Distance to Gas Station (opens in a new tab)

  • For a binary search, use left as minimum distance possible and right as maximum distance possible
  • For each distance, check if it is possible to add k stations with gap less than or equal to the distance
/**
 * @param {number[]} stations
 * @param {number} k
 * @return {number}
 */
var minmaxGasDist = function (stations, k) {
  let left = 0, right = stations.at(-1) - stations.at(0);
 
  while (right - left > 1e-6) {
    const mid = left + (right - left) / 2;
    const canFit = checkEligibleGap(stations, k, mid);
 
    if (canFit) {
      right = mid;
    } else {
      left = mid;
    }
  }
 
  return left;
};
 
function checkEligibleGap(stations, k, gap) {
  let newStations = 0;
 
  for (let i = 0; i < stations.length - 1; i++) {
    newStations += Math.ceil((stations[i + 1] - stations[i]) / gap) - 1;
 
    if (newStations > k) {
      return false;
    }
  }
 
  return true;
}
Complexity
  • Time: O(n log(W)) where W is the range of the answer
  • Space: O(1)

Minimum Number of Operations to Make Array Continuous (opens in a new tab)

  • Sort the given nums array by removing duplicates
  • Consider each element as the first element & find the number of elements that can be included in the subarray till the last
  • Consider the rest of the elements count as number of operations required
/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function (nums) {
  const uniqNums = [...new Set(nums)].sort((a, b) => a - b);
 
  // check if already continuous
  if (uniqNums.at(-1) - uniqNums[0] === 1) {
    return 0;
  }
 
  let minOps = nums.length;
  for (let idx = 0; idx < uniqNums.length; idx++) {
    const first = uniqNums[idx];
    const last = first + nums.length - 1; // last element to make it continuous
 
    const lastIdx = getUpperBound(uniqNums, last);
    const sortedCount = lastIdx - idx; // number of elements that are already present to make it continuous
    const ops = nums.length - sortedCount; // number of elements that need to be replaced
 
    minOps = Math.min(minOps, ops);
  }
 
  return minOps;
};
 
function getUpperBound(arr, k) {
  let left = 0, right = arr.length, ans = arr.length;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (k < arr[mid]) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
}
Complexity
  • Time: O(n log(n))
  • Space: O(n)
MathSliding Window