The challenge
Given an array of integers, arr, find out 2 indices m, n(0<=m<=arr.length-1, 0<=n<=arr.length-1, m<=n), so that as long as all elements in the subarray(from index m to n, indices m and n inclusive) are sorted properly, with this sorted subarray relacing original subarray, the whole array is sorted (no matter ascendingly or descendingly).
The subarray should include the least number of elements, means (n-m) must be of the smallest value, and n should also be the smallest one.
The function accept an array of integers, arr, reutrn the subarray’s start and end index in array format, [m,n] as a result.
For example, in an array [1,2,3,6,4,4], the SMALLEST(with the least numbers of integers) subarray to be found is [6,4,4], if we sort it to [4,4,6], then replace the original subarray, the whole array now turns to be[1,2,3,4,4,6], which is sorted completely. This subarray begins from index 3, and ends in index 5, so the result is [3,5].
If all elements in the array are the same, return array [0,0]. If all elements in the array are already sorted, no matter ascendingly or descendingly, return [0,0] as well.
The solution in Java code
Option 1:
public class FindIndexOfSubArray {
private int[] arr;
final boolean aval;
public FindIndexOfSubArray(int[] arr) {
this.arr = arr;
aval = arr[arr.length - 1] - arr[0] < 0;
}
public int[] findIndexOfSubArray(){
int[] size = {arr.length, 0};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (aval && arr[i] < arr[j] || !aval && arr[i] > arr[j]) {
size[0] = Math.min(i, size[0]);
size[1] = Math.max(j, size[1]);
}
}
}
return size[0] < arr.length ? size : new int[2];
}
}
Option 2:
import java.util.Arrays;
public class FindIndexOfSubArray {
private int[] arr;
public FindIndexOfSubArray(int[] arr) {
this.arr = arr;
}
public int[] findIndexOfSubArray(){
int [] someArr = new int[arr.length];
for (int i = 0; i <arr.length ; i++) {
someArr[i] = arr[i];
}
Arrays.sort(someArr);
if (arr[0] > arr[arr.length-1]) {
for (int i = 0; i < someArr.length/2; i++) {
int temp =someArr[i];
someArr[i] = someArr[someArr.length-1-i];
someArr[someArr.length-1-i] = temp;
}
}
boolean check = true;
int m = 0;
int n = 0;
for (int i = 0; i <arr.length ; i++) {
if (arr[i] != someArr[i] && check) {
m = i;
check = false;
}
}
check = true;
for (int i = arr.length-1; i >=0 ; i--) {
if (arr[i] != someArr[i] && check) {
n = i;
check = false;
}
}
System.out.println(m+ " "+ n);
return new int[] {m, n};
}
}
Option 3:
import java.util.Arrays;
import java.util.stream.IntStream;
class FindIndexOfSubArray {
private int[] arr;
public FindIndexOfSubArray(int[] arr) {
this.arr = arr;
}
public int[] findIndexOfSubArray(){
int[] ascending = Arrays.stream(this.arr).sorted().toArray();
int[] descending = IntStream.rangeClosed(1, ascending.length).map(i -> ascending[ascending.length-i]).toArray();
int m = 0; int n = 0;
int a = 0; int b = 0;
for (int i = 0; i < this.arr.length; i++) {
if (this.arr[i] != ascending[i]) {
n = i; break;
}
}
for (int i = this.arr.length-1; i > 0; i--){
if (this.arr[i] != descending[i]){
m = i; break;
}
}
for (int i = 0; i < this.arr.length; i++) {
if (this.arr[i] != descending[i]) {
a = i; break;
}
}
for (int i = this.arr.length-1; i > 0; i--){
if (this.arr[i] != ascending[i]){
b = i; break;
}
} return Math.abs(n - m) > Math.abs(a - b) ? new int[]{a, b} : new int[]{n, m};
}
}
Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertTrue;
import org.junit.runners.JUnit4;
import java.util.Arrays;
public class SolutionTest {
@Test
public void testSomething1() {
int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3, 6, 4, 4}).findIndexOfSubArray();
assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething2() {
int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3}).findIndexOfSubArray();
assertTrue("should return [0,0]", Arrays.deepEquals(new Integer[]{0, 0}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething3() {
int[] actual = new FindIndexOfSubArray(new int[]{1, 1, 1}).findIndexOfSubArray();
assertTrue("should return [0,0]", Arrays.deepEquals(new Integer[]{0, 0}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething4() {
int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3, 6, 5, 4}).findIndexOfSubArray();
assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething5() {
int[] actual = new FindIndexOfSubArray(new int[]{6, 5, 4, 1, 2, 3}).findIndexOfSubArray();
assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething6() {
int[] actual = new FindIndexOfSubArray(new int[]{9, 2, 32, 123, 3, 2, 2}).findIndexOfSubArray();
assertTrue("should return [0,4]", Arrays.deepEquals(new Integer[]{0, 4}, new Integer[]{actual[0], actual[1]}));
}
}
Additional Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertTrue;
import java.util.Arrays;
import java.util.Random;
public class SolutionTest {
@Test
public void testSomething1() {
int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3, 6, 4, 4}).findIndexOfSubArray();
assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething2() {
int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3}).findIndexOfSubArray();
assertTrue("should return [0,0]", Arrays.deepEquals(new Integer[]{0, 0}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething3() {
int[] actual = new FindIndexOfSubArray(new int[]{1, 1, 1}).findIndexOfSubArray();
assertTrue("should return [0,0]", Arrays.deepEquals(new Integer[]{0, 0}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething4() {
int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3, 6, 5, 4}).findIndexOfSubArray();
assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething5() {
int[] actual = new FindIndexOfSubArray(new int[]{6, 5, 4, 1, 2, 3}).findIndexOfSubArray();
assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
}
@Test
public void testSomething6() {
int[] actual = new FindIndexOfSubArray(new int[]{9, 2, 32, 123, 3, 2, 2}).findIndexOfSubArray();
assertTrue("should return [0,4]", Arrays.deepEquals(new Integer[]{0, 4}, new Integer[]{actual[0], actual[1]}));
}
private int[] generateExpectedResult(int[] arr) {
int[] clone = Arrays.copyOf(arr, arr.length);
Arrays.sort(clone);
int[] mnAsc = findIndex(arr, clone);
int temp;
for (int i = 0, j = clone.length - 1; i <= j; i++, j--) {
temp = clone[i];
clone[i] = clone[j];
clone[j] = temp;
}
int[] mnDesc = findIndex(arr, clone);
return mnAsc[1] - mnAsc[0] <= mnDesc[1] - mnDesc[0] ? mnAsc : mnDesc;
}
private int[] findIndex(int[] arr, int[] sorted) {
int m = -1, n = -1;
for (int i = 0; i < sorted.length; i++) {
if (arr[i] != sorted[i]) {
m = i;
break;
}
}
for (int i = sorted.length - 1; i >= 0; i--) {
if (arr[i] != sorted[i]) {
n = i;
break;
}
}
return new int[]{Math.max(m, 0), Math.max(n, 0)};
}
@Test
public void testSomethingRandom() {
for (int i = 50; i < 100; i++) {
int[] data = testDataGenerator(i);
int[] actual = new FindIndexOfSubArray(data).findIndexOfSubArray();
int[] expected = generateExpectedResult(data);
assertTrue(String.format("should return [%d,%d]", expected[0], expected[1]),
Arrays.deepEquals(new Integer[]{expected[0], expected[1]}, new Integer[]{actual[0], actual[1]}));
}
}
private int[] testDataGenerator(int size) {
int[] temp = new int[size];
int[] prefix = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int[] suffix = new int[]{101, 102, 103, 104, 105, 106, 107, 108, 109, 110};
Random random = new Random();
for (int i = 0; i < size; i++) {
temp[i] = random.nextInt(100);
}
if (random.nextBoolean()) {
for (int j = 0; j < 10; j++) {
temp[j] = prefix[j];
}
} else {
for (int j = size - 10, k = 0; j < size && k < 10; j++, k++) {
temp[j] = suffix[k];
}
}
return temp;
}
}
