Autocomplete Top K by Frequency
01 · Problem
You are building the suggestion box of a search bar. You are given an array sentences of distinct historical searches and a parallel array counts, where counts[i] is how many times sentences[i] was searched. You are also given an array of prefix queries and an integer k.
For each query, find all sentences that start with that query and return up to k of them, ordered by count descending; sentences with equal counts are ordered lexicographically ascending (by character codes, so a space sorts before any letter). If no sentence matches, the answer for that query is an empty list.
Return a list containing one answer list per query, in query order.
02 · Examples
sentences = ["go home","golang","google maps","go fast"], counts = [4,6,1,4], queries = ["go ","gol","x"], k = 3
[["go fast","go home"],["golang"],[]]
"go " matches "go home" and "go fast" (both 4), and the tie puts "go fast" first. "gol" matches only "golang". Nothing starts with "x".
sentences = ["apple","app","apply","ape"], counts = [2,2,1,3], queries = ["ap","app"], k = 2
[["ape","app"],["app","apple"]]
For "ap" all four match: "ape" (3) first, then "app" and "apple" tie at 2 and "app" is lexicographically smaller. For "app", "app" and "apple" (2 each) beat "apply" (1).
03 · Constraints
- 011 <= sentences.length == counts.length <= 1000, 1 <= sentences[i].length <= 100
- 021 <= counts[i] <= 105
- 031 <= queries.length <= 1000, 1 <= queries[j].length <= 100
- 041 <= k <= 10
- 05sentences[i] and queries[j] consist of lowercase English letters and spaces; all sentences are distinct
04 · Optimal complexity
- Time
- O(n * L * k log k + q * (P + k))
- Space
- O(n * L * k)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.