Detect permutation in array

Question

Given an array of integers, determine if any two elements in the array are permutations of each other. Your solution should return a boolean value indicating whether such a pair exists. The input will be an array of integers, and the output should be true if a permutation pair is found, otherwise false.

Codemia · Accepted Answer

To determine if any two elements in the array are permutations of each other, we need to recognize that two integers are permutations if they contain the same digits in different orders. This problem can be approached using a frequency counting method or by sorting the digits of the numbers. The most suitable pattern here is utilizing a hash map (or dictionary) to count the frequency of each digit in a number. This allows us to check for permutations efficiently. For example, the numbers 123 and 321 both have the same digit frequencies, thus they are permutations of each other.

1. Initialize an empty hash map to store the frequency of digit counts as keys.  
2. For each number in the array, convert it into a string and sort the digits.  
3. Use the sorted string representation of the number as a key in the hash map.  
4. If the key already exists in the map, it means we have found a permutation pair, and we return true.  
5. If not, add the key to the map and continue.  
6. If no pairs are found by the end of the loop, return false.

**Example:**  
Input: [123, 321, 456, 654]  
- For 123: sorted string is '123'. Add to map.  
- For 321: sorted string is '123'. Already in map, return true.

Here is a Python implementation of the above approach:

```python
def detect_permutation(arr):
    digit_map = {}
    for num in arr:
        sorted_digits = ''.join(sorted(str(num)))
        if sorted_digits in digit_map:
            return True
        digit_map[sorted_digits] = 1
    return False
```

This code iterates through each number, sorts its digits, and checks for duplicates in the hash map.

The time complexity of this solution is O(n * k log k), where n is the number of integers in the array and k is the average number of digits in the integers. This is due to sorting the digits of each number. The space complexity is O(n) for the hash map that stores the frequency of digit counts. Given the constraints of the input size, this approach is efficient.

1. **Single Element Array:** An array with only one element, e.g., [1], should return false since no pairs exist.  
2. **Negative Numbers:** If the array contains negative numbers, e.g., [-123, -321], they should be treated correctly; the sorted representation should consider the negative sign.  
3. **Zeros:** Numbers with zeros, e.g., [100, 010], should be correctly identified as permutations.  
4. **Large Numbers:** Ensure the algorithm handles large integers efficiently without overflow.  
5. **Duplicates:** An array like [112, 121] should return true, as the duplicates signify permutations.

Detect permutation in array

Doordash

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

Doordash Machine Learning 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