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

Posted in  Vinay Khatri
Last updated on September 27, 2022

## 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 = 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;

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 = 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;

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 = -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
```