Python Notes

Python Dominator

def dominator(a: list[int]) -> int:
    size = value = index = 0
    for k, v in enumerate(a):
        if size == 0:
            size += 1
            value = v
            index = k
        elif value != v:
            size -= 1
        else:
            size += 1
    candidate = value if size > 0 else -1

    count = sum(1 for v in a if v == candidate)
    if count <= len(a) / 2:
        index = -1

    return index

This finds a value that appears in more than half of the array, then returns one valid index for it.

Python Equi Leader

def equi_leader(a: list[int]) -> int:
    leader_size = value = 0
    for v in a:
        if leader_size == 0:
            leader_size += 1
            value = v
        elif value != v:
            leader_size -= 1
        else:
            leader_size += 1
    candidate = value if leader_size > 0 else -1

    count = len(a)
    leader_count = sum(1 for v in a if v == candidate)
    leader = candidate if leader_count > count / 2 else -1

    l_leader_count = 0
    equi_leaders = 0
    for k, v in enumerate(a):
        left_half = (k + 1) // 2
        right_half = (count - k - 1) // 2
        if v == leader:
            l_leader_count += 1

        r_leader_count = leader_count - l_leader_count
        if l_leader_count > left_half and r_leader_count > right_half:
            equi_leaders += 1

    return equi_leaders

This keeps leader counts on both sides of the split and counts positions where the same leader survives in each half.

Python Fib Frog

from collections import deque


def fib_frog(a: list[int]) -> int:
    size = len(a)

    fib = [0, 1]
    i = 1
    while fib[i] <= size:
        i += 1
        fib.append(fib[i - 1] + fib[i - 2])

    queue = deque([(-1, 0)])
    visited = [False] * size

    while queue:
        idx, jumps = queue.popleft()
        for f in range(len(fib) - 1, 1, -1):
            new_idx = idx + fib[f]
            if new_idx == size:
                return jumps + 1
            if new_idx > size or visited[new_idx] or a[new_idx] == 0:
                continue
            if a[new_idx] == 1:
                visited[new_idx] = True
                queue.append((new_idx, jumps + 1))

    return -1

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

Python Fish

def fish(a: list[int], b: list[int]) -> int:
    size = len(a)
    dead = 0
    downstream: list[int] = []

    for i in range(size):
        if b[i] == 1:
            downstream.append(a[i])
        else:
            while downstream:
                dead += 1
                if a[i] > downstream[-1]:
                    downstream.pop()
                else:
                    break

    return size - dead

This uses a stack for downstream fish and resolves fights only when opposite directions meet.

Python Flags

def flags(a: list[int]) -> int:
    size = len(a)
    if size == 0:
        return 0

    peaks = [False] * size
    for i in range(1, size):
        next_val = a[i + 1] if i + 1 < size else 0
        peaks[i] = a[i - 1] < a[i] and a[i] > next_val

    next_peak = [0] * size
    next_peak[size - 1] = -1
    for i in range(size - 2, -1, -1):
        next_peak[i] = i if peaks[i] else next_peak[i + 1]

    i = 1
    result = 0
    while i * (i - 1) <= size:
        pos = 0
        num = 0
        while pos < size and num < i:
            pos = next_peak[pos]
            if pos == -1:
                break
            num += 1
            pos += i
        i += 1
        result = max(result, num)

    return result

This finds all peaks first, then checks how many flags can be placed while keeping the required distance.

Python Frog Jmp

import math


def frog_jmp(x: int, y: int, d: int) -> int:
    return math.ceil((y - x) / d)

This computes the jump count with math instead of simulation, which is the cleanest way to solve it.

Python Frog River One

def frog_river_one(x: int, a: list[int]) -> int:
    existing: set[int] = set()
    for k, i in enumerate(a):
        if i not in existing and i <= x:
            existing.add(i)
            if len(existing) == x:
                return k

    return -1

This tracks the earliest time each needed position appears and stops as soon as the frog can cross.

Python Genomic Range Query

def genomic_range_query(s: str, p: list[int], q: list[int]) -> list[int]:
    result = []
    for pi, qi in zip(p, q):
        sub = s[pi:qi + 1]
        if "A" in sub:
            result.append(1)
        elif "C" in sub:
            result.append(2)
        elif "G" in sub:
            result.append(3)
        else:
            result.append(4)

    return result

This builds prefix counts for each DNA letter so every query can return the minimum impact factor quickly.

Python Is Ipv 4 Adress

def is_ipv4_address(input_string: str) -> bool:
    parts = input_string.split(".")
    if len(parts) != 4:
        return False

    for v in parts:
        try:
            n = int(v)
        except ValueError:
            return False
        if n > 255 or v == "" or v != str(n):
            return False

    return True

This splits the string by dots and validates each part as a normal IPv4 octet.

Python Ladder

def ladder(a: list[int], b: list[int]) -> list[int]:
    size = len(a)
    mod = (1 << max(b)) - 1

    fib = [0, 1]
    for i in range(2, max(a) + 2):
        fib.append((fib[i - 1] + fib[i - 2]) & mod)

    result = [0] * size
    for i in range(size):
        result[i] = fib[a[i] + 1] & ((1 << b[i]) - 1)

    return result

This precomputes climb counts once and applies the modulo per query, which avoids recalculating the same paths over and over.