I was asked the below question in an interview:

```
Given an array of integers, write a method to find indices m and n such that
if you sorted elements m through n, the entire array would be sorted. Minimize
n-m. i.e. find smallest sequence.
```

find my answer below and please do comment on the solution. Thanks!!!

I think the way i came to the solution, i should provide and please do comment if it's incorrect and also correct.

Lets take an example:

```
int a[] = {1,3,4,6,10,6,16,12,13,15,16,19,20,22,25}
```

Now if i will put this in to the graph (X-coordinate -> array index and Y-coordinate -> array's value) then the graph will look like as below:

Now if we see the graph there are two places where dip happens one is after 10 and another after 16. Now in the zig zag portion if we see the min value is 6 and max val is 16. So the portion which we should sort to make the whole array sorted is between (6,16). Please refer to the below image:

Now we can easily divide the array in to three part. And middle part the one which we want to sort so that the whole array will be sorted. Please provide your valuable inputs. I tried to explain to my label best, please let me know if i want to explain more. Waiting for valuable inputs.

The below code implements the above logic:

```
public void getMN(int[] a)
{
int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE;
for(int i=1; i<a.length; i++)
{
if(a[i]<a[i-1])
{
if(a[i-1] > max)
{
max = a[i-1];
}
if(a[i] < min)
{
min = a[i];
}
}
}
if(max == Integer.MIN_VALUE){System.out.println("Array already sorted!!!");}
int m =-1, n =-1;
for(int i=0; i<a.length; i++)
{
if(a[i]<=min)
{
m++;
}
else
{
m++;
break;
}
}
for(int i=a.length-1; i>=0; i--)
{
if(a[i]>=max)
{
n++;
}
else
{
n++;
break;
}
}
System.out.println(m +" : "+(a.length-1-n));
System.out.println(min +" : "+max);
}
```

Actually, I came up with something like that:

```
public static void sortMthroughN(int[] a)
{
int m = -1;
int n = -1;
int k = -1;
int l = -1;
int biggest;
int smallest;
// Loop through to find the start of the unsorted array.
for(int i = 0; i < a.length-1; i++)
if(a[i] > a[i+1]) {
m = i;
break;
}
// Loop back through to find the end of the unsorted array.
for(int i = a.length-2; i > 0; i--)
if(a[i] > a[i+1]) {
n = i;
break;
}
biggest = smallest = a[m];
// Find the biggest and the smallest integers in the unsorted array.
for(int i = m+1; i < n+1; i++) {
if(a[i] < smallest)
smallest = a[i];
if(a[i] > biggest)
biggest = a[i];
}
// Now, let's find the right places of the biggest and smallest integers.
for(int i = n; i < a.length-1; i++)
if(a[i+1] >= biggest) {
//1
k = i+1;
break;
}
for(int i = m; i > 0; i--)
if(a[i-1] <= smallest) {
//2
l = i-1;
break;
}
// After finding the right places of the biggest and the smallest integers
// in the unsorted array, these indices is going to be the m and n.
System.out.println("Start indice: " + l);
System.out.println("End indice: " + k);
}
```

But, I see that results are not the same with your solution @Trying, did i misunderstand the question? By the way, at the and of your code, it prints

```
4 : 9
6 : 16
```

What are these? Which ones are indices?

Thanks.

EDIT: by adding place marked as 1 this:

```
if(a[i+1] == biggest) {
k = i;
break;
}
```

and 2:

```
if(a[i+1] == smallest) {
l = i;
break;
}
```

it is better.

It's easier to find the max value starting from the end of array:

```
public void FindMinSequenceToSort(int[] arr)
{
if(arr == null || arr.length == 0) return;
int m = 0, min = findMinVal(arr);
int n = arr.length - 1, max = findMaxVal(arr);
while(arr[m] < min)
{
m ++;
}
while(arr[n] > max)
{
n --;
}
System.out.println(m);
System.out.println(n);
}
private int findMinVal(int[] arr)
{
int min = Integer.MAX_VALUE;
for(int i = 1; i < arr.length; i++)
{
if(arr[i] < arr[i-1] && arr[i] < min)
{
min = arr[i];
}
}
return min;
}
private int findMaxVal(int[] arr)
{
int max = Integer.MIN_VALUE;
for(int i = arr.length - 2; i >= 0; i--)
{
if(arr[i] >= arr[i+1] && arr[i] > max)
{
max = arr[i];
}
}
return max;
}
```

Actually, you can have two pointers and the last pointer moves backward to check start index of the shortest unsorted sequence. It's kind of O(N2) but it is more cleaner.

```
public static int[] findMinUnsortedSequence(int[] array) {
int firstStartIndex = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < i; j++) {
if (array[j] <= array[i]) {
startIndex = j + 1;
} else {
endIndex = i;
if (firstStartIndex == 0) {
firstStartIndex = startIndex;
}
}
}
}
return new int[]{firstStartIndex, endIndex};
}
```

Similar Questions

I'm having a hard time solving this problem. A[1..n] is an array of real numbers which is partially sorted: There are some p,q (1 <= p <= q <=n) so: A[1] <= ... <= A[p] A[p] >= ... &

How can I use Whole Program Optimization feature in Free Pascal 2.7.1 on Windows? I get this error: Project1.dpr(92,1) Fatal: Cannot find nm.exe or to extract symbol liveness information from l

I have a page that contains a table like the following (automatically sorted by Name column) Name Open Num Total Num ----------------------------------- Doe, John 0 0 Smith, Sarah 4 3 Tyler, Rose 7

I have 4 arrays that I need to combine into 1 by adding all the corresponding cells. So I would add up Cell 1,1 (row 1, column 1) of all 4 matrices and put that into Cell 1,1 of the resultant matrix.

On sorting an array i get : 1,10,2,3,4,5,6,7,8,9. What went wrong ? My code was: NSArray *sortedArray = [optionKeys sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)]; where optio

I am trying to learn and implement a min-heap to solve a problem: Loop that creates doubles and insert them into sorted array, in C Basically, I start with a set of doubles, sorted from smallest to la

I'm newbie in laravel 4.0. How to get the whole array from lang/en/texts.php? Is there a Lang::getAll() method? My goal is to generate keywords/description in my base controller, to fill them into t

I have this array $data['key'] = array(11,5,7); $data['value'] = array(78,54,96); I have sorted it based on value. So now I have - $data['key'] = (5,11,7); $data['value'] = (54,78,96); How can i get

I have a sorted array ( in ascending order) and I want to find the subscript of a number in the array which is the the next highest number to a given number. For example,if I have 67 as a given number

I have a sorted array of integers: {1,2,4,4,5,8,12,15,15,23,54} I want to find how many numbers in that array fall between a range, say 4 and 15. {4,4,5,6,12,15,15} So, there are 7 items in the arr

Does anybody knows how can I get the max and min value of the 2nd and 3rd columns in PHP? $ar = array(array(1, 10, 9.0, 'HELLO'), array(1, 11, 12.9, 'HELLO'), array(3, 12, 10.9, 'HELLO')); Output sho

I have a script to add items to a db. currently I have an array being created like this: foreach(blah as $album){ $add[] = array('album' => $album['name'], 'test' => $album['test'] ); } // end f

There is a sorted array which is of very large size. In it every element is repeated more than once except one element. How can I find the unrepeated element in O(log n) time complextiy.

I have a javascript array that I'd like to be sorted according to a number or string that I specify. I'd like the array to appear to be randomly sorted, but the array would always be sorted the same i

I have an array of objects of the following form: arr[0] = { 'item1' : 1234, 'item2' : 'a string' }; I sort it first by 'item1' which is straightforward. Now i want to sort arr (which is sorted by 'i

I have a Sorted set and want to get all members of set. How to identify a max/min score for command : zrange key min max ?

I have a hashmap, I wish to get an array of the keys in this hashmap, but I wish for the array to be sorted. For instance if the map looks like this: <2,obj1> <4,obj2> <6,obj3>

I have a reference array which contains all possible elements and is sorted in custom order different than alphanumeric sorting. For example, @ref_array = ('one','two','three','four','five','six'); N

I have an array a of 100 integers. What is a recommended way to find the min value in a[3] through a[70] AND the index of this min value? Assuming no duplication of values. I know the clumsy way of lo

In my little project here I have sorted a list in decending order, however, my goal is to sort it in this custom pattern. (largest -> smallest -> next largest -> next smallest ->)etc. In

Possible Duplicate: How do I randomly fill an array in Java? The last line of code below prints numbers in order. How to create an array where value are sorted randomly? List<Users> u = new A

I have following array: float[] arr = { 0, 0.1f, 0, 0.1f, 0, 0.2f }; What is the most elegant way to select min value that is bigger than 0 or bigger than some other value? I've tried using Min() and

In revising for an upcoming exam here is my solution to finding the min value of an array using 2 threads. I had to create a wrapper for int to pass the minimum value around by reference. What do you

Given a sorted array of integers, how can we find a pair of integers that sum to K? e.g. array = 1,3,5,6,0, K = 6, the answer is 1 and 5. Time complexity should be minimized.

Hey guys, how would you erase a whole array, as in it has no items. I want to do this so I could store new values (a new set of 100 floats) into it and find the minimum. Right now my program is readin

It has been done to death pretty much, here on SO and around the 'Net. However I was wondering if there was a way to leverage the standard min/max functions of: Array.max = function(array) { return Ma

Possible Duplicate: Searching a number in a rotated sorted Array Say the original list is 1 2 3 4 5 6 7 8 9 10 and u shift it so that it becomes 5 6 7 8 9 10 1 2 3 4 so say i want to check if 7 is i

So I'm working on project for my algorithms class that I'm currently taking. I'm doing some research online and see that some people are using an ArrayList<Integer> and some people are using an

In bash I'have a sorted integer array like: array[0]=1 array[1]=2 array[2]=3 array[3]=4 array[4]=7 array[5]=9 array[6]=10 array[7]=13 array[8]=15 array[9]=16 And I want to obtain output like: 1-4,7,

In c++, std::set which stores its element in sorted order can insert elements in O(log n) time. But all the methods i know take linear time: Inserting the element at the end of the array and swapping

I have two time pickers to let the user specify when he started and when he ended a job. With the way it works by default, the widget latest hour is 23:45 considering intervals of 15min. So the user w

The size of dynamic array is the twice the size of static array. I want to assign the values which starts from (N/2)-1 to N-1 of dynamic array to whole static array. The only way is copying the values

So, you have n sorted arrays (not necessarily of equal length), and you are to return the kth smallest element in the combined array (i.e the combined array formed by merging all the n sorted arrays)

Need Hints to design an efficient algorithm that takes the following input and spits out the following output. Input: two sorted arrays of integers A and B, each of length n Output: One sorted array t

i created an dinamic lib called InterfaceLayer.so when I call nm InterfaceLayer i get a symbol which is: 00000e28 T _Z5startv for example, but I expected it to be just start as the name of the func

I have seen answers to the question: Is it possible to arrange a numpy array (or python list) by using the indexes of the elements in decreasing order? (eg. Finding the Index of N biggest elements in

I came across this question in one Interview. Please help me in getting the solution. Question is: You have sorted rotatable array, i.e. the array contains elements which are sorted and it can

I have a set set of records that I am loading from a file and the first thing I need to do is get the max and min of a column. In SQL I would do this with a subquery like this: select c.state, c.popu

import java.util.*; public abstract class Player { abstract String nm; public abstract void displayDetails(); } class Booking extends Player { nm = Sam; void displayDetails() { System.out.println(N

Say I have an array of the following class sorted in ascending order by y: public class Obj { public int x; public int y; } How can I find the number of Obj items in the array that have y values with

I know how to put an array in order, but in this case I just want to see if it is in order. An array of strings would be the easiest, I imagine, and answers on that front are appreciated, but an answe

I am getting values which are sorted from a plist and displaying them in a tableview. I am providing the capability of entering a custom category which will be written to plist. But I want that to be

I have a sorted list and I want to insert a string if it matches the pattern in list. Example : Sorted List ['Amy Dave', 'Dee Waugh', 'Eva A', 'Gin', 'Joy Kola', 'Kay Min', 'Mae', 'Pam Deing'] Above

Suppose we have a min heap with some elements which satisfy the heap property. What happens if I change the algorithm from min heap to max heap without rearrange the internal array? That is, if I keep

I wrote this code to read N lines from console input and put it into array of string, but it's reading N-1 lines Any suggestions ? #include<iostream> #include<stdio.h> #include<string&g

I'm trying to implement a Min Heap in Java, but I'm having issues with inserting and removing elements (inserting at the end, removing the root as min). It seems to work for the most part (I use a pro

I have a problem with getting the min,max, and average of an elements of 2D array. I have a 2D array which contains Students and Grades. I am generating the grades with rand. For example When I enter

What is an easy way in Java to sort the array of elements maintaining information about indexes where the elements were stored in the original array? Is there a built-in function? There are few ways I

Given an array of integers, I would like to find the minimum number x such that increasing or decreasing the elements in the array by a number in the range of 0 to x will result in an array sorted in

I'm working on a homework problem and I'm having some difficulties creating a O(n*logn) solution. I need to write a function that takes a pre-sorted array and a value to search for. I then need to fin