Constraints

• 0 <= len(versions) <= 200000
• 0 <= len(supported_versions) <= 200000
• A valid version has exactly 3 non-empty numeric segments separated by dots
• Leading zeros are allowed and do not affect ordering
• Invalid version strings must be ignored

Examples

Solution

def solution(versions, supported_versions):
    def parse(version):
        if not isinstance(version, str):
            return None
        parts = version.split('.')
        if len(parts) != 3:
            return None
        nums = []
        for part in parts:
            if part == '' or not part.isdigit():
                return None
            nums.append(int(part))
        return tuple(nums)

    supported_set = set()
    if supported_versions is not None:
        for v in supported_versions:
            parsed = parse(v)
            if parsed is not None:
                supported_set.add(parsed)

    best = None
    if versions is not None:
        for v in versions:
            parsed = parse(v)
            if parsed is None:
                continue
            if parsed in supported_set:
                if best is None or parsed < best:
                    best = parsed

    if best is None:
        return None
    return f"{best[0]}.{best[1]}.{best[2]}"

Time complexity: O(V + S), where V = len(versions) and S = len(supported_versions). Space complexity: O(S).

Hints

1. Parse every valid version into a tuple of three integers so numeric comparison becomes easy.
2. Because support is not monotonic, scanning the list and tracking the minimum supporting version is enough; binary search does not apply.

Constraints

• 0 <= len(versions) <= 200000
• 0 <= len(supported_versions) <= 200000
• A valid version has exactly 3 non-empty numeric segments separated by dots
• Leading zeros are allowed and do not affect ordering
• The monotone representative guarantees listed above hold for all valid test cases
• Invalid version strings must be ignored

Examples

Solution

def solution(versions, supported_versions):
    from collections import defaultdict

    def parse(version):
        if not isinstance(version, str):
            return None
        parts = version.split('.')
        if len(parts) != 3:
            return None
        nums = []
        for part in parts:
            if part == '' or not part.isdigit():
                return None
            nums.append(int(part))
        return tuple(nums)

    def canonical(v):
        return f"{v[0]}.{v[1]}.{v[2]}"

    valid_versions = set()
    if versions is not None:
        for v in versions:
            parsed = parse(v)
            if parsed is not None:
                valid_versions.add(parsed)

    if not valid_versions:
        return None

    supported_set = set()
    if supported_versions is not None:
        for v in supported_versions:
            parsed = parse(v)
            if parsed is not None and parsed in valid_versions:
                supported_set.add(parsed)

    groups = defaultdict(lambda: defaultdict(list))
    for major, minor, patch in valid_versions:
        groups[major][minor].append(patch)

    majors = sorted(groups.keys())
    minor_list = {}
    patch_list = {}
    latest_minor = {}
    latest_major = {}

    for major in majors:
        minors = sorted(groups[major].keys())
        minor_list[major] = minors
        for minor in minors:
            patches = sorted(groups[major][minor])
            patch_list[(major, minor)] = patches
            latest_minor[(major, minor)] = (major, minor, patches[-1])
        last_minor = minors[-1]
        latest_major[major] = latest_minor[(major, last_minor)]

    def first_true(values, predicate):
        lo, hi = 0, len(values)
        while lo < hi:
            mid = (lo + hi) // 2
            if predicate(values[mid]):
                hi = mid
            else:
                lo = mid + 1
        return lo

    major_idx = first_true(majors, lambda major: latest_major[major] in supported_set)
    if major_idx == len(majors):
        return None
    chosen_major = majors[major_idx]

    minors = minor_list[chosen_major]
    minor_idx = first_true(minors, lambda minor: latest_minor[(chosen_major, minor)] in supported_set)
    if minor_idx == len(minors):
        return None
    chosen_minor = minors[minor_idx]

    patches = patch_list[(chosen_major, chosen_minor)]
    patch_idx = first_true(patches, lambda patch: (chosen_major, chosen_minor, patch) in supported_set)
    if patch_idx == len(patches):
        return None

    return canonical((chosen_major, chosen_minor, patches[patch_idx]))

Time complexity: O(N log N) total time for parsing, deduplication, and sorting; support checks are O(log A + log B + log C), where A is the number of majors, B is the number of minors in the chosen major, and C is the number of patches in the chosen minor. Space complexity: O(N).

Hints

1. Precompute the latest version in each major and the latest version in each minor of a major.
2. Run three lower-bound style binary searches: one over majors, one over minors in the chosen major, and one over patches in the chosen minor.