Road2Geeks

Binary Search on Answer – Smallest Divisor Given a Threshold Binary Search on Answer is a powerful problem-solving pattern where instead of searching within an array, we perform binary search over the range of possible answers . LeetCode problem 1283 – Smallest Divisor Given a Threshold is a classic example of this pattern. 🔍 Problem Intuition We are given an array of positive integers and a threshold. For any chosen divisor d , we divide each element by d , round it up using ceil , and sum the results. Our goal is to find the smallest possible divisor such that this sum does not exceed the given threshold. 💡 Key Observation If the divisor is small → the sum becomes large If the divisor is large → the sum becomes small This creates a monotonic condition , making it a perfect candidate for binary search on the answer. ⚠️ Important Edge Case The divisor can never be 0 . S...

Binary Search on Answer Pattern (Complete Practice Guide) Binary Search on Answer is a powerful problem-solving pattern frequently used in coding interviews and competitive programming. Instead of searching inside an array, we perform binary search on the range of possible answers . Minimum or maximum value is asked Answer lies within a numeric range A feasibility function exists Feasibility is monotonic 📌 LeetCode Problems Using Binary Search on Answer Problem Difficulty Core Idea 1283 – Find the Smallest Divisor Given a Threshold Easy Binary search on divisor value 1011 – Capacity To Ship Packages Within D Days ...

LeetCode 875: Koko Eating Bananas – Binary Search on Answer Explained LeetCode 875, Koko Eating Bananas , is a classic problem that looks simple at first glance but introduces a powerful and reusable concept: Binary Search on the Answer . In this article, we’ll break down the intuition, approach, and final Python solution step by step. 👉 Full source code is available here: GitHub – LeetCode 875 Solution 🧠 Problem Overview Koko loves bananas and has h hours to eat all the bananas from multiple piles. She can choose a speed k (bananas per hour) and eats from only one pile per hour. The goal is to find the minimum eating speed that allows her to finish within h hours. ❌ Why Brute Force Fails A naive approach would be to try every possible eating speed from 1 to max(piles) and check if Koko can finish on time. However, this leads to an ine...

Find Minimum in Rotated Sorted Array – Binary Search (LeetCode 153) In this problem, we are given a rotated sorted array with unique elements. The goal is to find the minimum element in O(log n) time, which naturally points to a binary search based solution. Key Observations A rotated sorted array always has one sorted half. If the array is not rotated, the first element is the minimum. The minimum element always lies in the unsorted half. Approach We use two pointers ( s and e ) and compare the middle element with the right boundary. Based on this comparison, we eliminate the sorted half and narrow the search space until both pointers converge. Python Code class Solution: def findMin(self, nums: List[int]) -> int: s, e = 0, len(nums) - 1 while s nums[e]: s = mid + 1 else: e = mid...

Binary Search in Rotated Sorted Array (LeetCode 33) Binary Search in a Rotated Sorted Array is a classic interview problem that tests your understanding of binary search beyond the basics. In this article, we’ll break down the logic, intuition, and implementation of an efficient O(log n) solution using Python. 🔍 Problem Overview You are given a rotated sorted array of distinct integers and a target value. Your task is to return the index of the target if it exists, otherwise return -1 . Example: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 The challenge arises because the array is sorted but rotated at an unknown pivot, which means traditional binary search cannot be applied directly. 🧠 Key Insight At any point in a rotated sorted array, at least one half is always sorted . We use this fact to decide which side of the array to discard during binary search. Identify whether the left or right half is sorted Check if the target lies within the so...

Binary Search in Python – Simple and Efficient Approach (LeetCode 704) Today I solved LeetCode 704: Binary Search , and the problem felt quite straightforward since I was already familiar with the binary search concept. This problem is a classic example of how knowing the fundamentals can make problem-solving much easier. The task is simple: given a sorted array of integers and a target value, return the index of the target if it exists. Otherwise, return -1 . Since the array is already sorted, binary search is the most optimal approach. Why Binary Search? Binary search works by repeatedly dividing the search space in half. Instead of checking every element one by one, we compare the middle element with the target and eliminate half of the array in each step. This drastically improves performance compared to a linear search. Approach Explained Initialize tw...

Happy Number – HashSet vs Floyd’s Cycle Detection The Happy Number problem looks simple at first, but it hides an important algorithmic concept: cycle detection . In this post, we’ll explore two valid approaches to solve the problem and understand why the optimized solution works. 📌 Complete Python solution code: View on GitHub Problem Overview A number is called happy if repeatedly replacing it with the sum of the squares of its digits eventually leads to 1 . If the process enters a cycle that does not include 1, the number is not happy. Example: 19 → 1² + 9² = 82 82 → 8² + 2² = 68 68 → 6² + 8² = 100 100 → 1² + 0² + 0² = 1 ✅ Approach 1: Using a HashSet The most commonly taught approach uses a HashSet to track numbers we have already seen. If a number repeats, we know we are stuck in a cycle. Idea Store every generated number in a set If the number becomes 1 → happy If the number repeats → cycle detected Code class Solution...