Implement rotated array binary search with duplicates

Q: Implement rotated array binary search with duplicates

This question evaluates algorithm design and analysis skills, focusing on binary-search variants, handling duplicates in rotated non-decreasing arrays, rotation-index reasoning, and rigorous edge-case analysis; domain: Coding & Algorithms, specifically search algorithms and array manipulation.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given an integer array nums that is a non-decreasing array rotated an unknown number of times. Duplicates may exist. Implement a function that returns a pair: (rotation_count, leftmost_index_of_target) where rotation_count is the index of the rotation point and leftmost_index_of_target is the smallest index i such that nums[i] == target or -1 if absent. Definitions and constraints:

Rotation point is the smallest index r such that nums[r] < nums[(r-1+n)%n]. If no such r exists (array already sorted or all equal), rotation_count = 0.
Time: O(log n) expected; discuss and handle worst-case O(n) when duplicates make direction ambiguous.
Space: O(1).
Edge cases: all elements equal; target duplicated across the rotation boundary; n=1; empty array.
Example: nums = [4,5,5,6,6,1,2,3,3], target=3 → rotation_count=5, leftmost_index_of_target=7.
Provide: (a) algorithm idea; (b) correctness argument; (c) complexity; (d) thorough unit tests covering edge cases.

Implement rotated array binary search with duplicates

Overview

Comments (0)