DSA sheet · Binary Search · Lower / upper bound pattern

Find K Rotations (Rotate Array)

In this video the teacher solves Rotate Array: shift every element of an array k steps to the right, with the elements that fall off the end wrapping around to the front. She goes step by step from a slow brute force (TLE) to three better ideas: a "jump to the correct spot" chain, a temporary array with (i + k) % n, and finally the three-reversal trick that needs no extra space. She also explains k % n: rotating n times brings the array back, so only the leftover rotations matter.

Why it matters: every "rotated sorted array" problem (Problems 5 and 6) is built from this operation. And the brute force → better → best journey is exactly what interviewers want to hear you talk through.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: rotate by one, k times
• Part B · Better idea: jump each element to i + k (cyclic placement)
• Part C · Easier O(n): a temporary array with (i + k) % n
• Part D · Optimal: three reversals, O(1) space
• Part E · Bonus: finding k in a rotated sorted array with binary search
• Part F · Revision page

Part 0 · Before starting

What does "rotate right by 1" mean?

Every element moves one index to the right. The last element has nowhere to go, so it wraps around to index 0. Rotating right is the same as rotating clockwise, if you imagine the array bent into a circle.

The modulo operator % (the "wrap around" tool)

a % n is the remainder after dividing a by n. It always lands in 0 … n−1, so it turns "an index that ran past the end" into "the index after wrapping around". With n = 7: 9 % 7 = 2, 7 % 7 = 0, 4 % 7 = 4.

Why k % n? Rotating n times does nothing

The teacher's example: n = 7, k = 9. After 7 rotations every element is back where it started. The 8th rotation gives 7 1 2 3 4 5 6, and the 9th gives 6 7 1 2 3 4 5, which is the same as rotating just 2 times. So we only need k % n = 9 % 7 = 2 rotations. And k can be up to 10⁵ even when n is tiny, so this matters a lot.

Why is this problem in the binary search sheet?

The teacher's note: after k rotations, a sorted array becomes sorted in two parts (left part and right part). That shape is what binary search attacks in "Search in Rotated Sorted Array" and "Minimum in Rotated Sorted Array". This video focuses on doing the rotation. To optimise it, though, she uses array tricks and two pointers (as in the first video of the playlist), not binary search.

Part E shows the binary-search side as a bonus: given an already-rotated sorted array, find k. That uses left, right, mid = left + (right - left) // 2 (the safe form that can't overflow in Java/C++; Python ints never overflow), and the "is mid in the big piece or the small piece?" test.

Part A · Brute force: rotate by one, k times

LeetCode 189 · Rotate Array

1The question in simple words

Given an integer array nums and a non-negative k, rotate the array to the right by k steps. Change nums in place. The function returns nothing; LeetCode reads nums afterwards.

• [1,2,3,4,5,6,7], k = 3 → [5,6,7,1,2,3,4]
• [-1,-100,3,99], k = 2 → [3,99,-1,-100]

2What the constraints tell us

• n from 1 to 10⁵, and k from 0 to 10⁵. k = 0 means "do nothing", and k can be bigger than n (so k % n matters).
• Values span the 32-bit range, but we only move them, never add them → no overflow concerns.
• The TLE check: about 10⁸ simple operations is the limit. An O(n·k) method can reach 10⁵ × 10⁵ = 10¹⁰ → TLE. We'll need roughly O(n).

3Intuition

If we can rotate by one step, we can just repeat that k times. So first solve "rotate by one".

How to rotate by one: why go from the RIGHT end

Each element at index i must move to i + 1. If we go left to right, copying nums[0] into index 1 wipes out the old nums[1] before we've moved it. We'd need an extra "previous value" variable at every step. It works, but it's fiddly.

The teacher goes right to left instead. First save the last element (7) in temp, since it's the one that wraps to the front. Then copy index 5 → 6, 4 → 5, …, 0 → 1. Each copy writes into a cell whose value has already been moved, so nothing is lost. Finally put temp into index 0.

4Building it from the example (one rotation of 1..7)

Wrap this in an outer loop that runs k times. The second round saves 6 and gives 6 7 1 2 3 4 5. The third saves 5 and gives 5 6 7 1 2 3 4.

5Approach steps

1. Repeat k times:
2.   temp = nums[n-1].
3.   For i from n − 2 down to 0: nums[i+1] = nums[i].
4.   nums[0] = temp.

6Code (Python)

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        for _ in range(k):                  # k rotations
            temp = nums[n - 1]              # the last element wraps around
            for i in range(n - 2, -1, -1):  # from n-2 down to 0
                nums[i + 1] = nums[i]       # shift one place right
            nums[0] = temp

7Code line by line

8Dry run (k = 3)

9Complexity & remember

• Time O(n · k): k rounds, each moving n elements. With n = k = 10⁵ that's 10¹⁰ → the teacher's submission got TLE.
• Space O(1): only temp.

Part B · Better idea: jump each element to i + k (cyclic placement)

1The question

Same as Part A, but without moving every element k separate times.

2What the constraints tell us

We need about O(n). So each element should be moved once, straight to its final spot.

3Intuition: where does each element end up?

Compare the original with the answer for k = 3:

index:     0  1  2  3  4  5  6
original:  1  2  3  4  5  6  7
answer:    5  6  7  1  2  3  4

1 moved 0 → 3,  2 moved 1 → 4,  3 moved 2 → 5   (each jumped +3 = +k)
5 moved 4 → 0,  6 moved 5 → 1,  7 moved 6 → 2   (4+3 = 7 → wraps to 0, so use % n)

Every element moves from i to (i + k) % n. So why not put each one straight there?

4Building it: the overwriting problem and the chain

If we drop 1 into index 3, the 4 that was there is lost. So first save 4 in temp. Now what next: should we place 2 or 4? The teacher's answer: place 4, the one we're holding. If we went on to 2, we'd have to save 5, then 6, then 7… more and more values to remember. Instead we follow a chain: each placed value kicks out the next one, which we place right away.

Seven moves, each element placed once. The teacher walks through the first part of this chain (1, 4, 7, 3, 6, …) and calls it a more optimised way than Part A.

5Approach steps

1. k %= n; if k is 0, nothing to do.
2. moved = 0, start = 0.
3. While moved < n: pick up nums[start]. Repeatedly jump to (cur + k) % n, swap the held value into that cell (now holding the kicked-out value), count a move. Stop when we land back on start.
4. start += 1 and continue with the next chain.

6Code (Python)

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        k %= n
        if k == 0:
            return
        moved = 0
        start = 0
        while moved < n:
            cur = start
            carry = nums[start]                 # the value we are holding
            while True:
                nxt = (cur + k) % n             # where the held value belongs
                nums[nxt], carry = carry, nums[nxt]   # place it, pick up the kicked-out one
                cur = nxt
                moved += 1
                if cur == start:                # chain closed
                    break
            start += 1                          # next chain (only if gcd(n, k) > 1)

7Code line by line

8Dry run (n = 6, k = 2, the case that needs two chains)

9Complexity & remember

• Time O(n): every element is placed exactly once.
• Space O(1): just carry and a few counters.

Part C · Easier O(n): a temporary array with (i + k) % n

1The question

Same rotation, but now we're allowed extra memory.

2What the constraints tell us

n ≤ 10⁵, so a second array of size n is fine for memory, and O(n) time is well under 10⁸.

3Intuition

The teacher's observation: all the trouble in Part B comes from writing into the same array we're reading from. So write the answer into a fresh copy (temp). Read old values from nums, which never changes during this pass, and write each one to temp[(i + k) % n]. Nothing gets overwritten, so there's nothing to remember.

4Building it from the example

Then copy temp back into nums, because the problem wants nums itself changed and doesn't read a return value.

5Approach steps

1. k %= n.
2. Make temp of size n.
3. For each i: temp[(i + k) % n] = nums[i].
4. For each i: nums[i] = temp[i].

6Code (Python)

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        k %= n                          # only the leftover rotations matter
        temp = [0] * n
        for i in range(n):
            temp[(i + k) % n] = nums[i] # each value straight to its final spot
        for i in range(n):
            nums[i] = temp[i]           # copy back: nums must change in place

7Code line by line

8Dry run (k = 9, n = 7)

k becomes 9 % 7 = 2. Index 0 → 2, 1 → 3, 2 → 4, 3 → 5, 4 → 6, 5 → 7 % 7 = 0, 6 → 8 % 7 = 1. temp = 6 7 1 2 3 4 5, matching the teacher's "9th rotation" answer ✓.

9Complexity & remember

• Time O(2n) = O(n): one loop to fill temp, one to copy back.
• Space O(n) for temp.

Part D · Optimal: three reversals, O(1) space

1The question

The interviewer asks: "The problem only wants nums changed in place. Why use a whole extra array?" Can we get O(n) time and O(1) space?

2What the constraints tell us

Same as before. Since k is used as an index here, we must do k %= n first, or k - 1 could point past the end.

3Intuition: look at the two blocks

original:  [1 2 3 4] [5 6 7]        k = 3: the last 3 must go to the front
answer:    [5 6 7] [1 2 3 4]

The two blocks just swap places, and each block keeps its own order. Reversing the whole array swaps the blocks' places but also flips each block backwards. So flip each block back:

4Building it: how to reverse a piece in place

Use two pointers: one at the start of the piece, one at the end. Swap them, move both inwards, and stop when they meet. No extra array.

5Approach steps

1. k %= n.
2. Reverse nums[0 .. n−1].
3. Reverse nums[0 .. k−1].
4. Reverse nums[k .. n−1].

6Code (Python)

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        k %= n

        def reverse(lo, hi):                # reverse nums[lo..hi] in place
            while lo < hi:
                nums[lo], nums[hi] = nums[hi], nums[lo]
                lo += 1
                hi -= 1

        reverse(0, n - 1)                   # 1. whole array
        reverse(0, k - 1)                   # 2. first k elements
        reverse(k, n - 1)                   # 3. the rest

7Code line by line

8Dry run: [-1,-100,3,99], k = 2

9Complexity & remember

• Time O(2n) = O(n): the teacher's count is n swaps-worth for the full reverse, plus k and n − k for the two partial ones. Together that's 2n.
• Space O(1): far better than Part C.

Part E · Bonus: finding k in a rotated sorted array with binary search

Not in this video. Added because the sheet calls this problem "Find K Rotations", and on GFG that name means the reverse task. It uses the method from Problem 6.

1The question

A sorted array of distinct values was rotated right k times. You get the rotated array; find k.

[5 6 7 1 2 3 4]  → k = 3     (the smallest value, 1, sits at index 3)
[1 2 3 4]        → k = 0

2Constraints

Distinct values (so comparisons are strict), at least 1 element. We want O(log n).

3Intuition

Rotating right k times moves the original index 0 (the minimum) to index k. So k = index of the minimum. And we already know how to find the minimum with binary search: compare nums[mid] with nums[right].

4Conditions

• nums[mid] <= nums[right] → mid..right is sorted → the minimum is at mid or left → right = mid.
• Else the drop is right of mid → left = mid + 1.

5Steps

1. Same loop as Problem 6, but return the index left instead of the value.

6Code (Python)

def find_k_rotation(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= arr[right]:   # right part sorted: min at mid or left
            right = mid
        else:                        # drop is to the right of mid
            left = mid + 1
    return left                      # index of the minimum = k

7Line by line

Identical to Problem 6, Part B. The only difference: return left (an index) instead of return arr[left] (a value).

8Dry run: [5,6,7,1,2,3,4]

9Complexity

O(log n) time, O(1) space.

Part F · Revision page

s = Solution()
a = [1, 2, 3, 4, 5, 6, 7]; s.rotate(a, 3); print(a)     # [5, 6, 7, 1, 2, 3, 4]
b = [-1, -100, 3, 99];     s.rotate(b, 2); print(b)     # [3, 99, -1, -100]
c = [1, 2, 3, 4, 5, 6, 7]; s.rotate(c, 9); print(c)     # [6, 7, 1, 2, 3, 4, 5]
d = [1, 2, 3, 4, 5, 6];    s.rotate(d, 2); print(d)     # [5, 6, 1, 2, 3, 4]

Based on this video: Find K Rotations (Rotate Array)