Algorithm - Maximum left sub-array with lesser elements

Question

I am working on a program where I need to get the index of element in an array of integers such that all elements to the right of the index are greater than all the elements from 0 to that index position.

For example:

Case : 1 - Given input - { 5, -2, 3, 8, 6 } then I need the index position as 2 (i.e array element with value 3) because all elements after index 2 are greater than all elements starting from index 0 to index 2 i.e {5,-2,3}

Case : 2 - Given input - { -5, 3, -2, 8, 6 } then 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 starting from index 0 to index 2 i.e {-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]);
    }
}

The program output is :

[5, -2, 3, 8, 6]
index = 2, element = 3
[-5, 3, -2, 8, 6]
index = 0, element = -5

It works for case 1 but fails for case 2. Can you please help me in fixing this. Is there any other better way to solve this,

This algorithm is not working properly. You invented it by yourself or it comes from other site? — ByeBye
– ByeBye, Commented Aug 9, 2017 at 7:55
@ByeBye I just took a scenario and tried implementing it, it is working for few cases only — Learner
– Learner, Commented Aug 9, 2017 at 7:57
Because you need to compute all possib I suggest to sotre in a map, and get min at end — azro
– azro, Commented Aug 9, 2017 at 7:59
in array2[0] value is -5 (negative). in your 2nd example value is 5 (positive). so your program seems to work correctly (since index 1 > value of index 0) — Stefan Warminski
– Stefan Warminski, Commented Aug 9, 2017 at 7:59
In case 2 the array starts with 5 and in code the array2 starts with -5 — Arun Sudhakaran
– Arun Sudhakaran, Commented Aug 9, 2017 at 7:59

DAle · Accepted Answer · 2017-08-09 16:27:01Z

4

Unfortunately, your solution has several logical mistakes. One of the counterexamples: [2, 1, 3, 6, 5] (your algorithm returns index 1, but the answer is 2).

I propose another solution with O(n) time complexity:

Iterate from left to the right calculating the maximum of elements in [0..i] interval.
Iterate from right to the left calculating the minimum of elements in [i+1..n] interval and comparing this minimum with the maximum of the elements to the left that were pre-calculated at the first step.

Sample implementation:

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

edited Aug 9, 2017 at 16:27

answered Aug 9, 2017 at 8:17

DAle

9,1922 gold badges28 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Hakes Over a year ago

just need to add a print case if the partition is from the (n-2)th element, example int[] array1 = { 3, -2, 3, -2, 3 };

DAle Over a year ago

@Hakes, but this case has no answer. From the question: "I need to get the index of element in an array of integers such that all elements to the right of the index are greater than all the elements from 0 to that index position".

Hakes Over a year ago

Yes, you are right greater than, not greater or equal, my mistake.

Learner Over a year ago

@DAle, Thank you. Can you please suggest me a good book on algorithms, I tried learning from coreman but I am not able to understand anything from it.

DAle Over a year ago

@user3181365, you are welcome! "Introduction to Algorithms" is a great book, it was my personal choice once upon a time. May be some Robert Sedgewick or Niklaus Wirth books would be helpful for you.

Hakes · Accepted Answer · 2017-08-09 09:55:00Z

Changed my comment to answer. Start from the end of the array right will only have one element and left will have n - 1 elements. Then check for the condition that maximum of left < minumum of right if this satisfies then it is done, else move the index to the left and check for this 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");
    }
}

Shubham Agrawal · Accepted Answer · 2017-08-09 09:24:30Z

I would suggest an algorithm for getting the correct output. It will be executed in O(n). Let us consider there are n elements 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)]. The value of minElementIndex[n-1]=n-1
maxElementIndex[i] stores the index of the maximum value element present in the subarray[0 ... (i)]. The value of maxElementIndex[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 for filling 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 through both the arrays like in following way:

for(int i=1;i<n-1;i++){ 
    if(arr[maxElementIndex[i]]< minElementIndex[i]){
        System.out.println(i);
    }
}

Let us dry run the proposed 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}. Clearly at i=2, arr[maxElementIndex[i]] < arr[minElementIndex[i]] which is 5 < 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}. Clearly at i=2, arr[maxElementIndex[i]] < arr[minElementIndex[i]] which is 3 < 6

Collectives™ on Stack Overflow

Algorithm - Maximum left sub-array with lesser elements

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related