FastPrepCount Prefix Matches in a Sorted Array
Problems/Count Prefix Matches in a Sorted Array

Count Prefix Matches in a Sorted Array

Google logoGoogle● MediumFULLTIMENEW GRADONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report links a sorted-string binary-search question to the prefix-count task but omits its exact predicate and boundary rules. The judged core task matches the visible source at about 90%.

Given a lexicographically sorted array of lowercase strings words and a lowercase string prefix, return the number of array entries that begin with prefix.

Duplicate words count separately. For this exercise, assume all words and the prefix are non-empty and use ordinary lowercase lexicographic order.

Use the sorted order to locate the contiguous matching range with binary search.

Function

countPrefixMatches(words: String[], prefix: String) → int

Examples

Example 1

words = ["apple","apply","apt","banana"]prefix = "app"return = 2

Only apple and apply begin with app.

Example 2

words = ["a","a","ab","b"]prefix = "a"return = 3

Both copies of a and the word ab match, so duplicates contribute separately.

Constraints

  • 0 <= words.length <= 2 * 10^5
  • Every word and prefix is a non-empty lowercase English string.
  • words is sorted in nondecreasing lexicographic order.
  • The total number of characters in words and prefix is at most 2 * 10^5.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int countPrefixMatches(String[] words, String prefix) {
        // Write your code here.
    }
}
Checking account…