For each candidate first index in a sorted array, use lower-bound search for only in the suffix starting at . A matching result is automatically at a different position. The outer loop invariant excludes all solutions whose smaller index precedes ; an unsuccessful suffix search extends this exclusion by one. Exhaustion proves absence of any pair. Searching all suffixes gives running time and constant auxiliary space. Compute the complement in a sufficiently wide type to avoid integer overflow before comparison.

Articles by others on the same topic (0)

There are currently no matching articles.