Author: devangini123

🌙 Problem Statement: Given a sorted array, this algorithm returns the k elements closest to a target value x. The output is sorted in ascending order. Approach: We apply binary search to find the best starting index of the k closest elements window. We compare arr[m + k] – x and x – arr[m] to decide whether to shift the window left or right. Once we find the optimal window, return the subarray from index l to l + k – 1. Time & Space Complexity: Time Complexity: O(log(n – k) + k) Space Complexity: O(k) Dry Run Input (assumed):…

🌙 Problem Statement: This algorithm finds the single non-duplicate element in a sorted array where every other element appears exactly twice. Approach: Use binary search between left (l) and right (r). At each mid (m): If arr[m] === arr[m – 1], count elements on the left. If that count is odd → single lies left → r = m – 2. If count is even → single lies right → l = m + 1. Same logic applies if arr[m] === arr[m + 1]. If neither left nor right match → return arr[m]. Time & Space Complexity: Time Complexity: O(logn)…

🌙 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:…