Minimize maximum adjacent difference in a path from top-left to bottom-right

0 0 10 minutes read

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 paths

Input:

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
- 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 path
bool 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 differences
int 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 code
int 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 approach
 
import 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 approach
 
m,n=0,0
# Function to check if there is a valid path
def 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 differences
def 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 Call
print(minimumEnergyPath(arr))
 
# This code is contributed by Pushpesh Raj.

C#

// C# implementation
using 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 approach
 
let m, n;
 
// Function to check if there is a valid path
function 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 differences
function 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 code
 
let arr = [
    [ 1, 2, 1 ],
    [ 2, 8, 2 ],
    [ 2, 4, 2 ],
];
m = arr.length, n = arr[0].length;
 
// Function Call
console.log(minimumEnergyPath(arr));
 
// This code is contributed by Potta Lokesh

Output

Time Complexity: O(log₂(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 zambiatek!