Reverse an Array In Place

In today’s practice question, we talk through the reverse an array in place question - no extra arrays allowed.

Problem Statement

Given an array of length n, reverse its elements in place so that the first element becomes the last, the second becomes the second‑to‑last, and so on.

You may not allocate another array—modify the array directly.

1. Clarify Requirements Before Jumping Into Code

Okay, so I’ve got an array of length n. I need to reverse its elements so the first becomes the last, the second becomes second‑to‑last, etc. And I must do this in place, which means no allocating a second array of size n. I should check:

• Allowed extra space? Probably O(1) extra variables (like a couple of pointers).

• Data types? Integers, strings, any—should work generically.

• Mutating input? Yes, I’m expected to modify the array itself.

Great—got it.

2. Identify the Category of the Question

This is an array manipulation problem, and I see a classic two‑pointer pattern: one pointer at the start, one at the end, swap, then move inward. It’s not sorting or searching—it’s in‑place transformation. Recognizing the two‑pointer technique early helps me jump to an optimal solution.

3. Consider a Brute‑Force Approach to Understand the Problem

If I ignore the ‘in place’ constraint, I could allocate a new array B of length n and fill it backwards:

B = [None] * n
for i in range(n):
    B[i] = A[n-1-i]

# then copy B back into A
for i in range(n):
    A[i] = B[i]

That’s O(n) time but O(n) space. It works, but violates the in‑place requirement.

4. Brainstorm More Solutions

How can I avoid that extra array? If I swap pairs directly in A, I don’t need extra storage. Use two pointers:

1. left = 0, right = n-1

2. While left < right: swap A[left] and A[right], then left++, right--.

3. 
   

This touches each element once (or half once), so O(n) time, O(1) space. Perfect.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Brute‑Force with B	O(n)	O(n)	Simple, easy to write	Uses extra O(n) memory
Two‑Pointer In‑Place	O(n)	O(1)	No extra memory, elegant	Slightly more logic to get right

Let's go with the two‑pointer in‑place swap because it meets the constraint and is still linear time.

6. Write Pseudocode to Structure Your Thoughts

function reverseInPlace(A):
    left  = 0
    right = length(A) - 1

    while left < right:
        swap A[left] and A[right]
        left  = left + 1
        right = right - 1

7. Consider Edge Cases

• Empty array ([]): Loop never runs; fine.

• Single element ([x]): left=0, right=0; left<right is false; fine.

• Even length ([1,2,3,4]): Swaps (0,3), (1,2).

• Odd length ([1,2,3,4,5]): Swaps (0,4), (1,3); middle stays.

Looks solid.

8. Write Full Code Syntax

def reverse_in_place(A):
    left, right = 0, len(A) - 1

    while left < right:
        # swap elements
        A[left], A[right] = A[right], A[left]
        left  += 1
        right -= 1

    # Done! A is now reversed

9. Test Your Code

# Test cases
arr = [1, 2, 3, 4, 5]
reverse_in_place(arr)
assert arr == [5, 4, 3, 2, 1]

arr = []
reverse_in_place(arr)
assert arr == []

arr = [42]
reverse_in_place(arr)
assert arr == [42]

arr = [1, 2, 3, 4]
reverse_in_place(arr)
assert arr == [4, 3, 2, 1]

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

If you're stuck, trying simplifying the question: In the brute-force section of this question, you saw me propose a solution that violated one of the constraints of the questions - no extra space. That's ok! Starting off with a simplified version of the question is a great way to get your mind working through ideas, especially if you're stuck.

Two‑Pointer Is Your Friend: Anytime you need to swap or compare elements from both ends, think two‑pointer. Here are some tips for recognizing when other problems might call for the two-pointer technique:

1. You’re Working on a Linear Structure

• Arrays or Strings: Anytime you need to process an array or string from both ends toward the middle, two pointers are a natural fit.

• Linked Lists: Fast/slow pointer patterns (like cycle detection or finding the middle node) are just a variation of the same idea.

2. You Need to Find Pairs or Triplets

• Sum-to‑Target Problems: If you’re asked to find two numbers that add up to a target (e.g., Two Sum II on a sorted array), you can often sort and then use left/right pointers.

• K‑Sum Variants: After sorting, reduce 3Sum, 4Sum, etc., to a series of two‑pointer searches.

3. The Problem Mentions “In-Place” or “Constant Space”

• If you must do it without extra arrays or hash maps, pointers moving within the original array are often the way to go.

4. You’re Searching for Subarrays or Substrings

• Sliding Window vs. Two Pointers: When the window can expand and contract at both ends (e.g., longest palindrome substring, min‑window substring), maintain two indices that move independently.

5. You See “Sorted” or “Monotonic”

• Sorted Input: Sorted arrays invite a “start + end” strategy—compare, move one pointer inward, repeat.

• Monotonic Sequences: If elements increase or decrease in a predictable way, pointers can exploit that order.

6. You’re Eliminating Candidates

• Two pointers are perfect when you want to “shrink” the search space from both sides—like partitioning an array around a pivot or removing duplicates in place.

7. You Need O(n) Instead of O(n²)

• Anytime a naive nested‑loop solution feels too slow, ask yourself: “Can I maintain two indices and adjust them in a single pass?”

With this pattern locked in, you’re ready for more complex in‑place and two‑pointer challenges—like rotating arrays, checking palindromes, and merging sorted lists. Keep practicing, and you’ll reverse any interview obstacle with ease!