Minimize Effort in Matrix Traversal with Height Differences
Adam is currently located at cell (0, 0) in a matrix of heights. Each value, in the matrix represented as heights[row][col] indicates the height of a cell at coordinates (row, col). Adamsβs goal is to reach the bottom right cell, which has coordinates (rows 1, columns 1) using up left or right movements. The objective is to determine the effort required to find a route with minimum effort with the difference in height between consecutive cells along the path.
Examples:
Input: heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]
Output: 2
Explanation: The sequence [1, 3, 5, 3, 5] has a difference of 2, at most between cells. Which we basically can see is better than the sequence [1,2,2,2,5] where the difference reaches 3.Input: heights = [[1, 2, 3], [3, 8, 4], [5, 3, 5]]
Output: 1
Explanation: The sequence [1,2,3,4,5] has a difference of 1 between consecutive cells. It is basically considered better when we compare it to the sequence [1,3,5,3,5].
Approach: To solve the problem follow the below idea:
To determine the effort required to travel from the left cell to the bottom right cell in a grid like structure efficiently and effectively. We can employ a Binary Search approach. By conducting this search on an effort range and examining each effort value individually. We can verify if there exists a path from the left cell to the bottom right cell while maintaining that the maximum absolute difference in heights between consecutive cells does not exceed our current effort value.
To solve the problem follow the below steps:
- Set βleftβ as 0 and βrightβ as the possible effort value which represents the maximum height difference within our grid.
- Continuously repeat these steps until βleftβ becomes greater than or equal to βrightβ;
- Calculate βmidβ by taking an average between βleftβ and βrightβ.
- Validate if there exists a path from our left cell, to our bottom right cell while ensuring that the maximum absolute height difference does not exceed βmidβ.
- This task can be accomplished by utilizing either Depth First Search (DFS) or Breadth First Search (BFS) algorithms.
- In the event that a path, like this, exists update the value of βrightβ, to βmidβ.
- If there is no path update the value of βleftβ to βmid + 1β.
- Ultimately the variable βleftβ will hold the effort needed to travel from the left cell to the bottom right cell.
- Check if it is possible using the function called βisPossibleβ.
- Create a helper function called βisPossibleβ that takes in βheightsβ and βmaxEffortβ as parameters. This function will check if there exists a path from the left cell to the bottom right cell where the maximum absolute difference in height between cells does not exceed βmaxEffortβ. The implementation of this helper function can utilize either Breadth First Search (BFS) or Depth First Search (DFS).
- We will Set b = 0. and now right will be equal to the possible effort value.
- Conduct a search within the left and right using the method.
- At last we will return βleftβ as it represents the effort.
Below is the C++ implementation of above approach:
C++
// C++ code for the above approach: #include <iostream> #include <queue> #include <vector> using namespace std; bool isPossible(vector<vector< int > >& heights, int maxEffort, int rows, int columns) { vector<vector< int > > dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; vector<vector< bool > > visited( rows, vector< bool >(columns, false )); queue<pair< int , int > > q; q.push({ 0, 0 }); visited[0][0] = true ; while (!q.empty()) { pair< int , int > curr = q.front(); q.pop(); // Reached the bottom-right cell if (curr.first == rows - 1 && curr.second == columns - 1) { return true ; } for (vector< int >& dir : dirs) { int newRow = curr.first + dir[0]; int newCol = curr.second + dir[1]; if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < columns && !visited[newRow][newCol]) { int heightDiff = abs ( heights[newRow][newCol] - heights[curr.first][curr.second]); if (heightDiff <= maxEffort) { q.push({ newRow, newCol }); visited[newRow][newCol] = true ; } } } } // No path found within the given effort // limit return false ; } int minimumEffortPath(vector<vector< int > >& heights) { int rows = heights.size(); int columns = heights[0].size(); int left = 0; // Maximum possible effort int right = 1e6; while (left < right) { int mid = left + (right - left) / 2; if (isPossible(heights, mid, rows, columns)) { right = mid; } else { left = mid + 1; } } return left; } // Drivers code int main() { vector<vector< int > > heights = { { 1, 2, 2 }, { 3, 8, 2 }, { 5, 3, 5 } }; int result = minimumEffortPath(heights); // Function Call cout << "Minimum Effort: " << result << endl; return 0; } |
Java
import java.util.*; public class MinimumEffortPath { static boolean isPossible(Vector<Vector<Integer>> heights, int maxEffort, int rows, int columns) { Vector<Vector<Integer>> dirs = new Vector<>(); dirs.add( new Vector<>(Arrays.asList( 0 , 1 ))); dirs.add( new Vector<>(Arrays.asList( 1 , 0 ))); dirs.add( new Vector<>(Arrays.asList( 0 , - 1 ))); dirs.add( new Vector<>(Arrays.asList(- 1 , 0 ))); Vector<Vector<Boolean>> visited = new Vector<>(rows); for ( int i = 0 ; i < rows; i++) { visited.add( new Vector<>(columns)); for ( int j = 0 ; j < columns; j++) { visited.get(i).add( false ); } } Queue<Vector<Integer>> q = new LinkedList<>(); q.add( new Vector<>(Arrays.asList( 0 , 0 ))); visited.get( 0 ).set( 0 , true ); while (!q.isEmpty()) { Vector<Integer> curr = q.poll(); // Reached the bottom-right cell if (curr.get( 0 ) == rows - 1 && curr.get( 1 ) == columns - 1 ) { return true ; } for (Vector<Integer> dir : dirs) { int newRow = curr.get( 0 ) + dir.get( 0 ); int newCol = curr.get( 1 ) + dir.get( 1 ); if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < columns && !visited.get(newRow).get(newCol)) { int heightDiff = Math.abs(heights.get(newRow).get(newCol) - heights.get(curr.get( 0 )).get(curr.get( 1 ))); if (heightDiff <= maxEffort) { q.add( new Vector<>(Arrays.asList(newRow, newCol))); visited.get(newRow).set(newCol, true ); } } } } // No path found within the given effort limit return false ; } static int minimumEffortPath(Vector<Vector<Integer>> heights) { int rows = heights.size(); int columns = heights.get( 0 ).size(); int left = 0 ; // Maximum possible effort int right = ( int ) 1e6; while (left < right) { int mid = left + (right - left) / 2 ; if (isPossible(heights, mid, rows, columns)) { right = mid; } else { left = mid + 1 ; } } return left; } // Driver code public static void main(String[] args) { Vector<Vector<Integer>> heights = new Vector<>(); heights.add( new Vector<>(Arrays.asList( 1 , 2 , 2 ))); heights.add( new Vector<>(Arrays.asList( 3 , 8 , 2 ))); heights.add( new Vector<>(Arrays.asList( 5 , 3 , 5 ))); int result = minimumEffortPath(heights); // Function Call System.out.println( "Minimum Effort: " + result); } } |
Python3
from typing import List , Tuple from queue import Queue def is_possible(heights: List [ List [ int ]], max_effort: int , rows: int , columns: int ) - > bool : # Directions for moving right, down, left, and up dirs = [( 0 , 1 ), ( 1 , 0 ), ( 0 , - 1 ), ( - 1 , 0 )] # Create a 2D array to keep track of visited cells visited = [[ False ] * columns for _ in range (rows)] # Create a queue for BFS traversal q = Queue() q.put(( 0 , 0 )) # Start from the top-left cell visited[ 0 ][ 0 ] = True while not q.empty(): curr = q.get() # Reached the bottom-right cell if curr[ 0 ] = = rows - 1 and curr[ 1 ] = = columns - 1 : return True for dir in dirs: new_row, new_col = curr[ 0 ] + dir [ 0 ], curr[ 1 ] + dir [ 1 ] # Check if the new position is within bounds and has not been visited if 0 < = new_row < rows and 0 < = new_col < columns and not visited[new_row][new_col]: height_diff = abs (heights[new_row][new_col] - heights[curr[ 0 ]][curr[ 1 ]]) # Check if the height difference is within the allowed effort if height_diff < = max_effort: q.put((new_row, new_col)) visited[new_row][new_col] = True # No path found within the given effort limit return False def minimum_effort_path(heights: List [ List [ int ]]) - > int : rows, columns = len (heights), len (heights[ 0 ]) left, right = 0 , 10 * * 6 # Binary search limits for the effort while left < right: mid = left + (right - left) / / 2 # Check if a path is possible with the current effort if is_possible(heights, mid, rows, columns): right = mid # Reduce the effort else : left = mid + 1 # Increase the effort return left # Driver Code if __name__ = = "__main__" : heights = [ [ 1 , 2 , 2 ], [ 3 , 8 , 2 ], [ 5 , 3 , 5 ] ] result = minimum_effort_path(heights) # Output the result print (f "Minimum Effort: {result}" ) |
C#
using System; using System.Collections.Generic; class Program { // Function to check if reaching the end cell is possible within maxEffort static bool IsPossible( int [][] heights, int maxEffort, int rows, int columns) { // Define directions: right, down, left, up int [][] dirs = { new int [] { 0, 1 }, new int [] { 1, 0 }, new int [] { 0, -1 }, new int [] { -1, 0 } }; // Create a visited array to mark visited cells bool [][] visited = new bool [rows][]; for ( int i = 0; i < rows; i++) { visited[i] = new bool [columns]; } // Queue to perform BFS traversal Queue<( int , int )> q = new Queue<( int , int )>(); q.Enqueue((0, 0)); // Start from the top-left cell visited[0][0] = true ; // Perform BFS while (q.Count > 0) { ( int r, int c) = q.Dequeue(); // Dequeue the current cell // Check if reached the bottom-right cell if (r == rows - 1 && c == columns - 1) { return true ; // Path found within the effort constraint } // Explore neighbors in all directions foreach ( int [] dir in dirs) { int newRow = r + dir[0]; int newCol = c + dir[1]; // Check if the neighbor is within bounds and not visited if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < columns && !visited[newRow][newCol]) { int heightDiff = Math.Abs(heights[newRow][newCol] - heights[r]); // Check if the height difference is within the effort limit if (heightDiff <= maxEffort) { q.Enqueue((newRow, newCol)); // Enqueue the valid neighbor visited[newRow][newCol] = true ; // Mark the neighbor as visited } } } } return false ; // No valid path found within the given effort constraint } // Function to find the minimum effort needed to traverse the grid static int MinimumEffortPath( int [][] heights) { int rows = heights.Length; int columns = heights[0].Length; int left = 0; int right = 1_000_000; // Maximum possible effort // Binary search to find the minimum effort while (left < right) { int mid = left + (right - left) / 2; if (IsPossible(heights, mid, rows, columns)) { right = mid; } else { left = mid + 1; } } return left; // Return the minimum effort required } static void Main( string [] args) { int [][] heights = new int [][] { new int [] { 1, 2, 2 }, new int [] { 3, 8, 2 }, new int [] { 5, 3, 5 } }; int result = MinimumEffortPath(heights); // Display the minimum effort required Console.WriteLine( "Minimum Effort: " + result); } } |
Javascript
function isPossible(heights, maxEffort, rows, columns) { const dirs = [ [0, 1], [1, 0], [0, -1], [-1, 0] ]; const visited = Array.from({ length: rows }, () => Array(columns).fill( false )); const q = []; q.push([0, 0]); visited[0][0] = true ; while (q.length > 0) { const curr = q.shift(); // Reached the bottom-right cell if (curr[0] === rows - 1 && curr[1] === columns - 1) { return true ; } for (const dir of dirs) { const newRow = curr[0] + dir[0]; const newCol = curr[1] + dir[1]; if ( newRow >= 0 && newRow < rows && newCol >= 0 && newCol < columns && !visited[newRow][newCol] ) { const heightDiff = Math.abs( heights[newRow][newCol] - heights[curr[0]][curr[1]] ); if (heightDiff <= maxEffort) { q.push([newRow, newCol]); visited[newRow][newCol] = true ; } } } } // No path found within the given effort limit return false ; } function minimumEffortPath(heights) { const rows = heights.length; const columns = heights[0].length; let left = 0; // Maximum possible effort let right = 1e6; while (left < right) { const mid = Math.floor(left + (right - left) / 2); if (isPossible(heights, mid, rows, columns)) { right = mid; } else { left = mid + 1; } } return left; } // Driver code const heights = [ [1, 2, 2], [3, 8, 2], [5, 3, 5] ]; const result = minimumEffortPath(heights); // Function Call console.log( "Minimum Effort:" , result); |
Minimum Effort: 2
Time Complexity: O(E*log(V))
Auxiliary Space: O(N.M)