Coding

Find out how many times the array is rotated

Asked at

M2P Fintech

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array nums of size n, sorted in ascending order with distinct values. The array has been right rotated an unknown number of times, between 0 and n-1 (including). Determine the number of rotations performed on the array.

Input : nums = [4, 5, 6, 7, 0, 1, 2, 3] Output: 4 Explanation: The original array should be [0, 1, 2, 3, 4, 5, 6, 7]. So, we can notice that the array has been rotated 4 times.

Input: nums = [3, 4, 5, 1, 2] Output: 3 Explanation: The original array should be [1, 2, 3, 4, 5]. So, we can notice that the array has been rotated 3 times.

Input: nums = [4, 5, 1, 2]

n == nums.length
1 <= n <= 104
-104 <= nums[i] <= 104
All the integers of nums are unique.

cpp

class Solution {
public:
    int findKRotation(vector<int> &nums)  {
        
    }
};

java

class Solution {
    public int findKRotation(ArrayList<Integer> nums) {
    
    }
}

python

class Solution:
    def findKRotation(self, nums):

javascript

class Solution {
    findKRotation(nums) {
      
    }
}

csharp

public class Solution
{
    public int findKRotation(int[] nums)
    {
        // Your code goes here
    }
}

func findKRotation(nums []int) int {
	//your code goes here
}

Stuck? Show a way to structure it+

01Recognize that right rotations equal the minimum index.
02Binary-search for the minimum.
03Return zero for an already sorted interval.
04Use middle versus high to discard the sorted half.
05Return the converged index.

Reference answer

A right-rotated strictly increasing array has its smallest original element at exactly the number of rotations, so reduce the task to finding the minimum index. Maintain low and high. If nums[low] is less than nums[high], the interval is sorted and low is the answer, including the unrotated case. Otherwise inspect mid: if nums[mid] is greater than nums[high], the pivot lies right of mid, so set low to mid plus one; otherwise mid may itself be the pivot, so set high to mid. When pointers meet, return that index. Explain why a pivot cannot be discarded in the second branch: it is smaller than the right endpoint. With distinct values this runs in O(log n) time and O(1) extra space. A linear scan is a valid baseline only, and misses the sorted-array property.

Then expect these follow-ups

How would duplicates affect the search?
Tests: follow-up reasoning
How can you search for a target once you know this pivot?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question