Phone Number Prefix - Solution & Explanation

Problem Overview: You receive a list of phone numbers. The task is to determine whether any number is a prefix of another number in the list. For example, if 911 and 9112345 both appear, the list is invalid because one number starts with another.

Approach 1: Brute Force Pair Comparison (O(n² * m) time, O(1) space)

Compare every phone number with every other phone number. For each pair, check whether one string starts with the other using a prefix comparison such as startsWith. If any match appears, return false immediately. This approach is easy to reason about but scales poorly because it checks n² pairs. With long phone numbers of length m, each comparison adds additional cost. This works only when the list size is very small.

Approach 2: Sorting + Prefix Checking (O(n log n * m) time, O(1) extra space)

Sort the phone numbers lexicographically using standard sorting. After sorting, any numbers that share a prefix will appear next to each other. Iterate through the sorted list once and compare each element with the next element. If numbers[i+1] starts with numbers[i], you found a prefix conflict. The key insight is that sorting groups similar prefixes together, eliminating the need for comparing every pair. This approach is simple, efficient, and widely used in interviews. The main operations are sorting the array and performing linear prefix checks using string operations.

Approach 3: Trie (Prefix Tree) (O(n * m) time, O(n * m) space)

Insert each phone number digit by digit into a trie. While inserting, check two conditions: if you reach a node already marked as the end of another number, or if the current number finishes but the node already has children. Either condition means one number is a prefix of another. Tries provide optimal lookup for prefix relationships and guarantee linear processing relative to total digits. The tradeoff is higher memory usage and more implementation overhead compared to sorting.

Recommended for interviews: Sorting + prefix checking is usually the expected answer. It shows you recognize that prefix conflicts must appear among neighboring elements after sorting. Mentioning the brute force approach demonstrates baseline reasoning, while presenting the sorted optimization shows algorithmic thinking. A trie solution is also strong when the interviewer specifically wants a prefix data structure or asks how to scale the solution for extremely large datasets.