Detect anagram in matrix

Question

Given a 2D matrix of characters and a target string, write a function to detect all occurrences of the anagram of the target string within the matrix. The function should return the starting coordinates (row, column) of each occurrence found, considering all possible horizontal and vertical directions. The output should be a list of tuples representing the positions of the anagrams in the matrix.

Codemia · Accepted Answer

To solve the problem of detecting anagrams in a 2D matrix, we can leverage the concept of frequency counting. An anagram consists of the same characters with the same frequency but possibly in a different order. Given the target string, we will create a frequency dictionary (or hash map) that counts the occurrences of each character in the target string. We will then compare this frequency count with the character counts in the horizontal and vertical substrings of the matrix. The main pattern we will utilize here is the sliding window technique for extracting substrings and comparing character frequencies.

1. **Create Frequency Map**: Start by creating a frequency map for the target string. For example, for the target 'abc', the frequency map will be: {'a': 1, 'b': 1, 'c': 1}.
2. **Iterate through Matrix**: For each row and each column in the matrix, extract all possible substrings of the same length as the target string. 
3. **Sliding Window Technique**: Use a sliding window of size equal to the target string's length to extract substrings from the rows and columns. For each substring, create a frequency map and compare it to the target frequency map. 
4. **Store Results**: If the frequency maps match, store the starting coordinates of the substring.
5. **Return Results**: Finally, return all the starting coordinates found.

For example, in a matrix:
```
['abca',
 'cadb',
 'dcba']
```
If the target is 'abc', the substrings 'abc' in the first row and 'cba' in the second row (starting from (1, 0)) are valid anagrams.

Here is the Python solution implementing the discussed approach:
```python
def detect_anagrams(matrix, target):
    from collections import Counter
    target_count = Counter(target)
    target_length = len(target)
    results = []

# Check rows
    for r in range(len(matrix)):
        for c in range(len(matrix[0]) - target_length + 1):
            substring = matrix[r][c:c + target_length]
            if Counter(substring) == target_count:
                results.append((r, c))

# Check columns
    for c in range(len(matrix[0])):
        for r in range(len(matrix) - target_length + 1):
            substring = ''.join(matrix[r + i][c] for i in range(target_length))
            if Counter(substring) == target_count:
                results.append((r, c))

return results
```
This code iterates through all possible starting positions in the matrix, extracts substrings, and compares their frequency counts.

The time complexity of this solution is O(n * m * k), where:
- n is the number of rows in the matrix,
- m is the number of columns,
- k is the length of the target string. 
This is because for each row (n) and each possible starting column (m - k + 1), we generate substrings of length k and compare their frequencies. The space complexity is O(k) due to the storage of the frequency map for the target string and the substrings.

1. **Empty Matrix**: If the matrix is empty, the function should return an empty list. 
2. **Target Longer than Matrix Dimensions**: If the target string is longer than any dimension of the matrix, no anagrams can be found, and the function should return an empty list. 
3. **Character Variations**: If the target string contains characters not present in the matrix, it should also return an empty list. 
4. **Multiple Occurrences**: The algorithm should correctly identify multiple occurrences of anagrams in the same row or column.

Detect anagram in matrix

NVIDIA

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

NVIDIA 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