Search in Rotated Sorted Array

🎯

Search in Rotated Sorted Array

mediumBINARY_SEARCHAmazonFacebookGoogle

Imagine you have a sorted list of product IDs that got rotated during a system update, and you need to quickly find if a certain product ID exists in this rotated list.

💡 This problem is a classic example of how binary search can be adapted to work on arrays that are not fully sorted but have a special structure. Beginners often struggle because the array is rotated, so the usual binary search assumptions don't hold directly.

📋

Problem Statement

Given an integer array nums sorted in ascending order, rotated at an unknown pivot, 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.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4All values of nums are unique.nums is guaranteed to be rotated at some pivot.-10^4 ≤ target ≤ 10^4

💡

Example

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

Output4

The target 0 is at index 4 in the rotated array.

Input"nums = [4,5,6,7,0,1,2], target = 3"

Output-1

The target 3 is not present in the array.

Input"nums = [1], target = 0"

Output-1

Single element array where target is not found.

• Array of length 1 → target present or absent
• Array not rotated (pivot at 0) → normal binary search
• Target is the pivot element → correct index returned
• Target is at the boundaries (start or end) → correct index returned

⚠️

Common Mistakes

Not checking which half is sorted correctly

Algorithm may search wrong half and fail to find target

✅ Always compare nums[low] and nums[mid] to identify sorted half correctly

Using mid = (low + high) / 2 without floor or integer division

In some languages, this causes float indices or overflow

✅ Use integer division or mid = low + (high - low) // 2 to avoid overflow

Not handling single element or empty array edge cases

Code may crash or return incorrect result

✅ Add checks for empty array and handle single element arrays explicitly

Confusing comparison operators when checking target range

May exclude target from search range incorrectly

✅ Use inclusive and exclusive comparisons carefully, e.g. nums[low] <= target < nums[mid]

Trying to find pivot and search in one pass without clear logic

Code becomes complex and buggy

✅ Separate pivot finding and binary search steps clearly or use approach 2

🧠

Brute Force (Linear Search)

💡 This approach exists to establish a baseline and ensure understanding of the problem before optimizing. It is simple but inefficient for large inputs.

Intuition

Check each element one by one until the target is found or the array ends.

Algorithm

1. Start from the first element of the array.
2. Compare the current element with the target.
3. If they match, return the current index.
4. If the end of the array is reached without a match, return -1.

💡 This algorithm is straightforward but inefficient because it does not leverage the sorted or rotated property of the array.

</>

Code

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

# Driver code
if __name__ == '__main__':
    print(search([4,5,6,7,0,1,2], 0))  # Output: 4
    print(search([4,5,6,7,0,1,2], 3))  # Output: -1

Line Notes

for i in range(len(nums))Iterate over every element to check for target presence

if nums[i] == targetCheck if current element matches the target

return iReturn index immediately upon finding target

return -1Return -1 if target not found after full traversal

public class Solution {
    public static int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 0)); // 4
        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 3)); // -1
    }
}

Line Notes

for (int i = 0; i < nums.length; i++)Loop through each element to find target

if (nums[i] == target)Check if current element equals target

return iReturn index immediately when target found

return -1Return -1 if target not found after full loop

#include <iostream>
#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    vector<int> nums1 = {4,5,6,7,0,1,2};
    cout << search(nums1, 0) << endl; // 4
    cout << search(nums1, 3) << endl; // -1
    return 0;
}

Line Notes

for (int i = 0; i < nums.size(); i++)Traverse each element to find target

if (nums[i] == target)Check if current element matches target

return iReturn index immediately upon match

return -1Return -1 if target not found after full traversal

function search(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            return i;
        }
    }
    return -1;
}

// Test cases
console.log(search([4,5,6,7,0,1,2], 0)); // 4
console.log(search([4,5,6,7,0,1,2], 3)); // -1

Line Notes

for (let i = 0; i < nums.length; i++)Iterate over all elements to find target

if (nums[i] === target)Check if current element equals target

return iReturn index immediately when target found

return -1Return -1 if target not found after full iteration

⏱

Complexity

TimeO(n)

SpaceO(1)

We potentially check every element once, so time is linear in array size. Space is constant as no extra storage is used.

💡 For n=100, this means up to 100 comparisons, which is inefficient compared to binary search's ~7 comparisons.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large arrays, so it is mainly useful to understand the problem before optimizing.

🧠

Modified Binary Search (Identify Sorted Half)

💡 This approach leverages the rotated sorted property by identifying which half of the array is sorted and narrowing the search accordingly.

Intuition

At each step, one half of the array is sorted. We check if the target lies in the sorted half; if yes, we search there, else in the other half.

Algorithm

1. Initialize low and high pointers at array ends.
2. While low ≤ high, find mid index.
3. If nums[mid] == target, return mid.
4. Check if left half nums[low..mid] is sorted.
5. If left half sorted and target in this range, move high to mid-1.
6. Else move low to mid+1.
7. If left half not sorted, right half must be sorted.
8. If target in right half range, move low to mid+1, else high to mid-1.
9. If not found, return -1.

💡 The key difficulty is correctly identifying the sorted half and deciding where to search next, which is the core insight of this problem.

</>

Code

def search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[low] <= nums[mid]:  # Left half sorted
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:  # Right half sorted
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1

# Driver code
if __name__ == '__main__':
    print(search([4,5,6,7,0,1,2], 0))  # Output: 4
    print(search([4,5,6,7,0,1,2], 3))  # Output: -1

Line Notes

low, high = 0, len(nums) - 1Initialize search boundaries

while low <= highLoop until search space is exhausted

mid = (low + high) // 2Find middle index to check

if nums[mid] == targetCheck if mid element is target

if nums[low] <= nums[mid]Check if left half is sorted

if nums[low] <= target < nums[mid]Check if target lies in sorted left half

high = mid - 1Narrow search to left half

else: low = mid + 1Search right half if target not in left half

else: # Right half sortedIf left half not sorted, right half must be sorted

if nums[mid] < target <= nums[high]Check if target lies in sorted right half

low = mid + 1Narrow search to right half

else: high = mid - 1Search left half otherwise

return -1Return -1 if target not found

public class Solution {
    public static int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) return mid;
            if (nums[low] <= nums[mid]) { // Left half sorted
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else { // Right half sorted
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 0)); // 4
        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 3)); // -1
    }
}

Line Notes

int low = 0, high = nums.length - 1Initialize search boundaries

while (low <= high)Loop until search space is empty

int mid = low + (high - low) / 2Calculate mid index safely

if (nums[mid] == target)Check if mid element is target

if (nums[low] <= nums[mid])Check if left half is sorted

if (nums[low] <= target && target < nums[mid])Check if target in left half

high = mid - 1Search left half

else { low = mid + 1; }Search right half otherwise

else { // Right half sortedIf left half not sorted, right half must be

if (nums[mid] < target && target <= nums[high])Check if target in right half

low = mid + 1Search right half

else { high = mid - 1; }Search left half otherwise

return -1Return -1 if target not found

#include <iostream>
#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    int low = 0, high = nums.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return mid;
        if (nums[low] <= nums[mid]) { // Left half sorted
            if (nums[low] <= target && target < nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else { // Right half sorted
            if (nums[mid] < target && target <= nums[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    vector<int> nums = {4,5,6,7,0,1,2};
    cout << search(nums, 0) << endl; // 4
    cout << search(nums, 3) << endl; // -1
    return 0;
}

Line Notes

int low = 0, high = nums.size() - 1Initialize search boundaries

while (low <= high)Loop until search space is empty

int mid = low + (high - low) / 2Calculate mid index safely to avoid overflow

if (nums[mid] == target) return midReturn index if mid element is target

if (nums[low] <= nums[mid])Check if left half is sorted

if (nums[low] <= target && target < nums[mid])Check if target lies in left half

high = mid - 1Search left half

else low = mid + 1Search right half otherwise

else { // Right half sortedIf left half not sorted, right half must be

if (nums[mid] < target && target <= nums[high])Check if target lies in right half

low = mid + 1Search right half

else high = mid - 1Search left half otherwise

return -1Return -1 if target not found

function search(nums, target) {
    let low = 0, high = nums.length - 1;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (nums[mid] === target) return mid;
        if (nums[low] <= nums[mid]) { // Left half sorted
            if (nums[low] <= target && target < nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else { // Right half sorted
            if (nums[mid] < target && target <= nums[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

// Test cases
console.log(search([4,5,6,7,0,1,2], 0)); // 4
console.log(search([4,5,6,7,0,1,2], 3)); // -1

Line Notes

let low = 0, high = nums.length - 1Initialize search boundaries

while (low <= high)Loop until search space is empty

let mid = Math.floor((low + high) / 2)Calculate mid index

if (nums[mid] === target) return midReturn index if mid element is target

if (nums[low] <= nums[mid])Check if left half is sorted

if (nums[low] <= target && target < nums[mid])Check if target lies in left half

high = mid - 1Search left half

else low = mid + 1Search right half otherwise

else { // Right half sortedIf left half not sorted, right half must be

if (nums[mid] < target && target <= nums[high])Check if target lies in right half

low = mid + 1Search right half

else high = mid - 1Search left half otherwise

return -1Return -1 if target not found

⏱

Complexity

TimeO(log n)

SpaceO(1)

Each iteration halves the search space by identifying the sorted half, leading to logarithmic time. Space is constant as no extra data structures are used.

💡 For n=1000, this means about 10 comparisons, which is much faster than linear search.

Interview Verdict: Accepted and optimal for this problem

This approach is the standard solution expected in interviews due to its efficiency and clever use of the rotated array property.

🧠

Binary Search with Pivot Finding + Normal Binary Search

💡 This approach first finds the rotation pivot (smallest element) and then performs a normal binary search in the appropriate subarray. It separates concerns but requires two binary searches.

Intuition

Find the index where the rotation happened (pivot), then decide which sorted subarray to search for the target using normal binary search.

Algorithm

1. Use binary search to find the pivot index where the smallest element is located.
2. Determine which subarray (left or right of pivot) the target belongs to.
3. Perform a standard binary search in that subarray.
4. Return the index if found, else -1.

💡 This approach breaks the problem into two simpler binary searches, making it easier to reason about but slightly more complex to implement.

</>

Code

def find_pivot(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if nums[mid] > nums[high]:
            low = mid + 1
        else:
            high = mid
    return low

def binary_search(nums, low, high, target):
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def search(nums, target):
    if not nums:
        return -1
    pivot = find_pivot(nums)
    if nums[pivot] <= target <= nums[-1]:
        return binary_search(nums, pivot, len(nums) - 1, target)
    else:
        return binary_search(nums, 0, pivot - 1, target)

# Driver code
if __name__ == '__main__':
    print(search([4,5,6,7,0,1,2], 0))  # Output: 4
    print(search([4,5,6,7,0,1,2], 3))  # Output: -1

Line Notes

while low < highLoop to find pivot by narrowing search space

if nums[mid] > nums[high]Pivot must be in right half if mid element greater than high

else: high = midPivot in left half or at mid

return lowPivot index found where smallest element is

while low <= highStandard binary search loop

if nums[mid] == targetReturn index if target found

elif nums[mid] < targetSearch right half if target greater

else: high = mid - 1Search left half otherwise

if nums[pivot] <= target <= nums[-1]Decide which subarray to search based on target range

return binary_search(...)Perform binary search in chosen subarray

public class Solution {
    public static int findPivot(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static int binarySearch(int[] nums, int low, int high, int target) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

    public static int search(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int pivot = findPivot(nums);
        if (target >= nums[pivot] && target <= nums[nums.length - 1]) {
            return binarySearch(nums, pivot, nums.length - 1, target);
        } else {
            return binarySearch(nums, 0, pivot - 1, target);
        }
    }

    public static void main(String[] args) {
        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 0)); // 4
        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 3)); // -1
    }
}

Line Notes

while (low < high)Loop to find pivot by narrowing search space

if (nums[mid] > nums[high])Pivot in right half if mid > high

else high = midPivot in left half or at mid

return lowPivot index found

while (low <= high)Standard binary search loop

if (nums[mid] == target) return midReturn index if target found

else if (nums[mid] < target) low = mid + 1Search right half if target greater

else high = mid - 1Search left half otherwise

if (target >= nums[pivot] && target <= nums[nums.length - 1])Choose subarray based on target range

return binarySearch(...)Perform binary search in chosen subarray

#include <iostream>
#include <vector>
using namespace std;

int findPivot(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int binarySearch(vector<int>& nums, int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int search(vector<int>& nums, int target) {
    if (nums.empty()) return -1;
    int pivot = findPivot(nums);
    if (target >= nums[pivot] && target <= nums.back()) {
        return binarySearch(nums, pivot, nums.size() - 1, target);
    } else {
        return binarySearch(nums, 0, pivot - 1, target);
    }
}

int main() {
    vector<int> nums = {4,5,6,7,0,1,2};
    cout << search(nums, 0) << endl; // 4
    cout << search(nums, 3) << endl; // -1
    return 0;
}

Line Notes

while (low < high)Loop to find pivot by narrowing search space

if (nums[mid] > nums[high])Pivot in right half if mid > high

else high = midPivot in left half or at mid

return lowPivot index found

while (low <= high)Standard binary search loop

if (nums[mid] == target) return midReturn index if target found

else if (nums[mid] < target) low = mid + 1Search right half if target greater

else high = mid - 1Search left half otherwise

if (target >= nums[pivot] && target <= nums.back())Choose subarray based on target range

return binarySearch(...)Perform binary search in chosen subarray

function findPivot(nums) {
    let low = 0, high = nums.length - 1;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

function binarySearch(nums, low, high, target) {
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (nums[mid] === target) return mid;
        else if (nums[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

function search(nums, target) {
    if (nums.length === 0) return -1;
    const pivot = findPivot(nums);
    if (target >= nums[pivot] && target <= nums[nums.length - 1]) {
        return binarySearch(nums, pivot, nums.length - 1, target);
    } else {
        return binarySearch(nums, 0, pivot - 1, target);
    }
}

// Test cases
console.log(search([4,5,6,7,0,1,2], 0)); // 4
console.log(search([4,5,6,7,0,1,2], 3)); // -1

Line Notes

while (low < high)Loop to find pivot by narrowing search space

if (nums[mid] > nums[high])Pivot in right half if mid > high

else high = midPivot in left half or at mid

return lowPivot index found

while (low <= high)Standard binary search loop

if (nums[mid] === target) return midReturn index if target found

else if (nums[mid] < target) low = mid + 1Search right half if target greater

else high = mid - 1Search left half otherwise

if (target >= nums[pivot] && target <= nums[nums.length - 1])Choose subarray based on target range

return binarySearch(...)Perform binary search in chosen subarray

⏱

Complexity

TimeO(log n)

SpaceO(1)

Two binary searches are performed sequentially, each O(log n), so overall time is O(log n). Space is constant.

💡 This approach is slightly more complex but still very efficient, with about twice the number of comparisons as the previous approach.

Interview Verdict: Accepted and efficient, but more complex than approach 2

This approach is useful to understand the problem structure deeply, but approach 2 is usually preferred for interviews due to simplicity.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 is the best balance of simplicity and efficiency and is recommended for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention only - never code
2. Modified Binary Search (Identify Sorted Half)	O(log n)	O(1)	No	N/A	Code this approach in interviews
3. Pivot Finding + Normal Binary Search	O(log n)	O(1)	No	N/A	Good to understand, but more complex to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Introduce the modified binary search approach and explain the intuition.Step 4: Code the modified binary search carefully, explaining each step.Step 5: Test your code with edge cases and discuss time and space complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of binary search adaptations, handling edge cases, and writing clean, efficient code.

Common Follow-ups

• How to handle duplicates in the rotated array? → Use a modified approach that handles equal elements carefully.
• Can you find the minimum element in the rotated array? → Use a similar pivot finding binary search.

💡 These follow-ups test your ability to adapt the solution to variations and deepen your understanding of rotated arrays.

🔍

Pattern Recognition

When to Use

1) Array is sorted but rotated; 2) Need to search efficiently; 3) Target may be anywhere; 4) O(log n) time required.

Signature Phrases

'rotated sorted array''search in O(log n) time''find target in rotated array'

NOT This Pattern When

Standard binary search on fully sorted arrays without rotation

Similar Problems

Find Minimum in Rotated Sorted Array - finding pivot indexSearch in Rotated Sorted Array II - handling duplicatesFind Peak Element - binary search on modified conditions

Practice

1. Consider the following code snippet implementing the binary search on value range approach to find the median of two sorted arrays. Given nums1 = [1, 3] and nums2 = [2, 4], what is the final returned median?

easy

A. 2.0

B. 2.5

C. 3.0

D. 2.25

Solution

1. Step 1: Trace binary search iterations

   Initial left=1, right=4. Mid=2, countLessEqual(2)=3 ≥ 2.5 so right=2. Next mid=1, countLessEqual(1)=1 < 2.5 so left=2.

2. Step 2: Compute median for even total length

   Left=2, total length=4 (even). Candidates before 2 are nums1[0]=1 and nums2[0]=2, max=2. Median=(2+3)/2=2.5 is correct median of combined sorted array [1,2,3,4]. The code snippet's logic is incomplete but assuming correct logic, median is 2.5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Median of combined sorted array [1,2,3,4] is 2.5 [OK]

Hint: Median of [1,2,3,4] is average of 2 and 3 [OK]

Common Mistakes:

• Off-by-one in bisect boundaries
• Confusing left with median
• Ignoring even length median averaging

2. You are given an array representing the days on which flowers bloom. You want to make m bouquets, each consisting of k adjacent flowers. What is the most efficient approach to find the minimum day by which you can make all bouquets?

easy

A. Apply binary search on the range of days and check feasibility for each mid value.

B. Use a greedy approach to pick the earliest blooming flowers until bouquets are formed.

C. Use dynamic programming to track the minimum days for each bouquet count.

D. Sort the bloom days and pick the first m*k flowers directly.

Solution

1. Step 1: Understand the problem constraints

   We need to find the minimum day such that we can form m bouquets of k adjacent flowers. The days range from min to max bloom day.

2. Step 2: Recognize the pattern

   Binary searching over the answer space (days) and checking feasibility for each candidate day efficiently narrows down the minimum day. Greedy or sorting alone do not guarantee correctness because adjacency and feasibility must be checked.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on answer space is the standard pattern for such minimum day feasibility problems. [OK]

Hint: Binary search on answer space fits minimum day feasibility problems [OK]

Common Mistakes:

• Thinking greedy or sorting alone solves adjacency constraints
• Using DP unnecessarily complicates the problem

3. What is the time complexity of the optimal binary search solution for finding the smallest divisor given an array of size n and maximum element max_num?

medium

A. O(n + log max_num)

B. O(n * max_num)

C. O(log n * max_num)

D. O(n log max_num)

Solution

1. Step 1: Identify the binary search iterations

   Binary search runs over the range [1, max_num], so it takes O(log max_num) steps.

2. Step 2: Analyze the feasibility check cost

   Each feasibility check sums over all n elements, costing O(n).

3. Step 3: Combine complexities

   Total time is O(n * log max_num), since feasibility is done each binary search iteration.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Binary search log factor times linear feasibility -> [OK]

Hint: Binary search log factor times linear feasibility check [OK]

Common Mistakes:

• Confusing max_num with n in complexity
• Forgetting feasibility check cost per iteration
• Assuming linear search complexity applies

4. The following code attempts to find the kth smallest element in a sorted matrix using a min-heap. Identify the line containing the subtle bug that can cause incorrect results when duplicates exist or when counting is off.

medium

A. Line where count is incremented after the kth check (count += 1)

B. Line where initial elements are pushed into the heap (heapq.heappush in for loop)

C. Line where the kth element is checked (if count == k: return val)

D. Line where next element in the row is pushed (heapq.heappush inside while loop)

Solution

1. Step 1: Understand counting logic

   Count should increment before checking if count == k to correctly identify the kth popped element.

2. Step 2: Identify off-by-one bug

   Currently, count is incremented after the check, so the function returns the (k-1)th element instead of kth.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Increment count before kth check fixes off-by-one error [OK]

Hint: Check order of count increment and kth check [OK]

Common Mistakes:

• Off-by-one in counting popped elements
• Returning before incrementing count
• Misplaced heap push causing missing elements

5. What is the time complexity of the optimized binary search solution for finding the k-th smallest number in an m x n multiplication table, where the counting function breaks early once count ≥ k?

medium

A. O(m * log(m * n))

B. O(m log(m * n))

C. O(log(m * n))

D. O(m * n log(m * n))

Solution

1. Step 1: Identify outer binary search iterations

   The binary search runs over the value range [1, m*n], so about O(log(m*n)) iterations.

2. Step 2: Analyze counting function complexity

   Counting iterates over m rows, each capped by min(n, x//i), but early break reduces average work. Worst case is O(m) per count.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(m * log(m * n)) [OK]

Hint: Counting is O(m), binary search O(log(m*n)) [OK]

Common Mistakes:

• Confusing n with m in complexity
• Assuming counting is O(m*n)