Is Phone Number Prefix easy or hard?

Phone Number Prefix is generally considered an easy problem. The main insight is recognizing that sorting places potential prefix pairs next to each other, allowing a single linear scan instead of comparing every pair.

Phone Number Prefix Python/Java solution

Most implementations sort the list of phone numbers and compare each number with the next one using a prefix check such as startswith in Python or startsWith in Java. This keeps the logic simple and runs in O(n log n * m) time.

How to solve Phone Number Prefix in O(n)?

A trie (prefix tree) can detect prefix conflicts in O(n * m) time, where n is the number of phone numbers and m is the maximum length. Insert each digit into the trie while checking if a node already marks the end of another number or has existing children. Either condition indicates a prefix relationship.

What is the best approach for Phone Number Prefix?

Sorting the phone numbers and checking adjacent pairs is the most practical solution. After lexicographic sorting, numbers with shared prefixes appear next to each other, so a single linear scan detects conflicts. The approach runs in O(n log n * m) time with O(1) extra space and is easy to implement in interviews.

Is Phone Number Prefix asked at Google/Amazon/Meta?

Prefix-based string problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often involve prefix validation, dictionary lookups, or trie-based searching. The problem tests understanding of sorting strategies and prefix data structures.

What data structure is used in Phone Number Prefix?

The problem can be solved using arrays and string comparisons with sorting, which is the simplest approach. A trie (prefix tree) is another common data structure for detecting prefix relationships efficiently when processing many strings.

What is the time complexity of Phone Number Prefix?

The common optimized solution uses sorting followed by a linear scan. Sorting n phone numbers costs O(n log n), and each prefix comparison takes O(m) for numbers of length m, giving O(n log n * m) total time. Space complexity is typically O(1) beyond the input array.

Description Hints 2 Solution Video 10:57

3491. Phone Number Prefix

Easy69.9% acceptancePremium elsewhere, free here

You are given a string array numbers that represents phone numbers. Return true if no phone number is a prefix of any other phone number; otherwise, return false.

Example 1:

Input: numbers = ["1","2","4","3"]

Output: true

Explanation:

No number is a prefix of another number, so the output is true.

Example 2:

Input: numbers = ["001","007","15","00153"]

Output: false

Explanation:

The string "001" is a prefix of the string "00153". Thus, the output is false.

Constraints:

2 <= numbers.length <= 50
1 <= numbers[i].length <= 50
All numbers contain only digits '0' to '9'.

Topics

Hints open one at a time

Hint 1

Sort the array.

Hint 2

For every adjacent pair, check if the left number is a prefix of the right number.

10:57

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

["1","2","4","3"]

Input

["001","007","15","00153"]

Your code is saved on this device.Solution