Search in a Rotated Sorted Array
Updated
Problem statement
An array of distinct integers was sorted in increasing order and then rotated: some number of elements were moved, keeping their order, from the front of the array to the back. For example, [2, 5, 8, 11, 14] rotated by 2 becomes [8, 11, 14, 2, 5]. The rotation may be 0, so the array may still be fully sorted.
You are given the rotated array nums and an integer target. Return the index of target in nums, or -1 if target is not in nums.
Try to use O(log n) time, where n is the length of nums.
Function
searchRotated(nums: int[], target: int) → intExamples
Example 1
nums = [15,18,22,3,7,9,12]target = 7return = 4This is the sorted array [3, 7, 9, 12, 15, 18, 22] rotated so that 15 comes first. The value 7 sits at index 4, so the answer is 4.
Example 2
nums = [8,11,2,5]target = 10return = -1In sorted order 10 would sit between 8 and 11, but it is not in the array, so the answer is -1.
Example 3
nums = [1,4,9,13]target = 13return = 3This array was rotated by 0, so it is still fully sorted. 13 is the last value, at index 3.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4-10^4 <= target <= 10^4- All values in
numsare distinct. numsis an increasing array rotated by some amount from 0 tonums.length - 1.
More Nutanix Phone Screen questions
- Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
- Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
- Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
- Find the Duplicate in a Read-Only ArrayPHONE SCREEN · Seen Apr 2021
- Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
- Kth Smallest Element in a BSTPHONE SCREEN · Seen Feb 2020
- Outline of a Binary TreePHONE SCREEN · Seen Jan 2020
- Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
- Inorder Predecessor in a BSTPHONE SCREEN · Seen Jan 2019
- K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019
Similar questions at other companies
- Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
- Koko Eating BananasThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Find First and Last Position in a Sorted ArrayInstacart · PHONE SCREENInstacart interview questions
- Random Pick with Weight Using Recorded DrawsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Longest Increasing SubsequenceAngel One · PHONE SCREEN
- Aggressive CowsAmazon · PHONE SCREEN
- Find First and Last Position of Element in Sorted ArrayEPAM · PHONE SCREENEPAM interview questions
- Find K Closest Elements in a Sorted ArrayNavi · PHONE SCREEN
- Search in Rotated Sorted ArrayZoomInfo · PHONE SCREEN
- Find a Peak ElementFox Corporation · PHONE SCREEN