Find largest continuous interval such that all number between starting and ending are greater than starting and less than ending

user_10556866 0
Viewed 367

you have given array of integers

for example 5,3,4,3,9,4,4,6,8,6,5,7

you have to find largest interval (i,j) such that all number between i and j are greater than equal to number at i but less than equal to number at j. numbers need not to be in sorted order. Also number at i should be less than number at j.

in above example there are two such intervals 3,4,3,9 and 4,4,6,8

In 3,4,3,9 - middle two numbers (4,3) are greater than equal to starting number(3) but less than equal to ending number(9) . Also starting number (3) is less than ending number(9).

In 4,4,6,8 - middle two numbers (4,6) are greater than equal to starting number(4) but less than equal to ending number(8). Also starting number(4) is less than ending number(8).

One way to solve this problem is check all intervals of size n, then size n-1 , so on till we get such interval. But I want efficient algo either by Divide or Conquer /DP/or some other approach

algorithm
2 Answers

We can solve this in O(n log n) by considering each element as the potential leftmost element in the interval. For each such candidate, (1) find the first element to the right that's lower than it - that's a bound on the right for the possible interval since including such an element would invalidate the constraints; (2) find the leftmost instance of the maximum element in the interval (or rightmost if A[j] is allowed to be equal to an element on its left) - that's the farthest right the interval could extend without invalidating the constraints.

We can store the answer for (1) for all elements in O(n), using a stack. We can preprocess a structure for range-maximum-query that would answer the first part of (2) in O(log n) time. Once the maximum for the interval is found, if we have an ordered list of its instances in the array (which we can preprocess in O(n) with a hash table), we can find the rightmost or leftmost occurrence of it in the interval in O(log n) time.

user_20347870

A simple answer by DP, hope it could help you:

public class Test {

    public static void main(String[] args){

        int[] input = {5,3,4,3,9,4,4,6,8,6,5,7};

        //
        // lenDp array to store the max possible interval sizes starting at every index.
        //
        int[] lenDp = new int[input.length];
        //
        // minNumIdxs array to store the indexes of minimum numbers in all sub arrays with the same length
        //
        int[] minNumIdxs = new int[input.length];

        //
        // for a start, every number is an interval with size of 1,
        // and there are as many sub arrays with length of 1 as input.length,
        // the minimum number in a sub array is the first number:
        //
        for(int i = 0; i < input.length; i++){
            lenDp[i] = 1;
            minNumIdxs[i] = i;
        }

        int maxLen = 1;

        //
        // check all possible intervals of size from 2 to input.length
        //
        for(int len = 2; len <= input.length; len++){
            //
            // for every possible interval with size of `len`, the starting index can be in range of [0, input.length - len]
            //
            for(int i = 0, end = input.length - len; i <= end ; i++ ){

                //
                // assume the interval of size `len` is possible for index i,then the number at input[i] has to be the minimum number,
                // and the number at input[i + len - 1] has to be greater than or equal to
                // the largest number ( at input[i + dp[i] - 1] ) of the current interval starting at index i.
                // in the corner case where dp[i] == 1 and len > 2, it wouldn't be valid, for example:
                // when len = 5, i = 0, dp[i] = dp[0] = 1, then input[i + len - 1] = input[0 + 5 - 1] = input[4] = 9;
                // 9 is greater than 5 (input[0]), but it's invalid.
                // So we also need to check (len == 2 || dp[i] > 1)
                //
                if(minNumIdxs[i] == i && input[i + len - 1] >= input[i + lenDp[i] - 1] &&
                        (len == 2 || lenDp[i] > 1)){
                    lenDp[i] = len;
                    maxLen = len;
                }

                //
                // update the index of the minimum number in the sub array starting at i
                //
                if(input[i + len - 1] < input[minNumIdxs[i]])minNumIdxs[i] = i + len - 1;
            }
        }



        //
        // print out the final result
        //
        for(int i = 0 ; i < lenDp.length ; i++){
            if(lenDp[i] == maxLen){
                System.out.println(Arrays.toString(Arrays.copyOfRange(input, i, i + maxLen)));
            }
        }

    }

}

output:

 [3, 4, 3, 9]
 [4, 4, 6, 8]
user_79949670
Related