Algorithm - max left submatrix with fewer elements
I am working on a program where I need to get the index of an element in an array of integers so that all elements to the right of the index are greater than all elements from 0
that index position.
For example:
Case : 1
- given input - { 5, -2, 3, 8, 6 }
then I need index position as 2 (i.e array element with value 3)
because all elements after index 2 are greater than all elements from index 0
to index 2
, that is {5, - 2,3}
Case : 2
- For a given input - { -5, 3, -2, 8, 6 }
I need the index position as 2 (i.e array element with value -2)
because all elements after index 2 are greater than all elements from index 0
to index 2
, that is, {-5, 3, -2}
Here is my Java program:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class ArrayProgram {
public static void main(String[] args) {
int[] array1 = { 5, -2, 3, 8, 6 };
int[] array2 = { -5, 3, -2, 8, 6 };
process(array1);
process(array2);
}
private static void process(int[] array) {
List<Integer> list = new ArrayList<Integer>();
int maxIndex = 0;
list.add(array[0]);
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] <= Collections.max(list)) {
list.add(array[i]);
maxIndex = i;
}
}
System.out.println("index = " + maxIndex + ", element = " + array[maxIndex]);
}
}
Program output:
[5, -2, 3, 8, 6]
index = 2, element = 3
[-5, 3, -2, 8, 6]
index = 0, element = -5
It works for case 1
, but doesn't work for case 2
. Could you please help me with this. Is there any other better way to solve this problem,
source to share
Unfortunately, your solution has several logical errors. One counterexample: [2, 1, 3, 6, 5]
(your algorithm returns the index 1
, but the answer 2
).
I suggest another solution with time complexity O(n)
:
- Navigate from left to right, calculating the maximum items in the interval
[0..i]
. - Iterate from right to left, calculating the minimum of elements in the interval
[i+1..n]
and comparing this minimum to the maximum of elements on the left that were previously calculated in the first step.
Implementation example:
static void process(int[] array) {
int n = array.length;
if (n < 2) return;
int[] maxLeft = new int[n];
maxLeft[0] = array[0];
for (int i = 1; i < n; ++i) {
maxLeft[i] = Math.max(maxLeft[i-1], array[i]);
}
int minRight = array[array.length-1];
for (int i = n-2; i >= 0; --i) {
if (maxLeft[i] < minRight) {
System.out.println("index = " + i + ", element = " + array[i]);
return;
}
minRight = Math.min(minRight, array[i]);
}
}
Runnable: http://ideone.com/mmfvmH
source to share
Modified my comment for the answer. Start at the end of the array, right will have only one element, and left will have n - 1 elements. Then check the condition that the maximum on the left is <minumum right, if that is true then it is done, otherwise move the pointer to the left and check it again.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class ArrayProgram {
public static void main(String[] args) {
int[] array1 = { 5, -2, 3, 8, 6 };
int[] array2 = { -5, 3, -2, 8, 6 };
int[] array3 = { 1, 3, 5, 8, 4 };
int[] array4 = { 1, 1, 1, 1, 1 };
process(array1);
process(array2);
process(array3);
process(array4);
}
private static void process(int[] array) {
List<Integer> listLeft = new ArrayList<Integer>();
List<Integer> listRight = new ArrayList<Integer>();
//create an array that consists upto n-1 elements
int arraySize = array.length;
if ( arraySize < 2){
System.out.println("None");
return;
}
for ( int i = 0; i < arraySize - 1; i++){
listLeft.add ( array[i]);
}
//create an array that has the last element
listRight.add ( array[arraySize - 1]);
//iterate from the last adding new elements till the condition satisfies
for ( int i = arraySize - 2; i >= 0; i--){
//if the condition is satisfied exit
if ( Collections.max(listLeft) < Collections.min(listRight)){
System.out.println("index = " + i + ", element = " + array[i]);
return;
}else{
//remove an element from left and add an element to right
listLeft.remove (listLeft.size() - 1);
listRight.add ( array[i]);
}
}
System.out.println("None");
}
}
source to share
I would suggest an algorithm for getting the correct output. It will execute in O (n). Consider the elements n
in arr[]
. Maintain 2 arrays int minElementIndex[]
and maxElementIndex[]
.
-
minElementIndex[i]
stores the index of the minimum value element present in the subarray [(i + 1) ... (n-1)]. ValueminElementIndex[n-1]=n-1
-
maxElementIndex[i]
stores the index of the maximum value element present in the subarray [0 ... (i)]. ValuemaxElementIndex[0]=0
Code for filling minElementIndex [0 ... n-1]
int index=minElementIndex[n-1];
for(int i=n-2;i>=0;i--){
minElementIndex[i] = index;
if(arr[i]<arr[index])
index=i;
}
Code to fill maxElementIndex [0 ... n-1]:
int index=maxElementIndex[0];
for(int i=1;i<n;i++){
if(arr[i]>arr[index])
index=i;
maxElementIndex[i]=index;
}
Now, just iterate over both arrays like this:
for(int i=1;i<n-1;i++){
if(arr[maxElementIndex[i]]< minElementIndex[i]){
System.out.println(i);
}
}
Dry the suggested algorithm.
Case 1: arr[5] = {5,-2,3,8,6}
minElementIndex[5] = {1,2,4,4,4}
and maxElementIndex[5] = {0,0,0,3,3}
. It is clear that when i=2
, arr[maxElementIndex[i]] < arr[minElementIndex[i]]
which is equal to5 < 6
Case 2: arr[5] = {-5,3,-2,8,6}
minElementIndex[5] = {2,2,4,4,4}
and maxElementIndex[5] = {0,1,1,3,3}
. It is clear that when i=2
, arr[maxElementIndex[i]] < arr[minElementIndex[i]]
which is equal to3 < 6
source to share