Given a matrix arr[][] of size M * N, where arr[i][j] represents the height of the cell (row, col). The task is to find a path from top-left to bottom-right such that the value of the maximum difference in height between adjacent cells is minimum for that path.
Note: A path energy is the maximum absolute difference in heights between two consecutive cells of the path.
Examples:
Input:
Example matrix
Output: 1
Explanation: The path {1, 2, 1, 2, 2} has a maximum absolute difference of 1 in consecutive cells and this is better than all other possible pathsInput:
Example matrix
Output: 1
Explanation: The highlighted path is the path with minimum value of maximum adjacent difference.
An approach using DFS + Binary Search:
The idea is to use Binary search to solve this problem, if we assume a threshold value as mid, and check whether there exist a path through which we can reach to end, then that might be my answer, else look for some bigger values.
- Initialize a variable start = 0 and end = maximum possible energy required and a variable result
- Do the following while start ? end
- Calculate mid = (start + end) / 2
- Check if mid energy is valid energy required by choosing any path into the matrix
- Checking the valid energy using a valid function
- Check if we go outside the matrix or if cell(i, j) is visited or absolute difference between consecutive cells is greater than our assumed maximum energy required
- If true, then return false
- Check if we reach the bottom-right cell
- If true, then return true
- Make the current cell(i, j) visited
- Make all four direction calls and check if any path is valid
- If true, then return true.
- Otherwise, return false
- Check if we go outside the matrix or if cell(i, j) is visited or absolute difference between consecutive cells is greater than our assumed maximum energy required
- Checking the valid energy using a valid function
- If the value from a valid function returns true, then update the result and move the end to mid – 1
- Otherwise, move the start to mid + 1
- Return the result
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;int m, n;// Function to check if there is a valid pathbool isValid(int i, int j, int x, vector<vector<bool> >& visited, vector<vector<int> >& arr, long long parent){ // Check if we go outside the matrix or // cell(i, j) is visited or absolute // difference between consecutive cell // is greater than our assumed maximum // energy required If true, // then return false if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || abs((long long)arr[i][j] - parent) > x) return false; // Check if we reach at bottom-right // cell If true, then return true if (i == m - 1 && j == n - 1) return true; // Make the current cell(i, j) visited visited[i][j] = true; // Make all four direction call and // check if any path is valid If true, // then return true. if (isValid(i + 1, j, x, visited, arr, arr[i][j])) return true; if (isValid(i - 1, j, x, visited, arr, arr[i][j])) return true; if (isValid(i, j + 1, x, visited, arr, arr[i][j])) return true; if (isValid(i, j - 1, x, visited, arr, arr[i][j])) return true; // Otherwise, return false return false;}// Function to find the minimum value among// the maximum adjacent differencesint minimumEnergyPath(vector<vector<int> >& arr){ // Initialize a variable start = 0 // and end = maximum possible // energy required int start = 0, end = 10000000; // Initialize a variable result int result = arr[0][0]; // Loop to implement the binary search while (start <= end) { int mid = (start + end) / 2; // Initialize a visited array // of size (m * n) vector<vector<bool> > visited( m, vector<bool>(n, false)); // Check if mid energy is valid // energy required by choosing any // path into the matrix If true, // update the result and // move end to mid - 1 if (isValid(0, 0, mid, visited, arr, arr[0][0])) { result = mid; end = mid - 1; } // Otherwise, move start to mid + 1 else { start = mid + 1; } } // Return the result return result;}// Driver codeint main(){ vector<vector<int> > arr = { { 1, 2, 1 }, { 2, 8, 2 }, { 2, 4, 2 }, }; m = arr.size(), n = arr[0].size(); // Function Call cout << minimumEnergyPath(arr); return 0;} |
Java
// Java code to implement the above approachimport java.io.*;class GFG { static int m, n; // Function to check if there is a valid path static boolean isValid(int i, int j, int x, boolean[][] visited, int[][] arr, long parent) { // Check if we go outside the matrix or // cell(i, j) is visited or absolute // difference between consecutive cell // is greater than our assumed maximum // energy required If true, // then return false if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || Math.abs(arr[i][j] - parent) > x) { return false; } // Check if we reach at bottom-right // cell If true, then return true if (i == m - 1 && j == n - 1) { return true; } // Make the current cell(i, j) visited visited[i][j] = true; // Make all four direction call and // check if any path is valid If true, // then return true. if (isValid(i + 1, j, x, visited, arr, arr[i][j])) return true; if (isValid(i - 1, j, x, visited, arr, arr[i][j])) return true; if (isValid(i, j + 1, x, visited, arr, arr[i][j])) return true; if (isValid(i, j - 1, x, visited, arr, arr[i][j])) return true; // Otherwise, return false return false; } // Function to find the minimum value among // the maximum adjacent differences static int minimumEnergyPath(int[][] arr) { // Initialize a variable start = 0 // and end = maximum possible // energy required int start = 0, end = 10000000; // Initialize a variable result int result = arr[0][0]; // Loop to implement the binary search while (start <= end) { int mid = (start + end) / 2; // Initialize a visited array // of size (m * n) boolean[][] visited = new boolean[m][n]; // Check if mid energy is valid // energy required by choosing any // path into the matrix If true, // update the result and // move end to mid - 1 if (isValid(0, 0, mid, visited, arr, arr[0][0])) { result = mid; end = mid - 1; } // Otherwise, move start to mid + 1 else { start = mid + 1; } } // Return the result return result; } public static void main(String[] args) { int[][] arr = { { 1, 2, 1 }, { 2, 8, 2 }, { 2, 4, 2 } }; m = arr.length; n = arr[0].length; // Function call System.out.print(minimumEnergyPath(arr)); }}// This code is contributed by lokesh. |
Python3
# Python code to implement the above approachm,n=0,0# Function to check if there is a valid pathdef isValid(i,j,x,visited,arr,parent): # Check if we go outside the matrix or # cell(i, j) is visited or absolute # difference between consecutive cell # is greater than our assumed maximum # energy required If true, # then return false if(i<0 or j<0 or i>=m or j>=n or visited[i][j] or abs(arr[i][j]-parent)>x): return False # Check if we reach at bottom-right # cell If true, then return true if(i==m-1 and j==n-1): return True # Make the current cell(i, j) visited visited[i][j]=True # Make all four direction call and # check if any path is valid If true, # then return true. if(isValid(i+1,j,x,visited,arr,arr[i][j])): return True if(isValid(i-1,j,x,visited,arr,arr[i][j])): return True if(isValid(i,j+1,x,visited,arr,arr[i][j])): return True if(isValid(i,j-1,x,visited,arr,arr[i][j])): return True # Otherwise, return false return False # Function to find the minimum value among# the maximum adjacent differencesdef minimumEnergyPath(arr): # Initialize a variable start = 0 # and end = maximum possible # energy required start,end=0,10000000 # Initialize a variable result result=arr[0][0] # Loop to implement the binary search while(start<=end): mid=(start+end)//2 # Initialize a visited array # of size (m * n) visited=[[False for i in range(n)] for j in range(m)] # Check if mid energy is valid # energy required by choosing any # path into the matrix If true, # update the result and # move end to mid - 1 if(isValid(0,0,mid,visited,arr,arr[0][0])): result=mid end=mid-1 # Otherwise, move start to mid + 1 else: start=mid+1 # Return the result return result # Driver Code arr=[[1,2,1],[2,8,2],[2,4,2]]m=len(arr)n=len(arr[0])# Function Callprint(minimumEnergyPath(arr))# This code is contributed by Pushpesh Raj. |
C#
// C# implementationusing System;public class GFG { static int m, n; // Function to check if there is a valid path public static bool isValid(int i, int j, int x, bool[, ] visited, int[, ] arr, int parent) { // Check if we go outside the matrix or // cell(i, j) is visited or absolute // difference between consecutive cell // is greater than our assumed maximum // energy required If true, // then return false if ((i < 0) || (j < 0) || (i >= m) || (j >= n) || (visited[i, j] == true) || (Math.Abs(arr[i, j] - parent) > x)) return false; // Check if we reach at bottom-right // cell If true, then return true if (i == m - 1 && j == n - 1) return true; // Make the current cell(i, j) visited visited[i, j] = true; // Make all four direction call and // check if any path is valid If true, // then return true. if (isValid(i + 1, j, x, visited, arr, arr[i, j])) return true; if (isValid(i - 1, j, x, visited, arr, arr[i, j])) return true; if (isValid(i, j + 1, x, visited, arr, arr[i, j])) return true; if (isValid(i, j - 1, x, visited, arr, arr[i, j])) return true; // Otherwise, return false return false; } // Function to find the minimum value among // the maximum adjacent differences public static int minimumEnergyPath(int[, ] arr) { // Initialize a variable start = 0 // and end = maximum possible // energy required int start = 0, end = 10000000; // Initialize a variable result int result = arr[0, 0]; // Loop to implement the binary search while (start <= end) { int mid = (int)((start + end) / 2); // Initialize a visited array // of size (m * n) bool[, ] visited = new bool[m, n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { visited[i, j] = false; } } // Check if mid energy is valid // energy required by choosing any // path into the matrix If true, // update the result and // move end to mid - 1 if (isValid(0, 0, mid, visited, arr, arr[0, 0]) == true) { result = mid; end = mid - 1; } // Otherwise, move start to mid + 1 else { start = mid + 1; } } // Return the result return result; } static public void Main() { int[, ] arr = { { 1, 2, 1 }, { 2, 8, 2 }, { 2, 4, 2 }, }; m = arr.GetLength(0); n = arr.GetLength(1); // Function Call Console.WriteLine(minimumEnergyPath(arr)); }}// This code is contributed by ksam24000 |
Javascript
// JavaScript code for the above approachlet m, n;// Function to check if there is a valid pathfunction isValid(i, j, x, visited, arr, parent){ // Check if we go outside the matrix or // cell(i, j) is visited or absolute // difference between consecutive cell // is greater than our assumed maximum // energy required If true, // then return false if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || Math.abs(arr[i][j] - parent) > x) return false; // Check if we reach at bottom-right // cell If true, then return true if (i == m - 1 && j == n - 1) return true; // make the current cell(i, j) visited visited[i][j] = true; // make all four direction call and // check if any path is valid If true, // then return true. if (isValid(i + 1, j, x, visited, arr, arr[i][j])) return true; if (isValid(i - 1, j, x, visited, arr, arr[i][j])) return true; if (isValid(i, j + 1, x, visited, arr, arr[i][j])) return true; if (isValid(i, j - 1, x, visited, arr, arr[i][j])) return true; // Otherwise, return false return false;}// Function to find the minimum value among// the maximum adjacent differencesfunction minimumEnergyPath(arr){ // Initialize a variable start = 0 // and end = maximum possible // energy required let start = 0, end = 10000000; // Initialize a variable result let result = arr[0][0]; // Loop to implement the binary search while(start <= end) { let mid = Math.floor((start + end) / 2); // Initialize a visited array // of size (m * n) let visited = new Array(m) for(let i = 0; i < m; i++) { visited[i] = new Array(n).fill(0) } // Check if mid energy is valid // energy required by choosing any // path into the matrix If true, // update the result and // move end to mid - 1 if(isValid(0, 0, mid, visited, arr, arr[0][0])) { result = mid; end = mid - 1; } // Otherwise, move start to mid + 1 else { start = mid + 1; } } // Return the result return result;}// Driver codelet arr = [ [ 1, 2, 1 ], [ 2, 8, 2 ], [ 2, 4, 2 ],];m = arr.length, n = arr[0].length;// Function Callconsole.log(minimumEnergyPath(arr));// This code is contributed by Potta Lokesh |
Output
1
Time Complexity: O(log2(K) * (M*N)), where K is the maximum element in the matrix and M, and N are the number of rows and columns in the given matrix respectively.
Auxiliary Space: O(M * N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
