Suma mínima de todas las diferencias absolutas de los mismos elementos de columna en filas adyacentes en una Array dada

Dada una array mat[][] que tiene N filas y M columnas, la tarea es encontrar la distancia mínima entre dos filas adyacentes donde la distancia entre dos filas se define como la suma de todas las diferencias absolutas entre dos elementos presentes en la misma columna en las dos filas.

Ejemplos:

Entrada: mat[][] = {{1, 4, 7, 10}, {2, 5, 8, 11}, {6, 9, 3, 12}}
Salida: 4
Explicación: La distancia entre los dos primeros las filas se pueden calcular como (2-1) + (5-4) + (8-7) + (11-10) = 4. De manera similar, la distancia entre la segunda y la tercera fila se puede calcular como (6-2) + (9-5) + (8-3) + (12-11) = 14. Por lo tanto, la distancia mínima entre todas las filas adyacentes es 4.             

Entrada: mat[][] = {{1, 25, 81}, {2, 36, 100}, {9, 49, 50}, {16, 64, 25}}
Salida: 31

Enfoque:  El problema dado es un problema basado en la implementación que se puede resolver iterando a través de la array por filas y calculando las distancias sobre todos los pares de filas adyacentes. Mantener el mínimo de todas las distancias calculadas en una variable que es la respuesta requerida.

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

// C++ program of the above approach.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum distance
// between two adjacent rows in mat
int calcDist(int N, int M, vector<vector<int> > mat)
{
    // Stores the required value
    int ans = INT_MAX;
 
    // Loop to traverse all the
    // pair of rows in mat[][]
    for (int i = 0; i < N - 1; i++) {
        // Stores the distance
        int dist = 0;
 
        // Loop to calculate
        // the distance
        for (int j = 0; j < M; j++) {
            dist += abs(mat[i][j] - mat[i + 1][j]);
        }
 
        // Update ans
        ans = min(ans, dist);
    }
 
    // Return Answer
    return ans;
}
 
// C++ program of the above approach
int main()
{
    vector<vector<int> > mat = { { 1, 4, 7, 10 },
                                 { 2, 5, 8, 11 },
                                 { 6, 9, 3, 2 } };
    cout << calcDist(mat.size(), mat[0].size(), mat);
 
    return 0;
}

// JAVA program of the above approach.
import java.util.*;
class GFG
{
 
  // Function to find minimum distance
  // between two adjacent rows in mat
  public static int
    calcDist(int N, int M,
             ArrayList<ArrayList<Integer> > mat)
  {
 
    // Stores the required value
    int ans = Integer.MAX_VALUE;
 
    // Loop to traverse all the
    // pair of rows in mat[][]
    for (int i = 0; i < N - 1; i++)
    {
 
      // Stores the distance
      int dist = 0;
 
      // Loop to calculate
      // the distance
      for (int j = 0; j < M; j++) {
        dist += Math.abs(mat.get(i).get(j)
                         - mat.get(i + 1).get(j));
      }
 
      // Update ans
      ans = Math.min(ans, dist);
    }
 
    // Return Answer
    return ans;
  }
 
  // JAVA program of the above approach
  public static void main(String[] args)
  {
    ArrayList<ArrayList<Integer> > mat
      = new ArrayList<ArrayList<Integer> >();
    ArrayList<Integer> temp1 = new ArrayList<Integer>(
      Arrays.asList(1, 4, 7, 10));
    ArrayList<Integer> temp2 = new ArrayList<Integer>(
      Arrays.asList(2, 5, 8, 11));
    ArrayList<Integer> temp3 = new ArrayList<Integer>(
      Arrays.asList(6, 9, 3, 2));
    mat.add(temp1);
    mat.add(temp2);
    mat.add(temp3);
 
    System.out.print(
      calcDist(mat.size(), mat.get(0).size(), mat));
  }
}
 
// This code is contributed by Taranpreet

# python3 program of the above approach.
INT_MAX = 2147483647
 
# Function to find minimum distance
# between two adjacent rows in mat
def calcDist(N, M, mat):
 
    # Stores the required value
    ans = INT_MAX
 
    # Loop to traverse all the
    # pair of rows in mat[][]
    for i in range(0, N - 1):
       
        # Stores the distance
        dist = 0
 
        # Loop to calculate
        # the distance
        for j in range(0, M):
            dist += abs(mat[i][j] - mat[i + 1][j])
 
        # Update ans
        ans = min(ans, dist)
 
    # Return Answer
    return ans
 
if __name__ == "__main__":
 
    mat = [[1, 4, 7, 10],
           [2, 5, 8, 11],
           [6, 9, 3, 2]]
 
    print(calcDist(len(mat), len(mat[0]), mat))
 
    # This code is contributed by rakeshsahni

// C# program of the above approach.
using System;
class GFG
{
 
  // Function to find minimum distance
  // between two adjacent rows in mat
  static int calcDist(int N, int M, int[, ] mat)
  {
 
    // Stores the required value
    int ans = Int32.MaxValue;
 
    // Loop to traverse all the
    // pair of rows in mat[][]
    for (int i = 0; i < N - 1; i++) {
      // Stores the distance
      int dist = 0;
 
      // Loop to calculate
      // the distance
      for (int j = 0; j < M; j++) {
        dist += Math.Abs(mat[i, j] - mat[i + 1, j]);
      }
 
      // Update ans
      ans = Math.Min(ans, dist);
    }
 
    // Return Answer
    return ans;
  }
 
  // Criver code
  public static void Main()
  {
    int[, ] mat = { { 1, 4, 7, 10 },
                   { 2, 5, 8, 11 },
                   { 6, 9, 3, 2 } };
    Console.Write(calcDist(mat.GetLength(0),
                           mat.GetLength(1), mat));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to find minimum distance
       // between two adjacent rows in mat
       function calcDist(N, M, mat)
       {
        
           // Stores the required value
           let ans = Number.MAX_VALUE;
 
           // Loop to traverse all the
           // pair of rows in mat[][]
           for (let i = 0; i < N - 1; i++) {
               // Stores the distance
               let dist = 0;
 
               // Loop to calculate
               // the distance
               for (let j = 0; j < M; j++) {
                   dist += Math.abs(mat[i][j] - mat[i + 1][j]);
               }
 
               // Update ans
               ans = Math.min(ans, dist);
           }
 
           // Return Answer
           return ans;
       }
 
       let mat = [[1, 4, 7, 10],
       [2, 5, 8, 11],
       [6, 9, 3, 2]];
       document.write(calcDist(mat.length, mat[0].length, mat));
 
      // This code is contributed by Potta Lokesh
   </script>

4

Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)