Determine the index of an element that satisfies given constraints in an array

Problem

Given an array of integers, find an index before which all elements are smallest than it and all elements are greater than it.

Sample Input

[1, 2, 2, 4, 6, 9,, 9]

Sample output

3 (0-based indexing)

Approach

We can create two auxiliary arrays in this problem. One array will store maximum elements so far to the left of every index, and the second array will store the minimum element so far to the right of every index.

If we find an index where the maximum element to its left is smaller than the element at the current index and the minimum element to its right is greater than the current element, we get our answer. The time complexity of this approach is O(N) and the auxiliary space required is also O(N)

C Programming

#include <stdio.h>
#include <limits.h>
 
int max(int x, int y) { return (x > y) ? x : y; }
int min(int x, int y) { return (x < y) ? x : y; }
 
int solve(int arr[], int n)
{

    int prefix[n];
 
    prefix[0] = INT_MIN;
 
    for (int i = 1; i < n; i++) {
        prefix[i] = max(prefix[i - 1], arr[i - 1]);
    }
 
    int suffix[n];
 
    suffix[n-1] = INT_MAX;
 
    for (int i = n - 2; i >= 0; i--) {
        suffix[i] = min(suffix[i + 1], arr[i + 1]);
    }
 

    for (int i = 1; i < n-1; i++)
    {

        if (prefix[i] < arr[i] && arr[i] < suffix[i]) {
            return i;
        }
    }
 
    return n;
}
 
int main()
{
    int arr[] = {1, 2, 2, 4, 6, 9, 9 };
    int n = sizeof arr / sizeof arr[0];
 
    int ans = solve(arr, n);
 
    if (ans >= 0 && ans < n) {
        printf("The index is %d", ans);
    }
    else {
        printf("Does not exists");
    }
 
    return 0;
}

Output

The index is 3

C++ Programming

#include <bits/stdc++.h>
using namespace std;
int solve(int arr[], int n)
{

    int prefix[n];
 
    prefix[0] = INT_MIN;
 
    for (int i = 1; i < n; i++) {
        prefix[i] = max(prefix[i - 1], arr[i - 1]);
    }
 
    int suffix[n];
 
    suffix[n-1] = INT_MAX;
 
    for (int i = n - 2; i >= 0; i--) {
        suffix[i] = min(suffix[i + 1], arr[i + 1]);
    }
 

    for (int i = 1; i < n-1; i++)
    {

        if (prefix[i] < arr[i] && arr[i] < suffix[i]) {
            return i;
        }
    }
 
    return n;
}
 
int main()
{
    int arr[] = {1, 2, 2, 4, 6, 9, 9 };
    int n = sizeof arr / sizeof arr[0];
 
    int ans = solve(arr, n);
 
    if (ans >= 0 && ans < n) {
        cout<<"The index is "<<ans;
    }
    else {
        cout<<"Does not exists";
    }
 
    return 0;
}

Output

The index is 3

Python Programming

import sys
 
def solve(A):
 
    n = len(A)
 
    prefix = [None] * n
 
    prefix[0] = -sys.maxsize
 
    for i in range(1, n):
        prefix[i] = max(prefix[i - 1], A[i - 1])
 
    suffix = [None] * n
 
    suffix[n-1] = sys.maxsize
 

    for i in reversed(range(n - 1)):
        suffix[i] = min(suffix[i + 1], A[i + 1])
 

    for i in range(1, n-1):
        if prefix[i] < A[i] < suffix[i]:
            return i
    return n
 
A = [1, 2, 2, 4, 6, 9, 9 ]
 
ans = solve(A)
if 0 <= ans < len(A):
    print("The index is", ans)
else:
    print("Does not exists")

Output

The index is 3

People are also reading:

• NameError name is not defined Solution in Python
• Binary Search in C
• Perfect Number in C
• Find the largest number amongst the numbers entered by the user
• WAP in C++ & Python for Armstrong Number
• Print the 1 to 10 Multiples of a Number
• WAP to raise any number x to a Positive Power n
• Find the divisors of a positive Integer
• WAP to create a loading bar