The “Find Kth Rotation” problem is a classic array question often asked in coding interviews. In this blog, we\u2019ll 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<\/p>\n\n\n\n
Given an increasing sorted rotated array arr <\/strong>of distinct integers. The array is right-rotated k<\/strong> times. Find the value of k<\/strong>. Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Examples:<\/strong><\/p>\n\n\n\n Constraints:<\/strong> Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large arrays.<\/p>\n\n\n\n
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]<\/p>\n\n\n\nInput: <\/strong>arr = [5, 1, 2, 3, 4]\nOutput:<\/strong> 1\nExplanation:<\/strong> 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.<\/pre>\n\n\n\n
Input: <\/strong>arr = [1, 2, 3, 4, 5]\nOutput:<\/strong> 0\nExplanation:<\/strong> The given array is not rotated.<\/pre>\n\n\n\n
1 \u2264 arr.size() \u2264105<\/sup>
1 \u2264 arri<\/sub> \u2264 107<\/sup><\/p>\n\n\n
\n\n\n\nBrute Force Solution (Linear Scan)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Go through the array from start to end. The rotation point is where a number is greater than the next number.<\/li>\n\n\n\n
The index after this drop is the number of rotations.<\/li>\n\n\n\n
In a rotated sorted array, the only place where the order breaks is at the rotation point.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n