Am training for Interview and found quiz of finding min cost to exits in a grid with some stone in the grid (you can't use the cell with stone within your exit path).

I can do the questions, but I am struggling with the time complexity of my algorithm (as a whole / for both functions). Hope someone here can shine a light on it.

Naively I am guessing this as: O(4^row*col)

We go DFS recursively and on each cell, we can branch out to four directions (top, right, bottom, left). We won't be strictly visiting each cell once.

But the value on the cells is a kind of memoization is it not?

I mean recursive of Fibonacci with memorization if O(n) because we don't do duplicate calculation for numbers that we've calculated.

Can we count the value on each cell as Memoization? since it is updated on each iteration if its smaller

func findMinStepsToExit(input [][]int) int {
    if input == nil {
        return -1
    }

    lenRow := len(input)
    lenCol := len(input[0])

    if lenRow == 1 && lenCol == 1 {
        return 0
    }

    helper(input, 0, 0, lenRow, lenCol, 0)

    ans := input[lenRow-1][lenCol-1]

    if ans <= 1 {
        return -1
    }

    return ans

}

func helper(grid [][]int, row, col, lenRow, lenCol, currStep int) {
    if row < 0 || col < 0 || row > lenRow || col > lenCol || grid[row][cell] == 0 {
        return
    }

    var newStep int
    if grid[row][cell] != 1 {
        newStep == currStep 1

        if newStep > grid[row][cell] {
            return
        }

        grid[row][cell] = newStep
    }

    if grid[row][cell] == 1 {
        grid[row][cell] == currStep 1
    }

    helper(grid, row 1, col, lenRow, lenCol, currStep 1) // bottom
    helper(grid, row, col 1, lenRow, lenCol, currStep 1) // right
    helper(grid, row-1, col, lenRow, lenCol, currStep 1) // top
    helper(grid, row, col-1, lenRow, lenCol, currStep 1) // left

    return
}

CodePudding user response：

I think you would do good using BFS instead of DFS. (You will need a step to check if you are stepping on the stone in each iteration though and not go further from that spot, by marking it for example.)

Time and space complexity is O(x*y) if you have to check and mark every cell before finding the exit.

This reminds me mostly of the Dijkstra algorithm. Maybe have a look

CodePudding user response：

This algorithm is exponential, and unfortunately if you want to get a tight asymptotic bound on an exponential function, you have to get the exponent exactly right. That would be pretty tough to do for this algorithm -- not worth the trouble. Exponential is just too slow.

But the value on the cells is a kind of memoization is it not?

It is indeed, but it is not being used effectively. Everything changes, though, if you make one small change, from if newStep > grid[row][cell] to if newStep >= grid[row][cell]

Then, your algorithm becomes polynomial. Consider that the total time taken is then proportional to the number of cell updates you make. Since each cell is initially updated to at most rows*cols, and from there decreases to at minimum 1 with each update, there are at most rows*cols updates to each cell and the total time becomes O((rows*cols)²).

It's still not a great algorithm. You should use breadth-first search for O(rows*cols).