A suffix array is a sorted list of the starting positions of every suffix of a string. Instead of storing the suffixes themselves (which would cost O(n²) space), you store just their start indices in the order the suffixes would appear in a dictionary. That single sorted array unlocks fast substring search, longest-common-prefix queries, and a lot of competitive-programming string tricks.
Core idea. A string of length n has exactly n suffixes — one starting at each index. Sort those
suffixes alphabetically, then write down their start indices in that order. For s = 'banana' the
suffix array is [5, 3, 1, 0, 4, 2].
The suffixes of banana are banana (0), anana (1), nana (2), ana (3), na (4), and a (5). Sorted as dictionary words they become a, ana, anana, banana, na, nana — whose start indices are 5, 3, 1, 0, 4, 2.
Intuition
Think of every suffix as a word and the suffix array as alphabetizing those words. You never need to keep the words around — once you know that the suffix starting at index 5 sorts first, the suffix at index 3 next, and so on, the index list [5, 3, 1, 0, 4, 2] captures the entire sorted order. Because suffixes of the same string overlap heavily, this compact index order is all the structure later algorithms (binary-searching for a pattern, computing longest common prefixes) ever need.
Walk through it
Step through the animation on the right. First the string banana is laid out one character per cell. Then, index by index, each suffix s[i:] is listed in its natural order 0 through 5 — the highlighted character marks where that suffix begins and it runs to the end of the string.
Once all six suffixes are listed, the sort happens: every suffix row slides up or down to its alphabetical position. a (index 5) rises to the top, ana (index 3) follows, then anana (1), banana (0), na (4), and nana (2). Reading the start indices top to bottom gives the suffix array [5, 3, 1, 0, 4, 2], shown in the final label.
The code, line by line
def suffix_array(s):
n = len(s)
return sorted(range(n), key=lambda i: s[i:])range(n)produces the candidate start indices0, 1, ..., n - 1— one per suffix.- The
key=lambda i: s[i:]tellssortedto compare each indexiby the suffix that starts there,s[i:], not by the number itself. sortedthen returns those indices reordered so their suffixes are in lexicographic order — exactly the suffix array.
Complexity
| Case | Time | Notes |
|---|---|---|
| Comparisons | O(n log n) (moderate) | sorting n suffixes |
| Each compare | O(n) (moderate) | two suffixes can share a long prefix |
| Total (this build) | O(n^2 log n) (moderate) | comparison cost times sort cost |
O(n^2) (slow)This simple build slices s[i:], so each suffix is a full O(n) string and a single comparison can scan up to n characters — giving an overall O(n² log n) worst case (the space is O(n²) because the slices materialize whole suffixes). It is perfect for learning and for short strings. Production suffix arrays use prefix-doubling (O(n log n)) or the DC3/SA-IS algorithms (O(n)), which sort indices by rank pairs instead of copying strings.
When to use / pitfalls
Reach for a suffix array when a problem is about substrings of one fixed string: pattern search,
counting distinct substrings, longest repeated substring, or longest common prefix between suffixes.
In an interview, the one-liner sorted(range(n), key=lambda i: s[i:]) is usually enough to show you
understand the structure; mention prefix-doubling if asked to make it scale.
The clean one-liner hides an O(n) comparison cost, so it is not truly O(n log n) — do not claim that
on a large input. Also remember the array holds start indices, not the suffix strings; the strings
are only there to define the sort order. Slicing s[i:] copies characters, so avoid this build for very
long strings.
Practice
For s = 'banana', which start index sorts FIRST in the suffix array, and why?
1. What does a suffix array actually store?
2. For s = 'banana', what is the suffix array?
3. What is the time complexity of the simple sorted(range(n), key=lambda i: s[i:]) build?
4. Why does the suffix 'a' sort before 'ana'?