Disclaimer: This is a user generated content submitted by a member of the WriteUpCafe Community. The views and writings here reflect that of the author and not of WriteUpCafe. If you have any complaints regarding this post kindly report it to us.

Imagine you meet a new person, have a nice conversation with them, and ask for their number to keep in touch. You’ll save it on your mobile phone, right!

 

 Now, what makes it possible to save the contacts? Well the mechanism behind saving certain items are arrays!

Arrays are one of the main data structure types that helps to save elements of the same type. So whenever you store a phone number, it files it under contacts because they’re of that type. 

 

Speaking of contacts, have you noticed them being in ascending order? What if you need it in descending order? Which method will you implicate?

 

The answer again is very simple! You will need to reverse an array. Reversal of an array helps users to access certain information in a specific order in which they desire it (ascending or descending order).

 

To understand this interesting problem, here’s a full guide which presents information regarding the methods through which you can reverse the given array to produce the desired outcome. 

 

Methods to Reverse an Array

 

Let’s take a sample problem to understand the concept of reversing an array. 

 

Input: arr[] = {S, T, A, R}

 

After we reverse the array the output would be,

 

arr[] = {R, A, T, S}

 

Method 1: Recursive Technique 

 

In this method, we will divide the array recursively into tiny subarrays so that we can reverse the remaining segments. 

 

Steps: 

 

  • You should initiate the reverse function (start, end, arr). 
  • The start must be 0 and the end must be N-1
  • Now keep recursively calling the same function for the start + 1 subarray and end – 1.

 

Time and space complexity:

 

As we’re using the reverse function recursively the time used is O(n) and the space would be O(1) since no extra space is used.

 

Method 2: Iterative Technique

 

In this method, we will use iteration loops on the loops till n/2 for every index before swapping it with (n-i-1)th character of the input array. 

 

Steps: 

 

  • First set the variable start as 0 and end as n-1 and initiate them.
  • Now operate a loop and proceed it over the array.
  • Then swap the characters at start and end.
  • Now change start to start + 1 and end to end – 1

 

Time and space complexity:

 

As the iteration happens once, the time taken is O(n) and due to no extra space being utilized the space taken is O(1).

 

Method 3: Python List Slicing

 

The best method to reverse an array would be python list slicing as it saves time and space. To start with this method, you will need to remember the syntax: list_name[start: end]

 

Steps:

 

  • If you proceed with printing list_name[::-1] your input array will easily be reversed.

 

Time and space complexity:

 

As we’re making use of the in-built slice approach of Python, the time taken for a single list that’s sliced is O(n).

 

Again, there isn’t any unnecessary space used so O(1) is the complexity.

 

Method 4: Reverse function (For C++)

 

Thanks to the C++ program, they have a reverse function that is in-built. The syntax is reversed(arr,arr+n).

 

The step is very easy. All you need to do is use the function and pass the first element’s address and the last element's address. Your array will be reversed. 

 

Time and space complexity:

 

The time taken by the in-built reverse function is O(n) and O(1) is the space taken due to no auxiliary space being wasted. 

 

Method 5: Swapping 

 

In this method we use a third variable to interchange the values within an array. We use iteration over an array to i=n/2 from i=0. We also swap arr[i] and arr[n-i-1]. 

 

Steps: 

 

  • First initiate start and end. 
  • Then swap array start and array end.
  • Increase the start by value 1 and decrease the end value by 1.
  • If the start value becomes n/2, terminate the process. 

 

Time and space complexity:

 

The iteration takes up time O(n) and the space again is O(1).

 

Method 6: User-defined ()

 

This method is similar to the iterative approach, but we will process with iteration and swapping without any in-built functions. 

 

Steps:

 

  • First you will need to define the reverseArray function.
  • In that function, set up the start as 0 and the end as n-1.
  • Now swap the elements of the start and end.
  • Change start to start+1 and end to end-1.

 

Time and space complexity:

 

O(n) is the time taken due to iteration and the space remains O(1).

 

Method 7: Using pointers (For C++)

 

With the help of pointers, we will reverse the array. We will keep a pointer at the array’s start and end addresses. Then we swap them. 

 

Steps: 

 

  • Prepare pointer 1 and pointer 1. 
  • Place the pointers at the array’s beginning and end addresses.
  • Now keep swapping the values at the start and last addresses. Keep increasing the beginning pointer by one and vice versa for the last pointer.
  • Keep repeating the step until the entire array is reversed. 

 

In this approach, we basically make use of the functions: reverse, swap and print. 

 

Time and space complexity:

 

Due to the iteration process during swapping, the time taken is O(n). Similar to the previous methods, space remains as O(1) due to no space wasted.

 

Extra Learning

 

Now that we have enriched ourselves regarding reversing an array, here is another topic briefly discussed to widen your DSA knowledge.

 

In interviews, interviewers regularly ask a question related to arrays, notably like what is a partition equal subset sum problem? 

 

With the help of partition sum, you can split the arrays into subarrays to make the process easier. 

 

To reverse an array, you can partition it and work on it. Some of the common methods used for this problem are

 

  • Brute Force
  • Dynamic Programming
  • Bit Solution

 

Final Thoughts

 

Reversing an array makes it possible to arrange data in any order we want. We hope with our  methods, you now know how to work on a similar problem. 

 

We also believe our quick teaching on partition equal subset sum has introduced how you can solve an array problem by dividing it. 

 

Happy learning!

Login

Welcome to WriteUpCafe Community

Join our community to engage with fellow bloggers and increase the visibility of your blog.
Join WriteUpCafe