Search Suggestions System - Practice Coding Problems

Search Suggestions System - Problem

Array String Binary Search Trie Sorting Heap (Priority Queue) Medium

You are given an array of strings products and a string searchWord. Design a system that suggests at most three product names from products after each character of searchWord is typed.

Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix, return the three lexicographically minimum products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Input & Output

Example 1 — Basic Case

$ Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

› Output: [["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

💡 Note: Typing 'm': products with 'm' are ["mobile","moneypot","monitor"]. Typing 'mo': products with 'mo' are ["mouse","mousepad"]. For 'mou', 'mous', 'mouse': all return ["mouse","mousepad"].

Example 2 — No Matches

$ Input: products = ["havana"], searchWord = "havana"

› Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

💡 Note: Each character of 'havana' matches the product 'havana', so we return ['havana'] for each prefix.

Example 3 — Empty Results

$ Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"

› Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

💡 Note: Typing 'b': ['baggage','bags','banner']. 'ba': ['baggage','bags','banner']. 'bag': ['baggage','bags']. 'bags': ['bags'].

Constraints

1 ≤ products.length ≤ 1000
1 ≤ products[i].length ≤ 3000
1 ≤ searchWord.length ≤ 1000
products[i] and searchWord consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Data

Products array and search word to type

Progressive Filtering

Each typed character narrows down suggestions

Output

List of suggestions for each prefix

Key Takeaway

🎯 Key Insight: Sorting products first enables efficient prefix matching and guarantees lexicographical order

Asked in

a Amazon 85 M Microsoft 45 G Google 30 🍎 Apple 25

The key insight is to sort products first to enable efficient prefix matching. The optimal approach uses two pointers to maintain a sliding window of matching products as we extend the search prefix character by character. Time: O(n log n + m × 3), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sort First - Optimized Filtering	O(n log n + m × n)	O(1)	Sort products once, then use binary search to find prefix matches efficiently
Brute Force - Filter and Sort for Each Prefix	O(n × m × k × log k)	O(k)	For each character typed, scan all products to find matches, sort them, and take top 3
Two Pointers - Optimized Range Tracking	O(n log n + m × 3)	O(1)	Sort products once, then maintain a sliding window of valid matches as we extend the prefix

Sort First - Optimized Filtering — Algorithm Steps

Step 1: Sort all products lexicographically once at the beginning
Step 2: For each prefix, use binary search to find first matching product
Step 3: From that position, collect up to 3 products with the same prefix
Step 4: Add these suggestions to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Products

Sort all products lexicographically once

Binary Search

For each prefix, find first match using binary search

Collect Matches

Take next 3 products that match the prefix

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return strcmp(*(char**)a, *(char**)b);
}

int binarySearchFirst(char** products, int size, char* prefix) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (strcmp(products[mid], prefix) < 0) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

char*** solution(char** products, int productsSize, char* searchWord, int* returnSize, int** returnColumnSizes) {
    qsort(products, productsSize, sizeof(char*), compare);
    
    int wordLen = strlen(searchWord);
    *returnSize = wordLen;
    *returnColumnSizes = (int*)malloc(wordLen * sizeof(int));
    char*** result = (char***)malloc(wordLen * sizeof(char**));
    
    for (int i = 0; i < wordLen; i++) {
        char prefix[101];
        strncpy(prefix, searchWord, i + 1);
        prefix[i + 1] = '\0';
        
        int left = binarySearchFirst(products, productsSize, prefix);
        
        char** suggestions = (char**)malloc(3 * sizeof(char*));
        int count = 0;
        
        for (int j = left; j < productsSize && count < 3; j++) {
            if (strncmp(products[j], prefix, strlen(prefix)) == 0) {
                suggestions[count] = products[j];
                count++;
            } else {
                break;
            }
        }
        
        (*returnColumnSizes)[i] = count;
        result[i] = suggestions;
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char** products = (char**)malloc(1000 * sizeof(char*));
    int productsSize = 0;
    
    char* token = strtok(line, "[],\"\n");
    while (token != NULL) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            products[productsSize] = (char*)malloc(strlen(token) + 1);
            strcpy(products[productsSize], token);
            productsSize++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    char searchWord[100];
    fgets(searchWord, sizeof(searchWord), stdin);
    searchWord[strcspn(searchWord, "\n")] = 0;
    
    int returnSize;
    int* returnColumnSizes;
    char*** result = solution(products, productsSize, searchWord, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("\"%s\"", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m × n)

O(n log n) to sort products, then O(m × n) to check prefixes for m characters

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra space besides input and output

✓ Linear Space

127.0K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort First - Optimized Filtering — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler