Application Page

Shortest Unique Subarray

This page uses the problem: why the shortest unique subarray becomes 'how far a suffix must go beyond both neighbors'.

Reasoning flow

Interval ms

Why

Suffix order

Answer

need for each start

start	left	right	same	need	state

C++

Core code

This shows only the application layer. Compression, suffix arrays, and LCP are explained on the linked concept pages.

int smallestUniqueSubarray(vector<int>& a) {    int n = a.size();    a = compress(a);    auto sa = buildSuffixArray(a);    auto lcp = buildLCP(a, sa);     vector<int> rank(n);    for (int i = 0; i < n; i++) rank[sa[i]] = i;     int res = n;    for (int i = 0; i < n; i++) {        int p = rank[i];        int same = 0;        if (p > 0) same = max(same, lcp[p]);        if (p + 1 < n) same = max(same, lcp[p + 1]);        int need = same + 1;        if (need <= n - i) res = min(res, need);    }    return res;}