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 :
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 →