Search Insert Position (LeetCode 35)

35. 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.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

Type	Value
Time	O(log n)
Space	O(1)

• Approach: Binary search; return insertion point when not found.
• Dry run (nums=[1,3,5,6], target=5):
  • left=0,right=3 → mid=1,val=3 < 5 → left=2
  • left=2,right=3 → mid=2,val=5 == 5 → return 2

---

Find First and Last Position of Element in Sorted Array (LeetCode 34)

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:
Input: nums = [], target = 0
Output: [-1,-1]

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{find(nums, target, true), find(nums, target, false)};
    }

    private int find(int[] nums, int target, boolean isFirst) {
        int left = 0, right = nums.length - 1;
        int ans = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                ans = mid;
                if (isFirst) {
                    right = mid - 1; 
                } else {
                    left = mid + 1;  
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }
}

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def find(is_first):
            left, right = 0, len(nums) - 1
            ans = -1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    ans = mid
                    if is_first:
                        right = mid - 1
                    else:
                        left = mid + 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return ans
        
        return [find(True), find(False)]

Type	Value
Time	O(log n)
Space	O(1)

• Approach: Perform two separate binary searches. One to find the first occurrence (when target is found, update answer and search left) and one to find the last occurrence (when target is found, update answer and search right).
• Dry run (nums=[5,7,7,8,8,10], target=8):
  • First target binary search: target 8 found at index 4 -> ans=4, go left. Found at index 3 -> ans=3, go left. Finish at 3.
  • Second target binary search: target 8 found at index 3 -> ans=3, go right. Found at index 4 -> ans=4, go right. Finish at 4.
  • Return [3,4].

---

Find Minimum in Rotated Sorted Array (LeetCode 153)

153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

class Solution {
    public int findMin(int[] nums) {
        int s = 0;
        int e = nums.length - 1;
        while (s < e) {
            int m = s + (e - s) / 2;
            if (nums[m] <= nums[e]) {
                e = m;
            } else
                s = m + 1;
        }
        return nums[s];
    }
}

class Solution:
    def findMin(self, nums: List[int]) -> int:
        s, e = 0, len(nums) - 1
        while s < e:
            m = s + (e - s) // 2
            if nums[m] <= nums[e]:
                e = m
            else:
                s = m + 1
        return nums[s]

Type	Value
Time	O(log n)
Space	O(1)

• Approach: Binary search focusing on the strictly increasing portion vs drop.
• Dry run (nums=[3,4,5,1,2]):
  • m=2 (5) > nums[e] (2) -> s=3
  • m=3 (1) <= nums[e] (2) -> e=3
  • s=e=3 -> returns nums[3] = 1.

---

Search in Rotated Sorted Array (LeetCode 33)

33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

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

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 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;
    }
}

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

Type	Value
Time	O(log n)
Space	O(1)

• Approach: Binary search. Identify which half of the array is sorted (left to mid, or mid to right). If the target falls into the sorted half's range, move onto that half; otherwise, search the other half.
• Dry run (nums = [4,5,6,7,0,1,2], target = 0):
  • left=0, right=6: mid=3 (val 7). Target 0 != 7.
  • Left half [4,5,6,7] is sorted. Target 0 is NOT between 4 and 7. Thus move to right half: left = mid + 1 = 4.
  • left=4, right=6: mid=5 (val 1). Target 0 != 1.
  • Right half [1,2] is sorted. Target 0 is NOT between 1 and 2. Thus move to left half: right = mid - 1 = 4.
  • left=4, right=4: mid=4 (val 0). Target 0 == 0. Return 4.

---

Search in Rotated Sorted Array II (LeetCode 81)

81. Search in Rotated Sorted Array II
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example 1:

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

Example 2:

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

class Solution {

    public boolean search(int[] nums, int target) {
        int s = 0;
        int e = nums.length - 1;
        while (s <= e) {
            int m = s + (e - s) / 2;
            if (nums[m] == target)
                return true;
            if (nums[s] == nums[m] && nums[m] == nums[e]) {
                s++;
                e--;
                continue;
            }
            if (nums[s] <= nums[m]) {
                if (nums[s] <= target && target < nums[m])
                    e = m - 1;
                else
                    s = m + 1;
            } else {
                if (nums[m] < target && target <= nums[e])
                    s = m + 1;
                else
                    e = m - 1;
           }
        }
        return false;
    }
}

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        s, e = 0, len(nums) - 1
        while s <= e:
            m = s + (e - s) // 2
            if nums[m] == target: return True
            if nums[s] == nums[m] == nums[e]:
                s += 1
                e -= 1
                continue
            if nums[s] <= nums[m]:
                if nums[s] <= target < nums[m]: e = m - 1
                else: s = m + 1
            else:
                if nums[m] < target <= nums[e]: s = m + 1
                else: e = m - 1
        return False

Type	Value
Time	O(log n) avg, O(n) worst
Space	O(1)

• Approach: Binary Search with a minor tweak to handle duplicates. Skip same elements at edges.
• Dry run (nums = [2,5,6,0,0,1,2], target = 0):
  • m=3 (val 0), target=0 -> returns true.

---

Kth Missing Positive Number (LeetCode 1539)

1539. Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Return the kth positive integer that is missing from this array.

Example 1:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            int missingNumbersTillNow = arr[mid] - (mid + 1);
            if (missingNumbersTillNow < k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return k + start;
    }
}

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            missing = arr[mid] - (mid + 1)
            if missing < k:
                left = mid + 1
            else:
                right = mid - 1
        return left + k

Type	Value
Time	O(log n)
Space	O(1)

• Approach: Use binary search. For any index mid, the number of missing positive integers before arr[mid] is arr[mid] - (mid + 1). If this count is less than k, the target must be to the right, so we set left = mid + 1. Otherwise, it's to the left, so we set right = mid - 1. The kth missing number is then left + k.
• Dry run (arr = [2,3,4,7,11], k = 5):
  • l=0, r=4. mid=2, val=4. Missing till mid: 4 - (2+1) = 1 < 5 -> l=3
  • l=3, r=4. mid=3, val=7. Missing till mid: 7 - (3+1) = 3 < 5 -> l=4
  • l=4, r=4. mid=4, val=11. Missing till mid: 11 - (4+1) = 6 >= 5 -> r=3
  • Loop ends. Return l + k = 4 + 5 = 9.

---

Koko Eating Bananas (LeetCode 875)

875. Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23

class Solution {
    public boolean canEat(int[] piles, int k, int h) {
        long hours = 0;
        for (int pile : piles) {
            hours += (pile + k - 1) / k;
        }
        return hours <= h;
    }

    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canEat(piles, mid, h)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

import math
class Solution:
    def canEat(self, piles: List[int], k: int, h: int) -> bool:
        hours = 0
        for pile in piles:
            hours += math.ceil(pile / k)
        return hours <= h

    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles)
        
        while left < right:
            mid = (left + right) // 2
            if self.canEat(piles, mid, h):
                right = mid
            else:
                left = mid + 1
        return left

Type	Value
Time	O(n log m)
Space	O(1)

• Approach: Binary search on the answer space. The minimum possible speed is 1, and the maximum is the maximum pile size (since she can only eat one pile per hour max). For each candidate speed mid, we calculate if it's possible to eat all piles within h hours. If yes, we search left (try slower). If no, we search right (go faster).
• Dry run (piles=[3,6,7,11], h=8):
  • l=1, r=11. mid=6. Hours: CEIL(3/6)+CEIL(6/6)+CEIL(7/6)+CEIL(11/6)=1+1+2+2=6 <= 8 -> right=6.
  • l=1, r=6. mid=3. Hours: CEIL(3/3)+CEIL(6/3)+CEIL(7/3)+CEIL(11/3)=1+2+3+4=10 > 8 -> left=4.
  • l=4, r=6. mid=5. Hours: CEIL(3/5)+CEIL(6/5)+CEIL(7/5)+CEIL(11/5)=1+2+2+3=8 <= 8 -> right=5.
  • l=4, r=5. mid=4. Hours: CEIL(3/4)+CEIL(6/4)+CEIL(7/4)+CEIL(11/4)=1+2+2+3=8 <= 8 -> right=4.
  • loop ends, return 4.

---

Find Peak Element (LeetCode 162)

162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return left

Type	Value
Time	O(log n)
Space	O(1)

• Approach: Use binary search. If nums[mid] > nums[mid + 1], a peak must exist on the left side (inclusive of mid), so set right = mid. Otherwise, a peak must exist on the right side, so set left = mid + 1.
• Dry run (nums = [1,2,3,1]):
  • left=0, right=3. mid=1. nums[1]=2 < nums[2]=3 -> left = mid + 1 = 2.
  • left=2, right=3. mid=2. nums[2]=3 > nums[3]=1 -> right = mid = 2.
  • left == right -> return left = 2.

---

Search a 2D Matrix (LeetCode 74)

74. Search a 2D Matrix

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int left = 0;
        int right = rows * cols - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midVal = matrix[mid / cols][mid % cols];
            if (midVal == target) {
                return true;
            } else if (midVal < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix)
        col = len(matrix[0])
        l = 0
        r = row * col - 1
        while l <= r:
            mid = l + (r - l) // 2
            curr = matrix[mid // col][mid % col]
            if curr == target:
                return True
            elif curr < target:
                l = mid + 1
            else:
                r = mid - 1
        return False

Type	Value
Time	O(log(m * n))
Space	O(1)

• Approach: Treat the 2D matrix as a sorted 1D array of size m * n. Perform binary search. The 1D index mid maps to the 2D indices row = mid / cols and col = mid % cols.
• Dry run (matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3):
  • m=3, n=4. left=0, right=11.
  • mid=5. matrix[5/4][5%4] = matrix[1][1] = 11.
  • 11 > 3 -> right = mid - 1 = 4.
  • mid=2. matrix[2/4][2%4] = matrix[0][2] = 5.
  • 5 > 3 -> right = mid - 1 = 1.
  • mid=0. matrix[0/4][0%4] = matrix[0][0] = 1.
  • 1 < 3 -> left = mid + 1 = 1.
  • mid=1. matrix[1/4][1%4] = matrix[0][1] = 3.
  • 3 == 3 -> return true.

---