Count Rotations of a Sorted Array
Updated
Problem statement
An array of distinct integers was sorted in increasing order. Then it was rotated to the right k times, where 0 <= k < n and n is the length of the array. One right rotation moves the last element to the front. For example, one right rotation turns [1, 2, 3, 4] into [4, 1, 2, 3].
You are given the array after the rotations, nums. Return k, the number of times it was rotated.
Try to solve it in O(log n) time.
Function
countRotations(nums: int[]) → intExamples
Example 1
nums = [21,34,47,3,9,15]return = 3The smallest value, 3, is at index 3. Before any rotation it was at index 0, and each right rotation moves every value one place to the right. So the array was rotated 3 times: [3, 9, 15, 21, 34, 47] becomes [47, 3, 9, 15, 21, 34], then [34, 47, 3, 9, 15, 21], then [21, 34, 47, 3, 9, 15].
Example 2
nums = [-4,0,6,13]return = 0The array is already in increasing order, so it was not rotated. The answer is 0.
Example 3
nums = [50,61,72,85,10]return = 4The smallest value, 10, is the last element, at index 4. The array was rotated 4 times, one less than its length.
Constraints
1 <= nums.length <= 5000-109 <= nums[i] <= 109- All values in
numsare distinct. numsis an increasing array rotated to the rightktimes for some0 <= k < nums.length.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Search a Row- and Column-Sorted MatrixByteDance · ONSITE INTERVIEWByteDance interview questions
- First and Last Target Position in a Mountain ArrayGoogle · ONSITE INTERVIEWGoogle interview questions
- 3Sum SmallerSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Smallest Batch Size Within a Step LimitMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Peak of an Increasing-Then-Decreasing ArraySnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- Online Meeting Scheduler with Fixed RoomsUber · ONSITE INTERVIEWUber interview questions
- Search in a Rotated Sorted ArrayAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Search in Rotated Sorted ArrayKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Find First and Last Position in Sorted ArrayPaytm · ONSITE INTERVIEWPaytm interview questions
- Detect a Silent SensorConfluent · ONSITE INTERVIEWConfluent interview questions
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)