Find Kth Rotation | GeeksforGeeks Solution Explained | Binary Search

The “Find Kth Rotation” problem is a classic array question often asked in coding interviews. In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations

Given an increasing sorted rotated array arr of distinct integers. The array is right-rotated k times. Find the value of k.
Let’s suppose we have an array arr = [2, 4, 6, 9], so if we rotate it by 2 times so that it will look like this:
After 1st Rotation : [9, 2, 4, 6]
After 2nd Rotation : [6, 9, 2, 4]

Here’s the [Problem Link] to begin with.

Examples:

Input: arr = [5, 1, 2, 3, 4]
Output: 1
Explanation: The given array is 5 1 2 3 4. The original sorted array is 1 2 3 4 5. We can see that the array was rotated 1 times to the right.

Input: arr = [1, 2, 3, 4, 5]
Output: 0
Explanation: The given array is not rotated.

Constraints:
1 ≤ arr.size() ≤10⁵
1 ≤ arr_i ≤ 10⁷

Brute Force Solution (Linear Scan)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Scan for the Point of Drop:
   Go through the array from start to end. The rotation point is where a number is greater than the next number.
2. Return the Index:
   The index after this drop is the number of rotations.
3. Why does this work?
   In a rotated sorted array, the only place where the order breaks is at the rotation point.

This approach is easy to understand but not efficient for large arrays.

Code Implementation

class Solution:
    def findKRotation(self, arr):
        n = len(arr)
        for i in range(0, n - 1):
            if arr[i] > arr[i + 1]:      # Find the drop point
                return i + 1             # Return index after the drop
        return 0                         # If no drop, no rotation

Code Explanation

• We loop through each element in the array.
• If we find an element greater than the next one, we return the next index.
• If we reach the end without finding such a point, the array is not rotated.

Dry Run

Input:
arr = [1]

• 5 < 6 → continue
• 6 > 1 → found drop at index 1, return 2

Final Output:
2

Time and Space Complexity

• Time Complexity: O(n)
  We may have to check every element.
• Space Complexity: O(1)
  Only a variable for looping.

Conclusion

The brute force approach is simple and works for small arrays, but it’s too slow for large inputs.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search:
   Use two pointers (low and high) to perform binary search.
2. Find the Minimum:
   • If the leftmost value is less than or equal to the rightmost, the subarray is already sorted; the smallest is at low.
   • Otherwise, check if the left half or the right half is sorted and move accordingly.
3. Track the Index:
   Keep track of the index where the minimum value is found.
4. Why does this work?
   The minimum element is the point of rotation. Binary search helps us find this quickly.

Code Implementation

class Solution:
    def findKRotation(self, nums) -> int:
        n = len(nums)
        low = 0
        high = n - 1
        minimum = float("inf")
        index = -1
        while low <= high:
            mid = (low + high) // 2
            if nums[low] <= nums[high]:
                if nums[low] < minimum:
                    minimum = nums[low]
                    index = low
                break
            if nums[low] <= nums[mid]:
                if nums[low] < minimum:
                    minimum = nums[low]
                    index = low
                low = mid + 1
            else:
                if nums[mid] < minimum:
                    minimum = nums[mid]
                    index = mid
                high = mid - 1
        return index

Code Explanation

• We use binary search with pointers low and high.
• If the subarray is already sorted, the smallest is at low.
• If the left half is sorted, move to the right half.
• If the right half is sorted, move to the left half.
• We keep updating the minimum and its index as we search.

Dry Run

Input:
arr = [1]

• low = 0, high = 5
• mid = 2 (nums=1)
• nums=5 > nums=1, so right half is sorted, update minimum and index to 1 at index 2, high = 1
• low = 0, high = 1
• mid = 0 (nums=5)
• nums=5 <= nums=6, so left half is sorted, but minimum already found, break

Final Output:
2

Time and Space Complexity

• Time Complexity: O(log n)
  Binary search divides the array each time.
• Space Complexity: O(1)
  Only a few pointers and variables.

Conclusion

The optimal solution is efficient and works well for large arrays. It’s the best approach for interviews and practical use.

Final Thoughts

The “Find Kth Rotation” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.