Further explanation

  • 0

    Re: Short O(mn) solution

    Explanation of this great algo: using a brut-force solution, you would scan all the cells (m+n) and foreach scan its corresponding row and column which leads to O((m+n)*mn). This is not a polynomial solution.

    The current solution will scan each cell exactly twice = O(m*n)! How? for each element, it scans whether it's part of a streak and the streak's length (a sequence of elements without a wall = a place where we can drop bomb and kill streak.length enemies).
    Once it knows the streak length, on every future cell we can tell its streak length (if not a wall) so no need to scan anything. By memorizing the streak's length and use it on all the streak members we can avoid rescanning the streak for every cell. Then if the streak ends and we face a Wall, we just reset our counters and start counting again.

    This is a key code line within the inner loops:
    if (!j || grid[i][j-1] == 'W') { loop again on all neighbours...

    This line which sets an inner loop within the outer loops will get entered only on the first element or when we hit a wall. This way it will never run twice on the same element so only the outer loops affects the time complexity.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.