Three Array Problems for Trading Geometry and Grouping

Problem Statement

In high-frequency automated systems, logs must be verified for geometric anomalies and identity reconciliation. Implement a utility class TradingToolkit with three independent static methods:

1. max_profit(prices: list[int]) -> int: Calculates the maximum achievable profit from buying on day i and selling on day j with i list[int] | None: Treats each entry prices[t] as a 2D coordinate (t, prices[t]) where t is the index. Identifies four distinct indices [i, j, k, l] with 0 <= i < j < k < l < len(prices) that lie on the exact same straight line in the 2D plane. If multiple quadruplets exist, return the one that is lexicographically smallest. If no such quadruplet exists, return None.

2. group_aliases(pairs: list[tuple[str, str]]) -> list[list[str]]: Given a list of alias pairs (a, b) indicating that name a and name b refer to the same trader, returns all connected components of aliases. Within each group, names must be sorted lexicographically. The outer list of groups must be sorted lexicographically by the first element of each group.

Input & Output Format

class TradingToolkit:
    @staticmethod
    def max_profit(prices: list[int]) -> int:
        pass

    @staticmethod
    def find_collinear_quad(prices: list[int]) -> list[int] | None:
        pass

    @staticmethod
    def group_aliases(pairs: list[tuple[str, str]]) -> list[list[str]]:
        pass

Constraints

• max_profit:

  • 0 <= len(prices) <= 10^5
  • -10^12 <= prices[i] <= 10^12 (values can be negative or large 64-bit integers)

• find_collinear_quad:

  • 4 <= len(prices) <= 2000
  • -10^9 <= prices[t] <= 10^9
  • All slope comparisons must use integer arithmetic to avoid floating-point inaccuracies.

• group_aliases:

  • 0 <= len(pairs) <= 5 * 10^4
  • 1 <= len(name) <= 32 for each name, consisting of lowercase English letters.

Examples

Example 1: max_profit

prices = [10, 7, 5, 8, 11, 9]
# Buy at 5 (index 2), sell at 11 (index 4)
assert TradingToolkit.max_profit(prices) == 6

prices_desc = [9, 8, 7, 5]
assert TradingToolkit.max_profit(prices_desc) == 0

Example 2: find_collinear_quad

# Coordinates: (0, 2), (1, 5), (2, 8), (3, 10), (4, 14), (5, 17)
# Points at indices 0, 1, 2, 5 lie on line y = 3x + 2
prices = [2, 5, 8, 10, 14, 17]
assert TradingToolkit.find_collinear_quad(prices) == [0, 1, 2, 5]

Example 3: group_aliases

pairs = [("trader_a", "bot_1"), ("trader_b", "bot_2"), ("bot_1", "trader_c")]
assert TradingToolkit.group_aliases(pairs) == [
    ["bot_1", "trader_a", "trader_c"],
    ["bot_2", "trader_b"]
]

Edge Cases

• prices with fewer than 2 elements in max_profit should return 0.
• Strictly decreasing prices in max_profit should return 0.
• In find_collinear_quad, points with slope zero (flat line) or steep negative slopes should be handled using cross-multiplication: (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1).
• Disconnected single-element nodes or self-pairs in group_aliases (e.g., ("a", "a")) should produce clean distinct groupings.