If you've spent time on LeetCode or GeeksforGeeks, you've probably run into the classic "Rearrange Array Alternately" problem.
The premise: given a sorted array of positive integers, rearrange it so the first element is the maximum, the second is the minimum, the third is the second maximum, the fourth is the second minimum, and so on.
For [1, 2, 3, 4, 5], the expected output is [5, 1, 4, 2, 3].
The Standard Solutions
There are usually two approaches taught for this:
- Temporary array (O(N) time, O(N) space) — use two pointers and a separate array to pick the largest and smallest numbers alternately.
-
Modulo math trick (O(N) time, O(1) space) — encode two numbers into a single index using
old_val + (new_val % M) * M.
The modulo trick is the standard "optimal" answer, but it feels more like a mathematical loophole than genuine array manipulation. While experimenting with pointer logic, I found a different way to hit O(1) space using pure structural manipulation instead of encoding.
I'm calling it Sequential Suffix Reversal — a heads up that this is a fresh application of a familiar idea (repeated suffix reversal shows up elsewhere in array problems, like building the lexicographically largest permutation), rather than a brand-new algorithmic concept. I haven't found this specific approach written up for this problem, so consider it a lesser-known alternative worth sharing, not an undiscovered algorithm.
The Concept
The logic relies on a pattern that emerges when you repeatedly reverse shrinking suffixes of the sorted array:
- Start at index
i = 0. - Reverse the subarray from index
ito the end of the array. - Move the index forward (
i += 1). - Repeat until you reach the end of the array.
By the time the loop finishes, the array has arranged itself into the max/min alternating pattern.
Tracing It
Let's trace arr = [1, 2, 3, 4, 5].
Step 1 (i = 0): Reverse the suffix from index 0 to the end.
[1, 2, 3, 4, 5] → [5, 4, 3, 2, 1]
(The max, 5, is now locked into index 0.)
Step 2 (i = 1): Reverse the suffix from index 1 to the end.
[5, 4, 3, 2, 1] → [5, 1, 2, 3, 4]
(The min, 1, is now locked into index 1.)
Step 3 (i = 2): Reverse the suffix from index 2 to the end.
[5, 1, 2, 3, 4] → [5, 1, 4, 3, 2]
(The second max, 4, is locked in.)
Step 4 (i = 3): Reverse the suffix from index 3 to the end.
[5, 1, 4, 3, 2] → [5, 1, 4, 2, 3]
(The second min, 2, is locked in.)
Step 5 (i = 4): Reversing a single element does nothing. Final array: [5, 1, 4, 2, 3]
The Code
To keep strict O(1) space, avoid Python's slicing (which allocates temporary lists) and use a manual two-pointer swap instead:
class Solution:
def rearrange(self, arr):
n = len(arr)
l, r = 0, n-1
for i in range(n):
while l < r:
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
l = i + 1
r = n - 1
The Pythonic shortcut
If you don't mind trading O(1) space for brevity, the same logic reads cleanly with slicing:
class Solution:
def rearrange(self, arr):
n = len(arr)
i = 0
while i < n:
arr[i:n] = reversed(arr[i:n])
i += 1
Complexity Analysis
- Space complexity: O(1) for the manual pointer version — no new arrays, no mathematical encoding, just in-place swaps.
- Time complexity: O(N²) — we reverse a shrinking subarray N times, and each reversal costs O(N) in the worst case.
Final Thoughts
In competitive programming, an O(N²) approach will usually trigger a Time Limit Exceeded error on large inputs, so the modulo trick remains the practical answer for auto-graders.
That said, from an algorithm-design standpoint, I found this pattern satisfying to discover. We often have to choose between optimizing for time or for memory, and this approach leans all the way into memory efficiency through pure structural manipulation rather than clever encoding.
Have you run into a similar suffix-reversal pattern while playing with array pointers? Let me know in the comments!
