What does a suffix array actually store, and why is its space O(n) rather than O(n^2)?
answer
- What exactly is being sorted here?
- Suffix lengths add up to about n^2/2
- Store a position, not a copy
- n integers, one per starting offset
- Each comparison reads the original text
basics
~20 sA suffix array holds n integers: the starting positions of a text's n suffixes, sorted in lexicographic order. The suffixes themselves are never copied — each is read from the original text — so the space stays O(n).
solid answer
~50 sA suffix array is an array of `n` integers, one per suffix of a length-`n` text, ordered so the suffixes those offsets point at are in lexicographic order. Writing the suffixes out really would cost O(n^2) characters, because suffix lengths sum to n(n+1)/2; the array dodges that by storing only offsets and comparing against the original text on demand. Construction that naively sorts suffixes with full character comparisons is O(n^2 log n); prefix-doubling gives O(n log n), and linear-time constructions such as SA-IS and DC3 exist. Once built, a substring query binary-searches the array: O(m log n) character comparisons for a pattern of length `m`, or O(m + log n) if an LCP array is carried alongside. The structure is static — inserting characters shifts offsets and changes ranks, so a changed text means a rebuild.
code
pseudocode · 14 lines// sa[0..n-1] = start offsets of the text's suffixes, lexicographically sorted
// compare_prefix(text, start, p) compares text[start..] against p,
// reading at most length(p) characters; returns <0, 0 (p is a prefix), or >0
lo = 0
hi = n
while lo < hi:
mid = (lo + hi) / 2 // integer division
if compare_prefix(text, sa[mid], p) < 0:
lo = mid + 1
else:
hi = mid
// lo is the first rank whose suffix is >= p
// p occurs iff lo < n and compare_prefix(text, sa[lo], p) == 0
// ... a second, symmetric search finds the end of the occurrence blockgo deeper
Recall the one-sentence definition: a sorted list of every suffix's starting position, stored as integers. Being able to say that the suffixes are pointed at rather than copied already answers most of what is asked here.
Explain the mechanics: why the sum of suffix lengths is quadratic but the array is linear, why sorted order makes the occurrences of a pattern contiguous, and why the query bound carries an m as well as a log n.
Show judgment about cost: know the construction tiers by name, estimate the resident memory for a real text size, and flag that the structure is static so any changing text forces a rebuild strategy.
Own the tradeoff of holding an offset index at all — memory per character against query volume, build time against freshness, and whether a simpler search over the raw text is the honest answer for the workload in front of you.
## The object itself Take a text of length `n`. It has exactly `n` suffixes: the whole text, the text minus its first character, and so on down to the last single character. A **suffix array** is a permutation of the numbers `0..n-1` such that reading the suffixes in that order gives them in lexicographic (dictionary) order. Nothing else is stored. Entry `sa[i]` is the starting offset in the text of the suffix that ranks `i`-th. That single design decision — store an offset, not a copy — is what the question is really testing. The suffixes collectively contain n + (n-1) + ... + 1 = n(n+1)/2 characters, which is Theta(n^2). Materialising them is impossible for any interesting `n`: a 100-million-character text would need on the order of 5·10^15 characters of storage. Storing `n` machine integers instead needs one word per position — a few hundred megabytes at that size, large but ordinary. Every comparison during construction or query dereferences back into the one copy of the text that already exists. ## What sorting buys Sorted order is not decoration; it is the whole query mechanism. A pattern `P` occurs in the text at position `j` exactly when `P` is a **prefix** of the suffix starting at `j`. All suffixes sharing the prefix `P` are lexicographically adjacent, so they occupy one contiguous block of the suffix array. Finding an occurrence therefore reduces to binary search: bisect on "is this suffix lexicographically below `P`?", a monotone predicate over the sorted order. The cost has two factors and both matter. There are O(log n) bisection steps, and each step's comparison may read up to `|P| = m` characters before it can decide. So a plain implementation is **O(m log n)**, not O(log n) — a very common misstatement. Carrying an LCP array (which records the shared prefix length of adjacent sorted suffixes) lets the search skip characters already known to match on both sides of the current bracket, giving **O(m + log n)**. To report *every* occurrence rather than one, run the search twice: once for the first rank at or after `P`, once for the first rank strictly past every string with prefix `P`. The offsets between those bounds are the occurrence positions, delivered in time proportional to their count. ## Construction cost, honestly stated Three tiers are worth being able to name: | Approach | Time | Comment | |---|---|---| | Sort suffixes with full comparisons | O(n^2 log n) | Each comparison is O(n); fine only for toy inputs | | Prefix doubling (Manber-Myers) | O(n log n) | Sort by first 1, 2, 4, 8 ... characters using previous ranks as keys | | SA-IS, DC3/skew | O(n) | Linear, and SA-IS is fast in practice, not merely asymptotically good | The naive tier is the one candidates skip past by saying "it's just a sort, so O(n log n)" — that ignores that a comparison between two suffixes is not O(1). The prefix-doubling insight is that after you know the rank of every suffix by its first `k` characters, the rank by its first `2k` characters is decided by the pair (rank of this suffix, rank of the suffix `k` further along), which is a constant-size key. That is the whole trick, and it is a good thing to be able to sketch. ## The properties that constrain how you use it - **Static.** Inserting or deleting a character changes the offsets of everything after it and can reorder ranks arbitrarily. There is no cheap patch; plain suffix arrays are built once over a frozen text. - **Needs the text.** The array is meaningless alone. Both the offsets and the original characters must be resident (or memory-mapped) for queries to run. - **Alphabet-agnostic.** Nothing above assumes small alphabets; comparisons just need a total order on symbols. - **Query cost is pattern-dominated.** For short patterns against a huge text, the `log n` factor is what you feel; for long patterns, the `m` term dominates and the LCP-augmented search is the fix. ## The failure mode to avoid saying out loud "A suffix array stores all `n` suffixes, so it's O(n^2) space" is the single most common wrong answer, and it is wrong in a way that also destroys the reasoning about everything downstream — the LCP array, the query bound, and the memory budget of a real index all follow from *offsets, not copies*. The second most common is quoting O(log n) for a query, which silently assumes constant-time string comparison. State the bound with the `m` in it and the direction of the claim stays right.
- How do you get every occurrence of the pattern, not just one?All suffixes beginning with the pattern are lexicographically adjacent, so they form one contiguous block of ranks. Run the binary search twice — once for the first rank at or after the pattern, once for the first rank past the block — and the offsets between those bounds are exactly the occurrence positions, reported in time proportional to how many there are.
- Why can't you binary-search the raw text and skip the array entirely?Binary search needs a sorted domain or a monotone predicate. The text in natural order is not sorted by suffix, so bisecting on a position tells you nothing about which half a pattern lives in. The suffix array is precisely the permutation that makes "all suffixes" a sorted sequence, which is what makes halving the candidate range valid.
- What happens to the array if the text gains a character at the front?Every existing offset shifts by one, and the ranks themselves can reorder, because a new suffix has been introduced and the lexicographic comparisons change. There is no cheap incremental repair for a plain suffix array — you rebuild. That staticness is a real constraint when choosing the structure for changing data.
It is a card catalogue rather than a second library: each card carries a shelf number, not a copy of the book, and you walk to the shelf whenever you actually need to read the text.
saying these in an interview costs you the question
- Says the array stores all n suffix strings, so O(n^2) space
- Quotes O(log n) per query, forgetting each comparison reads up to m characters
- Assumes construction is just a sort, so O(n log n) with no caveat
- Thinks the array can be queried without the original text present
- Believes new text can be appended and the array patched cheaply