Detect permutation in array

Question

Given array, detect all occurrences of the anagram pattern.

Codemia · Accepted Answer

To detect all occurrences of an anagram pattern in an array, we can utilize the **sliding window** technique combined with **frequency counting**. The reason this approach is optimal here is that anagrams, by definition, have the same characters with the same frequency, but potentially in different orders. Using a sliding window allows us to efficiently check subsets of the array of the same length as the anagram pattern. We'll maintain a frequency count of both the pattern and the current window in the array, allowing us to compare them directly.

1. **Frequency Count Initialization**: Create a frequency count (dictionary) for the characters in the anagram pattern. For example, if the pattern is 'abc', the frequency count would be {'a': 1, 'b': 1, 'c': 1}.
2. **Sliding Window Setup**: Initialize a sliding window of the same length as the pattern. Start with the first window of characters in the array and create a frequency count for this window.
3. **Window Comparison**: Compare the frequency count of the current window to that of the pattern. If they match, record the starting index of this window.
4. **Slide the Window**: Move the window one character to the right: remove the character that's sliding out of the window and add the character that's entering the window. Update the frequency count accordingly.
5. **Repeat**: Continue sliding the window until the end of the array is reached.

For example, with the array ['a', 'b', 'c', 'a', 'c', 'b', 'a'] and pattern 'abc', the windows will be:
- Window 1: ['a', 'b', 'c'] -> match
- Window 2: ['b', 'c', 'a'] -> match
- Window 3: ['c', 'a', 'c'] -> no match
- Window 4: ['a', 'c', 'b'] -> match
- Resulting indices: [0, 2, 4]

```python
from collections import Counter

def find_anagrams(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    current_count = Counter(arr[:pattern_length])
    result_indices = []

if current_count == pattern_count:
        result_indices.append(0)

for i in range(pattern_length, len(arr)):
        current_count[arr[i]] += 1  # Add new character to the window
        current_count[arr[i - pattern_length]] -= 1  # Remove the old character from the window

# Clean up the counter to avoid unnecessary keys
        if current_count[arr[i - pattern_length]] == 0:
            del current_count[arr[i - pattern_length]]

if current_count == pattern_count:
            result_indices.append(i - pattern_length + 1)

return result_indices
```
This code utilizes a sliding window and frequency counting to detect all starting indices of anagrams in the array.

The time complexity of this algorithm is **O(n)**, where n is the length of the input array. This is because we traverse the array once, and each lookup or update in the dictionary (for frequency counts) is O(1) on average. The space complexity is **O(k)**, where k is the size of the character set in the pattern. This space is used for storing the frequency counts. Given that k is generally much smaller than n, our approach is efficient in terms of both time and space.

1. **Empty Array**: If the input array is empty, the function should return an empty list as there are no anagrams to find.
2. **Pattern Longer than Array**: If the pattern is longer than the array, the function should also return an empty list since it's impossible to find an anagram.
3. **No Anagrams Present**: If the array contains distinct characters that do not form any anagrams of the pattern, the output should be an empty list.
4. **All Characters Same**: For a pattern like 'aaa' and array like ['a', 'a', 'a', 'a'], the function should return starting indices for every possible window since they are all anagrams.

Detect permutation in array

Apple

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

Apple 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