Google Onsite 2020 pt1

input: unsorted unique array
return the indices where: 
i < j < k and arr[i] < arr[j] < arr[k] strictly not equal
just find first match

/** 

Example 1)
input: [1, 3, 2, 7, 5]
output: [0, 1, 3]


input: [5, 1, 2, 7, 3]
output: [1, 2, 3]

input: [1, 7, 3, 5]
output: [0, 2, 3]

*/


public int[] find3Indices(int[] arr) {
	int i=-1, j=-1, k=-1;
	int[] resultArr = new int[3];

	for (int index=0; index < arr.length; index++) {
		if (i == -1) {
			i = index;
		} else if ((i != -1) && (j == -1)) {
			if (arr[i] > arr[index]) {
				i = index; // i = 0
			} else {
				// only set j if i is set and value is bigger
				j = index; // j = 1
			}
		} else if ((j != -1) && (arr[j] < arr[index])) {
			// only set k if j is set
			if ((arr[j] > arr[index]) && (arr[i] < arr[index])) {
				// update j index
				j = index
			} else {
				k = index;
				break; // because you found all three!
			}
		}
	}

	if ((i != -1) && (j != -1) && (k != -1)) {
		// populate resultArr if all found
		resultArr[0] = i;
		resultArr[1] = j;
		resultArr[2] = k;
	}

	// return empty array if nothing found
	return resultArr;
}
Time: O(n)
Space: O(n) // even though just populating 3 elements