Sorting Of A Rotated Sorted Array

Easy
0/40
Average time to solve is 10m
profile
Contributed by
6 upvotes
Asked in companies
AdobeHikeUnthinkable Solutions

Problem statement

Given a rotated sorted array of size ‘N’ and let the elements of the given array be a1,a2,......,an . You need to sort the given array in increasing order.

For Example - Consider ‘N’ = 4 and the given array is [2,3,4,1] then the output should be [1,2,3,4].

A rotated sorted array is a sorted array in which each element is shifted ‘x’ (‘x’ >= 0 and ‘x’ <= ’N’) times to its right and the rightmost element is shifted to the beginning of the array.

For Example - [3,4,1,2] is a rotated sorted array in which each element is shifted two times to its right.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows. 

The first line of each test case contains an integer ‘N’ denoting the size of the given rotated sorted array.

The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the given rotated sorted array.
Output Format : 
For each test case, print a single line containing 'N' single space-separated integers representing the elements of the sorted array.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
1 <= N <= 10^4
-10^9 <= a[i] <= 10^9 

Where ‘T’ is the total number of test cases, ‘N’ is the size of the array and a[i] is an element of the array.

Time Limit: 1 sec
Sample Input 1 :
2
5
6 8 9 2 3
6
7 8 9 1 3 5
Sample Output 1 :
2 3 6 8 9
1 3 5 7 8 9
Explanation of Sample Input 1 :
Test case 1 :
The given array [6,8,9,2,3] is rotated around index 3 so the required array after sorting will be [2,3,6,8,9].

Test case 2 :
The given array [7,8,9,1,3,5] is rotated around index 3 so the required array after sorting will be [1,3,5,7,8,9].
Sample Input 2 :
2
6
9 1 3 5 7 8
4
4 5 2 3
Sample Output 2 :
1 3 5 7 8 9
2 3 4 5
Hint

Shift the elements of array one at a time.

Approaches (3)
Brute Force
  • Find the rotation point is the rotated array using linear search and store its index in a variable ‘shiftCount’.
  • Run a while loop ‘shiftCount’ times and in each iteration do the following:
    • Store the element at index 0 in variable ‘leftElement’
    • Shift each element with index > 0 to its left.
    • Store the element stored in ‘leftElement at the last index.

 

 

 

Before Iteration

After Iteration

Time Complexity

O(N^2), Where ‘N’ is the number of elements in the given array.

 

In the worst case, each shift operation in the array will require nearly O(N) time and the maximum number of times this shifting needs to be done will be  ‘N’.

Space Complexity

O(1)

 

Changes will be made in the given array itself. Hence, no extra space is used.

Code Solution
(100% EXP penalty)
Sorting Of A Rotated Sorted Array
Full screen
Console