Author: akshay

Problem Statement Write a function secondLargest(arr) that takes an array of numbers and returns the second largest unique number in the array. Approach Check array length: If the array contains fewer than 2 elements, return “Array should have at least two numbers”. Initialize two variables: firstLargest as the smallest possible value (e.g., -∞ or Integer.MIN_VALUE). secondLargest as the smallest possible value. Iterate through the array: For each element num: If num is greater than firstLargest: Update secondLargest to firstLargest. Update firstLargest to num. Else if num is greater than secondLargest and not equal to firstLargest: Update secondLargest to num. Result:…

Find k Closest Elements Given a sorted array, this algorithm returns the k elements closest to a target value x. The output is sorted in ascending order. Steps 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. Dry Run Input: [1, 2, 3, 4, 5], k = 4, x = 3 Output: [1, 2,…

This algorithm finds the single non-duplicate element in a sorted array where every other element appears exactly twice. Steps 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] Dry Run Input: [1,1,2,3,3,4,4,5,5,8,8] → Output: 2 Input: [3,3,7,7,10,11,11] →…

This algorithm finds the peak element in a mountain array using binary search. A mountain array increases to a peak and then decreases. Steps 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 Dry Run Input: [0,1,0] → Output: 1 Input: [0,2,1,0] → Output: 1 Input: [0,10,5,2] → Output: 1 Time & Space Complexity Time: O(log n)…

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. Steps 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 Dry Run Input: [5,7,7,8,8,10], target = 8 First binary search finds first index 3 Second binary search finds last index 4 Output: [3, 4] Input: target = 6 → Output: [-1, -1] Input: target = 0 → Output: [-1, -1]…

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]. Steps 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]. Dry Run Input: [5,7,7,8,8,10], target = 8 First binary search finds index 3 Second binary search finds index 4 Answer: [3, 4] Input: [5,7,7,8,8,10], target = 6 Output: [-1, -1] Input: [5,7,7,8,8,10], target = 0 Output: [-1, -1] Time & Space Complexity Time Complexity: O(log n)…

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. Steps 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 = m -…

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. Steps 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 or peak →…

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. Steps 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. Return r. Dry…

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. Steps 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 right: l =…