Distancia máxima entre dos elementos cuya diferencia absoluta es K

Posted on by Rudeus Greyrat

Dada una array arr[] y un número K , la tarea de encontrar la distancia máxima entre dos elementos cuya diferencia absoluta es K. Si no es posible encontrar ninguna distancia máxima, imprima «-1» .

Ejemplo:

Entrada: arr[] = {3, 5, 1, 4, 2, 2}
Salida: 5
Explicación : 
la distancia máxima entre los dos elementos (3, 2) en el índice 0 y 5 es 5. 

Entrada: arr[] = {11, 2, 3, 8, 5, 2}
Salida: 3
Explicación: 
La distancia máxima entre los dos elementos (3, 2) en el índice 2 y 5 es 3. 

Enfoque ingenuo: la idea es elegir cada elemento (por ejemplo, arr[i] ) uno por uno, buscar el elemento anterior (arr[i] – K) y el siguiente elemento (arr[i] + K) . Si existe alguno de los dos elementos, encuentre la distancia máxima entre el elemento actual y su elemento siguiente o anterior. 

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar hashmap . A continuación se muestran los pasos: 

  1. Recorra la array y almacene el índice de la primera aparición en un HashMap.
  2. Ahora, para cada elemento de la array arr[] , compruebe si arr[i] + K y arr[i] – K están presentes en el hashmap o no.
  3. Si está presente, actualice la distancia desde ambos elementos con el arr[i] y busque el siguiente elemento.
  4. Imprime la distancia máxima obtenida después de los pasos anteriores.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that find maximum distance
// between two elements whose absolute
// difference is K
int maxDistance(int arr[], int K, int N)
{
 
    // To store the first index
    map<int, int> Map;
     
    // Traverse elements and find
    // maximum distance between 2
    // elements whose absolute
    // difference is K
    int maxDist = 0;
 
    for(int i = 0; i < N; i++)
    {
 
        // If this is first occurrence
        // of element then insert
        // its index in map
        if (Map.find(arr[i]) == Map.end())
            Map[arr[i]] = i;
 
        // If next element present in
        // map then update max distance
        if (Map.find(arr[i] + K) != Map.end())
        {
            maxDist = max(maxDist,
                          i - Map[arr[i] + K]);
        }
 
        // If previous element present
        // in map then update max distance
        if (Map.find(arr[i] - K) != Map.end())
        {
            maxDist = max(maxDist,
                          i - Map[arr[i] - K]);
        }
    }
 
    // Return the answer
    if (maxDist == 0)
        return -1;
    else
        return maxDist;
}
 
// Driver code
int main()
{
     
    // Given array arr[]
    int arr[] = { 11, 2, 3, 8, 5, 2 };
     
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given difference K
    int K = 2;
 
    // Function call
    cout << maxDistance(arr, K, N);
 
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function that find maximum distance
    // between two elements whose absolute
    // difference is K
    static int maxDistance(int[] arr, int K)
    {
 
        // To store the first index
        Map<Integer, Integer> map
            = new HashMap<>();
 
        // Traverse elements and find
        // maximum distance between 2
        // elements whose absolute
        // difference is K
        int maxDist = 0;
 
        for (int i = 0; i < arr.length; i++) {
 
            // If this is first occurrence
            // of element then insert
            // its index in map
            if (!map.containsKey(arr[i]))
                map.put(arr[i], i);
 
            // If next element present in
            // map then update max distance
            if (map.containsKey(arr[i] + K)) {
                maxDist
                    = Math.max(
                        maxDist,
                        i - map.get(arr[i] + K));
            }
 
            // If previous element present
            // in map then update max distance
            if (map.containsKey(arr[i] - K)) {
                maxDist
                    = Math.max(maxDist,
                            i - map.get(arr[i] - K));
            }
        }
 
        // Return the answer
        if (maxDist == 0)
            return -1;
        else
            return maxDist;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        // Given array arr[]
        int[] arr = { 11, 2, 3, 8, 5, 2 };
 
        // Given difference K
        int K = 2;
 
        // Function call
        System.out.println(
            maxDistance(arr, K));
    }
}

Python3

# Python3 program for the above approach
 
# Function that find maximum distance
# between two elements whose absolute
# difference is K
def maxDistance(arr, K):
     
    # To store the first index
    map = {}
     
    # Traverse elements and find
    # maximum distance between 2
    # elements whose absolute
    # difference is K
    maxDist = 0
     
    for i in range(len(arr)):
         
        # If this is first occurrence
        # of element then insert
        # its index in map
        if not arr[i] in map:
            map[arr[i]] = i
             
        # If next element present in
        # map then update max distance
        if arr[i] + K in map:
            maxDist = max(maxDist,
                        i - map[arr[i] + K])
             
        # If previous element present
        # in map then update max distance
        if arr[i] - K in map:
            maxDist = max(maxDist,
                        i - map[arr[i] - K])
             
    # Return the answer
    if maxDist == 0:
        return -1
    else:
        return maxDist
     
# Driver code
 
# Given array arr[]
arr = [ 11, 2, 3, 8, 5, 2 ]
 
# Given difference K
K = 2
 
# Function call
print(maxDistance(arr,K))
 
# This code is contributed by Stuti Pathak

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function that find maximum distance
// between two elements whose absolute
// difference is K
static int maxDistance(int[] arr, int K)
{
 
    // To store the first index
    Dictionary<int,
            int> map = new Dictionary<int,
                                        int>();
 
    // Traverse elements and find
    // maximum distance between 2
    // elements whose absolute
    // difference is K
    int maxDist = 0;
 
    for (int i = 0; i < arr.Length; i++)
    {
 
    // If this is first occurrence
    // of element then insert
    // its index in map
    if (!map.ContainsKey(arr[i]))
        map.Add(arr[i], i);
 
    // If next element present in
    // map then update max distance
    if (map.ContainsKey(arr[i] + K))
    {
        maxDist = Math.Max(maxDist,
                        i - map[arr[i] + K]);
    }
 
    // If previous element present
    // in map then update max distance
    if (map.ContainsKey(arr[i] - K))
    {
        maxDist = Math.Max(maxDist,
                            i - map[arr[i] - K]);
    }
    }
 
    // Return the answer
    if (maxDist == 0)
    return -1;
    else
    return maxDist;
}
 
// Driver Code
public static void Main(String []args)
{
    // Given array []arr
    int[] arr = { 11, 2, 3, 8, 5, 2 };
 
    // Given difference K
    int K = 2;
 
    // Function call
    Console.WriteLine(
    maxDistance(arr, K));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript program for the above approach
 
// Function that find maximum distance
// between two elements whose absolute
// difference is K
function maxDistance(arr, K, N)
{
 
    // To store the first index
    var map = new Map();
     
    // Traverse elements and find
    // maximum distance between 2
    // elements whose absolute
    // difference is K
    var maxDist = 0;
 
    for(var i = 0; i < N; i++)
    {
 
        // If this is first occurrence
        // of element then insert
        // its index in map
        if (!map.has(arr[i]))
            map.set(arr[i], i);
 
        // If next element present in
        // map then update max distance
        if (map.has(arr[i] + K))
        {
            maxDist = Math.max(maxDist,
                          i - map.get(arr[i] + K));
        }
 
        // If previous element present
        // in map then update max distance
        if (map.has(arr[i] - K))
        {
            maxDist = Math.max(maxDist,
                          i - map.get(arr[i] - K));
        }
    }
 
    // Return the answer
    if (maxDist == 0)
        return -1;
    else
        return maxDist;
}
 
// Driver code
// Given array arr[]
var arr = [11, 2, 3, 8, 5, 2];
 
var N = arr.length;
 
// Given difference K
var K = 2;
 
// Function call
document.write( maxDistance(arr, K, N));
 
// This code is contributed by famously.
</script>
Producción: 

2

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *