Reverse An Array In Java Leetcode

Reversing an array is a common operation in programming that involves rearranging the elements of an array in reverse order. This task frequently appears in algorithms, data structure manipulations, and coding challenges like those found on LeetCode. In this article, you will learn how to effectively reverse an array in Java using various approaches, understanding their underlying mechanics and practical applications.

Problem Statement

The core problem is to take an array of elements and modify it such that the first element becomes the last, the second becomes the second-to-last, and so on, until the last element becomes the first. This operation is fundamental in tasks ranging from displaying data in reverse chronological order to implementing certain cryptographic algorithms or manipulating stacks and queues. Its importance lies in its ability to transform data order, which is crucial for various computational processes.

Example

Consider an array of integers: Input: [1, 2, 3, 4, 5] Expected Output: [5, 4, 3, 2, 1]

Background & Knowledge Prerequisites

To understand the array reversal techniques, a basic understanding of the following Java concepts is helpful:

• Arrays: How to declare, initialize, and access elements in a Java array.
• Loops: for loops are essential for iterating through arrays.
• Variables: Basic variable declaration and assignment.
• Methods: Understanding how to define and call methods.

Relevant imports for some approaches include java.util.Collections for utility methods.

Use Cases or Case Studies

Reversing an array finds application in numerous scenarios:

• Displaying Search Results: Showing the most recent results first by reversing a chronologically sorted list.
• Undo/Redo Functionality: Maintaining a history of actions that can be reversed.
• String Manipulation: Reversing a string often involves reversing its underlying character array, useful in palindrome checks.
• Algorithm Implementations: Some algorithms, like reversing a linked list or specific permutation problems, might involve similar logic to array reversal.
• Data Serialization: Certain data formats might require elements to be written or read in reverse order.

Solution Approaches

Here are three common approaches to reverse an array in Java, with detailed explanations for the key methods.

Approach 1: In-Place Reversal Using Two Pointers

This is the most efficient and widely used method. It involves using two pointers, one starting at the beginning of the array and the other at the end. These pointers swap elements and move towards each other until they meet or cross, effectively reversing the array without needing extra space.

• One-line summary: Swap elements from opposite ends of the array using two pointers until they meet in the middle.

// In-Place Array Reversal with Two Pointers
import java.util.Arrays; // For printing the array easily

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println("Original Array: " + Arrays.toString(arr));

        // Step 1: Initialize two pointers
        int start = 0;
        int end = arr.length - 1;

        // Step 2: Loop while the start pointer is less than the end pointer
        while (start < end) {
            // Step 3: Swap elements at start and end positions
            int temp = arr[start]; // Store the element at 'start'
            arr[start] = arr[end]; // Replace 'start' element with 'end' element
            arr[end] = temp;       // Replace 'end' element with stored 'start' element

            // Step 4: Move pointers towards the center
            start++;
            end--;
        }

        System.out.println("Reversed Array (Two Pointers): " + Arrays.toString(arr));
    }
}

Run

• Sample Output:

Original Array: [1, 2, 3, 4, 5]
Reversed Array (Two Pointers): [5, 4, 3, 2, 1]

• Stepwise Explanation:

1. Two integer pointers, start and end, are initialized. start points to the first element (index 0), and end points to the last element (index arr.length - 1).
2. A while loop continues as long as start is less than end. This ensures that elements are swapped only once and that the pointers don't cross unnecessarily.
3. Inside the loop, the element at arr[start] is swapped with the element at arr[end]. A temporary variable (temp) is used to hold one of the values during the swap.
4. After each swap, start is incremented, and end is decremented, moving them closer to the center of the array.
5. The loop terminates when start becomes equal to or greater than end, indicating that all necessary swaps have been performed.

Approach 2: Using a Temporary Array

This approach involves creating a new array of the same size and populating it with elements from the original array in reverse order.

• One-line summary: Create a new array and fill it with elements from the original array, iterating backward.

// Array Reversal with Temporary Array
import java.util.Arrays; // For printing the array easily

public class Main {
    public static void main(String[] args) {
        int[] originalArr = {1, 2, 3, 4, 5};
        System.out.println("Original Array: " + Arrays.toString(originalArr));

        // Step 1: Create a new temporary array of the same size
        int[] reversedArr = new int[originalArr.length];

        // Step 2: Iterate through the original array in reverse
        // and populate the new array from the beginning
        for (int i = 0; i < originalArr.length; i++) {
            reversedArr[i] = originalArr[originalArr.length - 1 - i];
        }

        System.out.println("Reversed Array (Temporary Array): " + Arrays.toString(reversedArr));
    }
}

Run

• Sample Output:

Original Array: [1, 2, 3, 4, 5]
Reversed Array (Temporary Array): [5, 4, 3, 2, 1]

• Stepwise Explanation:

1. A new array, reversedArr, is created with the same length as the originalArr.
2. A for loop iterates from the beginning of the originalArr (index i from 0 to length - 1).
3. In each iteration, the element from the originalArr at the index originalArr.length - 1 - i (which represents iterating backward from the end) is assigned to reversedArr[i].
4. After the loop completes, reversedArr will contain the elements in reverse order. This approach uses O(N) extra space for the new array.

Approach 3: Using java.util.Collections.reverse() (for ArrayList or List)

While Collections.reverse() doesn't work directly on primitive arrays (int[], char[]), it's a convenient method for reversing List implementations like ArrayList. It's worth mentioning for completeness, especially if working with dynamic arrays.

• One-line summary: Convert the primitive array to a List, then use Collections.reverse() for an easy reversal.

// Array Reversal with Collections.reverse()
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Integer[] originalArr = {1, 2, 3, 4, 5}; // Must use Wrapper type for List
        System.out.println("Original Array: " + Arrays.toString(originalArr));

        // Step 1: Convert the array to a List
        // Arrays.asList returns a fixed-size list backed by the array.
        // To allow modification (like reversal), it's often better to create a new ArrayList.
        List<Integer> list = new ArrayList<>(Arrays.asList(originalArr));
        
        System.out.println("List before reversal: " + list);

        // Step 2: Use Collections.reverse() method
        Collections.reverse(list);

        System.out.println("Reversed List: " + list);

        // Optional: Convert back to an array if needed
        Integer[] reversedArr = list.toArray(new Integer[0]);
        System.out.println("Reversed Array (from List): " + Arrays.toString(reversedArr));
    }
}

Run

• Sample Output:

Original Array: [1, 2, 3, 4, 5]
List before reversal: [1, 2, 3, 4, 5]
Reversed List: [5, 4, 3, 2, 1]
Reversed Array (from List): [5, 4, 3, 2, 1]

• Stepwise Explanation:

1. The primitive array int[] is first converted to an Integer[] (wrapper class array) because List in Java stores objects, not primitives directly.
2. Arrays.asList(originalArr) creates a fixed-size List from the array. To ensure it's mutable for Collections.reverse(), it's then wrapped into a new ArrayList.
3. Collections.reverse(list) is called on the List object. This method modifies the list in-place.
4. If an array is still needed, the toArray() method of the List can convert it back.

Conclusion

Reversing an array in Java can be achieved through several methods, each with its own trade-offs. The in-place two-pointer approach is generally preferred for its efficiency in terms of both time complexity (O(N)) and space complexity (O(1)). Using a temporary array is straightforward but consumes O(N) extra space. For List objects, Collections.reverse() provides a highly convenient and readable solution. The choice of method depends on the specific requirements of the problem, including memory constraints and whether an in-place modification is acceptable.

Summary

• Problem: Rearranging array elements in reverse order.
• Two-Pointer Approach: Most efficient (O(N) time, O(1) space). Swaps elements from opposite ends inwards.
• Temporary Array Approach: Simple to understand (O(N) time, O(N) space). Creates a new array with elements in reverse.
• Collections.reverse(): Convenient for List types (O(N) time, O(N) if converting from array, O(1) for existing list). Requires converting primitive arrays to List.
• Key Consideration: In-place vs. new array; memory usage.