Reverse K Subarrays solution and explanation
The problem
You are given an integer array nums of length n and an integer k.
You must partition the array into k contiguous subarrays of equal length and reverse each subarray.
It is guaranteed that n is divisible by k.
Return the resulting array after performing the above operation.
Example 1:
Input: nums = [1,2,4,3,5,6], k = 3
Output: [2,1,3,4,6,5]
Explanation:
- The array is partitioned into
k = 3subarrays:[1, 2],[4, 3], and[5, 6]. - After reversing each subarray:
[2, 1],[3, 4], and[6, 5]. - Combining them gives the final array
[2, 1, 3, 4, 6, 5].
Example 2:
Input: nums = [5,4,4,2], k = 1
Output: [2,4,4,5]
Explanation:
- The array is partitioned into
k = 1subarray:[5, 4, 4, 2]. - Reversing it produces
[2, 4, 4, 5], which is the final array.
Constraints:
1 <= n == nums.length <= 10001 <= nums[i] <= 10001 <= k <= nnis divisible byk.
Approach overview
Problem Overview: You are given an array and an integer k. The task is to reverse every contiguous subarray of size k. Process the array in chunks of length k and reverse the elements inside each chunk while preserving the order of the chunks themselves.
This problem focuses on careful index manipulation. You traverse the array in steps of k, and for each segment, reverse the elements in-place. The core technique is the classic two-pointer reversal commonly used in two pointers problems over an array.
Approach 1: Auxiliary Array Simulation (O(n) time, O(n) space)
The straightforward method creates a new result array. Iterate over the original array in blocks of size k. For each block, traverse it backward and append elements to the result. This simulates the reversal without modifying the input array. The logic is simple and reduces the risk of index mistakes, but it uses additional memory proportional to the input size.
This approach works well when immutability matters or when you want the clearest implementation. However, interviews usually expect an in-place solution when working with arrays.
Approach 2: In-Place Two-Pointer Reversal (O(n) time, O(1) space)
The optimal solution reverses each k-sized segment directly inside the array. Start from index 0 and move in increments of k. For each segment, set two pointers: left = start and right = min(start + k - 1, n - 1). Swap elements while left < right, moving the pointers toward the center.
This is the same logic used when reversing an array or string segment. Every element participates in at most one swap per segment, so the total work across the entire array remains linear. No additional memory is required beyond a few pointer variables.
The key insight: treat each chunk as an independent mini-array and apply a standard reversal routine. Because segments never overlap, processing them sequentially guarantees correctness.
Recommended for interviews: The in-place two-pointer method is what interviewers expect. It demonstrates that you can manipulate array indices safely and apply standard reversal logic efficiently. Mentioning the auxiliary array version first shows understanding of the brute-force simulation, but implementing the O(n) time and O(1) space approach signals stronger problem-solving skills.
Solution
Since we need to partition the array into k subarrays of equal length, the length of each subarray is m = \frac{n}{k}. We can use a loop to traverse the array with a step size of m, and in each iteration, reverse the current subarray.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1), as we only use a constant amount of extra space.
class Solution:
def reverseSubarrays(self, nums: list[int], k: int) -> list[int]:
n = len(nums)
m = n // k
for i in range(0, n, m):
nums[i : i + m] = nums[i : i + m][::-1]
return numsclass Solution {
public int[] reverseSubarrays(int[] nums, int k) {
int n = nums.length;
int m = n / k;
for (int i = 0; i < n; i += m) {
int l = i, r = i + m - 1;
while (l < r) {
int t = nums[l];
nums[l++] = nums[r];
nums[r--] = t;
}
}
return nums;
}
}class Solution {
public:
vector<int> reverseSubarrays(vector<int>& nums, int k) {
int n = nums.size();
int m = n / k;
for (int i = 0; i < n; i += m) {
int l = i, r = i + m - 1;
while (l < r) {
swap(nums[l++], nums[r--]);
}
}
return nums;
}
};function reverseSubarrays(nums: number[], k: number): number[] {
const n = nums.length;
const m = Math.floor(n / k);
for (let i = 0; i < n; i += m) {
let l = i,
r = i + m - 1;
while (l < r) {
const t = nums[l];
nums[l++] = nums[r];
nums[r--] = t;
}
}
return nums;
}func reverseSubarrays(nums []int, k int) []int {
n := len(nums)
m := n / k
for i := 0; i < n; i += m {
l, r := i, i+m-1
for l < r {
nums[l], nums[r] = nums[r], nums[l]
l++
r--
}
}
return nums
}impl Solution {
pub fn reverse_subarrays(mut nums: Vec<i32>, k: i32) -> Vec<i32> {
let n = nums.len();
let m = n / k as usize;
for i in (0..n).step_by(m) {
let mut l = i;
let mut r = i + m - 1;
while l < r {
nums.swap(l, r);
l += 1;
r -= 1;
}
}
nums
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Auxiliary Array Simulation | O(n) | O(n) | When clarity matters more than memory usage or when the original array must remain unchanged |
| In-Place Two-Pointer Reversal | O(n) | O(1) | Best general solution; optimal for interviews and large arrays |
Frequently asked questions
Is Reverse K Subarrays easy or hard?
Reverse K Subarrays is typically considered a medium-level problem. The algorithm itself is straightforward, but handling segment boundaries and index calculations correctly can cause mistakes during interviews.
Reverse K Subarrays Python/Java solution
Most implementations iterate over the array with a step size of k and reverse each segment using a two-pointer loop. Python, Java, C++, Go, TypeScript, and Rust solutions follow the same logic with small syntax differences.
How to solve Reverse K Subarrays in O(n)?
Traverse the array in increments of k. For each starting index, set two pointers at the beginning and end of the k-sized segment, then swap elements while moving the pointers inward. Each element participates in at most one reversal operation, which keeps the total work linear.
What is the best approach for Reverse K Subarrays?
The in-place two-pointer approach is the best solution. Iterate through the array in steps of k and reverse each segment using two pointers from both ends of the segment. This method runs in O(n) time and uses O(1) extra space, making it optimal for interviews and large inputs.
Is Reverse K Subarrays asked at Google/Amazon/Meta?
Array segment manipulation problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants such as reversing nodes in k-groups or reversing subarrays test similar skills around pointer manipulation and boundary handling.
What data structure is used in Reverse K Subarrays?
The problem primarily uses arrays and the two-pointer technique. Two pointers move from the start and end of each k-sized segment to swap elements until the segment is reversed.
What is the time complexity of Reverse K Subarrays?
The optimal solution runs in O(n) time because every element is visited a constant number of times during the segment reversals. Space complexity is O(1) when reversing segments directly inside the array.