algoadvance

Given an n x n matrix matrix, which contains a single snake marked with ‘S’ cells, surrounded by ‘.’ cells, determine if the snake touches itself. The snake touches itself if there are at least two adjacent cells marked ‘S’ (horizontally or vertically) or any part of the snake forms a loop.

Clarifying Questions

1. Input Constraints:
   • What are the possible values of n (size of the matrix)?
     • n is guaranteed to be between 1 and 50 inclusive.
   • Are cells with ‘S’ guaranteed to form a single continuous snake?
     • Yes, the snake cells are contiguous.
2. Output:
   • Return True if the snake touches itself, otherwise False.

Strategy

1. Identify all ‘S’ cells:
   • Iterate through the matrix and collect the coordinates of all ‘S’ cells.
2. Check for touching adjacency:
   • For each ‘S’ cell, check its four possible neighboring positions: left, right, up, and down.
   • If any neighboring cell contains ‘S’, it indicates the snake is touching itself.
3. Check for loops using BFS or DFS:
   • Use Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse from any ‘S’ cell.
   • While traversing, if we encounter a previously visited cell that is not the immediately preceding cell in the path, it indicates a loop.

Code

def touches_itself(matrix):
    n = len(matrix)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # Find all 'S' cells
    s_cells = [(i, j) for i in range(n) for j in range(n) if matrix[i][j] == 'S']
    if not s_cells:
        return False
    
    # Check for adjacent 'S' cells
    visited = set()
    
    def dfs(x, y, parent):
        # Mark the cell as visited
        visited.add((x, y))
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and matrix[nx][ny] == 'S':
                if (nx, ny) not in visited:
                    if dfs(nx, ny, (x, y)):
                        return True
                elif (nx, ny) != parent:
                    # Found a loop
                    return True
        return False
    
    # Start DFS from the first 'S' cell
    start_x, start_y = s_cells[0]
    if dfs(start_x, start_y, None):
        return True
    
    return False

# Example test cases
matrix = [
    ['.', '.', '.', 'S', '.'],
    ['.', '.', 'S', 'S', '.'],
    ['.', '.', '.', 'S', '.'],
    ['.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.']
]
print(touches_itself(matrix))  # Output: True

matrix = [
    ['.', '.', '.', '.', '.'],
    ['.', '.', 'S', 'S', '.'],
    ['.', '.', '.', 'S', '.'],
    ['.', '.', '.', '.', '.'],
    ['.', '.', '.', '.', '.']
]
print(touches_itself(matrix))  # Output: False

Time Complexity

• Initialization: Finding all ‘S’ cells and setting up the matrix takes (O(n^2)) time.
• DFS Traversal: The DFS will potentially visit each ‘S’ cell once, resulting in a time complexity of (O(n^2)) in the worst case since there are at most (n^2) cells.
• Overall Time Complexity: (O(n^2)).

The space complexity is also (O(n^2)) due to the visited set for tracking the visited ‘S’ cells.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?