LeetCode 1268 Search Suggestions System - Example and Complexity Analysis

Sorted: ["mobile","moneypot","monitor","mouse","mousepad"].

Prefix "m": binary search finds "mobile" at index 0. Check indices 0, 1, 2: all start with "m". Return ["mobile","moneypot","monitor"].

Prefix "mo": binary search finds "mobile". Check 0, 1, 2: all start with "mo". Return ["mobile","moneypot","monitor"].

Prefix "mou": binary search finds "mouse" at index 3. Check 3, 4: both start with "mou". Return ["mouse","mousepad"].

Sort: $O(n \log n)$. For each of $m$ prefixes, binary search $O(\log n)$ plus checking 3 products. Total: $O(n \log n + m \log n)$.