Short and Concise Python Solution


  • 2
    D

    Basically start with the edges and add all the coordinates that can reach edges into two sets (pacific and atlantic). The answer is just the intersection of the two sets. There's no data about the run times for this problem yet, but this code completes in about 225 ms. Is that any good?

    class Solution(object):
    	def pacificAtlantic(self, matrix):
    		def fill(ocean, stack):
    			while stack:
    				r,c = stack.pop()
    				if (r,c) in ocean: continue
    				ocean.add((r,c))
    				stack.extend([
    					[nr, nc] for nr, nc in [[r-1,c], [r+1,c], [r,c-1], [r,c+1]]
    					if 0 <= nr < m and 0 <= nc < n and matrix[r][c] <= matrix[nr][nc]])
    					
    		if not matrix or not matrix[0]:	return []
    		m, n = len(matrix), len(matrix[0])
    		pacific, atlantic = set(), set()
    		pstack = [[r,0] for r in xrange(m)] + [[0,c] for c in xrange(1,n)]
    		astack = [[r,n-1] for r in xrange(m)] + [[m-1,c] for c in xrange(n-1)]
    
    		fill(pacific, pstack)
    		fill(atlantic, astack)
    		
    		return [list(x) for x in pacific&atlantic]
    

Log in to reply
 

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