Given an array of N numbers where a subarray is sorted in descending order and rest of the numbers in the array are in ascending order. The task is to sort an array where a subarray of a sorted array is in reversed order.
Examples:
Input: 2 5 65 55 50 70 90
Output: 2 5 50 55 65 70 90
The subarray from 2nd index to 4th index is in reverse order.
So the subarray is reversed, and the sorted array is printed.Input: 1 7 6 5 4 3 2 8
Output: 1 2 3 4 5 6 7 8
A naive approach will be to sort the array and print the array. Time Complexity of this approach will be O(N log n).
An efficient approach will be to find and store the starting index and ending index of the reversed subarray. Since the subarray is in descending order and the rest of the elements are in ascending order, only reversing the subarray will sort the complete array. Reverse the subarray using two pointer approach.
Below is the implementation of the above approach:
C++
// C++ program to sort an array where// a subarray of a sorted array// is in reversed order#include <bits/stdc++.h>using namespace std;// Function to print the sorted array// by reversing the subarrayvoid printSorted(int a[], int n){ int front = -1, back = -1; // find the starting index of the // reversed subarray for (int i = 1; i < n; i++) { if (a[i] < a[i - 1]) { front = i - 1; break; } } // find the ending index of the // reversed subarray for (int i = n - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { back = i + 1; break; } } // if no reversed subarray is present if (front == -1 and back == -1) { for (int i = 0; i < n; i++) cout << a[i] << " "; return; } // swap the reversed subarray while (front <= back) { // swaps the front and back element // using c++ STL swap(a[front], a[back]); // move the pointers one step // ahead and one step back front++; back--; } for (int i = 0; i < n; i++) cout << a[i] << " ";}// Driver Codeint main(){ int a[] = { 1, 7, 6, 5, 4, 3, 2, 8 }; int n = sizeof(a) / sizeof(a[0]); printSorted(a, n); return 0;} |
Java
// Java program to sort an array where// a subarray of a sorted array// is in reversed orderimport java.io.*;class GFG{// Function to print the sorted array// by reversing the subarraystatic void printSorted(int a[], int n){ int front = -1, back = -1; // find the starting index of the // reversed subarray for (int i = 1; i < n; i++) { if (a[i] < a[i - 1]) { front = i - 1; break; } } // find the ending index of the // reversed subarray for (int i = n - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { back = i + 1; break; } } // if no reversed subarray is present if (front == -1 && back == -1) { for (int i = 0; i < n; i++) System.out.println(a[i] + " "); return; } // swap the reversed subarray while (front <= back) { // swaps the front and back element // using c++ STL int temp = a[front]; a[front] = a[back]; a[back] = temp; // move the pointers one step // ahead and one step back front++; back--; } for (int i = 0; i < n; i++) System.out.print(a[i] + " ");}// Driver Codepublic static void main (String[] args){ int a[] = { 1, 7, 6, 5, 4, 3, 2, 8 }; int n = a.length; printSorted(a, n);;}}// This code is contributed by anuj_67.. |
Python3
# Python 3 program to sort an array where# a subarray of a sorted array is in # reversed order# Function to print the sorted array# by reversing the subarraydef printSorted(a, n): front = -1 back = -1 # find the starting index of the # reversed subarray for i in range(1, n, 1): if (a[i] < a[i - 1]): front = i - 1 break # find the ending index of the # reversed subarray i = n - 2 while(i >= 0): if (a[i] > a[i + 1]): back = i + 1 break i -= 1 # if no reversed subarray is present if (front == -1 and back == -1): for i in range(0, n, 1): print(a[i], end = " ") return # swap the reversed subarray while (front <= back): # swaps the front and back element # using c++ STL temp = a[front] a[front] = a[back] a[back] = temp # move the pointers one step # ahead and one step back front += 1 back -= 1 for i in range(0, n, 1): print(a[i], end = " ") # Driver Codeif __name__ == '__main__': a = [1, 7, 6, 5, 4, 3, 2, 8] n = len(a) printSorted(a, n)# This code is contributed by# Sahil_Shelangia |
C#
// C# program to sort an array where // a subarray of a sorted array // is in reversed order using System;class GFG{// Function to print the sorted array // by reversing the subarray static void printSorted(int []a, int n) { int front = -1, back = -1; // find the starting index of the // reversed subarray for (int i = 1; i < n; i++) { if (a[i] < a[i - 1]) { front = i - 1; break; } } // find the ending index of the // reversed subarray for (int i = n - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { back = i + 1; break; } } // if no reversed subarray is present if (front == -1 && back == -1) { for (int i = 0; i < n; i++) { Console.Write(a[i] + " "); } return; } // swap the reversed subarray while (front <= back) { // swaps the front and back element // using c++ STL swap(a, front, back); // move the pointers one step // ahead and one step back front++; back--; } for (int i = 0; i < n; i++) { Console.Write(a[i] + " "); }}static void swap(int[] a, int front, int back) { int c = a[front]; a[front] = a[back]; a[back] = c;}// Driver Code public static void Main() { int []a = {1, 7, 6, 5, 4, 3, 2, 8}; int n = a.Length; printSorted(a, n);}}// This code contributed by 29AjayKumar |
PHP
<?php// PHP program to sort an array where// a subarray of a sorted array// is in reversed order// Function to print the sorted array// by reversing the subarrayfunction printSorted($a, $n){ $front = -1; $back = -1; // find the starting index of the // reversed subarray for ($i = 1; $i < $n; $i++) { if ($a[$i] < $a[$i - 1]) { $front = $i - 1; break; } } // find the ending index of the // reversed subarray for ($i = $n - 2; $i >= 0; $i--) { if ($a[$i] > $a[$i + 1]) { $back = $i + 1; break; } } // if no reversed subarray is present if ($front == -1 && $back == -1) { for ($i = 0; $i < $n; $i++) echo $a[$i] . " "; return; } // swap the reversed subarray while ($front <= $back) { // swaps the front and back element // using c++ STL $temp = $a[$front]; $a[$front] = $a[$back]; $a[$back] = $temp; // move the pointers one step // ahead and one step back $front++; $back--; } for ($i = 0; $i < $n; $i++) echo $a[$i] . " ";}// Driver Code$a = array(1, 7, 6, 5, 4, 3, 2, 8);$n = sizeof($a);printSorted($a, $n);// This code is contributed // by Akanksha Rai |
Javascript
<script>// JavaScript program to sort an array where// a subarray of a sorted array// is in reversed order // Function to print the sorted array // by reversing the subarray function printSorted(a , n) { var front = -1, back = -1; // find the starting index of the // reversed subarray for (i = 1; i < n; i++) { if (a[i] < a[i - 1]) { front = i - 1; break; } } // find the ending index of the // reversed subarray for (i = n - 2; i >= 0; i--) { if (a[i] > a[i + 1]) { back = i + 1; break; } } // if no reversed subarray is present if (front == -1 && back == -1) { for (i = 0; i < n; i++) document.write(a[i] + " "); return; } // swap the reversed subarray while (front <= back) { // swaps the front and back element // using c++ STL var temp = a[front]; a[front] = a[back]; a[back] = temp; // move the pointers one step // ahead and one step back front++; back--; } for (i = 0; i < n; i++) document.write(a[i] + " "); } // Driver Code var a = [ 1, 7, 6, 5, 4, 3, 2, 8 ]; var n = a.length; printSorted(a, n);// This code is contributed by todaysgaurav </script> |
Output
1 2 3 4 5 6 7 8
Time Complexity: O(n)
Auxiliary Space: O(1)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
