Detect anagram in matrix

Question

Given a 2D matrix of characters and a string, write a function to detect all occurrences of the string as an anagram within the matrix. An anagram can be formed by rearranging the characters in the string, and the function should return the starting coordinates of each occurrence in the matrix. The search should consider all possible horizontal and vertical placements of the anagram.

Codemia · Accepted Answer

To detect anagrams in a 2D matrix of characters, we can leverage the concept of frequency counting. An anagram consists of the same characters in different orders, so the frequency of each character in both the anagram string and any substring of the matrix must match. This problem can be approached using a combination of sliding window techniques for horizontal searches and vertical searches using frequency counting. The reason this pattern applies is that we must check contiguous sequences of characters in both dimensions of the matrix.

1. **Frequency Count**: Start by creating a frequency count of the characters in the target string. For example, for the string 'abc', the frequency map would be `{ 'a': 1, 'b': 1, 'c': 1 }`.

2. **Horizontal Search**: Iterate over each row in the matrix. For each starting position in the row, check the next characters (up to the length of the target string) to see if they form an anagram by comparing their frequency count to the target's.

3. **Vertical Search**: Similarly, iterate over each column in the matrix. For each starting position in the column, check the next characters vertically for anagrams.

4. **Store Results**: If a match is found, store the starting coordinates (row, column) in a results list.

5. **Return Results**: At the end of the search, return the list of starting coordinates.

Here is a Python solution for the problem:

```python
from collections import Counter

def find_anagrams_in_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return []

target_count = Counter(target)
    target_length = len(target)
    results = []
    rows, cols = len(matrix), len(matrix[0])

# Horizontal search
    for r in range(rows):
        for c in range(cols - target_length + 1):
            window = matrix[r][c:c + target_length]
            if Counter(window) == target_count:
                results.append((r, c))

# Vertical search
    for c in range(cols):
        for r in range(rows - target_length + 1):
            window = ''.join(matrix[r + i][c] for i in range(target_length))
            if Counter(window) == target_count:
                results.append((r, c))

return results
```

The time complexity of this solution is O(N * M * K), where N is the number of rows, M is the number of columns, and K is the length of the target string. This is because we are checking each possible starting position in the matrix (which is N * M) and creating a frequency count for each substring (which takes O(K)). The space complexity is O(K) for storing the frequency count of the target string.

1. **Empty Matrix**: If the matrix is empty, the function should return an empty list.
2. **Target Longer Than Matrix**: If the target string is longer than either dimension of the matrix, the function should also return an empty list since it can't fit.
3. **Non-Existent Anagrams**: If no anagrams are found, the function should return an empty list.
4. **Multiple Occurrences**: Ensure the function correctly identifies all occurrences, including overlapping anagrams in the rows or columns.

Detect anagram in matrix

Scale AI

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

Scale AI 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