Practice DSA interview questions

A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors (up, down, left, right). Given an `m x n` matrix, find and return the coordinates of *any* peak element. The problem guarantees that a peak exists. This can be solved in O(n log m) or O(m log n) time by using Binary Search on the rows or columns, and then finding the max in that middle row/column.

You have `n` baskets at positions `position[i]` and `k` balls. You want to place the `k` balls in the baskets such that the *minimum* magnetic force between any two balls is *maximized*. The force between two balls at `x` and `y` is `|x - y|`. This is a classic 'Binary Search on the Answer' problem, identical in structure to 'Aggressive Cows'. We binary search for the minimum distance.

You are given `n`, `index`, and `maxSum`. You must construct an array `nums` of `n` positive integers such that `nums[index] == value`, `abs(nums[i] - nums[i+1]) <= 1`, and the `sum(nums)` does not exceed `maxSum`. Find the *maximum* possible `value` for `nums[index]`. This is a hard 'Binary Search on the Answer' problem. We binary search for the 'value' and check if a valid array can be constructed.

You are given a sorted `stations` array and an integer `k`. You can add `k` new gas stations anywhere on the line. What is the *smallest possible maximum distance* between any two adjacent gas stations? This is a 'Binary Search on the Answer' problem. The answer is a floating-point number (the distance), so the Binary Search is on a continuous range.

Given an array `arr` of positive integers sorted in a strictly increasing order, and an integer `k`, return the `k`th positive integer that is *missing* from this array. For example, `arr = [2,3,4,7,11]`, `k = 5`. The missing numbers are `[1, 5, 6, 8, 9, 10, 12, ...]`. The 5th missing number is 9. This can be solved in O(log n) time by binary searching on the *number of missing elements* at each index.

Given an infinite sorted binary array (all 0s followed by all 1s), find the index of the *first* occurrence of 1. You do not know the size of the array. This problem combines 'Find Position in Infinite Array' with 'Find First and Last Position'. We must first find the bounds where the '1' could be, and then perform a 'lower bound' binary search.

Given an `m x n` matrix `grid` which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in `grid`. This can be solved with a brute-force O(m*n), a per-row binary search O(m log n), or an optimal O(m+n) 'staircase' search. The staircase search is the most common and efficient solution.

Given an integer array `nums` and `k`, the distance of a pair `(i, j)` is `abs(nums[i] - nums[j])`. Return the `k`th smallest pair distance. This is a very hard 'Binary Search on the Answer' problem. The 'answer' (the distance) is in the range `[0, max(nums) - min(nums)]`. We binary search for this distance and create a `check` function that counts how many pairs have a distance less than or equal to `mid`.

Given an integer array `nums`, return the length of the longest strictly increasing subsequence (LIS). The classic DP solution is O(n^2). An O(n log n) solution exists that uses an auxiliary array (often called `tails` or `sub`) and Binary Search. This array stores the smallest tail of all increasing subsequences of a given length. This is a clever application of Binary Search (specifically, 'lower bound').

Given an array `arr` that is a 'mountain' (it strictly increases, then strictly decreases), return the index `i` such that `arr[0] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[n-1]`. This is guaranteed to be a peak. The problem is identical to 'Find Peak Element', requiring an O(log n) solution. We just need to find the single maximum element.

You are a product manager leading a team. You have `n` versions `[1, ..., n]`. One is the first bad version, and all versions after it are bad. You have an API `isBadVersion(version)`. Find the first bad version in minimal API calls. This is a classic Binary Search problem. The search space is not an array, but a range of version numbers from 1 to `n`. The goal is to find the 'lower bound' or the first `true` in a series of `[F, F, F, T, T, T]`.

We are playing a guessing game. The game picks a number from 1 to `n`. You have to guess the number. You have an API `guess(num)` which returns -1 if your guess is lower, 1 if your guess is higher, and 0 if you are correct. You must find the number. This is a simple, direct application of the Binary Search algorithm, where the comparison is hidden behind an API call. It's a common 'warm-up' question.

Given a Bitonic array (an array that first increases and then decreases, like a mountain) and a `target`, find if the `target` exists in the array. This problem is a combination of two Binary Search tasks. First, you must find the 'peak' of the mountain. Second, you perform two separate Binary Searches: one on the increasing (left) half and one on the decreasing (right) half.

(This is a hard version of the previous problem). You are given an API `MountainArray.get(k)` and `MountainArray.length()`. You cannot access the array directly. Find the *minimum index* `k` such that `MountainArray.get(k) == target`. If it does not exist, return -1. This is a hard problem because you must minimize API calls. It combines finding the peak and two binary searches, all through an API.

Given an integer array `bloomDay`, where `bloomDay[i]` is the day the `i`-th flower blooms, and two integers `m` and `k`. You want to make `m` bouquets. To make one bouquet, you need `k` adjacent flowers. Find the minimum number of days to wait. This is a 'Binary Search on the Answer' problem. The answer (number of days) is in a known range. We binary search for the *day* and check if it's possible to make `m` bouquets.

You are given an array `nums` where `nums[i]` is the number of balls in the `i`-th bag. You are also given `maxOperations`. Your operation is to take a bag with `x` balls and divide it into two new bags with `a` and `b` balls (`a + b = x`). You want to minimize the maximum number of balls in any bag. Find this minimum possible maximum. This is another 'Binary Search on the Answer' problem.

Given `m`, `n`, and `k`, find the `k`-th smallest element in the `m x n` multiplication table (where `table[i][j] = (i+1) * (j+1)`). This is a hard 'Binary Search on the Answer' problem, very similar to 'Kth Smallest in Sorted Matrix'. The key is to create an efficient `check` function that counts how many numbers in the table are less than or equal to a given value.

You are given a sorted array `arr` containing 1 and some prime numbers. You are also given `k`. Consider all possible fractions `arr[i] / arr[j]` where `0 <= i < j < n`. Return the `k`-th smallest fraction. This is a very hard 'Binary Search on the Answer' problem. The answer (the fraction's value) is a float in the range `[0, 1]`. We binary search for this value.

You are given two arrays `spells` and `potions`, and an integer `success`. A spell `i` and potion `j` are successful if `spells[i] * potions[j] >= success`. Return an integer array `pairs` where `pairs[i]` is the number of potions that will form a successful pair with the `i`-th spell. This is a classic 'search in a sorted array' problem. To be efficient, we sort the `potions` array.

Given a string `s` and an array of strings `words`, return the number of `words` that are a subsequence of `s`. A subsequence is formed by deleting zero or more characters. A naive solution is O(n*m*k). We can optimize this by pre-processing `s` into a map of `char -> list_of_indices`. Then, for each word, we can use Binary Search ('upper bound') to find the *next* valid index for each character.

Implement a `MyCalendar` class that supports `book(start, end)`. This method should add a new event to the calendar if it does not cause a *double booking*. A double booking occurs if the new event overlaps with any existing event. It should return `true` if the booking is successful. This problem can be solved by maintaining a sorted list of events and using Binary Search to find the correct insertion point and check for overlaps.

You have `n` jobs. You are given `startTime`, `endTime`, and `profit` arrays. Find the maximum profit you can take such that there are no overlapping jobs. This is a hard Dynamic Programming problem. A top-down DP with memoization is `dp(i)` = max profit starting from job `i`. The key is that after doing job `i`, you must find the *next non-overlapping* job. This search can be optimized from O(n) to O(log n) using Binary Search.

You are given `envelopes` where `envelopes[i] = [width, height]`. An envelope can fit into another if both `width` and `height` are greater. Find the maximum number of envelopes you can 'Russian doll'. This is a 2D Longest Increasing Subsequence (LIS) problem. It can be reduced to a 1D LIS problem (solvable in O(n log n) with Binary Search) by sorting cleverly.

You are given an array of `intervals`. For each interval `i`, you need to find the 'right interval' `j`. A 'right interval' is an interval whose `start` is greater than or equal to `i.end`, and this `start` is minimized. Return an array of these indices. If no such interval exists, put -1. This problem combines sorting with Binary Search.

You are given `time`, where `time[i]` is the time taken by the `i`-th bus to complete one trip. You are also given `totalTrips`. Find the *minimum time* required for all buses to complete at least `totalTrips`. This is a 'Binary Search on the Answer' problem. The 'answer' (the minimum time) is in a known range, and we can check if a given time is 'valid'.

You have `n` computers and `m` batteries. `batteries[i]` gives the running time of the `i`-th battery. You can use batteries in parallel. Find the *maximum time* you can run all `n` computers simultaneously. A computer must be connected to one battery. This is a hard 'Binary Search on the Answer' problem. We binary search for the 'time' (the answer).

Given an array `nums` of `n + 1` integers where each is in `[1, n]`, find the one repeated number. This is an alternative to the cycle detection method. We can use 'Binary Search on the Answer'. The 'answer' (the duplicate number) is in the range `[1, n]`. We binary search for this number by *counting* how many array elements are less than or equal to `mid`.

Given a sorted array `nums` and a `target`, return `true` if `target` is a 'majority element', and `false` otherwise. A majority element is an element that appears more than `n / 2` times. This problem can be solved in O(log n) by finding the first and last occurrence of the target.

You are given an `m x n` matrix `mat` where each row is sorted in non-decreasing order. Find the smallest common element that is present in *all* rows. If there is no such element, return -1. This problem can be solved by counting frequencies, but a more efficient approach uses Binary Search.

Given two integer arrays `arr1` and `arr2`, and an integer `d`, return the 'distance value'. The distance value is the number of elements `arr1[i]` such that there is *no* element `arr2[j]` with `|arr1[i] - arr2[j]| <= d`. This problem can be efficiently solved by sorting `arr2` and using Binary Search to check the condition for each element in `arr1`.