Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.2.1.
 
2.3.
Implementation in Python
2.3.1.
Complexity Analysis
3.
Optimized Approach - 1
3.1.
Steps of Algorithm
3.2.
Pseudocode
3.3.
Implementation in C++
3.3.1.
 
3.4.
Implementation in Python
3.4.1.
Complexity Analysis
4.
Optimized Approach - 2
4.1.
Steps of Algorithm
4.2.
Pseudocode
4.3.
Implementation in C++
4.3.1.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What are the different sorting algorithms that can be used in the above approach?
5.2.
What is the difference between sort function used in Python and C++?
5.3.
What is the difference between sort and sorted function in Python?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if reversing a sub-array make the array sorted

Author Akshit Mehra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will be discussing the problem of checking if there exists a certain subarray that, when reversed, makes the whole array sorted. For this, we have used three approaches:

  1. Brute force: Here, we will use a naïve approach with two loops. We check for each subarray.
  2. Sorting based: This is an efficient approach that uses the concept of sorting. However, the space complexity here is O(n).
  3. Linear approach: This is the most efficient approach for this problem. Here the time complexity is O(n) while the space complexity is O(1).

Problem Statement

The problem above states that given an array of elements, we have to check if reversing any subarray makes the collection sorted.

Sample Example

Input 1: 

arr[] = {1, 2, 3, 6, 5 }

 

Output 1: 

Yes

 

Explanation: In the above array, reversing the [6 5] subarray makes the array sorted.

 

Input 2: 

arr[] = {5, 9, 7, 3, 1}

 

Output 2: 

No

 

Explanation: As in the above array, there exists no such subarray which can be reversed to make the array sorted.

Brute Force Approach

Below is the brute force approach:

  1. Check for every subarray by reversing it. 
  2. If the array becomes sorted for any subarray being reversed, return true. 
  3. If no such subarray 

Pseudocode

For i = 0 to n:
   For j = 0 to i:
		reverse the subarray arr[i:j]
		if the array becomes sorted:
			return true
If no such subarray exist:
	return false

Implementation in C++

#include "bits/stdc++.h"
using namespace std;
void solve()
{  
    int arr[] = [1, 2, 3, 5, 4];
    int n = sizeof(arr)/sizeof(int);
   
    //Traversing the loop for getting a subarray.
    for(int i = 0;i<n;i+=1){
        for(int j = i;j<n;j+=1){
            int l = i;int r = j;

            //Now, for each subrarray from arr[i..j], we reverse
            //To check if this is the one.
            while(r>l){
                swap(arr[l], arr[r]);
                r-=1;l+=1;
            }

            //Checking if reversing makes it sorted.
            bool sorted = true;
            for(int j = 1;j<n;j+=1){
                if(arr[j]<arr[j-1]){
                    sorted=false;
                    break;
                }
            }
            //If yes, we return true;
            if(sorted){
                cout<<"YES\n";return;
            }

            //We readjust the subarray if the array ain't sorted.
            l=i;r=j;
            while(r>l){
                swap(arr[l], arr[r]);
                r-=1;l+=1;
            }
        }
    }
    cout<<"NO\n";
}  
int main()
{
    solve();
    return 0;
}

 

Implementation in Python

def solve(arr, n):
    for i in  range(n):
        for j in range(i):

            #Here, we are using another array for storing the reversed subarray. Therefore
            #Space Complexity is O(n)
            reversed_list= arr[0:i] + arr[j:i-1:-1] + arr[j+1:]
        
            #Checking if the reversing the subarray made the whole array sorted
            f = True
            for j in range(1, n):
                if reversed_list[j]<reversed_list[j-1]:
                    f = False
                    break
            
            #If sorted, then yes.
            if f:
                print("YES")
                return
    #If not sorted, we print No
    print("NO")


arr = [1, 2, 3, 5, 4]
n = len(arr)
solve(arr, n)

 

Output: 

Yes

 

Complexity Analysis

Time complexity: O(n2)

 As in the above approach, we use two nested loops of size n, and the time complexity for the above approach becomes O(n2)

Space complexity: O(1)

As in the above approach to solve the problem, we haven’t used any extra space for solving it. Therefore, the space complexity is O(1), i.e. constant.

Read More - Time Complexity of Sorting Algorithms and  Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach - 1

An efficient approach for solving the above problem is to use sorting techniques. Here, we first create a copy of the original which we then sort. Then compare the two arrays to check if any required subarray exists. For sorting, we can use Merge sort. 

Steps of Algorithm

  1. We begin by creating a copy of the original array and then sort it.
  2. Now, compare the original array with the sorted array. Mark the first and the last index that does not match the two arrays.
  3. If no such indices exist, then return true.
  4. Else, the elements between the two indices found shall be in decreasing order in the original array. 
  5. If the condition is not fulfilled, then we return false. Else we return true.

Pseudocode

temp = arr
sort(temp, temp + n)
front = -1
back = -1
for i = 0 to n:
	if arr[i]!=temp[i]:
		front = i
		break
for i = n-1 to 0:
	if arr[i]!=temp[i]:
		back = i
		break
if front is -1:
	return true
for i = front to back:
	if arr[front] < arr[front+1]:
		return false
return true

Implementation in C++

#include "bits/stdc++.h"
using namespace std;
void solve()
{  
    int arr[] = [1, 2, 3, 5, 4];
    int n = sizeof(arr)/sizeof(int);
   
    // Creating a temporary array
    int temp[n];
    for(int i = 0;i<n;i+=1){
        temp[i]=arr[i];
    }

    //Sorting the array.
    sort(temp, temp+n);
    int fr,bk;

    //Defining the front and back variables.
    fr = -1;bk = -1;
    for(int i = 0;i<n;i+=1){

        //Getting the front variable value.
        if(arr[i]!=temp[i]){
            fr = i;
            break;
        }
    }
   
    //If front doesn't exist, then the array is already sorted.
    if(fr == -1){
        cout<<"YES\n";
        return;
    }

    //Getting the value of back variable.
    for(int i = n-1;i>=0;i--){
        if(temp[i]!=arr[i]){
            bk = i;
            break;
        }
    }

    //Now, we check if the array between front and back variable
    //is sorted in descending order.
    for(int i = fr;i<bk;i++){
        //If not, therefore No single subarray exist.
        if(arr[i]<arr[i+1]){
            cout<<"NO\n";return;
        }
    }
    cout<<"YES\n";
}  
int main()
{
    solve();
    return 0;
}

 

Implementation in Python

def solve(arr, n):
    
    #Creating a temporary array
    temp = [0]*n
    for i in range(n):
        temp[i] = arr[i]
    
    #Sorting the array.
    temp.sort()
    
    #Defining the front and back variables
    global fr, bk
    fr = bk = -1
    
    #Getting the front variable value
    for i in range(n):
        if temp[i]!=arr[i]:
            fr = i
            break
    
    if fr == -1:
        print("YES")
        return
    
    #Getting the back variable value
    for i in range(n-1, -1, -1):
        if temp[i]!=arr[i]:
            bk = i
            break
    
    #If whole array is sorted
    if fr>=bk:
        print("YES")
        return
    
    #Now, we check if the array between front and back variable
    #is sorted in descending order.
    for i in range(fr, bk):
        if arr[i]<arr[i+1]:
            print("NO")
            return 
    
    print("YES")
    return
   


arr = [1, 2, 3, 5, 4];
n = len(arr)
solve(arr, n)

 

Output: 

Yes

 

Complexity Analysis

Time complexity: O(nlog(n))

The Time complexity for the above code can be broken down into two parts:

  1. O(nlog(n)) : For sorting the array.
  2. O(n): For copying the original and getting front and back indexes.

Therefore, final Time complexity is O(n) + O(nlog(n)) which comes out to be O(nlog(n)).

Space complexity: O(n)

As we create a new temp array for sorting purposes, the space complexity becomes O(n).

Also Read - Selection Sort in C

Optimized Approach - 2

A more efficient approach only includes a linear traversal of the array. If the given condition is to be fulfilled, then the array shall be divided into three parts:

  1. Increasing with the minimal set elements in the array.
  2. Decreasing segment
  3. Again increasing with the maximum set of elements.

Steps of Algorithm

  1. Start traversing the array. Now, check the index till where the first part of the array is increasing. Let this be ind. If ind is n, then return true.
  2. Now, as we got the first part, we start looking for the next decreasing array segment. Again we traverse the array. Along with it, we also have to compare these elements with the prior segment. As we can only reverse a particular decreasing segment, the relative order of elements between the segments shall be maintained.
  3. Similarly, we repeat the above process for the 3rd segment.

Pseudocode

# Find first increasing part
i = 1
for i in range(1, n):
	if arr[i - 1] is less than arr[i] :
	i is equal to n:
		return True
	else:
		break
		
#Finding the reversed part
j = i
while j less than n and arr[j] less than arr[j - 1]:
	if i greater than 1 and arr[j] less than arr[i - 2]):
		return False
	j += 1
	
If j is equal to n:
return True

#Finding the last increasing part
k = j

#To check that the last increasing part elements are greater than the first part.
if arr[k] is less than arr[i - 1]
	return False

while k greater than 1 and k less than n:
	if (arr[k] < arr[k - 1]):
		return False
	k += 1
return True

Implementation in C++

#include "bits/stdc++.h"
using namespace std;
void solve()
{  
    int arr[] = {1, 2, 3, 5, 4};
    int n = sizeof(arr)/sizeof(int);
   
    //First, we find the increasing array part.
    int i = 1;
    while(i<n){
        if(arr[i]<arr[i-1]){
            break;
        }
        i+=1;
    }

    //If we reach end, then yes.
    if(i == n){
        cout<<"YES\n";
        return;
    }

    //Now we find the next decreasing array.
    int j = i;
    while(j<n && arr[j]<arr[j-1]){
        if(i>1 && arr[j]<arr[i-2]){
            cout<<"NO\n";
            return;
        }
        j+=1;
    }

    //If we reach the end of array, the yes.
    if(j == n){
        cout<<"YES\n";
        return;
    }

    //Next, we find the third increasing array.
    int k = j;

    //Here we see that, if the elements here are greater than the
    //Middle segment.
    if(arr[k]<arr[i-1]){
        cout<<"NO\n";
        return;
    }
    while(k>1 && k<n){
        if(arr[k]<arr[k-1]){
            cout<<"NO\n";
            return;
        }
        k+=1;
    }
    cout<<"YES\n";
}  
int main()
{
    solve();
    return 0;
}

 

Output: 

Yes

 

Complexity Analysis

Time complexity: O(n)

As in the above approach, we use only a single loop for traversing the whole array. So the overall time complexity of the above approach is O(n).

Space complexity: O(1)

As no extra space has been used in the above approach, thus the space complexity of the above approach is O(1)

Must Read  C Program to Reverse a Number

Frequently Asked Questions

What are the different sorting algorithms that can be used in the above approach?

Apart from Merge sort, we can use Quicksort in the above problem, as it also gives O(nlog(n)) as its average time complexity. But, if we’ve used Bubble sort, Insertion sort, or selection sort, our time complexity would have become O(n2).

What is the difference between sort function used in Python and C++?

It is a built-in function of the algorithm header file that is used to organise containers such as arrays and vectors. Internally, Quick-sort is used to implement this function.

Python employs the Timsort algorithm. Timsort is a hybrid sorting algorithm that combines merge sort and insertion sort to produce good results on a wide range of real-world data.

What is the difference between sort and sorted function in Python?

Sort() sorts the list in place, changing its indexes and returning None, whereas sorted() returns a new sorted list while leaving the original list unaltered. Another distinction is that sorted() allows any iterable, whereas list only accepts a single iterable. Sort() is a list class method that can only be used with lists.

Conclusion

This article discussed the problem of checking if there exists a subarray that, when reversed, makes the whole array sorted. Once you are done with this, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

We hope that this blog has helped you increase your knowledge regarding such DSA problems, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"

Previous article
Print Next Greater Number of Q Queries
Next article
Smallest Difference Triplet from Three arrays
Live masterclass