Rotating Chore Chart

Mediumtwo pointersAlso known as Rotate Array

Your shared house has a chore chart: a fixed list of chores (dishes, bins, bathroom, vacuuming, shopping) and a list of names beside it, one name per chore. To keep things fair, the names move down the chart every week. Whoever falls off the bottom wraps around to the top.

After a holiday the chart is several weeks behind. You want to move the names down by that many places in one go, rewriting the list you already have rather than making a new chart.

Your task

Write rotateChores(names, k). Move every name k places towards the end of the list, wrapping around: the name at index i ends up at index (i + k) % names.length.

Change names in place and return nothing. k can be larger than the list, and the list can be empty. Try to use only O(1) extra memory.

rotateChores(names: string[], k: int) → void (changes names in place)

Examples

Example 1

Input

names = ["Ana", "Ben", "Caro", "Dev", "Eli"]
k = 2

Output

["Dev", "Eli", "Ana", "Ben", "Caro"]

Why

Everyone moves down 2 places. Dev and Eli fall off the bottom and wrap to the top, in the same order they were in.

Example 2

Input

names = ["Ana", "Ben", "Caro"]
k = 7

Output

["Caro", "Ana", "Ben"]

Why

Moving 3 places brings everyone back where they started, so 7 places is the same as 7 % 3 = 1 place. Caro wraps to the top.

Constraints

0 ≤ names.length ≤ 100,000
0 ≤ k ≤ 1,000,000,000
Names are non-empty strings and may repeat.

Start with brute force

Rotate by one place, k times: take the last name off and put it at the front, shifting everyone else down.

Each one-place rotation moves all n names, so this costs n × k steps. With 100,000 names and k in the billions it never finishes. Reducing k to k % n helps, but it is still up to n² moves. Copying into a new list is fast, O(n), but uses a second list of n names.

Hints

0 of 4 shown

Hint 1
Rotate [A, B, C, D, E] by 2 and you get [D, E, A, B, C]. Which block moved to the front, and did the order inside each block change?
Hint 2
The list is two blocks, [A, B, C] and [D, E], that swap places while keeping their inner order. And rotating by the list length changes nothing, so first replace k with k % n.
Hint 3
Reverse the whole list: [E, D, C, B, A]. The blocks are now in the right places, but each one is backwards. What could fix that?
Hint 4
With k = k % n: reverse the whole list, then reverse the first k items, then reverse the remaining n - k items. Write one helper that reverses a range in place with two pointers swapping inward.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Rotating right by k takes the last k names and puts them in front of the others, each block keeping its own order. Reversing the whole list puts the two blocks in the right places but flips each of them. Reversing each block again flips it back.

Trace [Ana, Ben, Caro, Dev, Eli] with k = 2:

k % 5 = 2, unchanged.
Reverse everything: [Eli, Dev, Caro, Ben, Ana]. Dev and Eli are on top, but backwards.
Reverse the first 2: [Dev, Eli, Caro, Ben, Ana].
Reverse the last 3: [Dev, Eli, Ana, Ben, Caro]. Done.

Two traps. First, rotating by a full lap is a no-op, so reduce k before doing anything, and check for an empty list first, because k % 0 is not a number in JavaScript and an error in Python. Second, "in place" means changing the list you were given: names = newList only points your local variable somewhere else. In Python, names[:] = names[-k:] + names[:-k] does write into the original list, but it builds a full copy first.

Reference solution

function rotateChores(names, k) {
  const n = names.length;
  if (n === 0) return;
  k = k % n; // full laps change nothing
  reverse(names, 0, n - 1); // blocks swap places, but each is backwards
  reverse(names, 0, k - 1); // fix the block that wrapped to the top
  reverse(names, k, n - 1); // fix the rest
}
 
function reverse(a, lo, hi) {
  while (lo < hi) {
    [a[lo], a[hi]] = [a[hi], a[lo]];
    lo++;
    hi--;
  }
}

def rotate_chores(names, k):
    n = len(names)
    if n == 0:
        return
    k %= n  # full laps change nothing
    reverse(names, 0, n - 1)  # blocks swap places, but each is backwards
    reverse(names, 0, k - 1)  # fix the block that wrapped to the top
    reverse(names, k, n - 1)  # fix the rest
 
 
def reverse(a, lo, hi):
    while lo < hi:
        a[lo], a[hi] = a[hi], a[lo]
        lo += 1
        hi -= 1

TimeO(n)Three reversals, and each name is swapped at most twice.

SpaceO(1)Swaps happen inside the list; only a few index variables are used.

Learn the idea: Arrays Two Pointers

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code