Subarreglo con diferencia entre máximo y mínimo elemento mayor o igual a su longitud

Dado un arreglo arr[] , la tarea es encontrar un subarreglo con la diferencia entre el elemento máximo y mínimo mayor o igual a la longitud del subarreglo. Si no existe tal subarreglo, imprima -1 .
Ejemplos: 
 

Entrada: arr[] = {3, 7, 5, 1} 
Salida: 3 7 
|3 – 7| > longitud ({3, 7}) es decir, 4 ≥ 2
Entrada: arr[] = {1, 2, 3, 4, 5} 
Salida: -1 
No existe tal subarreglo que cumpla con los criterios. 
 

Enfoque ingenuo: Encuentre todos los subarreglos que sean posibles con al menos dos elementos y luego verifique cada uno de los subarreglos que satisfagan la condición dada, es decir, max (subarreglo) – min (subarreglo) ≥ len (subarreglo) Enfoque eficiente: encuentre los
subarreglos de longitud 2 donde la diferencia absoluta entre los dos únicos elementos es mayor o igual a 2. Esto cubrirá casi todos los casos porque solo hay tres casos en los que no existe tal subarreglo: 
 

1. Cuando la longitud de la array es 0 .
2. Cuando todos los elementos del arreglo son iguales.
3. Cuando cada dos elementos consecutivos en la array tienen una diferencia absoluta de 0 o 1.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required subarray
void findSubArr(int arr[], int n)
{
 
    // For every two consecutive element subarray
    for (int i = 0; i < n - 1; i++) {
 
        // If the current pair of consecutive
        // elements satisfies the given condition
        if (abs(arr[i] - arr[i + 1]) >= 2) {
            cout << arr[i] << " " << arr[i + 1];
            return;
        }
    }
 
    // No such subarray found
    cout << -1;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 4, 6, 7 };
    int n = sizeof(arr) / sizeof(int);
 
    findSubArr(arr, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Function to find the required subarray
    static void findSubArr(int arr[], int n)
    {
     
        // For every two consecutive element subarray
        for (int i = 0; i < n - 1; i++)
        {
     
            // If the current pair of consecutive
            // elements satisfies the given condition
            if (Math.abs(arr[i] - arr[i + 1]) >= 2)
            {
                System.out.print(arr[i] + " " + arr[i + 1]);
                return;
            }
        }
     
        // No such subarray found
        System.out.print(-1);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { 1, 2, 4, 6, 7 };
        int n = arr.length;
     
        findSubArr(arr, n);
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to find the required subarray
def findSubArr(arr, n) :
 
    # For every two consecutive element subarray
    for i in range(n - 1) :
 
        # If the current pair of consecutive
        # elements satisfies the given condition
        if (abs(arr[i] - arr[i + 1]) >= 2) :
            print(arr[i] ,arr[i + 1],end="");
            return;
 
    # No such subarray found
    print(-1);
 
# Driver code
if __name__ == "__main__" :
    arr = [ 1, 2, 4, 6, 7 ];
    n = len(arr);
 
    findSubArr(arr, n);
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to find the required subarray
    static void findSubArr(int []arr, int n)
    {
     
        // For every two consecutive element subarray
        for (int i = 0; i < n - 1; i++)
        {
     
            // If the current pair of consecutive
            // elements satisfies the given condition
            if (Math.Abs(arr[i] - arr[i + 1]) >= 2)
            {
                Console.Write(arr[i] + " " + arr[i + 1]);
                return;
            }
        }
     
        // No such subarray found
        Console.Write(-1);
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = { 1, 2, 4, 6, 7 };
        int n = arr.Length;
     
        findSubArr(arr, n);
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// JavaScript implementation of the approach
 
// Function to find the required subarray
function findSubArr(arr, n) {
 
    // For every two consecutive element subarray
    for (let i = 0; i < n - 1; i++) {
 
        // If the current pair of consecutive
        // elements satisfies the given condition
        if (Math.abs(arr[i] - arr[i + 1]) >= 2) {
            document.write(arr[i] + " " + arr[i + 1]);
            return;
        }
    }
 
    // No such subarray found
    document.write(-1);
}
 
// Driver code
 
let arr = [1, 2, 4, 6, 7];
let n = arr.length
 
findSubArr(arr, n);
 
// This code is contributed by gfgking
 
</script>

2 4

Complejidad de tiempo: O(N)