How Do You Construct a Suffix Array?
Learn how prefix doubling builds a suffix array in O(n log n) and how it pairs with LCP arrays for this interview question.
Expected Interview Answer
A suffix array is built by generating every suffix of a string, sorting those suffixes lexicographically, and storing only their starting indices, which naive comparison-sort does in O(nĀ² log n) but the prefix-doubling algorithm reduces to O(n log n) by ranking suffixes on doubling prefix lengths each round.
Prefix doubling starts by ranking every suffix by its first character, then repeatedly doubles the comparison window ā ranking by the first 2 characters using the previous round's ranks, then 4, then 8, and so on ā because a pair of already-ranked half-length ranks can stand in for a full comparison in O(1). Each round is an O(n log n) sort, and O(log n) rounds are needed to cover a string of length n, giving O(n log n) total. Suffix arrays support O(m log n) substring search via binary search over the sorted suffixes, and pairing the array with an LCP (longest common prefix) array, built in O(n) with Kasai's algorithm, unlocks pattern matching, longest repeated substring, and other string-processing tasks in far less space than a suffix tree. The suffix array is the compact, cache-friendly cousin of the suffix tree, trading a bit of query speed for a fraction of the memory.
- O(n log n) construction via prefix doubling
- O(m log n) substring search using binary search
- Far more memory-efficient than a suffix tree
- Pairs with an LCP array for repeated-substring problems
AI Mentor Explanation
Building a suffix array is like taking every possible remaining partnership length in an innings scorecard ā starting from every ball onward ā and sorting those tail-partnerships alphabetically by the sequence of shots played. Instead of comparing entire tails ball by ball, the scorer first ranks each tail by its first shot, then doubles the comparison window to the first two shots using the prior round's ranks, then four, and so on, halving the work needed each round. After log n rounds the full sorted order of every tail-partnership is known without ever comparing full-length sequences directly. This doubling trick is exactly why suffix arrays sort in O(n log n) instead of comparing every suffix pair from scratch.
Step-by-Step Explanation
Step 1
Rank by first character
Initialize each suffix's rank based on its first character alone.
Step 2
Double the comparison window
Rank suffixes by pairs of (rank at offset 0, rank at offset k), doubling k each round: 1, 2, 4, 8...
Step 3
Sort each round in O(n log n)
Repeat for O(log n) rounds until every suffix has a unique rank, giving O(n log n) total.
Step 4
Optionally build the LCP array
Use Kasai's algorithm in O(n) to compute longest common prefixes between adjacent suffixes for pattern-matching tasks.
What Interviewer Expects
- Explain the prefix-doubling mechanism, not just "sort the suffixes"
- State the O(n log n) construction complexity and why naive sorting is worse
- Mention substring search via binary search: O(m log n)
- Know the LCP array pairing and Kasai's algorithm as the standard companion structure
Common Mistakes
- Describing only naive O(nĀ² log n) sorting without mentioning prefix doubling
- Confusing a suffix array with a suffix tree (different space/time tradeoffs)
- Forgetting the LCP array is needed for many pattern-matching applications
- Miscounting doubling rounds as O(n) instead of O(log n)
Best Answer (HR Friendly)
āA suffix array lists every "starting point onward" of a string, sorted alphabetically, so you can find substrings extremely fast using binary search. Building it efficiently means comparing longer and longer chunks each round, doubling the chunk size instead of comparing whole strings from scratch every time, which is what makes it fast even for very long text.ā
Code Example
def build_suffix_array(s):
n = len(s)
rank = [ord(c) for c in s]
sa = list(range(n))
k = 1
while True:
def key(i):
second = rank[i + k] if i + k < n else -1
return (rank[i], second)
sa.sort(key=key)
new_rank = [0] * n
new_rank[sa[0]] = 0
for i in range(1, n):
new_rank[sa[i]] = new_rank[sa[i - 1]]
if key(sa[i]) != key(sa[i - 1]):
new_rank[sa[i]] += 1
rank = new_rank
if rank[sa[-1]] == n - 1:
break
k *= 2
return sa # sorted list of suffix starting indicesFollow-up Questions
- How would you use the suffix array to find the longest repeated substring?
- What does Kasai's algorithm compute and why is it useful alongside a suffix array?
- How does a suffix array compare to a suffix tree in space and query time?
- How would you search for a pattern of length m using a built suffix array?
MCQ Practice
1. What is the time complexity of building a suffix array using prefix doubling?
Prefix doubling runs O(log n) rounds, each an O(n log n) sort, giving O(n log n) total.
2. What does the LCP array store alongside a suffix array?
The LCP array records the longest common prefix length between consecutive suffixes in the sorted suffix array, enabling many string algorithms.
3. What is the time complexity of substring search using a built suffix array?
Binary search over the sorted suffixes, comparing up to m characters per step, gives O(m log n) search time.
Flash Cards
What technique builds a suffix array in O(n log n)? ā Prefix doubling ā ranking suffixes by doubling comparison windows each round.
What does a suffix array store? ā The starting indices of every suffix of a string, sorted lexicographically.
What algorithm builds the LCP array in O(n)? ā Kasai's algorithm, using the suffix array and its inverse rank.
Why prefer a suffix array over a suffix tree? ā Far lower memory usage, at the cost of slightly more query overhead for some operations.