Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem Challenge 3: Rotation Count (medium)

Problem Statement

Given an array of numbers which is sorted in ascending order and is rotated ‘k’ times around a pivot, find ‘k’.

You can assume that the array does not have any duplicates.

Note: You need to solve the problem in O(logn) time complexity.

Example 1:

Input: [10, 15, 1, 3, 8]
Output: 2
Explanation: The array has been rotated 2 times.

Example 2:

Input: [4, 5, 7, 9, 10, -1, 2]
Output: 5
Explanation: The array has been rotated 5 times.

Example 3:

Input: [1, 3, 8, 10]
Output: 0
Explanation: The array has not been rotated.

Constraints:

.....

.....

.....

Like the course? Get enrolled and start learning!
P

Pete Stenger

· 2 years ago

    lo = 0
    hi = len(arr) - 1
    while lo <= hi:
      mid = (lo + hi) // 2
      if mid > 0 and arr[mid-1] > arr[mid]:
        return mid

      if arr[0] < arr[mid]:
        lo = mid + 1
      else:
        hi = mid - 1
    
    return len(arr) - 1 - mid
P

Pete Stenger

· 4 years ago

I always find my solutions look quite different in terms of internal comparisons than the solution... is that OK?

def solve(arr): start, end = 0, len(arr) - 1 if arr[start] < arr[end]: return 0 while start

M

Michael Shum

· 3 years ago

For the similar problem, we never checked the 'end' value for the original solution. so why should we check for that in the similar problem?

Show 4 replies
H

henrisilver

· 3 years ago

The problem states that we can assume the array has no duplicates. However, one of the test cases is [10, 20, 30, 10, 20]. Elements 10 and 20 are duplicates... Was it a mistake to have those test cases in there?

V

varun.vjr

· 2 years ago

The stated algorithm provides 3 as the rotation count instead of 5.

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def countRotations(self, arr):
    length = len(arr) - 1
    b, e = 0, length
    m = (b + e) // 2 
    
    # edge case: if the array is fully reversed like [5, 4, 3, 2, 1]
    if arr[b] > arr[m] > arr[e]:
      return length     

    while b <= e:
      m = (b + e) // 2    

      # check and discard the first half 
      if arr[b] <= arr[m]:
        # before [b = m + 1] check if we have found the index 
        if m < length and arr[m] > arr[m + 1]:
          return m + 1
        # nothing found just discard 
        b = m + 1
      
      # check and discard the the second half  
      elif arr[m] <= arr[e]:
        # before [e = m - 1] check if we have found the index 
        if m - 1 >= 0 and arr[m - 1] > arr[m]:
          return m
        # nothing