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

Posted in

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

Vinay Khatri
Last updated on April 23, 2024

    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:

    Leave a Comment on this Post

    0 Comments