Element with Left Side Smaller and Right Side Greater

In this class, We discuss Element with Left Side Smaller and Right Side Greater.

The reader can take the complete competitive course. Click Here.

Question:

Given N elements in an array.

Find the element before which all the elements are smaller and after which all the elements are greater than the element.

Note:

Left and right side elements can be equal.

Extreme elements are not considered to select.

Example:

[5, 1, 4, 3, 6, 8, 10, 7, 9]

Output: 6

The elements before 6 are smaller, and after six are greater.

Example 1:

[5, 1, 4, 4]

Output: -1

Time complexity = O(N)

Space complexity = O(N)

Logic:

One way:

Take each element and check the left side is smaller and the right side greater.

This approach had a time complexity of O(N^2)

Second way:

The explanation is provided in the video.

Code:

def findElement( arr, n):

    leftMax = [None] * n

    leftMax[0] = arr[0]

    for i in range(1, n):

        leftMax[i] = max(leftMax[i-1], arr[i-1])

    rightMin = [None]*n

    rightMin[n-1] = arr[n-1]

    for i in range(n-2, -1, -1):

        rightMin[i] = min(rightMin[i+1], arr[i])

    for i in range(1, n-1):

        if leftMax[i] <= arr[i] and arr[i] <= rightMin[i]:

            return arr[i]

    return -1

n = int(input())

arr=list(map(int,input().strip().split()))

j = findElement(arr, n)

print(j)