LC-2596 Medium LeetCode

2596. Check Knight Tour Configuration

Array Depth-First Search Breadth-First Search Matrix Simulation

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 57% Topics: Array, Depth-First Search, Breadth-First Search, Matrix, Simulation

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min Math & Geometry 12 min

Reference solution (spoiler · python)

# Time:  O(m * n)
# Space: O(m * n)

# hash table, simulation
class Solution(object):
    def checkValidGrid(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: bool
        """
        if grid[0][0]:
            return False
        lookup = [None]*(len(grid)*len(grid[0]))
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                lookup[grid[i][j]] = (i, j)
        return all(sorted([abs(lookup[i+1][0]-lookup[i][0]), abs(lookup[i+1][1]-lookup[i][1])]) == [1, 2] for i in xrange(len(lookup)-1))

    
# Time:  O(m * n)
# Space: O(m * n)
# hash table, simulation
class Solution2(object):
    def checkValidGrid(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: bool
        """
        lookup = {grid[i][j]:(i, j) for i in xrange(len(grid)) for j in xrange(len(grid[0]))}
        return grid[0][0] == 0 and all(sorted([abs(lookup[i+1][0]-lookup[i][0]), abs(lookup[i+1][1]-lookup[i][1])]) == [1, 2] for i in xrange(len(lookup)-1))

Solution from kamyu104/LeetCode-Solutions · MIT