def find_leaders(arr: list) -> list:
    """
    Time Complexity: O(n)
    Space Complexity: O(1)
    Returns: List of leaders in the array
    """
    n = len(arr)
    leaders = []
    max_right = arr[n-1]
    leaders.append(max_right)
    
    for i in range(n-2, -1, -1):
        if arr[i] > max_right:
            leaders.append(arr[i])
            max_right = arr[i]
    
    return leaders[::-1]  # Reverse to maintain original order

# Alternative approach with scanning from left
def find_leaders_left_scan(arr: list) -> list:
    n = len(arr)
    leaders = []
    current_max = float('-inf')
    
    for i in range(n):
        is_leader = True
        for j in range(i+1, n):
            if arr[i] <= arr[j]:
                is_leader = False
                break
        if is_leader and arr[i] > current_max:
            leaders.append(arr[i])
            current_max = arr[i]
    
    return leaders

def find_majority_element(arr: list) -> int:
    """
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    candidate = None
    count = 0
    
    # Finding candidate
    for num in arr:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    
    # Verifying candidate
    count = sum(1 for num in arr if num == candidate)
    return candidate if count > len(arr) // 2 else None

# Extended version for elements appearing > n/3 times
def find_majority_elements_n3(arr: list) -> list:
    """
    Find elements appearing more than n/3 times
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    if not arr:
        return []
        
    count1 = count2 = 0
    candidate1 = candidate2 = None
    
    # Finding candidates
    for num in arr:
        if candidate1 == num:
            count1 += 1
        elif candidate2 == num:
            count2 += 1
        elif count1 == 0:
            candidate1 = num
            count1 = 1
        elif count2 == 0:
            candidate2 = num
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1
    
    # Verifying candidates
    count1 = count2 = 0
    for num in arr:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1
    
    result = []
    threshold = len(arr) // 3
    if count1 > threshold:
        result.append(candidate1)
    if count2 > threshold:
        result.append(candidate2)
    
    return result

def find_missing_number(arr: list) -> int:
    """
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(arr) + 1
    expected_sum = (n * (n + 1)) // 2
    actual_sum = sum(arr)
    return expected_sum - actual_sum

# XOR approach
def find_missing_number_xor(arr: list) -> int:
    n = len(arr) + 1
    xor_all = 0
    
    # XOR all numbers from 1 to n
    for i in range(1, n + 1):
        xor_all ^= i
    
    # XOR with array elements
    for num in arr:
        xor_all ^= num
    
    return xor_all

# Multiple missing numbers
def find_multiple_missing(arr: list) -> list:
    """
    Find all missing numbers in range [1,n]
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(arr)
    for i in range(n):
        while 0 < arr[i] <= n and arr[arr[i]-1] != arr[i]:
            arr[arr[i]-1], arr[i] = arr[i], arr[arr[i]-1]
    
    missing = []
    for i in range(n):
        if arr[i] != i + 1:
            missing.append(i + 1)
    
    return missing

def find_duplicate(arr: list) -> int:
    """
    Floyd's Tortoise and Hare (Cycle Detection)
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    tortoise = hare = arr[0]
    
    # Find intersection point
    while True:
        tortoise = arr[tortoise]
        hare = arr[arr[hare]]
        if tortoise == hare:
            break
    
    # Find entrance to cycle
    tortoise = arr[0]
    while tortoise != hare:
        tortoise = arr[tortoise]
        hare = arr[hare]
    
    return hare

# Find all duplicates
def find_all_duplicates(arr: list) -> list:
    """
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    duplicates = []
    
    for num in arr:
        index = abs(num) - 1
        if arr[index] > 0:
            arr[index] = -arr[index]
        else:
            duplicates.append(abs(num))
    
    return duplicates

def rearrange_alternate(arr: list) -> None:
    """
    Rearrange array in alternating positive and negative items
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(arr)
    i = 0
    j = n - 1
    
    # Separate positive and negative numbers
    while i < j:
        while i < n and arr[i] >= 0:
            i += 1
        while j >= 0 and arr[j] < 0:
            j -= 1
        if i < j:
            arr[i], arr[j] = arr[j], arr[i]
    
    # Rearrange alternatively
    k = 0
    while k < n and i < n:
        arr[k], arr[i] = arr[i], arr[k]
        k += 2
        i += 1

def rearrange_array_elements(arr: list) -> None:
    """
    Rearrange array such that arr[i] becomes arr[arr[i]]
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(arr)
    
    # First step: Increase all elements by (arr[arr[i]] % n) * n
    for i in range(n):
        arr[i] += (arr[arr[i]] % n) * n
    
    # Second step: Divide all elements by n
    for i in range(n):
        arr[i] //= n

def rotate_matrix(matrix: list) -> None:
    """
    Rotate matrix 90 degrees clockwise in-place
    Time Complexity: O(n²)
    Space Complexity: O(1)
    """
    n = len(matrix)
    
    # Transpose
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    
    # Reverse each row
    for i in range(n):
        matrix[i].reverse()

def search_sorted_matrix(matrix: list, target: int) -> bool:
    """
    Search in sorted matrix (each row and column is sorted)
    Time Complexity: O(m + n)
    Space Complexity: O(1)
    """
    if not matrix or not matrix[0]:
        return False
    
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1
    
    while row < m and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    
    return False

def set_matrix_zeroes(matrix: list) -> None:
    """
    Set row and column to zero if element is zero
    Time Complexity: O(m*n)
    Space Complexity: O(1)
    """
    if not matrix or not matrix[0]:
        return
    
    m, n = len(matrix), len(matrix[0])
    is_first_row_zero = 0 in matrix[0]
    is_first_col_zero = 0 in [matrix[i][0] for i in range(m)]
    
    # Use first row/column as markers
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0
    
    # Set zeroes based on markers
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    
    # Handle first row and column
    if is_first_row_zero:
        matrix[0] = [0] * n
    if is_first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

def spiral_matrix(matrix: list) -> list:
    """
    Return matrix elements in spiral order
    Time Complexity: O(m*n)
    Space Complexity: O(1)
    """
    if not matrix:
        return []
    
    result = []
    top = left = 0
    bottom, right = len(matrix) - 1, len(matrix[0]) - 1
    
    while top <= bottom and left <= right:
        # Traverse right
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1
        
        # Traverse down
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        
        if top <= bottom:
            # Traverse left
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1
        
        if left <= right:
            # Traverse up
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    
    return result

def maximum_product_three(arr: list) -> int:
    """
    Find maximum product of three numbers in array
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    min1 = min2 = float('inf')
    max1 = max2 = max3 = float('-inf')
    
    for num in arr:
        # Update minimums
        if num <= min1:
            min2 = min1
            min1 = num
        elif num <= min2:
            min2 = num
            
        # Update maximums
        if num >= max1:
            max3 = max2
            max2 = max1
            max1 = num
        elif num >= max2:
            max3 = max2
            max2 = num
        elif num >= max3:
            max3 = num
    
    return max(min1 * min2 * max1, max1 * max2 * max3)

def find_peak_element(arr: list) -> int:
    """
    Find a peak element (element greater than both neighbors)
    Time Complexity: O(log n)
    Space Complexity: O(1)
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] > arr[mid + 1]:
            right = mid
        else:
            left = mid + 1
    
    return left

def find_all_peaks(arr: list) -> list:
    """
    Find all peak elements in array
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(arr)
    peaks = []
    
    for i in range(n):
        is_peak = True
        if i > 0 and arr[i] <= arr[i-1]:
            is_peak = False
        if i < n-1 and arr[i] <= arr[i+1]:
            is_peak = False
        if is_peak:
            peaks.append(i)
    
    return peaks

def matrix_chain_multiplication(dimensions: list) -> int:
    """
    Find minimum number of multiplications needed for matrix chain
    Time Complexity: O(n³)
    Space Complexity: O(n²)
    """
    n = len(dimensions) - 1
    dp = [[0] * n for _ in range(n)]
    
    # Length of chain
    for L in range(2, n + 1):
        # Starting index of chain
        for i in range(n - L + 1):
            j = i + L - 1
            dp[i][j] = float('inf')
            # Try different partitions
            for k in range(i, j):
                cost = (dp[i][k] + dp[k + 1][j] + 
                       dimensions[i] * dimensions[k + 1] * dimensions[j + 1])
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

def modify_matrix(matrix: list) -> None:
    """
    Modify matrix: if an element is 1, set its entire row and column to 1
    Time Complexity: O(m*n)
    Space Complexity: O(1)
    """
    m, n = len(matrix), len(matrix[0])
    first_row = any(matrix[0][j] == 1 for j in range(n))
    first_col = any(matrix[i][0] == 1 for i in range(m))
    
    # Mark rows and columns using first row/column
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 1:
                matrix[i][0] = matrix[0][j] = 1
    
    # Modify based on marks
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 1 or matrix[0][j] == 1:
                matrix[i][j] = 1
    
    # Modify first row and column
    if first_row:
        for j in range(n):
            matrix[0][j] = 1
    if first_col:
        for i in range(m):
            matrix[i][0] = 1

def next_permutation(arr: list) -> None:
    """
    Rearrange numbers to get next greater permutation
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(arr)
    i = n - 2
    
    # Find first decreasing element
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1
    
    if i >= 0:
        j = n - 1
        # Find next greater element
        while j >= 0 and arr[j] <= arr[i]:
            j -= 1
        arr[i], arr[j] = arr[j], arr[i]
    
    # Reverse suffix
    left = i + 1
    right = n - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

def rearrange_by_index(arr: list) -> None:
    """
    Rearrange array so that arr[i] becomes arr[arr[i]]
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(arr)
    
    # Update elements with encoded information
    for i in range(n):
        arr[i] += (arr[arr[i]] % n) * n
    
    # Decode information
    for i in range(n):
        arr[i] //= n

def max_circular_subarray(arr: list) -> int:
    """
    Find maximum sum circular subarray
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    def kadane(arr: list) -> int:
        max_so_far = max_ending_here = arr[0]
        for num in arr[1:]:
            max_ending_here = max(num, max_ending_here + num)
            max_so_far = max(max_so_far, max_ending_here)
        return max_so_far
    
    # Case 1: Maximum subarray sum without wrapping
    max_normal = kadane(arr)
    
    # Case 2: Maximum subarray sum with wrapping
    array_sum = sum(arr)
    inverted = [-x for x in arr]
    max_inverted = kadane(inverted)
    max_wrapped = array_sum + max_inverted
    
    # Return maximum of two cases
    return max(max_normal, max_wrapped) if max_wrapped != 0 else max_normal

def count_subarrays_with_sum(arr: list, target_sum: int) -> int:
    """
    Count number of subarrays with given sum
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    count = 0
    curr_sum = 0
    sum_count = {0: 1}  # prefix sum : frequency
    
    for num in arr:
        curr_sum += num
        if curr_sum - target_sum in sum_count:
            count += sum_count[curr_sum - target_sum]
        sum_count[curr_sum] = sum_count.get(curr_sum, 0) + 1
    
    return count

def find_pattern_leaders(arr: list) -> list:
    """
    Find pattern leaders (elements greater than all following distinct elements)
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    n = len(arr)
    seen = set()
    leaders = []
    max_right = float('-inf')
    
    for i in range(n-1, -1, -1):
        if arr[i] not in seen and arr[i] > max_right:
            leaders.append(arr[i])
            max_right = arr[i]
        seen.add(arr[i])
    
    return leaders[::-1]

def search_pattern(text: str, pattern: str) -> list:
    """
    Find all occurrences of pattern in text (KMP Algorithm)
    Time Complexity: O(n + m)
    Space Complexity: O(m)
    """
    def compute_lps(pattern: str) -> list:
        m = len(pattern)
        lps = [0] * m
        length = 0
        i = 1
        
        while i < m:
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps
    
    n, m = len(text), len(pattern)
    if m == 0:
        return []
    
    lps = compute_lps(pattern)
    result = []
    i = j = 0
    
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == m:
            result.append(i - j)
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return result