Leetcode Problem 1102 - Path With Maximum Minimum Value.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Problem Statement.\n",
    "\n",
    "Given a matrix of integers grid with m rows and n columns, find the maximum score of a path starting at [0,0] and ending at [m-1,n-1].\n",
    "\n",
    "The score of a path is the minimum value in that path.  For example, the value of the path 8 →  4 →  5 →  9 is 4.\n",
    "\n",
    "A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: [[5,4,5],[1,2,6],[7,4,6]]\n",
    "Output: 4\n",
    "Explanation: \n",
    "The path with the maximum score is highlighted in yellow. \n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]\n",
    "Output: 2\n",
    "\n",
    "Example 3:\n",
    "\n",
    "Input: [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]\n",
    "Output: 3\n",
    "\n",
    " \n",
    "\n",
    "Note:\n",
    "\n",
    "    1 <= m, n <= 100\n",
    "    0 <= grid[i][j] <= 109"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Time Limit Exceeded"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid)-1, len(grid[0])-1\n",
    "        target = (m, n)\n",
    "        \n",
    "        def maximumMinimumValue(visited, source, minValue):\n",
    "            if source == target: return minValue\n",
    "            \n",
    "            x, y = source\n",
    "            score = 0\n",
    "            \n",
    "            for x1, y1 in [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]:\n",
    "                if 0 <= x1 <= m and 0 <= y1 <= n and (x1, y1) not in visited:\n",
    "                    currMin = maximumMinimumValue(visited.union({(x1, y1)}), (x1, y1), min(minValue, grid[x1][y1]))\n",
    "                    score = max(score, currMin)\n",
    "\n",
    "            return score\n",
    "        \n",
    "        return maximumMinimumValue({(0, 0)}, (0, 0), grid[0][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Djikstra - Max Heap -  O(M * N Log M * N) runtime, O(M * N) space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, A: List[List[int]]) -> int:\n",
    "        dire = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        R, C = len(A), len(A[0])\n",
    "        \n",
    "        maxHeap = [(-A[0][0], 0, 0)]\n",
    "        seen = [[0 for _ in range(C)] for _ in range(R)]\n",
    "        seen[0][0] = 1\n",
    "        \n",
    "        while maxHeap:\n",
    "            val, x, y = heappop(maxHeap)\n",
    "            if x == R - 1 and y == C - 1: return -val\n",
    "            for dx, dy in dire:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < R and 0 <= ny < C and not seen[nx][ny]:\n",
    "                    seen[nx][ny] = 1 # passed\n",
    "                    heappush(maxHeap, (-1 * min(-val, A[nx][ny]), nx, ny))\n",
    "                    \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "instance = Solution()\n",
    "instance.maximumMinimumPath([[5,4,5],[1,2,6],[7,4,6]])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}