Given a 2D array of size M * N and two points in the form (X1, Y1) and (X2 , Y2) where X1 and X2 represents the rows and Y1 and Y2 represents the column. The task is to calculate the Manhattan distance between the given points.
Examples:
Input: M = 5, N = 5, X1 = 1, Y1 = 2, X2 = 3, Y2 = 3
Output: 3
Explanation: As per the definition, the Manhattan the distance is same as sum of the absolute difference of the coordinates.Input: M = 5, N = 5, X1 = 4, Y1 = 2, X2 = 4, Y2 = 2
Output: 0
Approach: The approach is based on mathematical observation. The Manhattan distance between two points is the sum of absolute difference of the coordinates.
Manhattan distance = |X1 – X2| + |Y1 – Y2|
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Code to calculate Manhattan distanceint manhattanDist(int M, int N, int X1, int Y1, int X2, int Y2){ int dist = abs(X2 - X1) + abs(Y2 - Y1); return dist;}// Driver codeint main(){ // Define size of 2-D array int M = 5, N = 5; // First point int X1 = 1, Y1 = 2; // Second point int X2 = 3, Y2 = 3; cout << manhattanDist(M, N, X1, Y1, X2, Y2); return 0;} |
Java
// java code to implement above approachclass GFG{ // Code to calculate Manhattan distance static int manhattanDist(int M, int N, int X1, int Y1, int X2, int Y2) { int dist = Math.abs(X2 - X1) + Math.abs(Y2 - Y1); return dist; } // Driver code public static void main(String args[]) { // Define size of 2-D array int M = 5, N = 5; // First point int X1 = 1, Y1 = 2; // Second point int X2 = 3, Y2 = 3; System.out.println(manhattanDist(M, N, X1, Y1, X2, Y2)); }}// This code is contributed by gfgking. |
Python3
# Python code for the above approachimport math as Math# Code to calculate Manhattan distancedef manhattanDist(M, N, X1, Y1, X2, Y2): dist = Math.fabs(X2 - X1) + Math.fabs(Y2 - Y1) return (int)(dist)# Driver code# Define size of 2-D arrayM = 5N = 5# First pointX1 = 1Y1 = 2# Second pointX2 = 3Y2 = 3print(manhattanDist(M, N, X1, Y1, X2, Y2))# This code is contributed by Saurabh Jaiswal |
C#
// C# code to implement above approachusing System;class GFG { // Code to calculate Manhattan distance static int manhattanDist(int M, int N, int X1, int Y1, int X2, int Y2) { int dist = Math.Abs(X2 - X1) + Math.Abs(Y2 - Y1); return dist; } // Driver code public static void Main() { // Define size of 2-D array int M = 5, N = 5; // First point int X1 = 1, Y1 = 2; // Second point int X2 = 3, Y2 = 3; Console.WriteLine( manhattanDist(M, N, X1, Y1, X2, Y2)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Code to calculate Manhattan distance function manhattanDist(M, N, X1, Y1, X2, Y2) { let dist = Math.abs(X2 - X1) + Math.abs(Y2 - Y1); return dist; } // Driver code // Define size of 2-D array let M = 5, N = 5; // First point let X1 = 1, Y1 = 2; // Second point let X2 = 3, Y2 = 3; document.write(manhattanDist(M, N, X1, Y1, X2, Y2)); // This code is contributed by Potta Lokesh </script> |
3
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!