MINIMUM LENGTH UNSORTED SUBARRAY

      MINIMUM LENGTH UNSORTED SUBARRAY

                                               Image result for java
                                             
Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.
Examples: 
1) If the input array is [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], your program should be able to find that the subarray lies between the indexes 3 and 8.
2) If the input array is [0, 1, 15, 25, 6, 7, 30, 40, 50], your program should be able to find that the subarray lies between the indexes 2 and 5

Input and Output Format: 
The first line of the input consists of an integer, n that corresponds to the number of elements in the input array.
The next 'n' lines in the input correspond to the elements in the array.
Output is an array of integers.

Sample Input1: 
11
10
12
20
30
25
40
32
31
35
50
60
Sample Output1: 
The unsorted subarray which makes the given array sorted lies between the indexes 3 and 8
 
Sample Input2: 
5
1
3
5
7
9
Sample Output1: 
The complete array is sorted

Code:
  1. import java.util.*;
  2. class Hello {

  3.     public static void main(String[] args) {
  4.             int i,start=0,end=0,flag=0,flag1=0,sorted=0;
  5.             Scanner sc=new Scanner(System.in);
  6.             int n=sc.nextInt();
  7.             int[] arr=new int[n];
  8.             int[] arr1=new int[n];
  9.             for(i=0;i<n;i++)
  10.                 {
  11.                     arr[i]=sc.nextInt();
  12.                     arr1[i]=arr[i];
  13.                 }
  14.             Arrays.sort(arr1);
  15.                           if(Arrays.equals(arr,arr1))
  16.                 {
  17.                     System.out.println("sorted array");
  18.                     sorted=1;
  19.                 }
  20.                 else
  21.                 for(i=0;i<n;i++)
  22.                 {
  23.                    if(flag==0)
  24.                    if(arr[i]!=arr1[i])
  25.                    {
  26.                        start=i;
  27.                        flag=1;
  28.                    }
  29.                 }
  30.                 for(i=n-1;i>=0;i--)
  31.                 {
  32.                     if(flag1==0)
  33.                         if(arr[i]!=arr1[i])
  34.                             {
  35.                                 end=i;
  36.                                 flag1=1;
  37.                             }
  38.                 }
  39.                 if(sorted==0)
  40.                 System.out.println("start= "+start+"end= "+end);
  41. }
  42. }

Add a Comment

Your email address will not be published. Required fields are marked *