08_equi_leader.py

"""https://app.codility.com/programmers/lessons/8-leader/equi_leader/"""

# Time complexity:
# Precompute right frequency count = O(N),
# Sliding window with O(1) ops per element = O(N)
# Overall: O(2N) = O(N)

# Space complexity:
# O(2N) = O(N) for frequency counts

def solution_a(a: list[int]) -> int:
    """Sliding window with frequency count"""
    left, right = {}, {}
    n = len(a)
    for num in a:
        right[num] = right.get(num, 0) + 1
    equi_leaders = 0
    # Partition sizes
    left_size = 0
    right_size = n
    # Maintain leader element in left partition.
    # An equi-leader requires the left leader to be the leader element in the right partition.
    left_leader = -1
    for i in range(n-1):
        num = a[i]
        # Update frequency counts
        left[num] = left.get(num, 0) + 1
        right[num] -= 1
        # Check leader element in left partition
        if left[num] > left.get(left_leader, 0):
            left_leader = num
        # Update sizes
        left_size += 1
        right_size -= 1
        if left[left_leader] > left_size // 2 and right[left_leader] > right_size // 2:
            equi_leaders += 1
    return equi_leaders

# Time complexity:
# Single pass to find leader candidate = O(N),
# Single pass to verify leader = O(N),
# Single pass to count equi-leaders = O(N)
# Overall: O(3N) = O(N)

# Space complexity: O(1)

def solution_b(a: list[int]) -> int:
    """
    Space-optimised solution generated by gemini-3-pro (my explanations added),
    Count equi-leaders using Boyer–Moore majority voting algorithm
    """
    n = len(a)
    if n == 0:
        return 0

    # Suppose we have value X. For it to be an equi-leader (dominant in left and right partitions)
    # then (cnt_left(X) > size_left / 2) and (cnt_right(X) > size_right / 2).
    # Combining inequalities (cnt_left(X) + cnt_right(X) = cnt_total(X)) and
    # (size_left + size_right = n), when X is an equi-leader of the 2 partitions,
    # (cnt_total(X) > n / 2) must hold true, the definition of a leader.
    # Therefore, an equi-leader must be the leader of the entire array.

    # Find leader candidate using Boyer–Moore majority voting algorithm
    candidate_index = -1
    cnt = 0
    for i in range(n):
        if cnt == 0:
            candidate_index = i
            cnt = 1
        elif a[i] == a[candidate_index]:
            cnt += 1
        else:
            cnt -= 1

    # Verify candidate is true leader
    candidate = a[candidate_index]
    total_count = a.count(candidate)

    # No leader == no equi-leaders
    if total_count <= n // 2:
        return 0

    # Count equi-leaders using sliding window
    equi_leaders = 0
    left_count = 0
    for i in range(n-1):
        if a[i] == candidate:
            left_count += 1
        left_size = i + 1
        right_size = n - left_size
        if left_count > left_size // 2 and (total_count - left_count) > right_size // 2:
            equi_leaders += 1

    return equi_leaders