Array In-Place Algorithm: Reverse Array

Introduction

After covering the fundamental Array operations in previous lessons, we will now examine in-place Array operations, which are crucial in terms of interviewing.

In-place array operations modify the array without creating a new one. Examples include shifting items when inserting or removing them. These operations are useful in various situations.

During programming interviews, candidates are commonly expected to optimize their implementations in terms of time and space complexity.

In-place array operations, which aim to reduce space complexity, are techniques that candidates frequently encounter during such interviews.

What are in-place algorithms mean?

An in-place algorithm refers to an algorithm that operates directly on the input data structure without requiring additional auxiliary space.

In-place algorithms manipulate array elements directly, avoiding the need for a new array or extra memory. This involves swapping, rearranging, or changing values within the same array.

In-place algorithms are desirable because they optimize space usage and can be more efficient in terms of memory consumption. They are commonly used when memory is a constraint, or when it is necessary to optimize the space complexity of an algorithm.

They often require careful manipulation of indices or pointers to achieve the desired result while adhering to the constraints of not using extra memory.

Once you do in-place algorithm, you are actually destroying the input array.

Reverse array

Here's an example of an in-place algorithm in Java that reverses an array:

import java.util.Arrays;

public class ArrayInPlaceAlgorithm {
  public static void reverseArray(int[] array) {
    int startIndex = 0;
    int endIndex = array.length - 1;

    while (startIndex < endIndex) {
      // Swap elements at startIndex and endIndex indices
      int temp = array[startIndex];
      array[startIndex] = array[endIndex];
      array[endIndex] = temp;

      // Move towards the center
      startIndex++;
      endIndex--;
    }
  }

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

    reverseArray(INPUT);
    System.out.println("Reversed Array: " + Arrays.toString(INPUT));
  }
}

In this example, the reverseArray method takes an integer array (array) as a parameter and reverses its elements in-place using a two-pointer approach. The startIndex pointer starts from the beginning of the array, the endIndex pointer starts from the end of the array, and they gradually move towards the centre while swapping elements.

The main method demonstrates the usage of the reverseArray method by initializing an array, calling the method, and printing the original and reversed arrays for verification.

Complexity analysis

Time complexity: The time taken by the algorithm is half the size of a number of elements. As we are traversing both from start and end in a single iteration. If we consider n as the number of elements, then the total number of times the loop runs is n/2, rounded to O(n) time.

Space complexity: We have not created any extra space, so the space is O(1), which is constant time.

Note: In-place algorithms always takes O(1) time.

When it comes to algorithms, using out-of-place ones is generally considered a safer option. This is because they don't cause any side effects. However, if you're short on space, you may need to use an in-place algorithm.