Open In App

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

Last Updated : 25 Apr, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given an array, find an element before which all elements are smaller than it, and after which all are greater than it. Return the index of the element if there is such an element, otherwise, return -1.

Examples:

Input: arr[] = {5, 1, 4, 3, 6, 8, 10, 7, 9}; 
Output:
Explanation: All elements on left of arr[4] are smaller than it 
and all elements on right are greater.

Input: arr[] = {5, 1, 4, 4}; 
Output: -1 
Explanation : No such index exits.

Expected time complexity: O(n).

A simple solution is to consider every element one by one. For every element, compare it with all elements on the left and all elements on right. The time complexity of this solution is O(n2). 

Code-

C++




// C++ program to find the element which is greater than
// all left elements and smaller than all right elements.
#include <bits/stdc++.h>
using namespace std;
 
//Function to check
bool check(int arr[], int n,int ind){
    int i=ind-1;
    int j=ind+1;
     
    while(i>=0){
        if(arr[i]>arr[ind]){return false;}
        i--;
    }
     
    while(j<n){
        if(arr[j]<arr[ind]){return false;}
        j++;
    }
     
    return true;
}
 
 
// Function to return the index of the element which is greater than
// all left elements and smaller than all right elements.
int findElement(int arr[], int n)
{
    
    // Traverse array from 1st to n-1 th index because
    //Extrem elements can't be aur answer
    for (int i=1; i<n-1; i++)
    {
       if(check(arr,n,i)){return i;}
    }
 
    // If there was no element matching criteria
    return -1;
}
 
// Driver program
int main()
{
    int arr[] = {5, 1, 4, 3, 6, 8, 10, 7, 9};
    int n = sizeof arr / sizeof arr[0];
    cout << "Index of the element is " << findElement(arr, n);
    return 0;
}


Java




// Java program to find the element which is greater than
// all left elements and smaller than all right elements.
 
import java.util.*;
 
class Main {
    // Function to check
    static boolean check(int arr[], int n, int ind)
    {
        int i = ind - 1;
        int j = ind + 1;
 
        while (i >= 0) {
            if (arr[i] > arr[ind]) {
                return false;
            }
            i--;
        }
 
        while (j < n) {
            if (arr[j] < arr[ind]) {
                return false;
            }
            j++;
        }
 
        return true;
    }
 
    // Function to return the index of the element which is
    // greater than all left elements and smaller than all
    // right elements.
    static int findElement(int arr[], int n)
    {
 
        // Traverse array from 1st to n-1 th index because
        // Extrem elements can't be aur answer
        for (int i = 1; i < n - 1; i++) {
            if (check(arr, n, i)) {
                return i;
            }
        }
 
        // If there was no element matching criteria
        return -1;
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int arr[] = { 5, 1, 4, 3, 6, 8, 10, 7, 9 };
        int n = arr.length;
        System.out.println("Index of the element is "
                           + findElement(arr, n));
    }
}


Python3




# python3 program to find the element which is greater than
# all left elements and smaller than all right elements.
 
# Function to check
 
 
def check(arr, n, ind):
    i = ind - 1
    j = ind + 1
 
    while i >= 0:
        if arr[i] > arr[ind]:
            return False
        i -= 1
 
    while j < n:
        if arr[j] < arr[ind]:
            return False
        j += 1
 
    return True
 
 
# Function to return the index of the element which is greater than
# all left elements and smaller than all right elements.
def findElement(arr, n):
    # Traverse array from 1st to n-1 th index because
    # Extrem elements can't be aur answer
    for i in range(1, n - 1):
        if check(arr, n, i):
            return i
 
    # If there was no element matching criteria
    return -1
 
 
arr = [5, 1, 4, 3, 6, 8, 10, 7, 9]
n = len(arr)
print("Index of the element is", findElement(arr, n))


C#




using System;
 
public class MainClass {
    public static bool Check(int[] arr, int n, int ind)
    {
        int i = ind - 1;
        int j = ind + 1;
 
        while (i >= 0) {
            if (arr[i] > arr[ind]) {
                return false;
            }
            i--;
        }
 
        while (j < n) {
            if (arr[j] < arr[ind]) {
                return false;
            }
            j++;
        }
 
        return true;
    }
 
    public static int FindElement(int[] arr, int n)
    {
        // Traverse array from 1st to n-1 th index because
        // Extrem elements can't be aur answer
        for (int i = 1; i < n - 1; i++) {
            if (Check(arr, n, i)) {
                return i;
            }
        }
 
        // If there was no element matching criteria
        return -1;
    }
 
    public static void Main()
    {
        int[] arr = { 5, 1, 4, 3, 6, 8, 10, 7, 9 };
        int n = arr.Length;
        Console.WriteLine("Index of the element is "
                          + FindElement(arr, n));
    }
}


Javascript




// Function to check
function check(arr, n, ind) {
    let i = ind - 1;
    let j = ind + 1;
 
    while (i >= 0) {
        if (arr[i] > arr[ind]) {
            return false;
        }
        i--;
    }
 
    while (j < n) {
        if (arr[j] < arr[ind]) {
            return false;
        }
        j++;
    }
 
    return true;
}
 
// Function to return the index of the element which is greater than
// all left elements and smaller than all right elements.
function findElement(arr, n) {
    // Traverse array from 1st to n-1 th index because
    // Extrem elements can't be our answer
    for (let i = 1; i < n - 1; i++) {
        if (check(arr, n, i)) {
            return i;
        }
    }
 
    // If there was no element matching criteria
    return -1;
}
 
// Driver program
let arr = [5, 1, 4, 3, 6, 8, 10, 7, 9];
let n = arr.length;
console.log("Index of the element is " + findElement(arr, n));
 
// This code is contributed by sarojmcy2e


Output

Index of the element is 4

Time Complexity: O(n2), Time complexity of the given program is O(n^2) as there are two nested while loops in the check function, which are iterating over at most n-2 elements each, and they are being called for each element in the array except the first and last elements.
Auxiliary Space: O(1), Space complexity of the program is O(1) as no extra space is being used, except for the input array and some integer variables used for indexing and loop control. 

An Efficient Solution can solve this problem in O(n) time using O(n) extra space. Below is the detailed solution.

  1. Create two arrays leftMax[] and rightMin[].
  2. Traverse input array from left to right and fill leftMax[] such that leftMax[i] contains a maximum element from 0 to i-1 in the input array.
  3. Traverse input array from right to left and fill rightMin[] such that rightMin[i] contains a minimum element from to n-1 to i+1 in the input array.
  4. Traverse input array. For every element arr[i], check if arr[i] is greater than leftMax[i] and smaller than rightMin[i]. If yes, return i.

Further Optimization to the above approach is to use only one extra array and traverse input array only twice. The first traversal is the same as above and fills leftMax[]. Next traversal traverses from the right and keeps track of the minimum. The second traversal also finds the required element.

Below image is a dry run of the above approach:

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

Below is the implementation of the above approach. 

C++




// C++ program to find the element which is greater than
// all left elements and smaller than all right elements.
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the index of the element which is greater than
// all left elements and smaller than all right elements.
int findElement(int arr[], int n)
{
    // leftMax[i] stores maximum of arr[0..i-1]
    int leftMax[n];
    leftMax[0] = INT_MIN;
 
    // Fill leftMax[1..n-1]
    for (int i = 1; i < n; i++)
        leftMax[i] = max(leftMax[i-1], arr[i-1]);
 
    // Initialize minimum from right
    int rightMin = INT_MAX;
 
    // Traverse array from right
    for (int i=n-1; i>=0; i--)
    {
        // Check if we found a required element
        if (leftMax[i] < arr[i] && rightMin > arr[i])
             return i;
 
        // Update right minimum
        rightMin = min(rightMin, arr[i]);
    }
 
    // If there was no element matching criteria
    return -1;
}
 
// Driver program
int main()
{
    int arr[] = {5, 1, 4, 3, 6, 8, 10, 7, 9};
    int n = sizeof arr / sizeof arr[0];
    cout << "Index of the element is " << findElement(arr, n);
    return 0;
}


Java




// Java program to find the element which is greater than
// all left elements and smaller than all right elements.
import java.io.*;
import java.util.*;
 
public class GFG {
       static int findElement(int[] arr, int n)
       {
              // leftMax[i] stores maximum of arr[0..i-1]
              int[] leftMax = new int[n];
              leftMax[0] = Integer.MIN_VALUE;
 
              // Fill leftMax[1..n-1]
              for (int i = 1; i < n; i++)
                   leftMax[i] = Math.max(leftMax[i - 1], arr[i - 1]);
                    
              // Initialize minimum from right
              int rightMin = Integer.MAX_VALUE;
 
              // Traverse array from right
              for (int i = n - 1; i >= 0; i--)
              {
                   // Check if we found a required element
                   if (leftMax[i] < arr[i] && rightMin > arr[i])
                       return i;
 
                   // Update right minimum
                   rightMin = Math.min(rightMin, arr[i]);
              }
                
              // If there was no element matching criteria
              return -1;
 
               
       }
 
       // Driver code
       public static void main(String args[])
       {
              int[] arr = {5, 1, 4, 3, 6, 8, 10, 7, 9};
              int n = arr.length;
              System.out.println("Index of the element is " +
              findElement(arr, n));
       }
 
       // This code is contributed
       // by rachana soma
}


Python3




# Python3 program to find the element which is greater than
# all left elements and smaller than all right elements.
 
 
def findElement(arr, n):
 
    # leftMax[i] stores maximum of arr[0..i-1]
    leftMax = [None] * n
    leftMax[0] = arr[0]
 
    # Fill leftMax[1..n-1]
    for i in range(1, n):
        leftMax[i] = max(leftMax[i-1], arr[i-1])
 
    # Initialize minimum from right
    rightMin = [None]*n
    rightMin[n-1] = arr[n-1]
 
    # Fill rightMin
    for i in range(n-2, -1, -1):
        rightMin[i] = min(rightMin[i+1], arr[i])
    # Traverse array from right
    for i in range(1, n-1):
 
        # Check if we found a required element
        # for ith element, it should be more than maximum of array
        # elements [0....i-1] and should be less than the minimum of
        # [i+1.....n-1] array elements
        if leftMax[i-1] <= arr[i] and arr[i] <= rightMin[i+1]:
            return i
 
    # If there was no element matching criteria
    return -1
 
 
# Driver program
if __name__ == "__main__":
 
    arr = [5, 1, 4, 3, 6, 8, 10, 7, 9]
    n = len(arr)
    print("Index of the element is", findElement(arr, n))
 
# This code is contributed by Rituraj Jain


C#




// C# program to find the element which is greater than
// all left elements and smaller than all right elements.
using System;
 
class GFG
{
static int findElement(int[] arr, int n)
{
    // leftMax[i] stores maximum of arr[0..i-1]
    int[] leftMax = new int[n];
    leftMax[0] = int.MinValue;
 
    // Fill leftMax[1..n-1]
    for (int i = 1; i < n; i++)
        leftMax[i] = Math.Max(leftMax[i - 1], arr[i - 1]);
 
    // Initialize minimum from right
    int rightMin = int.MaxValue;
 
    // Traverse array from right
    for (int i=n-1; i>=0; i--)
    {
        // Check if we found a required element
        if (leftMax[i] < arr[i] && rightMin > arr[i])
            return i;
 
        // Update right minimum
        rightMin = Math.Min(rightMin, arr[i]);
    }
 
    // If there was no element matching criteria
    return -1;
}
 
// Driver program
public static void Main()
{
    int[] arr = {5, 1, 4, 3, 6, 8, 10, 7, 9};
    int n = arr.Length;
    Console.Write( "Index of the element is " + findElement(arr, n));
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)


PHP




<?php
// PHP program to find the element
// which is greater than all left
// elements and smaller than all
// right elements.
 
function findElement($arr, $n)
{
    // leftMax[i] stores maximum
    // of arr[0..i-1]
    $leftMax = array(0);
    $leftMax[0] = PHP_INT_MIN;
 
    // Fill leftMax[1..n-1]
    for ($i = 1; $i < $n; $i++)
        $leftMax[$i] = max($leftMax[$i - 1],
                               $arr[$i - 1]);
 
    // Initialize minimum from right
    $rightMin = PHP_INT_MAX;
 
    // Traverse array from right
    for ($i = $n - 1; $i >= 0; $i--)
    {
        // Check if we found a required
        // element
        if ($leftMax[$i] < $arr[$i] &&
            $rightMin > $arr[$i])
            return $i;
 
        // Update right minimum
        $rightMin = min($rightMin, $arr[$i]);
    }
 
    // If there was no element
    // matching criteria
    return -1;
}
 
// Driver Code
$arr = array(5, 1, 4, 3, 6, 8, 10, 7, 9);
$n = count($arr);
echo "Index of the element is " ,
           findElement($arr, $n);
 
// This code is contributed
// by Sach_Code
?>


Javascript




<script>
 
// Javascript program to find the element
// which is greater than all left elements
// and smaller than all right elements.
 
// Function to return the index of the
// element which is greater than all
// left elements and smaller than all right elements.
function findElement(arr, n)
{
     
    // leftMax[i] stores maximum of arr[0..i-1]
    var leftMax = Array(n).fill(0);
    leftMax[0] = Number.MIN_VALUE;
 
    // Fill leftMax[1..n-1]
    for(i = 1; i < n; i++)
        leftMax[i] = Math.max(leftMax[i - 1],
                                  arr[i - 1]);
 
    // Initialize minimum from right
    var rightMin = Number.MAX_VALUE;
 
    // Traverse array from right
    for(i = n - 1; i >= 0; i--)
    {
         
        // Check if we found a required element
        if (leftMax[i] < arr[i] && 
              rightMin > arr[i])
            return i;
 
        // Update right minimum
        rightMin = Math.min(rightMin, arr[i]);
    }
 
    // If there was no element
    // matching criteria
    return -1;
}
 
// Driver code
var arr = [ 5, 1, 4, 3, 6, 8, 10, 7, 9 ];
var n = arr.length;
 
document.write("Index of the element is " +
               findElement(arr, n));
 
// This code is contributed by aashish1995
 
</script>


Output: 

Index of the element is 4

Time Complexity: O(n), The program uses two loops to traverse the input array, one from left to right and another from right to left. The time complexity of the first loop is O(n) and that of the second loop is also O(n), so the overall time complexity of the program is O(n).
Auxiliary Space: O(n), The program uses an extra array of size n to store the maximum of all left elements, so the space complexity of the program is O(n). 
Thanks to Gaurav Ahirwar for suggesting the above solution.

Space Optimized Approach: 

C++




// C++ program to find the element which is greater than
// all left elements and smaller than all right elements.
#include <bits/stdc++.h>
using namespace std;
 
int findElement(int a[], int n)
{
    // Base case
    if (n == 1 || n == 2) {
        return -1;
    }
 
    // 1.element is the possible candidate for the solution
    // of the problem.
      // 2.idx is the index of the possible
    // candidate.
      // 3.maxx is the value which is maximum on the
    // left side of the array.
      // 4.bit tell whether the loop is
    // terminated from the if condition or from the else
    // condition when loop do not satisfied the condition.
    // 5.check is the variable which tell whether the
    // element is updated or not
 
    int element = a[0], maxx = a[0], bit = -1, check = 0;
    int idx = -1;
 
    // The extreme two of the array can not be the solution
    // Therefore iterate the loop from i = 1 to < n-1
    for (int i = 1; i < (n - 1);) {
 
        // here we find the possible candidate where Element
        // with left side smaller and right side greater.
        // when the if condition fail we check and update in
        // else condition.
 
        if (a[i] < maxx && i < (n - 1)) {
            i++;
            bit = 0;
        }
 
        // here we update the possible element if the
        // element is greater than the maxx (maximum element
        // so far). In while loop we sur-pass the value which
        // is greater than the element
        else {
            if (a[i] >= maxx) {
                element = a[i];
                idx = i;
                check = 1;
                maxx = a[i];
            }
            if (check == 1) {
                i++;
            }
            bit = 1;
            while (a[i] >= element && i < (n - 1)) {
                if (a[i] > maxx) {
                    maxx = a[i];
                }
                i++;
            }
            check = 0;
        }
    }
 
    // checking for the last value and whether the loop is
    // terminated from else or if block.
 
    if (element <= a[n - 1] && bit == 1) {
        return idx;
    }
    else {
        return -1;
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 1, 4, 3, 6, 8, 10, 7, 9 };
    int n = sizeof arr / sizeof arr[0];
   
      // Function Call
    cout << "Index of the element is "
         << findElement(arr, n);
    return 0;
}


Java




// Java program to find the element
// which is greater than all left
// elements and smaller than all
// right elements.
class GFG{
     
static int findElement(int []a, int n)
{
     
    // Base case
    if (n == 1 || n == 2)
    {
        return -1;
    }
     
    // 1.element is the possible candidate for
    // the solution of the problem.
    // 2.idx is the index of the possible
    // candidate.
    // 3.maxx is the value which is maximum on the
    // left side of the array.
    // 4.bit tell whether the loop is
    // terminated from the if condition or from
    // the else condition when loop do not
    // satisfied the condition.
    // 5.check is the variable which tell whether the
    // element is updated or not
    int element = a[0], maxx = a[0],
            bit = -1, check = 0;
    int idx = -1;
     
    // The extreme two of the array can
    // not be the solution. Therefore
    // iterate the loop from i = 1 to < n-1
    for(int i = 1; i < (n - 1);)
    {
         
        // Here we find the possible candidate
        // where Element with left side smaller
        // and right side greater. When the if
        // condition fail we check and update in
        // else condition.
        if (a[i] < maxx && i < (n - 1))
        {
            i++;
            bit = 0;
        }
         
        // Here we update the possible element
        // if the element is greater than the
        // maxx (maximum element so far). In
        // while loop we sur-pass the value which
        // is greater than the element
        else
        {
            if (a[i] >= maxx)
            {
                element = a[i];
                idx = i;
                check = 1;
                maxx = a[i];
            }
            if (check == 1)
            {
                i++;
            }
            bit = 1;
              
            while (a[i] >= element && i < (n - 1))
            {
                if (a[i] > maxx)
                {
                    maxx = a[i];
                }
                i++;
            }
            check = 0;
        }
    }
     
    // Checking for the last value and whether
    // the loop is terminated from else or
    // if block.
    if (element <= a[n - 1] && bit == 1)
    {
        return idx;
    }
    else
    {
        return -1;
    }
         
}
 
// Driver code
public static void main(String []args)
{
    int []arr = { 5, 1, 4, 3, 6, 8, 10, 7, 9 };
    int n = arr.length;
     
    System.out.println("Index of the element is " +
                       findElement(arr, n));
}
}
 
// This code is contributed by avanitrachhadiya2155


Python3




# Python3 program to find the element which
# is greater than all left elements and
# smaller than all right elements.
def findElement (a, n):
 
    # Base case
    if (n == 1 or n == 2):
        return -1
 
    # 1. element is the possible candidate
    # for the solution of the problem
    # 2. idx is the index of the
    # possible candidate
    # 3. maxx is the value which is maximum
    # on the left side of the array
    # 4. bit tell whether the loop is
    # terminated from the if condition or
    # from the else condition when loop do
    # not satisfied the condition.
    # 5. check is the variable which tell
    # whether the element is updated or not
    element, maxx, bit = a[0], a[0], -1
    check = 0
    idx = -1
 
    # The extreme of the array can't be
    # the solution Therefore iterate
    # the loop from i = 1 to < n-1
    i = 1
    while (i < (n - 1)):
 
        # Here we find the possible candidate
        # where element with left side smaller
        # and right side greater. when the if
        # condition fail we check and update
        # in else condition
        if (a[i] < maxx and i < (n - 1)):
            i += 1
            bit = 0
 
        # Here we update the possible element
        # if the element is greater than the
        # maxx (maximum element so far). In
        # while loop we sur-pass the value
        # which is greater than the element
        else:
            if (a[i] >= maxx):
                element = a[i]
                idx = i
                check = 1
                maxx = a[i]
 
            if (check == 1):
                i += 1
 
            bit = 1
            while (a[i] >= element and i < (n - 1)):
                if (a[i] > maxx):
                    maxx = a[i]
 
                i += 1
 
            check = 0
 
    # Checking for the last value and whether
    # the loop is terminated from else or
    # if block
    if (element <= a[n - 1] and bit == 1):
        return idx
    else:
        return -1
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 5, 1, 4, 3,
            6, 8, 10, 7, 9 ]
    n = len(arr)
 
    # Function call
    print("Index of the element is",
           findElement(arr, n))
 
# This code is contributed by himanshu77


C#




// C# program to find the element
// which is greater than all left
// elements and smaller than all
// right elements.
using System;
  
class GFG{
  
static int findElement(int []a, int n)
{
     
    // Base case
    if (n == 1 || n == 2)
    {
        return -1;
    }
     
    // 1.element is the possible candidate for
    // the solution of the problem.
    // 2.idx is the index of the possible
    // candidate.
    // 3.maxx is the value which is maximum on the
    // left side of the array.
    // 4.bit tell whether the loop is
    // terminated from the if condition or from
    // the else condition when loop do not
    // satisfied the condition.
    // 5.check is the variable which tell whether the
    // element is updated or not
    int element = a[0], maxx = a[0],
        bit = -1, check = 0;
    int idx = -1;
  
    // The extreme two of the array can
    // not be the solution. Therefore
    // iterate the loop from i = 1 to < n-1
    for(int i = 1; i < (n - 1);)
    {
         
        // Here we find the possible candidate
        // where Element with left side smaller
        // and right side greater. When the if
        // condition fail we check and update in
        // else condition.
        if (a[i] < maxx && i < (n - 1))
        {
            i++;
            bit = 0;
        }
         
        // Here we update the possible element
        // if the element is greater than the
        // maxx (maximum element so far). In
        // while loop we sur-pass the value which
        // is greater than the element
        else
        {
            if (a[i] >= maxx)
            {
                element = a[i];
                idx = i;
                check = 1;
                maxx = a[i];
            }
            if (check == 1)
            {
                i++;
            }
            bit = 1;
             
            while (a[i] >= element && i < (n - 1))
            {
                if (a[i] > maxx)
                {
                    maxx = a[i];
                }
                i++;
            }
            check = 0;
        }
    }
  
    // Checking for the last value and whether
    // the loop is terminated from else or
    // if block.
    if (element <= a[n - 1] && bit == 1)
    {
        return idx;
    }
    else
    {
        return -1;
    }
}
 
// Driver code
public static void Main(string[] args)
{
    int []arr = { 5, 1, 4, 3, 6, 8, 10, 7, 9 };
    int n = arr.Length;
 
    // Function Call
    Console.Write("Index of the element is " +
                   findElement(arr, n));
}
}
 
// This code is contributed by rutvik_56


Javascript




<script>
// javascript program to find the element
// which is greater than all left
// elements and smaller than all
// right elements.   
function findElement(a , n)
{
 
        // Base case
        if (n == 1 || n == 2)
        {
            return -1;
        }
 
        // 1.element is the possible candidate for
        // the solution of the problem.
        // 2.idx is the index of the possible
        // candidate.
        // 3.maxx is the value which is maximum on the
        // left side of the array.
        // 4.bit tell whether the loop is
        // terminated from the if condition or from
        // the else condition when loop do not
        // satisfied the condition.
        // 5.check is the variable which tell whether the
        // element is updated or not
        var element = a[0], maxx = a[0], bit = -1, check = 0;
        var idx = -1;
 
        // The extreme two of the array can
        // not be the solution. Therefore
        // iterate the loop from i = 1 to < n-1
        for (i = 1; i < (n - 1);) {
 
            // Here we find the possible candidate
            // where Element with left side smaller
            // and right side greater. When the if
            // condition fail we check and update in
            // else condition.
            if (a[i] < maxx && i < (n - 1)) {
                i++;
                bit = 0;
            }
 
            // Here we update the possible element
            // if the element is greater than the
            // maxx (maximum element so far). In
            // while loop we sur-pass the value which
            // is greater than the element
            else {
                if (a[i] >= maxx) {
                    element = a[i];
                    idx = i;
                    check = 1;
                    maxx = a[i];
                }
                if (check == 1) {
                    i++;
                }
                bit = 1;
 
                while (a[i] >= element && i < (n - 1)) {
                    if (a[i] > maxx) {
                        maxx = a[i];
                    }
                    i++;
                }
                check = 0;
            }
        }
 
        // Checking for the last value and whether
        // the loop is terminated from else or
        // if block.
        if (element <= a[n - 1] && bit == 1)
        {
            return idx;
        }
        else
        {
            return -1;
        }
 
    }
 
    // Driver code
        var arr = [ 5, 1, 4, 3, 6, 8, 10, 7, 9 ];
        var n = arr.length;
        document.write("Index of the element is " + findElement(arr, n));
 
// This code is contributed by gauravrajput1
</script>


Output

Index of the element is 4

Time Complexity: O(n), The time complexity of this program is O(n) where n is the size of the input array. This is because the program iterates through the array only once to find the element that satisfies the given condition. 
Auxiliary Space: O(1), The space complexity of this program is O(1) because it uses only a constant amount of extra space to store some variables like element, maxx, bit, check, and idx, which are not dependent on the input size. Therefore, the space used by the program does not increase with the size of the input array.

 



Previous Article
Next Article

Similar Reads

Length of longest subarray in which elements greater than K are more than elements not greater than K
Given an array arr[] of length N. The task is to find the length of the longest subarray in which elements greater than a given number K are more than elements not greater than K.Examples: Input : N = 5, K = 2, arr[]={ 1, 2, 3, 4, 1 } Output : 3 The subarray [2, 3, 4] or [3, 4, 1] satisfy the given condition, and there is no subarray of length 4 or
10 min read
Delete Array Elements which are Smaller than Next or Become Smaller
Given an array arr[] and a number k. The task is to delete k elements which are smaller than next element (i.e., we delete arr[i] if arr[i] &lt; arr[i+1]) or become smaller than next because next element is deleted. Example: Input : arr[] = { 3, 100, 1 }, k = 1Output : 100, 1Explanation : arr[0] &lt; arr[1] means 3 is less than 100, so delete 3 Inp
10 min read
For all Array elements find Product of Sum of all smaller and Sum of all greater elements
Given an array arr[] of integers of length N, the task is to find the product of the sum of all the numbers larger than that number with the sum of all the numbers less than that number for each number in the array. Examples: Input: arr[] = {8, 4, 9, 3}, N = 4Output:- 63, 51, 0, 0Explanation:For first number 8: Sum of elements smaller than this is
15 min read
Modify Array such that no element is smaller/greater than half/double of its adjacent elements
Given an array, arr[] of size N. Find the minimum number of elements we need to insert between array elements such that the maximum element from two adjacent elements is not more than twice bigger than the minimum element i.e., max(arr[i], arr[i+1]) ? 2 * min(arr[i], arr[i+1]) where 0 ? i &lt; N - 1. Examples: Input: N = 5, A[] = {1, 2, 3, 4, 3}Out
7 min read
Find all Array elements that are smaller than all elements to their right
Given an array arr[] containing N positive integers. The task is to find all the elements which are smaller than all the elements to their right. Examples: Input: arr[] = {6, 14, 13, 21, 17, 19}Output: [6, 13, 17, 19]Explanation: All the elements in the output are following the condition. Input: arr[] = {10, 3, 4, 8, 7}Output: [3, 4, 7] Naive appro
12 min read
Size of smallest subarray to be removed to make count of array elements greater and smaller than K equal
Given an integer K and an array arr[] consisting of N integers, the task is to find the length of the subarray of smallest possible length to be removed such that the count of array elements smaller than and greater than K in the remaining array are equal. Examples: Input: arr[] = {5, 7, 2, 8, 7, 4, 5, 9}, K = 5Output: 2Explanation:Smallest subarra
10 min read
Largest element smaller than current element on left for every element in Array
Given an array arr[] of the positive integers of size N, the task is to find the largest element on the left side of each index which is smaller than the element present at that index. Note: If no such element is found then print -1. Examples: Input: arr[] = {2, 5, 10} Output: -1 2 5 Explanation : Index 0: There are no elements before it So Print -
11 min read
Smallest subarray of size greater than K with sum greater than a given value
Given an array, arr[] of size N, two positive integers K and S, the task is to find the length of the smallest subarray of size greater than K, whose sum is greater than S. Examples: Input: arr[] = {1, 2, 3, 4, 5}, K = 1, S = 8Output: 2Explanation: Smallest subarray with sum greater than S(=8) is {4, 5}Therefore, the required output is 2. Input: ar
15 min read
Maximum Difference between Two Elements such that Larger Element Appears after the Smaller Element
Given an array arr[] of integers, find out the maximum difference between any two elements such that larger element appears after the smaller number. Examples : Input : arr = {2, 3, 10, 6, 4, 8, 1}Output : 8Explanation : The maximum difference is between 10 and 2. Input : arr = {7, 9, 5, 6, 3, 2}Output : 2Explanation : The maximum difference is bet
15+ min read
Find a peak element which is not smaller than its neighbours
Given an array arr of n elements that is first strictly increasing and then maybe strictly decreasing, find the maximum element in the array. Note: If the array is increasing then just print the last element will be the maximum value. Example: Input: array[]= {5, 10, 20, 15}Output: 20Explanation: The element 20 has neighbors 10 and 15, both of them
15+ min read
Article Tags :
Practice Tags :
three90RightbarBannerImg