# (8) Binary Search: Path With Minimum Effort

[Question Link](https://leetcode.com/problems/path-with-minimum-effort/)  and  [Solution Link](https://leetcode.com/submissions/detail/615661058/) 

**Difficulty**: Medium

**Prerequisite**: DFS on the grid

**Problem Statement**: Given a 2D grid, you need to find a path such that difference of adjacent elements of that grid is minimum possible.

**Approach**: We will make DFS call on the grid and assume `mid` is the minimum difference between adjacent elements of the path. If it satisfies the condition then `high = mid` else `low = mid + 1`.

```
int vis[105][105];
void ok(int mid, int x, int y, vector<vector<int>> &heights)
{
    if (!vis[x][y])
    {
        vis[x][y] = 1;
        int N = heights.size(), M = heights[0].size();
        if (x - 1 >= 0 && !vis[x - 1][y] && abs(heights[x][y] - heights[x - 1][y]) <= mid)
            ok(mid, x - 1, y, heights);
        if (y - 1 >= 0 && !vis[x][y - 1] && abs(heights[x][y] - heights[x][y - 1]) <= mid)
            ok(mid, x, y - 1, heights);
        if (x + 1 < N && !vis[x + 1][y] && abs(heights[x][y] - heights[x + 1][y]) <= mid)
            ok(mid, x + 1, y, heights);
        if (y + 1 < M && !vis[x][y + 1] && abs(heights[x][y] - heights[x][y + 1]) <= mid)
            ok(mid, x, y + 1, heights);
    }
}
int minimumEffortPath(vector<vector<int>> &heights)
{
    int N = heights.size();
    int M = heights[0].size();
    int low = 0, high = 1e9 + 2, mid;
    while (low < high)
    {
        mid = low + (high - low) / 2;
        memset(vis, 0, sizeof(vis));
        ok(mid, 0, 0, heights);
        if (vis[N - 1][M - 1]) high = mid;
        else low = mid + 1;
    }
    return low;
}
``` 

**Subscribe to the newsletter so that you never miss any post or update just like this one.**

You can follow me on Hashnode for:

- Daily Data Structure and Algorithm based questions
- Getting knowledge of various development-related tools, concepts, and practices

 [Twitter](https://twitter.com/_Arsalaan_) ,  [GitHub](https://github.com/arsalanhub) ,  [LinkedIn](https://www.linkedin.com/in/mohammadarsalan/)  and  [Hashnode](https://hashnode.com/@mohdarsalan)