search

madhuri7112 / Leetcode

Leetcode Solutions
GNU General Public License v3.0
0 stars 0 forks source link

Maximum minimum Node in path matrix #151

Open madhuri7112 opened 4 years ago

madhuri7112 commented 4 years ago

https://leetcode.com/discuss/interview-question/377735/Amazon-Interview-Question.

Given a grid M x N cells having weight in each cell(any integer), For every path from TOP-LEFT to BOTTOM-RIGHT, find the minimum weight you come across.(Minimum per path.) Now from all those minimum weights, find the Maximum. You can move in all 8 directions.

Link of the question: https://careercup.com/question?id=5715463313555456

madhuri7112 commented 4 years ago

Very cute problem. Had to think about it for a few minutes.

HINT: Look to work through cells (finite), not paths (infinite).

Algorithm is as follows: Add all cells to a min heap Take lowest node Check if path from top left to bottom right not using any previously seen nodes exists; if it does, this is the min on that path, and otherwise this is never a min Add the mins to a stack and the last one on is our answer

madhuri7112 commented 4 years ago

For each cell check if there is a path with this value as minimum -> check if there is a path where all the cells are greater than this value. -> so treat every cell with greater value as block.

Find the max of such possible cell

This can be optimized to ^^