"""
# 2013. Detect Squares

You are given a stream of points on the X-Y plane. Design an algorithm that:
- **Adds** new points from the stream into a data structure.
- **Counts** the number of ways to choose three points from the data structure such that the
  three points and a given query point form an **axis-aligned square** with **positive area**.

An axis-aligned square has all four sides parallel to the axes and all four sides equal in length.

Implement the `DetectSquares` class:
- `DetectSquares()` Initializes the object with an empty data structure.
- `void add(int[] point)` Adds a new point `point = [x, y]` to the data structure.
- `int count(int[] point)` Counts the number of ways to form axis-aligned squares with `point`.

## Examples

```text
Input:
["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3,10]], [[11,2]], [[3,2]], [[11,10]], [[14,8]], [[11,2]], [[11,10]]]
Output:
[null, null, null, null, 1, 0, null, 2]
```

## Constraints
- point.length == 2
- 0 <= point[x], point[y] <= 1000
- At most 3000 calls will be made to add and count.
"""

from collections import defaultdict
from typing import List


class DetectSquares:
    def __init__(self):
        self.pt_count = defaultdict(int)   # (x,y) -> count
        self.x_to_ys = defaultdict(set)    # x -> set of y values

    def add(self, point: List[int]) -> None:
        # Increment count of this point in the frequency map
        # O(1) time — update frequency map and x->y index
        x, y = point
        self.pt_count[(x, y)] += 1
        self.x_to_ys[x].add(y)

    def count(self, point: List[int]) -> int:
        # For each point sharing the same x as query, try it as diagonal corner
        # The other two corners are determined; check if they exist in the map
        # O(n) time — for each diagonal point, check if square can be completed
        qx, qy = point
        result = 0
        for y in self.x_to_ys[qx]:
            if y == qy:
                continue
            side = abs(y - qy)
            for dx in (qx + side, qx - side):
                result += self.pt_count[(qx, y)] * self.pt_count[(dx, qy)] * self.pt_count[(dx, y)]
        return result


if __name__ == '__main__':
    ds = DetectSquares()
    ds.add([3, 10]); ds.add([11, 2]); ds.add([3, 2])
    assert ds.count([11, 10]) == 1
    assert ds.count([14, 8]) == 0
    ds.add([11, 2])
    assert ds.count([11, 10]) == 2
    print("All tests passed.")

"""
# 168. Excel Sheet Column Title

Given an integer `columnNumber`, return its corresponding column title as it appears in an Excel sheet.

```text
A -> 1
B -> 2
...
Z -> 26
AA -> 27
AB -> 28
...
```

## Examples

```text
Input: columnNumber = 1
Output: "A"

Input: columnNumber = 28
Output: "AB"

Input: columnNumber = 701
Output: "ZY"
```

## Constraints
- 1 <= columnNumber <= 2^31 - 1
"""

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        # Base-26 conversion but 1-indexed (A=1, Z=26, AA=27)
        # Subtract 1 before modulo to handle the 1-indexed offset
        # O(log n) time, O(log n) space for result string
        result = []
        while columnNumber:
            columnNumber -= 1
            result.append(chr(columnNumber % 26 + ord('A')))
            columnNumber //= 26
        return ''.join(reversed(result))


if __name__ == '__main__':
    s = Solution()
    assert s.convertToTitle(1) == "A"
    assert s.convertToTitle(26) == "Z"
    assert s.convertToTitle(28) == "AB"
    assert s.convertToTitle(701) == "ZY"
    print("All tests passed.")

"""
# 1071. Greatest Common Divisor of Strings

For two strings `s` and `t`, we say "t divides s" if and only if `s = t + t + ... + t`
(i.e., `t` is concatenated with itself one or more times).

Given two strings `str1` and `str2`, return the largest string `x` such that `x` divides both `str1` and `str2`.

## Examples

```text
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Input: str1 = "LEET", str2 = "CODE"
Output: ""
```

## Constraints
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of English uppercase letters.
"""

from math import gcd


class Solution:
    def gcdOfStrings_brute(self, str1: str, str2: str) -> str:
        # O(n^2) time — check every prefix of the shorter string
        shorter, longer = (str1, str2) if len(str1) <= len(str2) else (str2, str1)
        for length in range(len(shorter), 0, -1):
            t = shorter[:length]
            if len(str1) % length == 0 and len(str2) % length == 0:
                if t * (len(str1) // length) == str1 and t * (len(str2) // length) == str2:
                    return t
        return ""

    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # If str1+str2 == str2+str1, a GCD string exists
        # Its length is gcd(len(str1), len(str2))
        # O(n) time — GCD of lengths gives candidate; verify with concatenation check
        if str1 + str2 != str2 + str1:
            return ""
        return str1[:gcd(len(str1), len(str2))]


if __name__ == '__main__':
    s = Solution()
    for method in (s.gcdOfStrings_brute, s.gcdOfStrings):
        assert method("ABCABC", "ABC") == "ABC"
        assert method("ABABAB", "ABAB") == "AB"
        assert method("LEET", "CODE") == ""
    print("All tests passed.")

"""
# 202. Happy Number

Write an algorithm to determine if a number `n` is happy.

A **happy number** is a number defined by the following process:
- Starting with any positive integer, replace the number by the sum of the squares of its digits.
- Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1.
- Numbers for which this process ends in 1 are happy.

Return `true` if `n` is a happy number, and `false` if not.

## Examples

```text
Input: n = 19
Output: true
Explanation: 1^2 + 9^2 = 82 -> 8^2 + 2^2 = 68 -> ... -> 1

Input: n = 2
Output: false
```

## Constraints
- 1 <= n <= 2^31 - 1
"""


def _sum_of_squares(n: int) -> int:
    total = 0
    while n:
        n, d = divmod(n, 10)
        total += d * d
    return total


class Solution:
    def isHappy_set(self, n: int) -> bool:
        # O(log n) time per step, O(log n) space — hash set to detect cycle
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = _sum_of_squares(n)
        return n == 1

    def isHappy(self, n: int) -> bool:
        # Repeatedly sum squares of digits; cycle detection via set or Floyd's
        # If we reach 1, it's happy; if we revisit a number, it's not
        # O(log n) time per step, O(1) space — Floyd's slow/fast cycle detection
        slow, fast = n, _sum_of_squares(n)
        while fast != 1 and slow != fast:
            slow = _sum_of_squares(slow)
            fast = _sum_of_squares(_sum_of_squares(fast))
        return fast == 1


if __name__ == '__main__':
    s = Solution()
    for method in (s.isHappy_set, s.isHappy):
        assert method(19) is True
        assert method(2) is False
        assert method(1) is True
    print("All tests passed.")

"""
# 2807. Insert Greatest Common Divisors in Linked List

Given the head of a linked list, for every pair of adjacent nodes, insert a new node
with value equal to the greatest common divisor of those two nodes' values.

Return the linked list after insertion.

## Examples

```text
Input: head = [18, 6, 10, 3]
Output: [18, 6, 6, 2, 10, 1, 3]

Input: head = [7]
Output: [7]
```

## Constraints
- The number of nodes in the list is in the range [1, 5000].
- 1 <= Node.val <= 1000
"""

from __future__ import annotations
from math import gcd
from typing import Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional[ListNode] = None):
        self.val = val
        self.next = next


class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Between each pair of adjacent nodes, insert a node with gcd(a, b)
        # O(n) time, O(1) space — single pass inserting GCD nodes between each pair
        cur = head
        while cur and cur.next:
            g = gcd(cur.val, cur.next.val)
            cur.next = ListNode(g, cur.next)
            cur = cur.next.next
        return head


def to_list(head: Optional[ListNode]) -> list:
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

def from_list(vals: list) -> Optional[ListNode]:
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next


if __name__ == '__main__':
    s = Solution()
    assert to_list(s.insertGreatestCommonDivisors(from_list([18, 6, 10, 3]))) == [18, 6, 6, 2, 10, 1, 3]
    assert to_list(s.insertGreatestCommonDivisors(from_list([7]))) == [7]
    print("All tests passed.")

"""
# 43. Multiply Strings

Given two non-negative integers `num1` and `num2` represented as strings, return the product
of `num1` and `num2`, also represented as a string.

**Note:** You must not use any built-in BigInteger library or convert the inputs to integer directly.

## Examples

```text
Input: num1 = "2", num2 = "3"
Output: "6"

Input: num1 = "123", num2 = "456"
Output: "56088"
```

## Constraints
- 1 <= num1.length, num2.length <= 200
- num1 and num2 consist of digits only.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
"""


class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        # Simulate grade-school multiplication digit by digit
        # Result digit at position i+j comes from nums1[i] * nums2[j]
        # Propagate carries after all multiplications
        # O(m*n) time — grade-school digit-by-digit multiplication with position tracking
        if num1 == "0" or num2 == "0":
            return "0"
        m, n = len(num1), len(num2)
        pos = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = (ord(num1[i]) - 48) * (ord(num2[j]) - 48)
                p1, p2 = i + j, i + j + 1
                total = mul + pos[p2]
                pos[p2] = total % 10
                pos[p1] += total // 10
        result = ''.join(str(d) for d in pos).lstrip('0')
        return result or "0"


if __name__ == '__main__':
    s = Solution()
    assert s.multiply("2", "3") == "6"
    assert s.multiply("123", "456") == "56088"
    assert s.multiply("0", "456") == "0"
    assert s.multiply("99", "99") == "9801"
    print("All tests passed.")

"""
# 66. Plus One

You are given a **large integer** represented as an integer array `digits`, where each `digits[i]`
is the i-th digit of the integer. The digits are ordered from most significant to least significant.

Increment the large integer by one and return the resulting array of digits.

## Examples

```text
Input: digits = [1,2,3]
Output: [1,2,4]

Input: digits = [4,3,2,1]
Output: [4,3,2,2]

Input: digits = [9]
Output: [1,0]
```

## Constraints
- 1 <= digits.length <= 100
- 0 <= digits[i] <= 9
- digits does not contain any leading 0's.
"""

from typing import List


class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # Add 1 from the last digit; propagate carry leftward
        # If carry remains after all digits, prepend 1
        # O(n) time, O(1) extra space — iterate from end propagating carry
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0
        return [1] + digits


if __name__ == '__main__':
    s = Solution()
    assert s.plusOne([1,2,3]) == [1,2,4]
    assert s.plusOne([9]) == [1,0]
    assert s.plusOne([9,9]) == [1,0,0]
    assert s.plusOne([4,3,2,1]) == [4,3,2,2]
    print("All tests passed.")

"""
# 50. Pow(x, n)

Implement `pow(x, n)`, which calculates `x` raised to the power `n` (i.e., x^n).

## Examples

```text
Input: x = 2.00000, n = 10
Output: 1024.00000

Input: x = 2.10000, n = 3
Output: 9.26100

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/4 = 0.25
```

## Constraints
- -100.0 < x < 100.0
- -2^31 <= n <= 2^31 - 1
- n is an integer.
- Either x is not zero or n > 0.
- -10^4 <= x^n <= 10^4
"""


class Solution:
    def myPow_brute(self, x: float, n: int) -> float:
        # O(n) time — multiply x by itself n times (TLE for large n)
        if n < 0:
            x, n = 1 / x, -n
        result = 1.0
        for _ in range(n):
            result *= x
        return result

    def myPow(self, x: float, n: int) -> float:
        # Fast exponentiation: x^n = (x^(n//2))^2; halve n each step — O(log n)
        # Handle negative n by inverting x and using abs(n)
        # O(log n) time — fast exponentiation by squaring
        if n < 0:
            x, n = 1 / x, -n
        result = 1.0
        while n:
            if n % 2 == 1:
                result *= x
            x *= x
            n //= 2
        return result


if __name__ == '__main__':
    s = Solution()
    for method in (s.myPow_brute, s.myPow):
        assert abs(method(2.0, 10) - 1024.0) < 1e-5
        assert abs(method(2.0, -2) - 0.25) < 1e-5
        assert abs(method(2.0, 0) - 1.0) < 1e-5
    print("All tests passed.")

"""
# 13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

```text
Symbol  Value
I       1
V       5
X       10
L       50
C       100
D       500
M       1000
```

Roman numerals are usually written largest to smallest from left to right. However, when a smaller
value precedes a larger value, it is subtracted (e.g., IV = 4, IX = 9).

Given a roman numeral, convert it to an integer.

## Examples

```text
Input: s = "III"
Output: 3

Input: s = "LVIII"
Output: 58

Input: s = "MCMXCIV"
Output: 1994
```

## Constraints
- 1 <= s.length <= 15
- s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
- It is guaranteed that s is a valid roman numeral in the range [1, 3999].
"""


class Solution:
    def romanToInt(self, s: str) -> int:
        # If current symbol < next symbol, subtract it (e.g. IV = 5-1)
        # Otherwise add it; process left to right
        # O(n) time — left-to-right scan, subtract when smaller value precedes larger
        val = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        result = 0
        for i in range(len(s)):
            if i + 1 < len(s) and val[s[i]] < val[s[i+1]]:
                result -= val[s[i]]
            else:
                result += val[s[i]]
        return result


if __name__ == '__main__':
    s = Solution()
    assert s.romanToInt("III") == 3
    assert s.romanToInt("LVIII") == 58
    assert s.romanToInt("MCMXCIV") == 1994
    assert s.romanToInt("IV") == 4
    print("All tests passed.")

"""
# 48. Rotate Image

You are given an `n x n` 2D matrix representing an image. Rotate the image by 90 degrees clockwise **in-place**.

You must modify the input matrix directly. Do not allocate another 2D matrix.

## Examples

```text
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
```

## Constraints
- n == matrix.length == matrix[i].length
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
"""

from typing import List


class Solution:
    def rotate_transpose(self, matrix: List[List[int]]) -> None:
        # O(n^2) time, O(1) space — transpose then reverse each row
        n = len(matrix)
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for row in matrix:
            row.reverse()

    def rotate(self, matrix: List[List[int]]) -> None:
        # Transpose the matrix (swap matrix[i][j] with matrix[j][i])
        # Then reverse each row to achieve 90-degree clockwise rotation
        # O(n^2) time, O(1) space — four-way cyclic swap layer by layer
        n = len(matrix)
        for i in range(n // 2):
            for j in range(i, n - 1 - i):
                tmp = matrix[i][j]
                matrix[i][j] = matrix[n-1-j][i]
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
                matrix[j][n-1-i] = tmp


if __name__ == '__main__':
    import copy
    s = Solution()
    for method in (s.rotate_transpose, s.rotate):
        m = [[1,2,3],[4,5,6],[7,8,9]]
        method(m)
        assert m == [[7,4,1],[8,5,2],[9,6,3]], f"Failed: {m}"
    print("All tests passed.")

"""
# 73. Set Matrix Zeroes

Given an `m x n` integer matrix, if an element is `0`, set its entire row and column to `0`s.

You must do it **in place**.

## Examples

```text
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
```

## Constraints
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
"""

from typing import List


class Solution:
    def setZeroes_extra_space(self, matrix: List[List[int]]) -> None:
        # O(m*n) time, O(m+n) space — record zero rows/cols then zero them out
        rows, cols = set(), set()
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if matrix[r][c] == 0:
                    rows.add(r); cols.add(c)
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if r in rows or c in cols:
                    matrix[r][c] = 0

    def setZeroes(self, matrix: List[List[int]]) -> None:
        # Use first row and first column as markers to avoid O(m+n) extra space
        # First pass: mark rows/cols that need zeroing using first row/col
        # Second pass: zero cells based on markers; then zero first row/col if needed
        # O(m*n) time, O(1) space — use first row/col as markers
        m, n = len(matrix), len(matrix[0])
        first_row_zero = any(matrix[0][c] == 0 for c in range(n))
        first_col_zero = any(matrix[r][0] == 0 for r in range(m))
        for r in range(1, m):
            for c in range(1, n):
                if matrix[r][c] == 0:
                    matrix[r][0] = matrix[0][c] = 0
        for r in range(1, m):
            for c in range(1, n):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0
        if first_row_zero:
            for c in range(n): matrix[0][c] = 0
        if first_col_zero:
            for r in range(m): matrix[r][0] = 0


if __name__ == '__main__':
    import copy
    s = Solution()
    for method in (s.setZeroes_extra_space, s.setZeroes):
        m = [[1,1,1],[1,0,1],[1,1,1]]
        method(m)
        assert m == [[1,0,1],[0,0,0],[1,0,1]], f"Failed: {m}"
    print("All tests passed.")

"""
# 54. Spiral Matrix

Given an `m x n` matrix, return all elements of the matrix in spiral order.

## Examples

```text
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
```

## Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 10
- -100 <= matrix[i][j] <= 100
"""

from typing import List


class Solution:
    def spiralOrder_layers(self, matrix: List[List[int]]) -> List[int]:
        # O(m*n) time — peel off outer layer iteratively
        result = []
        top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
        while top <= bottom and left <= right:
            result += matrix[top][left:right+1]
            for r in range(top + 1, bottom + 1):
                result.append(matrix[r][right])
            if top < bottom:
                result += matrix[bottom][left:right][::-1]
            if left < right:
                for r in range(bottom - 1, top, -1):
                    result.append(matrix[r][left])
            top += 1; bottom -= 1; left += 1; right -= 1
        return result

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # Shrink boundaries (top, bottom, left, right) after traversing each side
        # Traverse: left-to-right, top-to-bottom, right-to-left, bottom-to-top
        # O(m*n) time — direction simulation with visited marking
        m, n = len(matrix), len(matrix[0])
        dirs = [(0,1),(1,0),(0,-1),(-1,0)]
        d = r = c = 0
        result = []
        for _ in range(m * n):
            result.append(matrix[r][c])
            matrix[r][c] = None
            nr, nc = r + dirs[d][0], c + dirs[d][1]
            if not (0 <= nr < m and 0 <= nc < n and matrix[nr][nc] is not None):
                d = (d + 1) % 4
                nr, nc = r + dirs[d][0], c + dirs[d][1]
            r, c = nr, nc
        return result


if __name__ == '__main__':
    s = Solution()
    assert s.spiralOrder_layers([[1,2,3],[4,5,6],[7,8,9]]) == [1,2,3,6,9,8,7,4,5]
    assert s.spiralOrder([[1,2,3],[4,5,6],[7,8,9]]) == [1,2,3,6,9,8,7,4,5]
    assert s.spiralOrder_layers([[1,2,3,4],[5,6,7,8],[9,10,11,12]]) == [1,2,3,4,8,12,11,10,9,5,6,7]
    print("All tests passed.")

"""
# 867. Transpose Matrix

Given a 2D integer array `matrix`, return the transpose of `matrix`.

The transpose of a matrix is the matrix flipped over its main diagonal,
switching the matrix's row and column indices.

## Examples

```text
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

Input: matrix = [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]
```

## Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 1000
- 1 <= m * n <= 10^5
- -10^9 <= matrix[i][j] <= 10^9
"""

from typing import List


class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        # Swap rows and columns: result[j][i] = matrix[i][j]
        # O(m*n) time, O(m*n) space — build transposed matrix directly
        m, n = len(matrix), len(matrix[0])
        return [[matrix[r][c] for r in range(m)] for c in range(n)]


if __name__ == '__main__':
    s = Solution()
    assert s.transpose([[1,2,3],[4,5,6],[7,8,9]]) == [[1,4,7],[2,5,8],[3,6,9]]
    assert s.transpose([[1,2,3],[4,5,6]]) == [[1,4],[2,5],[3,6]]
    print("All tests passed.")