DAY 2/10: This could be your Pre-Interview Checklist for DSA -Binary Search on LeetCode

Binary search interview questions guide in Java

13 min readMar 11, 2024

How do I build intuition to solve a Leetcode (DSA) question?

How can I efficiently review the extensive list of DSA questions for binary search algorithm before my interview?

While solving any question, I have always leaned towards the optimal solution rather than considering brute force approach. How do I start from naive solution?

So, if these are some of the things that are going on in your mind, then do not worry; we are in the same boat. And that is exactly what I will try to address in my article today, as I have started an article series around it.

Here is the 1st article — Pre-interview checklist | Arrays & Strings

Think of this series like a guide: you must spend an hour or two before an interview and revise all the important questions. We’ll focus solely on conceptual understanding, discussing the thought process behind the solution and analyzing its time and space complexity, instead of talking about the code.

Because if you can visualise the problem along with the various types of solutions, the code in your language of choice should naturally come to you.

You are free to take your own notes and keep them handy for even crisper revision material.

Also, for all the below questions, we have added the video explanation in the form of Youtube playlist links, so you might as well want to check those out if you don’t understand the text based approach or code.

Let’s get started!!

How to identify binary search problems?

Array will be sorted.
Time complexity of O(log n) will be mentioned in the problem
If you encounter a problem where you need to search for a particular element or find an optimal solution by repeatedly dividing the search space, binary search might be a good fit.
Many problem statements explicitly mention or hint at binary search. Look for keywords like “search,” “find,” “sorted,” “range,” or “divide and conquer” in the problem description.
With practice, you will start recognizing recurring problem patterns that are suited for binary search.

I have recently started with day-wise DSA revision series also, you can check that out for a quick refresher of concepts probably before your tech interview:

Questions List:

1. 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]

The leetcode question for this is available here.

Optimal Approach — Binary Search:

To achieve a time complexity of O(log n), you can use binary search twice(for starting and ending position). Once target is found, continue binary searching towards the left to find the first occurrence of target. Similarly, perform another binary search to find the ending position of the target element by searching towards the right.

Java Code is available on GitHub here.

2. Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

The leetcode question for this is available here.

Optimal Approach:

Square root of a number will never be greater than the mid of that number (half of the number). If you use this observation the search range will reduce to half. Now apply binary search and in each iteration, check whether square of the element at mid is equal to x. If it is greater, search in the left half, else, search in the right half of the array.

Java Code is available on GitHub here.

3. First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

The leetcode question for this is available here.

Optimal Approach:

Since the versions are sorted and all versions after a bad one are also bad, you can use binary search to find the first bad version efficiently. Check whether the element at mid is a good or bad version. If it is a good version, check in the right half of the array (as array is sorted and all versions after a bad version are also bad). If it is a bad version, store that index(as it may be the first bad version) and then check in the left half of the array(as it may not be the first bad version).

Java Code is available on GitHub here.

4. Peak Index in a Mountain Array

An array arr is a mountain if the following properties hold:

arr.length >= 3

There exists some i with 0 < i < arr.length - 1 such that:

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

The leetcode question for this is available here.

Optimal Approach:

To achieve a time complexity of O(log n), you can use binary search algorithm. Start by initializing pointers at the start (low) and end (high) of the array. Narrow down the search range iteratively by comparing the middle element with its adjacent elements to determine whether the peak lies to the left or right. By adjusting the pointers based on the comparison, you eventually converge on the peak element.

Java Code is available on GitHub here.

5. 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 rotated at an unknown pivot 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 rotated at pivot index 3 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

The leetcode question for this is available here.

Optimal Approach — Modified Binary Search:

Use binary search to find the pivot point(the point at which the array is rotated). The target can lie in either of the two halves of the array. Check whether the target falls in the range of left half or right half of the array. Once you find where the target might be present, perform binary search in that half of the array.

Java Code is available on GitHub here.

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

The leetcode question for this is available here.

Optimal Approach:

The previous approach may not work if there are duplicates in the array. Instead of comparing the middle element with the left and right elements, you can handle the cases where the middle element is equal to the left or right elements. If the middle element is equal to the left element, increment the left pointer. Similarly, if the middle element is equal to the right element, decrement the right pointer. This helps in handling duplicate elements and ensures that the search is continued towards the unsorted part of the array.

Java Code is available on GitHub here.

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

The leetcode question for this is available here.

Optimal Approach:

Use binary search to efficiently find the pivot point or the smallest element in the rotated sorted array. Initialize low and high pointers representing the search range. While low < high, compare nums[mid] with nums[high] to determine which half might contain the minimum element and update low or high accordingly. Repeat this process until low and high meet, indicating the minimum element is found.

Java Code is available on GitHub here.

8. Find Minimum in Rotated Sorted Array II

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

[4,5,6,7,0,1,4] if it was rotated 4 times.
[0,1,4,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 that may contain duplicates, return the minimum element of this array.

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

Example 1:

Input: nums = [1,3,5]
Output: 1

Example 2:

Input: nums = [2,2,2,0,1]
Output: 0

The leetcode question for this is available here.

Optimal Approach:

To handle duplicates in the array while finding the minimum element in a rotated sorted array, you can make a slight adjustment to the binary search algorithm. When the value at the middle index is equal to the value at the high index, it indicates that the pivot point might lie in the right half of the array. In such cases, decrement the high index by one and continue with the binary search. This ensures that we explore both halves of the array even if there are duplicates.

Java Code is available on GitHub here.

9. Search in a 2D matrix — I

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

The leetcode question for this is available here.

Optimal Approach:

Treat the matrix as a flattened sorted array and perform binary search directly on it. Think of the 2D matrix as a 1D array with m * n elements. Initialize left as 0 and right as m * n-1, and then perform binary search as usual.

Java Code is available on GitHub here.

10. Search in a 2D matrix — II

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

The leetcode question for this is available here.

Optimal Approach:

As the integers in the matrix are sorted from left to right as well as top to bottom, perform a binary search considering both, rows as well as columns. If the target is less than the current element, move leftwards in the same row. If the target is greater than the current element, move downwards in the same column.

Java Code is available on GitHub here.

12. H-Index II

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in ascending order, return the researcher's h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

You must write an algorithm that runs in logarithmic time.

Example 1:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

Input: citations = [1,2,100]
Output: 2

The leetcode question for this is available here.

Optimal Approach:

To find the H-index, you have to find out the maximum value, say m, such that there are at least m number of papers which have more than or equal to m citations(m will be the h-index). To do this, you can use binary search to check whether the element at mid index is satisfying the required condition. The number of papers having citations more than m will be all the papers to the right of mid, including mid(as array is sorted in ascending order). If element at mid is less than the papers, search in the right half, else search in the left half of the array. If exact match is not found, all elements to the right of mid will be the h-index.

Java Code is available on GitHub here.

Below is the playlist containing most of the above questions, so if you need a detailed dry-run, go ahead and tune into this.

That’s all for this article.

Thanks for reading.

If you liked this article, please click the “clap” button 👏 a few times.

It gives me enough motivation to put out more content like this. Please share it with a friend who you think this article might help.

Follow my Youtube channel — Code With Ease — By Varsha, where we discuss Java & Data Structures & Algorithms and so much more.

Subscribe here to receive alerts whenever I publish an article.

Happy learning and growing together.

DAY 2/10: This could be your Pre-Interview Checklist for DSA -Binary Search on LeetCode

Binary search interview questions guide in Java

How to identify binary search problems?

Questions List:

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

2. Sqrt(x)

3. First Bad Version

4. Peak Index in a Mountain Array

5. Search in Rotated Sorted Array

6. Search in Rotated Sorted Array II

7. Find Minimum in Rotated Sorted Array

8. Find Minimum in Rotated Sorted Array II

9. Search in a 2D matrix — I

10. Search in a 2D matrix — II

12. H-Index II

Written by Varsha Das