Q2-binary-search

def findMinimumTime(password: str, attackOrder: list[int], m: int) -> int:
    N = len(password)

    if N == 0:
        return 0

    if m == 0:
        return 1 # After 1st attack (N>=1), malicious_substring_count > 0, so >= 0.

    total_possible_substrings = N * (N + 1) // 2

    def count_substrings_from_length(k: int) -> int:
        if k <= 0:
            return 0
        return k * (k + 1) // 2

    # This function checks if performing 'num_attacks' makes the password irrecoverable
    def check(num_attacks: int) -> bool:
        if num_attacks == 0: # 0 attacks mean 0 malicious substrings
             return 0 >= m # True only if m is also 0 (handled above) or negative

        is_malicious = [False] * N
        for i in range(num_attacks):
            # attackOrder is 1-indexed
            attack_idx_0_based = attackOrder[i] - 1
            is_malicious[attack_idx_0_based] = True

        current_total_clean_substrings = 0
        current_clean_length = 0
        for i in range(N):
            if not is_malicious[i]:
                current_clean_length += 1
            else:
                current_total_clean_substrings += count_substrings_from_length(current_clean_length)
                current_clean_length = 0
        current_total_clean_substrings += count_substrings_from_length(current_clean_length) # For the last segment

        num_malicious_substrings = total_possible_substrings - current_total_clean_substrings
        return num_malicious_substrings >= m

    # Binary search for the minimum number of attacks (time)
    min_time = N # The answer must be at most N
    low = 1
    high = N

    while low <= high:
        mid_time = low + (high - low) // 2
        if mid_time == 0 and m > 0 : # Edge case for binary search reaching 0 if not careful
             low = mid_time + 1
             continue

        if check(mid_time):
            min_time = mid_time # This time works, try smaller
            high = mid_time - 1
        else:
            low = mid_time + 1

    return min_time