Author: devangini123

🌙 Problem Statement: This algorithm finds the peak element in a mountain array using binary search. A mountain array increases to a peak and then decreases. Approach: Initialize l = 0 and r = arr.length – 1. Use binary search: If arr[m + 1] > arr[m], peak is to the right → l = m + 1. Else peak is at m or to the left → r = m. When loop ends, l (or r) is the peak index. Time & Space Complexity: Time Complexity: O(logn) Space Complexity: O(1) Dry Run Input: arr = [1, 3, 5, 6, 4,…

🌙 Problem Statement: This version improves clarity by separating the two binary searches more cleanly. We use one binary search to find the first index, and another to find the last index of the target. Approach: Binary search for the **first index** (on match, shift right side). Binary search for the **last index** (on match, shift left side). Update ans[0] and ans[1] accordingly. Time & Space Complexity: Time Complexity: O(logn) Space Complexity: O(1) Dry Run Input: arr = [5, 7, 7, 8, 8, 10], target = 8 Initial: l = 0, r = 5 ans = [-1, -1] — First…

🌙 Problem Statement: This problem asks us to find the first and last positions of a given target in a sorted array. If the target is not found, return [-1, -1]. Approach: Use binary search twice. Once to find the **first occurrence** (left bound). Once to find the **last occurrence** (right bound). Store results in ans[0] and ans[1]. Time & Space Complexity: Time Complexity: O(logn) Space Complexity: O(1) Dry Run Input: arr = [5, 7, 7, 8, 8, 10], target = 8 Initial: l = 0, r = 5 ans = [-1, -1] — First While Loop (find first index)…

🌙 Problem Statement: This problem asks us to find the smallest element in an array that was originally sorted in ascending order and then rotated. The array has no duplicates. Approach: We use binary search to locate the minimum element efficiently. Initialize l = 0 and r = a.length – 1. While l ≤ r. If a[l] ≤ a[r] → subarray is sorted → return a[l]. Find mid: m = l + floor((r – l) / 2). If a[m] < a[m - 1] → pivot found → return a[m]. If a[l] > a[m] → rotation point is left → r…

🌙 Problem Statement: This problem involves finding any **peak element** in an array. A peak element is an element that is strictly greater than its neighbors. The array is unsorted, but there’s guaranteed to be at least one peak. Approach: We use binary search to find a peak efficiently. Initialize l = 0 and r = arr.length – 1. While l < r: Find middle: m = l + floor((r - l) / 2) If arr[m] < arr[m + 1] → we are in ascending slope → shift l = m + 1. Else → we are in descending slope…

🌙 Problem Statement: This problem finds the first bad version in a sequence of versions from 1 to n. We have an API isBadVersion(version) that returns whether a version is bad. We use binary search to pinpoint the earliest bad version. Approach: Initialize pointers: l = 1 and r = n. While l < r: Compute mid: m = l + floor((r - l) / 2). If isBadVersion(m) is false → move right (l = m + 1). Else (true) → move left or stay (r = m). Loop ends when l == r, which is the first bad version.…

🌙 Problem Statement: This problem requires finding a target value in a rotated sorted array nums. Using a modified binary search, we determine which half of the array is sorted in each iteration and narrow the search range accordingly. Approach: Initialize two pointers: l = 0 and r = nums.length – 1. While l ≤ r: Compute mid: m = l + floor((r – l) / 2). If nums[m] === target, return m. Check which side is sorted: If nums[l] ≤ nums[m], left side is sorted: If target ∈ [nums[l], nums[m]], move left: r = m – 1. Else, move…

🌙 Problem Statement: This problem uses binary search to find a hidden number between 1 and n using a feedback API guess(num), which tells us whether our guess is too high, too low, or correct. Approach: Initialize two pointers: l = 1 and r = n. Use binary search to guess the middle number m. If guess(m) returns: 0 → m is the correct number. -1 → the picked number is smaller → move left. 1 → the picked number is larger → move right. Repeat until the number is found. Edge Case Input: n= 1, pick = 1 Output:…

🌙 Problem Statement: This problem is about computing the floor of the square root of a number x using an optimized binary search approach. A best practice in binary search is to calculate the mid-point in a way that avoids integer overflow: m = l + (r – l) / 2. Approach: If x is less than 2, return x. Set search boundaries: l = 2, r = floor(x / 2). Calculate mid-point safely: m = l + floor((r – l) / 2). Compare m * m with x. If m * m == x, return m. If m *…

🌙 Problem Statement: This problem is about finding the floor value of the square root of a non-negative integer x. You cannot use built-in square root functions. The goal is to use binary search to compute the answer efficiently. Approach: If x is 0 or 1, return x. Set the binary search range: l = 2, r = floor(x / 2). Use binary search to find the greatest number m such that m * m ≤ x. If m * m === x, return m. If m * m > x, search left side. If m * m < x,…