Solution Contract Specification¶

# solutions/0001_two_sum.py
from typing import List
from _runner import get_solver

SOLUTIONS = {
    "default": {
        "class": "Solution",
        "method": "twoSum",
        "complexity": "O(n) time, O(n) space",
        "description": "Single pass with hash map",
    },
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        return []

def solve():
    import sys
    import json
    lines = sys.stdin.read().strip().split('\n')
    nums = json.loads(lines[0])
    target = int(lines[1])

    solver = get_solver(SOLUTIONS)
    result = solver.twoSum(nums, target)
    print(json.dumps(result, separators=(',', ':')))

if __name__ == "__main__":
    solve()

from typing import List
from _runner import get_solver

SOLUTIONS = {
    "default": {
        "class": "SolutionHeap",
        "method": "mergeKLists",
        "complexity": "O(N log k)",
        "description": "Min-heap approach",
    },
    "divide": {
        "class": "SolutionDivideConquer",
        "method": "mergeKLists",
        "complexity": "O(N log k)",
        "description": "Divide and conquer",
    },
    "greedy": {
        "class": "SolutionGreedy",
        "method": "mergeKLists",
        "complexity": "O(N * k)",
        "description": "Sequential merge",
    },
}

class SolutionHeap:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        ...

class SolutionDivideConquer:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        ...

class SolutionGreedy:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        ...

def solve():
    # ... parse input ...
    solver = get_solver(SOLUTIONS)
    result = solver.mergeKLists(lists)
    print(result)

from _runner import get_solver

def solve():
    solver = get_solver(SOLUTIONS)  # Returns correct class instance
    result = solver.methodName(args)  # Natural LeetCode-style call

# ❌ DEPRECATED
def solve_a(nums, val):
    return SolutionA().removeElement(nums, val)

SOLUTIONS = {
    "default": {"method": "solve_a", ...},  # Missing 'class' field
}

"""
Problem: Two Sum
Link: https://leetcode.com/problems/two-sum/

Given an array of integers nums and an integer target, return indices 
of the two numbers such that they add up to target.

Constraints:
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists.
"""

# ============================================================================
# Solution 1: Sliding Window (Optimized with Jump)
# Time: O(n), Space: O(min(n, σ))
#   - Each character visited at most twice
#   - Uses last-seen-index array for O(1) duplicate detection
#   - Direct position jumping instead of incremental contraction
# ============================================================================
class SolutionSlidingWindow:   # ← No blank line
    ...

# ============================================================================
# Solution 1: Interval DP (Character Printing)
# Time: O(n³), Space: O(n²)
#   - Key insight: when s[k] == s[i], extend first print to cover s[k]
#   - Preprocess: remove consecutive duplicates
# ============================================================================
class Solution:
    # State: dp[i][j] = minimum turns to print s[i:j+1]
    # Base case: dp[i][i] = 1 (single char needs 1 turn)
    # Transition: dp[i][j] = min(dp[i+1][j] + 1,
    #                            dp[i+1][k-1] + dp[k][j]) for s[k]==s[i]

    def strangePrinter(self, s: str) -> int:
        ...

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.global_max = float('-inf')

        def max_contribution(node: Optional[TreeNode]) -> int:
            if not node:
                return 0

            # Prune negative branches - they can only decrease path sum
            left_gain = max(0, max_contribution(node.left))
            right_gain = max(0, max_contribution(node.right))

            # Path through this node as apex: left → node → right
            path_through_here = node.val + left_gain + right_gain
            self.global_max = max(self.global_max, path_through_here)

            # Return single-branch max to parent (can't fork upward)
            return node.val + max(left_gain, right_gain)

        max_contribution(root)
        return self.global_max

SOLUTIONS = {
    "key": {
        "class": str,        # REQUIRED: Class name
        "method": str,       # REQUIRED: Method name (LeetCode original)
        "complexity": str,   # RECOMMENDED: Time/space complexity
        "description": str,  # RECOMMENDED: Brief description
    },
}

SOLUTIONS = {
    "default": {
        "class": "SolutionBacktrackSets",
        "method": "solveNQueens",
        "complexity": "O(N!) time, O(N) space",
        "description": "Backtracking with hash sets for O(1) conflict detection",
    },
    "sets": {
        "class": "SolutionBacktrackSets",
        "method": "solveNQueens",
        "complexity": "O(N!) time, O(N) space",
        "description": "Backtracking with hash sets for O(1) conflict detection",
    },
    "bitmask": {
        "class": "SolutionBacktrackBitmask",
        "method": "solveNQueens",
        "complexity": "O(N!) time, O(N) space",
        "description": "Backtracking with bitmask for ultra-fast conflict detection",
    },
}

JUDGE_FUNC = judge  # Module-level assignment

def judge(actual, expected, input_data: str) -> bool:
    """
    Custom validation function.

    Args:
        actual: Program output (parsed if possible, else raw string)
        expected: Expected output (parsed if possible, else raw string, or None)
        input_data: Raw input string

    Returns:
        bool: True if answer is correct, False otherwise
    """

def judge(actual: list, expected, input_data: str) -> bool:
    """Validate N-Queens solution."""
    n = int(input_data.strip())

    # Known solution counts for N-Queens
    KNOWN_COUNTS = {1: 1, 2: 0, 3: 0, 4: 2, 5: 10, 6: 4, 7: 40, 8: 92, 9: 352}

    # 1. Verify each board is valid
    for board in actual:
        if not _is_valid_board(board, n):
            return False

    # 2. Check no duplicates
    unique = set(tuple(row for row in board) for board in actual)
    if len(unique) != len(actual):
        return False

    # 3. Check count
    if expected is not None:
        return len(actual) == len(expected)
    else:
        # Judge-only: use known counts
        expected_count = KNOWN_COUNTS.get(n)
        if expected_count is not None:
            return len(actual) == expected_count
        return True  # Accept if count unknown

JUDGE_FUNC = judge

# ============================================
# JUDGE_FUNC - Required for generator support
# ============================================
# Uses brute force O(m+n) merge to compute the correct answer,
# then compares with the solution output.
# ============================================
def judge(actual, expected, input_data: str) -> bool:   # ← No blank line
    ...

JUDGE_FUNC = judge

COMPARE_MODE = "sorted"  # Module-level assignment

# Example: N-Queens output
actual   = [[".Q..", "...Q"], ["..Q.", "Q..."]]
expected = [["..Q.", "Q..."], [".Q..", "...Q"]]
# After sorting: both become the same → PASS

SOLUTIONS = {
    "default": {
        "class": "Solution",           # REQUIRED
        "method": "twoSum",            # REQUIRED
        "complexity": "O(n)",          # RECOMMENDED
        "description": "Hash map",     # RECOMMENDED
    },
}

# Optional validation
JUDGE_FUNC = judge        # Custom validation
COMPARE_MODE = "sorted"   # Comparison mode

# solutions/{problem_id}_{slug}.py
"""
Problem: {Problem Title}
Link: https://leetcode.com/problems/{slug}/

{Brief problem description}

Constraints:
- {constraint 1}
- {constraint 2}
"""

**Note:** Link format must be `https://leetcode.com/problems/{slug}/` (without `/description/` suffix).

```python
from typing import List
from _runner import get_solver

# ============================================
# Optional: Custom validation
# ============================================
# JUDGE_FUNC = judge        # For "any order" or complex validation
# COMPARE_MODE = "sorted"   # For simple "any order" problems

# ============================================
# SOLUTIONS metadata (REQUIRED)
# ============================================
SOLUTIONS = {
    "default": {
        "class": "Solution",
        "method": "methodName",
        "complexity": "O(?)",
        "description": "Brief description",
    },
}

# ============================================
# Solution 1: {Approach Name}
# Time: O(?), Space: O(?)
#   - {Key insight or implementation detail}
#   - {Additional notes}
# ============================================
class Solution:   # ← No blank line after comment block
    def methodName(self, ...):
        ...

# ============================================
# Entry point
# ============================================
def solve():
    import sys
    lines = sys.stdin.read().strip().split('\n')
    # Parse input...

    solver = get_solver(SOLUTIONS)
    result = solver.methodName(...)

    print(result)

if __name__ == "__main__":
    solve()