Find earliest supporting dependency version

Question

Given a list of dependency versions (e.g. [103.003.02, 103.003.03, 203.003.02]) and a black-box API isSupported(v), design an algorithm to find the earliest (lowest) version that supports a target feature. 2) Versions follow {major}.{minor}.{patch}. Support is not monotonic: a higher version may drop support, but it is guaranteed that some later version will support again. The API is rate-limited, so total calls must be sub-linear to the number of versions. Devise a strategy—e.g., group by latest patch per major, binary-search majors, then minors, then patches—to minimize API usage while reliably returning the earliest supporting version.

Find Earliest Supporting Dependency Version

Find the earliest dependency version that supports a target feature, using as few API probes as possible.

What to implement

solution(versions, supported_versions)

• versions — a list of distinct version strings, each in the form "major.minor.patch" (numeric components, possibly zero-padded, e.g. "104.000.01"). The list is already sorted in ascending semantic-version order.
• supported_versions — a list that simulates a black-box API isSupported(v): a version supports the feature if and only if it appears in supported_versions. This list is always a subset of versions.

Return the earliest (smallest in the sorted order) version string that supports the feature, or None if no version supports it.

Why this isn't a plain search

Support is not monotonic across the full version list: an early version may support the feature, a later version (in a new major or minor) may not, and an even later one may support again. So you cannot simply scan or binary-search the whole list directly.

Structure guarantees (these make a sub-linear API strategy possible)

The data obeys a three-level hierarchical pattern:

1. Major level. If any version supports the feature, there is a first supporting major, and every major after it also contains at least one supporting version.
2. Minor level. Inside that first supporting major, there is a first supporting minor, and every later minor within that major also contains at least one supporting version.
3. Patch level. Inside that first supporting major/minor pair, support is monotonic by patch among the listed versions — once support starts, it continues.

Additionally, if a major or a minor contains any supporting version, then its latest listed version is guaranteed to be supporting. This lets you probe a single representative version per major and per minor.

The earliest supporting version is therefore the first supporting patch inside the first supporting minor inside the first supporting major.

Constraints

• 0 <= len(versions) <= 200000
• versions is sorted ascending, all versions are distinct, and supported_versions is a subset of versions.
• The support pattern always obeys the hierarchical guarantees above: if support exists at all, a first supporting major exists; within it a first supporting minor exists; within it a first supporting patch exists; and the latest listed version of any supporting major or minor is also supporting.

Examples

• versions = ["103.003.01", "103.003.02", "103.004.01", "104.000.01", "104.001.01", "104.001.02", "105.000.01"], supported_versions = ["103.004.01", "104.001.02", "105.000.01"] → "103.004.01"
• versions = ["101.000.01", "101.001.01", "102.000.01", "102.000.02", "102.001.01", "103.000.01"], supported_versions = ["102.000.02", "102.001.01", "103.000.01"] → "102.000.02"
• versions = ["200.000.01"], supported_versions = ["200.000.01"] → "200.000.01"
• versions = ["300.000.01", "300.000.02"], supported_versions = [] → None
• versions = [], supported_versions = [] → None

Hints

1. You do not need to probe every version. The latest version inside a major tells you whether that major contains any supporting version.
2. After finding the first supporting major, repeat the same idea for minors, then binary search patches inside the chosen minor.

Approach

The data hides a feature behind three nested layers, and within each layer the supporting versions form a suffix (once support starts, it never stops). So the solution does three binary searches, one per layer.

Step 1 — bucket the versions. A single linear pass splits every "major.minor.patch" string and groups versions into a nested map:

• major_order / major_map[major] — ordered list of distinct majors, each tracking its latest listed version, its minor_order, and its minors.
• each minor tracks its own latest version and the ordered versions list for its patches.

Because input is already sorted, latest ends up holding the highest version seen in each bucket.

Step 2 — find the first supporting major. first_true is a classic "leftmost true" binary search. The key guarantee: if a major contains any supporting version, its latest listed version is supporting, and supporting majors form a suffix. So testing major_map[major]['latest'] in supported is monotonic across major_order, and the binary search finds the earliest qualifying major.

Step 3 — find the first supporting minor inside that major using the same latest in supported predicate over minor_order.

Step 4 — find the first supporting patch. Within the chosen major/minor, support is monotonic by patch, so a plain leftmost binary search over patch_versions returns the earliest supported version.

If any layer has no supporting bucket, the search returns None. The empty-input and all-None cases short-circuit correctly. Correctness rests entirely on the problem's suffix/monotonicity guarantees, which make each in supported probe a valid binary-search predicate.

• Time complexity: O(n)
• Space complexity: O(n)