Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which the total cost incurred is minimum.
From the cell (i,j) we can go (i,j-1), (i, j+1), (i-1, j), (i+1, j).
Note: It is assumed that negative cost cycles do not exist in the input matrix.
Example 1:
Input: grid = {{9,4,9,9},{6,7,6,4},
{8,3,3,7},{7,4,9,10}}
Output: 43
Explanation: The grid is-
9 4 9 9
6 7 6 4
8 3 3 7
7 4 9 10
The minimum cost is-
9 + 4 + 7 + 3 + 3 + 7 + 10 = 43.
My working code:
global INT_MAX
global n
n = 4
INT_MAX = 3 ** 38
class Solution:
# <- this returns the minVertex's co-orinates ->
def minimumVertex(self,distMat,visited):
minVertexi = 0
minVertexj = 0
max1 = INT_MAX
for i in range(n):
for j in range(n):
if distMat(i)(j) < max1 and visited(i)(j) == False:
max1 = distMat(i)(j)
minVertexi = i
minVertexj = j
return minVertexi, minVertexj
def minimumCostPath(self, grid):
for listItem in grid:
n = len(listItem)
# <- visited matrix is created with all False ->
visited = ()
for i in range(n):
eachRow = ()
for j in range(n):
eachRow.append(False)
visited.append(eachRow)
# <- distMat is created with all values initialized with INT_MAX ->
distMat = ()
for i in range(n):
eachRow1 = ()
for j in range(n):
eachRow1.append(INT_MAX)
distMat.append(eachRow1)
distMat(0)(0) = grid(0)(0)
drow = (-1, 1, 0, 0)
dcol = (0, 0, -1, 1)
for _ in range(n):
for currj in range(n):
mini,minj = self.minimumVertex(distMat,visited)
visited(mini)(minj) = True
for k in range(len(drow)):
nbri = mini + drow(k)
nbrj = minj + dcol(k)
# print("outside nbri = ",nbri,"outside nbrj = ",nbrj)
if nbri >=0 and nbrj >= 0 and nbri < n and nbrj < n:
if visited(nbri)(nbrj) == False:
# print("inside nbri = ",nbri,"inside nbrj = ",nbrj)
if distMat(nbri)(nbrj) > distMat(mini)(minj) + grid(nbri)(nbrj):
distMat(nbri)(nbrj) = distMat(mini)(minj) + grid(nbri)(nbrj)
return distMat(n-1)(n-1)
Expected Time Compelxity: O(n2*log(n))
Expected Auxiliary Space: O(n2)
Problem with my code:
My logic is alright however it is exceeding the time limit, how do I optimize it?