Speedy Python solution with thorough explanations and cautionary tales


  • 0
    M

    Note: this solution builds upon the work of others here. I'm presenting this to help you understand how such solutions work (because code you don't understand is code you can't maintain).

    My first attempt was total brute force (just to get a working solution first before optimizing). For each point with a valid starting point, I'd work outward in the four directions to calculate the number of enemies. It worked but was slow - about 8000 ms for a [100x1000] grid. The worst case (no walls) makes the time complexity O((mn)^2) - pretty awful for a large grid! (The space complexity is of course a minimal O(1).)

    As this was an unfamiliar problem to me, and wanting to learn more about dynamic programming, I looked at the solutions to gain insights. No matter what, you end up walking the grid at least once, but storing calculations as you go (memoizing) saves a lot of duplicated effort. The key to this is reading each row and each column twice: first forward, then backwards.

    Given a "hit grid" (of the same dimensions as the given grid) initialized with zeroes:

    • Walk each row forward, then backward, then walk each column forward, then backward. On each of these passes:
      • init temp counter to zero
      • increment temp counter if you encounter an enemy E or reset if you hit a wall W
      • add the current temp counter value to the value in the hit grid at that point (if the current point is E or W, you can of course skip that write as it will never be a starting point).

    In total you have walked the grid four times: sweeping in each of the four axial directions (up and down X, then up and down Y).

    Finally, walk the hit grid and find the max value. (As an optimization, you can do this during the hit grid update in the last walk above to save making a fifth walk of the whole grid).

    While it may not be intuitive, you can visualize it with pen and paper to verify it works.

    This has time complexity O(mn) using space O(mn) - quite an improvement.

    Realizing that time O(mn) is really O(kmn), it can be helpful to optimize k. Above, we brought k from 5 to 4 with a minor change... perhaps we can halve that?

    Rather than walk rows and columns forwards and backwards in four grid loops (each grid loop is a pair of nested for loops), let's do it in two.

    To do this, we temporarily accumulate by columns (making the space usage O(mn+n) which is still O(mn) effectively)) and each time we write to the hit grid we write the accumulated value at that column along with the one for that row. Then we do the same in reverse. Here's that solution:

        def maxKilledEnemies(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if not grid:
                return 0
            n_x = len(grid)
            n_y = len(grid[0])
            enemies = 0
            hits = [[0 for y in range(n_y)] for x in range(n_x)]
            col_cnt = [0] * n_y
            for x in range(n_x):
                row_cnt = 0
                for y in range(n_y):
                    if grid[x][y] == 'E':
                        row_cnt += 1
                        col_cnt[y] += 1
                    elif grid[x][y] == 'W':
                        row_cnt = 0
                        col_cnt[y] = 0
                    else:
                        hits[x][y] += row_cnt + col_cnt[y]
            col_cnt = [0] * n_y
            for x in range(n_x-1, -1, -1):
                row_cnt = 0
                for y in range(n_y-1, -1, -1):
                    if grid[x][y] == 'E':
                        row_cnt += 1
                        col_cnt[y] += 1
                    elif grid[x][y] == 'W':
                        row_cnt = 0
                        col_cnt[y] = 0
                    else:
                        hits[x][y] += row_cnt + col_cnt[y]
                        enemies = max(enemies, hits[x][y])
            return enemies    
    

    Now you might think, "if we can do this in two grid loops, why not just one?" You can - you'll need a second row counter and column counting array, and in theory for every count you just calculate the second coordinate pairs and effectively repeat the same steps. A bit of duplicated code is still present (could abstract that into functions but there's overhead associated with that), a bit more space is used for the second array, and roughly the same calculations are happening, but it certainly eliminates the extra grid loop so that ought to be good or at least no worse...

    But it turns out it actually is worse.

    This is a case of over-optimizing, where the calculations you make to bury the second grid loop end up costing you just as much as having the second loop in the first place! (It actually costs more here, probably because of internal efficiencies with regard to looping in Python.) The code works, but it ends up being a bit less intuitive, somewhat slower, and that much more difficult to intuit and maintain:

        def maxKilledEnemies_OVEROPTIMIZED_DONTDOTHIS(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if not grid:
                return 0
            n_x = len(grid)
            n_y = len(grid[0])
            enemies = 0
            hits = [[0 for y in range(n_y)] for x in range(n_x)]
            col_cnt_f = [0] * n_y
            col_cnt_r = [0] * n_y
            for x_f in range(n_x):
                row_cnt_f = 0
                row_cnt_r = 0
                for y_f in range(n_y):
                    x = x_f
                    y = y_f
                    if grid[x][y] == 'E':
                        row_cnt_f += 1
                        col_cnt_f[y] += 1
                    elif grid[x][y] == 'W':
                        row_cnt_f = 0
                        col_cnt_f[y] = 0
                    else:
                        hits[x][y] += row_cnt_f + col_cnt_f[y]
                        enemies = max(enemies, hits[x][y])
                    x = n_x - x_f - 1
                    y = n_y - y_f - 1
                    if grid[x][y] == 'E':
                        row_cnt_r += 1
                        col_cnt_r[y] += 1
                    elif grid[x][y] == 'W':
                        row_cnt_r = 0
                        col_cnt_r[y] = 0
                    else:
                        hits[x][y] += row_cnt_r + col_cnt_r[y]
                        enemies = max(enemies, hits[x][y])
            return enemies
    

    Another idea that might occur to you (depending on the data type of the initial grid, and assuming you can modify the initial grid) is to use the initial grid itself for saving count data. There are some tricks for doing this rather than allocating extra space, but they are risky.

    I saw one solution that actually used this technique: it was somewhat cryptic but it probably works fine - until a given count exceeds the size of char, and you waste time trying to figure out why it suddenly failed badly (also, the trick being employed was itself not well-described). Great for code golf, but good luck maintaining that code in production!

    Optimization is valuable but once again, over-optimization can quickly turn ugly and become un-maintainable.


Log in to reply
 

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