Trail to Minimize Effort - Google Top Interview Questions


Problem Statement :


You are given a two-dimensional list of integers matrix where element represents the height of a hill. 

You are currently on the top left cell and want to go to the bottom right cell. 

In each move, you can go up, down, left, or right.

 A path's cost is defined to the largest absolute difference of heights between any two consecutive cells in the path. 

Return the minimum cost of any path.

Constraints

1 ≤ n, m ≤ 250 where n and m are the number of rows and columns in matrix

Example 1
\
Input


matrix = [

    [1, 5, 3],

    [2, 4, 3],

    [3, 5, 3]

]

Output

2

Explanation

We can take the following path [1, 2, 4, 5, 3]. The largest absolute difference of heights between any 
two consecutive cells is between 2 and 4.



Solution :



title-img




                        Solution in C++ :

int solve(vector<vector<int>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    vector<int> dir{0, -1, 0, 1, 0};
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    set<pair<int, pair<int, int>>> s;

    // setting the base case
    dist[0][0] = 0;
    s.insert({0, {0, 0}});

    while (!s.empty()) {
        auto [distance, cord] = *s.begin();
        auto [xcord, ycord] = cord;
        s.erase(s.begin());
        for (int k = 0; k < 4; k++) {
            int x = xcord + dir[k];
            int y = ycord + dir[k + 1];
            if (x >= 0 and x < n and y >= 0 and y < m) {
                int maxd = max(distance, abs(matrix[x][y] - matrix[xcord][ycord]));
                if (dist[x][y] > maxd) {
                    if (s.find({dist[x][y], {x, y}}) != s.end()) {
                        s.erase(s.find({dist[x][y], {x, y}}));
                    }
                    dist[x][y] = maxd;
                    s.insert({dist[x][y], {x, y}});
                }
            }
        }
    }
    return dist[n - 1][m - 1];
}
                    


                        Solution in Java :

import java.util.*;

class Solution {
    static int M;
    public int solve(int[][] matrix) {
        int N = matrix.length;
        M = matrix[0].length;
        DisjointSetUnion dsu = new DisjointSetUnion(N * M);
        ArrayList<Edge> edges = new ArrayList<Edge>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (i < N - 1)
                    edges.add(new Edge(i, j, 'D', Math.abs(matrix[i][j] - matrix[i + 1][j])));
                if (j < M - 1)
                    edges.add(new Edge(i, j, 'R', Math.abs(matrix[i][j] - matrix[i][j + 1])));
            }
        }
        Collections.sort(edges);

        for (Edge e : edges) {
            dsu.connect(e.a, e.b);
            if (dsu.connected(0, N * M - 1))
                return e.w;
        }
        return 0;
    }

    static class Edge implements Comparable<Edge> {
        int a;
        int b;
        int w;
        public Edge(int i, int j, char d, int w) {
            a = i * M + j;
            if (d == 'D')
                b = (i + 1) * M + j;
            else
                b = i * M + (j + 1);
            this.w = w;
        }

        public int compareTo(Edge e) {
            return w - e.w;
        }
    }

    static class DisjointSetUnion {
        public int[] parent;
        public int[] weight;
        public int count;

        public DisjointSetUnion(int N) {
            count = N;
            parent = new int[N];
            for (int i = 0; i < N; i++) parent[i] = i;
            weight = new int[N];
            Arrays.fill(weight, 1);
        }

        //"find"
        public int root(int p) {
            if (p == parent[p])
                return p;
            return parent[p] = root(parent[p]);
        }

        //"union"
        public void connect(int p, int q) {
            p = root(p);
            q = root(q);
            if (p == q)
                return;
            if (weight[p] < weight[q]) {
                parent[p] = q;
                weight[q] += weight[p];
            } else {
                parent[q] = p;
                weight[p] += weight[q];
            }
            count--;
        }

        public boolean connected(int p, int q) {
            return root(p) == root(q);
        }
    }
}
                    


                        Solution in Python : 
                            
class Solution:
    def solve(self, A):
        R, C = len(A), len(A[0])
        DIRS = [[1, 0], [0, 1], [-1, 0], [0, -1]]

        def bfs(cost):
            q = [[0, 0]]
            seen = set(tuple([0, 0]))
            while q:
                i, j = q.pop()
                if i == R - 1 and j == C - 1:
                    return True
                for di, dj in DIRS:
                    ni, nj = di + i, dj + j
                    if (
                        0 <= ni < R
                        and 0 <= nj < C
                        and abs(A[ni][nj] - A[i][j]) <= cost
                        and tuple([ni, nj]) not in seen
                    ):
                        seen.add(tuple([ni, nj]))
                        q.append([ni, nj])
            return False

        l = 0
        r = max([max(x) for x in A])

        while l < r:
            m = l + r >> 1
            if bfs(m):
                r = m
            else:
                l = m + 1
        return l
                    


View More Similar Problems

Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →

Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →