Reverse Every K Block
Problem
Given a list and a positive integer k, reverse the order of the values inside every consecutive block of k values: the first k, then the next k, and so on. If the length is not a multiple of k, the final block is shorter than k and stays as it is. Work in place with O(1) extra space and return the same list.
Examples
Input: nums = [1, 2, 3, 4, 5, 6, 7, 8], k = 3
Output: [3, 2, 1, 6, 5, 4, 7, 8]
Why: two full blocks are reversed; 7 and 8 form a short blockInput: nums = [1, 2, 3, 4], k = 4
Output: [4, 3, 2, 1]
Why: one block covers the whole listInput: nums = [5, 6], k = 3
Output: [5, 6]
Why: edge case, there is no full block at allHints
0 / 3
Split the list mentally into chunks of k starting at index 0. Each full chunk is its own small reversal, independent of the others.
A reversal in place needs only two indexes that swap values and walk toward each other. The remaining question is where each chunk starts and ends.
Loop over block starts 0, k, 2k and so on, stopping before a start whose block would run past the end. For each block, swap the values at its two ends and move both indexes inward until they meet.
Solution
Block starts are 0, k, 2k and so on, and a block is only reversed when all k of its values exist, which the range bound len(nums) - k + 1 enforces. Each block is reversed by two indexes that swap values and meet in the middle, so no second list is built. Every value is swapped at most once. Time is O(n) and space is O(1).
def reverse_blocks(nums, k):
for start in range(0, len(nums) - k + 1, k): # full blocks only
lo, hi = start, start + k - 1
while lo < hi: # swap the ends, walk inward
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
return nums
print(reverse_blocks([1, 2, 3, 4, 5, 6, 7, 8], 3)) # -> [3, 2, 1, 6, 5, 4, 7, 8]
print(reverse_blocks([1, 2, 3, 4], 4)) # -> [4, 3, 2, 1]
print(reverse_blocks([5, 6], 3)) # -> [5, 6]Stuck on the idea rather than the code? In-Place Reversal covers it.