package algoexpert.hard;

/*

PROBLEM:

Given an array, return the start and end endices of the subarray which when sorted makes the whole array sorted.

- array is at least of length 2

EXAMPLE:

[1,2,4,7,10,11,7,12,6,7,16,18,19] -> [3,9]

LOGIC:

Two ways to solve:

Both -> find min, max numbers not in order and find their position

1. Find range -> MinMax -> Expand

- Find prospective start and end by checking array[i] < array[i+1] & vice versa

- Now that we have a range find its min and max

- expand range : first if any index less than it's index > min from range & vice versa

- return expanded range

2. MinMax -> Expand

- check each elem for OutOfOrder & find min, max elem among them

*/

public class SubarraySort

{

public static void test()

{

int [] test1 = new int[] {1,2,4,7,10,11,7,12,6,7,16,18,19};

int [] test2 = new int[] {2,1};

int [] test3 = new int[] {1,2,4,7,10,11,7,12,7,7,16,18,19};

int [] pair = subarraySort(test3);

System.out.println(pair[0] + ", " + pair[1]);

}

public static int[] subarraySort(int[] array)

{

return solutionTwo(array);

}

// SOLUTION 2

// ========================================================

public static boolean isOutOfOrder(int index, int [] array)

{

if(index == 0)

{ return array[index] > array[index + 1]; }

else if (index == array.length - 1)

{ return array[index] < array[index - 1]; }

else

{ return array[index] > array[index + 1] || array[index] < array[index - 1]; }

}

public static int[] solutionTwo(int[] array)

{

int minElem = Integer.MAX_VALUE;

int maxElem = Integer.MIN_VALUE;

for (int i = 0; i < array.length; ++i)

{

if (isOutOfOrder(i, array))

{

minElem = Integer.min(minElem, array[i]);

maxElem = Integer.max(maxElem, array[i]);

}

}

if (minElem == Integer.MAX_VALUE) { return new int[] {-1, -1}; }

int start = 0;

while (array[start] <= minElem)

{

start += 1;

}

int end = array.length - 1;

while (array[end] >= maxElem)

{

end -= 1;

}

return new int[] {start, end};

}

// SOLUTION 1

// ============================================================

public static int[] findMinMax(int start, int end, int[] array)

{

int min = array[start];

int max = array[end];

for(int i = start; i < end + 1; ++i)

{

if (min > array[i]) { min = array[i]; }

}

for (int i = end; i > start - 1; --i)

{

if (max < array[i]) { max = array[i]; }

}

return new int[] {min, max};

}

public static int[] solutionOne(int[] array)

{

// Find Prospective Range

int first = 0;

while (first < array.length - 1)

{

if (array[first] > array[first + 1])

{ break; }

first += 1;

}

if (first == array.length - 1)

{ return new int[] {-1, -1}; }

int second = array.length - 1;

while (second > 0)

{

if (array[second - 1] > array[second])

{ break; }

second -= 1;

}

// Find Min Max in Prospective Range

int[] minMax = findMinMax(first, second, array);

int minInRange = minMax[0];

int maxInRange = minMax[1];

// Expand

for(int i = 0; i < first; ++i)

{

if (array[i] > minInRange)

{

first = i;

break;

}

}

for(int i = array.length - 1; i > second; --i)

{

if (array[i] < maxInRange)

{

second = i;

break;

}

}

return new int[] {first, second};

}

}