LeetCode 3865 - Reverse K Subarrays

LeetCode Problem 3865

Difficulty: 🟡 Medium
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem asks us to take an integer array nums of length n and divide it into k contiguous subarrays of equal length, then reverse each subarray individually. The resulting array should preserve the order of the subarrays but reflect the reversal within each one. For example, if nums = [1,2,4,3,5,6] and k = 3, each subarray will have length n / k = 6 / 3 = 2, producing [1,2], [4,3], [5,6]. After reversing each, the subarrays become [2,1], [3,4], [6,5], and the concatenation of these produces the final output [2,1,3,4,6,5].

The input represents the original array of integers and the integer k that dictates how many contiguous partitions to create. The output is an array of the same length as the input, with subarrays reversed. The constraints guarantee that n is divisible by k, so every subarray will be of equal length, and there are no empty or partial subarrays.

Important edge cases include k = 1, which means the entire array is reversed, and k = n, which means each element is a subarray of length 1, producing the same array as output. Additionally, very small arrays (n = 1) or arrays with repeated values should be considered.

Approaches

The brute-force approach is straightforward: compute the length of each subarray as length = n / k. Then iterate over the array, extract each subarray of this length, reverse it, and place it back in the correct position. This works correctly but involves creating temporary subarrays and performing multiple reverse operations, which introduces extra overhead.

The optimal approach leverages in-place reversal. Since each subarray is contiguous, we can reverse elements directly within the original array using a two-pointer technique. For each subarray, one pointer starts at the beginning and another at the end of the subarray, swapping elements until the pointers meet or cross. This reduces extra space usage to O(1) and avoids constructing new lists.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Extracts subarrays and reverses each in temporary storage
Optimal	O(n)	O(1)	Reverses subarrays in place using two-pointer swaps

Algorithm Walkthrough

1. Compute the length of each subarray by dividing n by k, giving length = n // k. This ensures every subarray has the same size.
2. Iterate over the array with a step of length to identify the start of each subarray. The start index is i and the end index is i + length - 1.
3. For each subarray, initialize two pointers: left at the start index and right at the end index.
4. Swap nums[left] with nums[right], then increment left and decrement right.
5. Continue swapping until left >= right. At this point, the subarray is reversed in place.
6. Move to the next subarray by increasing i by length and repeat steps 3-5 until the entire array has been processed.
7. Return the modified array.

Why it works: Each subarray is reversed independently without affecting other subarrays because the indices for each reversal are carefully bounded. The iteration ensures every element is visited exactly once, and in-place swaps maintain O(1) space usage.

Python Solution

class Solution:
    def reverseSubarrays(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        length = n // k
        
        for i in range(0, n, length):
            left, right = i, i + length - 1
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        
        return nums

The implementation first calculates the size of each subarray. Then it iterates over the array, processing each subarray independently. The two-pointer technique reverses elements in place. Finally, the original nums array, now modified with all subarrays reversed, is returned.

Go Solution

func reverseSubarrays(nums []int, k int) []int {
    n := len(nums)
    length := n / k
    
    for i := 0; i < n; i += length {
        left, right := i, i+length-1
        for left < right {
            nums[left], nums[right] = nums[right], nums[left]
            left++
            right--
        }
    }
    
    return nums
}

The Go version mirrors the Python solution closely. It calculates the subarray length and iterates over the array in steps. Two pointers reverse each subarray in place. Go handles slice assignment directly, similar to Python's tuple swap, making the implementation straightforward.

Worked Examples

Example 1: nums = [1,2,4,3,5,6], k = 3

Step	Subarray	Operation	Result
1	[1,2]	Reverse	[2,1]
2	[4,3]	Reverse	[3,4]
3	[5,6]	Reverse	[6,5]
Final	-	Combine	[2,1,3,4,6,5]

Example 2: nums = [5,4,4,2], k = 1

Step	Subarray	Operation	Result
1	[5,4,4,2]	Reverse	[2,4,4,5]
Final	-	Combine	[2,4,4,5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is visited exactly once for reversal; iterating over all elements in subarrays
Space	O(1)	Reversal is done in place with no extra data structures

The time complexity is linear in the number of elements because each element is swapped at most once. The space complexity is constant because no additional arrays or slices are created; all operations are in-place.

Test Cases

# Provided examples
assert Solution().reverseSubarrays([1,2,4,3,5,6], 3) == [2,1,3,4,6,5]  # multiple small subarrays
assert Solution().reverseSubarrays([5,4,4,2], 1) == [2,4,4,5]  # entire array reversed

# Edge cases
assert Solution().reverseSubarrays([1], 1) == [1]  # single element
assert Solution().reverseSubarrays([1,2,3,4], 4) == [1,2,3,4]  # k = n, each element reversed individually (no change)
assert Solution().reverseSubarrays([1,2,3,4,5,6], 2) == [3,2,1,6,5,4]  # k = 2, each subarray length 3
assert Solution().reverseSubarrays([7,7,7,7], 2) == [7,7,7,7]  # identical elements, reversal has no visible effect

Test	Why
[1,2,4,3,5,6], 3	Validates multiple small subarrays
[5,4,4,2], 1	Entire array reversal
[1], 1	Single element array edge case
[1,2,3,4], 4	Each element is its own subarray
[1,2,3,4,5,6], 2	Even split with longer subarrays
[7,7,7,7], 2	All identical elements

Edge Cases

A key edge case is when k = 1. In this scenario, the entire array becomes a single subarray and must be reversed entirely. This could be a source of off-by-one errors when computing subarray boundaries. Our implementation handles it correctly because the start index is 0, and the end index is n-1.

Another important edge case is when k = n. Here, each subarray contains exactly one element. Naive implementations that assume subarrays have length greater than 1 could attempt swaps incorrectly. Our two-pointer approach correctly identifies that left equals right immediately, performing no swaps.

A third edge case involves arrays with repeated values. Reversing subarrays with identical elements will not change the array, but the algorithm should not fail or perform unnecessary operations. The implementation treats each element individually, swaps elements even if they are equal, and correctly returns the array.