Detect palindrome in matrix

Question

Given a 2D matrix of characters, write a function to detect all occurrences of palindromic sequences in the matrix. A palindrome is defined as a sequence that reads the same forwards and backwards, and your function should return a list of all such sequences found in horizontal, vertical, and diagonal directions. The output should include the starting coordinates of each palindrome along with the palindrome itself.

Codemia · Accepted Answer

To detect palindromic sequences in a 2D matrix, we can utilize the concept of searching in multiple directions (horizontal, vertical, and diagonal). The problem can be approached using a depth-first search (DFS) pattern, as we can explore potential palindromes by checking character sequences in all these directions from each starting point in the matrix. This is effective because we need to evaluate the characters sequentially to determine if they form a palindrome. 1. **Iterate through each cell** in the matrix. For each cell, we will treat it as a potential starting point for a palindrome. 2. **Check all directions**: For each starting point, we will check in four possible directions: horizontal (right), vertical (down), diagonal (down-right), and anti-diagonal (down-left). 3. **Expand outwards**: For each direction, we will expand outwards by appending characters and checking for palindrome properties (i.e., the sequence should read the same forwards and backwards). 4. **Store results**: Whenever we find a palindrome of length >= 2, we will store the starting coordinates and the palindrome itself. 5. **Return results**: After exploring the entire matrix, we will return all detected palindromes with their coordinates. Here is a Python implementation of the described approach: ```python def is_palindrome(sequence): return sequence == sequence[::-1] def find_palindromes(matrix): if not matrix or not matrix[0]: return [] rows, cols = len(matrix), len(matrix[0]) palindromes = [] directions = [(0, 1), (1, 0), (1, 1), (1, -1)] # right, down, down-right, down-left for r in range(rows): for c in range(cols): for dr, dc in directions: # Check for palindromes starting at (r, c) in (dr, dc) direction length = 1 # Starting length chars = matrix[r][c] while True: nr, nc = r + dr * length, c + dc * length if 0 <= nr < rows and 0 <= nc < cols: chars += matrix[nr][nc] if len(chars) > 1 and is_palindrome(chars): palindromes.append(((r, c), chars)) length += 1 else: break return palindromes ``` This code defines a helper function to check for palindromes and iterates through each cell in the matrix to find palindromic sequences. The time complexity of this approach is O(N * M * K), where N is the number of rows, M is the number of columns, and K is the maximum length of palindrome we check. In the worst-case scenario, we may explore the entire matrix for every character, which leads to this complexity. The space complexity is O(P), where P is the number of palindromes found since we are storing them in a list. 1. **Empty Matrix**: If the input matrix is empty (i.e., `[]`), the function should return an empty list. 2. **Single Character**: If the matrix contains only one character (e.g., `[['a']]`), it should also return an empty list since a palindrome requires at least two characters. 3. **All Identical Characters**: If the matrix consists entirely of the same character (e.g., `[['a', 'a'], ['a', 'a']]`), the function should detect palindromes of various lengths starting from different coordinates.

Detect palindrome in matrix

Databricks

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Databricks Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string