"""
LC 704 - Binary Search
======================

Given an array of integers `nums` which is sorted in ascending order, and an
integer `target`, write a function to search `target` in `nums`. If `target`
exists, return its index. Otherwise, return -1.

Examples
--------
```text
Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
```

Constraints
-----------
- 1 <= nums.length <= 10^4
- -10^4 < nums[i], target < 10^4
- All integers in nums are unique
- nums is sorted in ascending order
"""

from typing import List


class Solution:
    def method_brute_force(self, nums: List[int], target: int) -> int:
        # O(n) time | O(1) space
        for i, v in enumerate(nums):
            if v == target:
                return i
        return -1

    def search(self, nums: List[int], target: int) -> int:
        # Standard binary search: compare mid to target, halve search space
        # O(log n) time | O(1) space
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1


if __name__ == "__main__":
    s = Solution()
    assert s.search([-1, 0, 3, 5, 9, 12], 9) == 4
    assert s.search([-1, 0, 3, 5, 9, 12], 2) == -1
    assert s.method_brute_force([-1, 0, 3, 5, 9, 12], 9) == 4
    assert s.method_brute_force([-1, 0, 3, 5, 9, 12], 2) == -1
    print("All tests passed.")

"""
LC 1011 - Capacity To Ship Packages Within D Days
===================================================

A conveyor belt has packages that must be shipped from one port to another
within `days` days. The i-th package on the conveyor belt has a weight of
`weights[i]`. Each day, we load the ship with packages in the order given by
`weights`. We may not load more weight than the maximum weight capacity of the
ship.

Return the least weight capacity of the ship that will result in all the
packages on the conveyor belt being shipped within `days` days.

Examples
--------
```text
Input:  weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

Input:  weights = [3,2,2,4,1,4], days = 3
Output: 6

Input:  weights = [1,2,3,1,1], days = 4
Output: 3
```

Constraints
-----------
- 1 <= days <= weights.length <= 5 * 10^4
- 1 <= weights[i] <= 500
"""

from typing import List


class Solution:
    def _days_needed(self, weights: List[int], cap: int) -> int:
        # Simulate loading: start new day when adding next package exceeds capacity
        days, load = 1, 0
        for w in weights:
            if load + w > cap:
                days += 1
                load = 0
            load += w
        return days

    def method_linear(self, weights: List[int], days: int) -> int:
        # Try every capacity from max(weights) upward — O(sum*n)
        # O(sum(weights) * n) time | O(1) space
        cap = max(weights)
        while self._days_needed(weights, cap) > days:
            cap += 1
        return cap

    def shipWithinDays(self, weights: List[int], days: int) -> int:
        # Binary search on capacity: lo=max(weights) (must fit heaviest), hi=sum(weights)
        # If days_needed(mid) <= days, mid is feasible — try smaller capacity
        # O(n * log(sum(weights))) time | O(1) space
        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = (lo + hi) // 2
            if self._days_needed(weights, mid) <= days:
                hi = mid
            else:
                lo = mid + 1
        return lo


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

"""
LC 1095 - Find in Mountain Array
==================================

You may recall that an array `arr` is a mountain array if and only if:
  - arr.length >= 3
  - There exists some index i (0-indexed) with 0 < i < arr.length - 1 such
    that arr[0] < arr[1] < ... < arr[i] > arr[i+1] > ... > arr[arr.length-1]

Given a mountain array `mountainArr`, return the minimum index such that
mountainArr.get(index) == target. If such an index does not exist, return -1.

You cannot access the mountain array directly. You may only access the array
using a MountainArray interface:
  - MountainArray.get(k) returns the element of the array at index k (0-indexed)
  - MountainArray.length() returns the length of the array

Submissions making more than 100 calls to MountainArray.get will be judged
Wrong Answer.

Examples
--------
```text
Input:  array = [1, 2, 3, 4, 5, 3, 1], target = 3
Output: 2

Input:  array = [0, 1, 2, 4, 2, 1], target = 3
Output: -1
```

Constraints
-----------
- 3 <= mountain_arr.length() <= 10^4
- 0 <= target <= 10^9
- 0 <= mountain_arr.get(index) <= 10^9
"""


class MountainArray:
    """Mock interface for testing."""

    def __init__(self, arr: list):
        self._arr = arr
        self._calls = 0

    def get(self, index: int) -> int:
        self._calls += 1
        assert self._calls <= 100, "Exceeded 100 API calls"
        return self._arr[index]

    def length(self) -> int:
        return len(self._arr)


class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        # Step 1: find peak — binary search where arr[mid] < arr[mid+1] means peak is right
        # Step 2: binary search ascending left half [0..peak]
        # Step 3: binary search descending right half [peak+1..n-1] (reversed comparisons)
        # O(log n) time | O(1) space
        n = mountain_arr.length()

        # 1. Find peak index
        lo, hi = 0, n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                lo = mid + 1
            else:
                hi = mid
        peak = lo

        # 2. Binary search ascending left half
        lo, hi = 0, peak
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1

        # 3. Binary search descending right half
        lo, hi = peak + 1, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val > target:
                lo = mid + 1
            else:
                hi = mid - 1

        return -1


if __name__ == "__main__":
    s = Solution()
    assert s.findInMountainArray(3, MountainArray([1, 2, 3, 4, 5, 3, 1])) == 2
    assert s.findInMountainArray(3, MountainArray([0, 1, 2, 4, 2, 1])) == -1
    assert s.findInMountainArray(1, MountainArray([1, 2, 3, 4, 5, 3, 1])) == 0
    assert s.findInMountainArray(5, MountainArray([1, 2, 3, 4, 5, 3, 1])) == 4
    print("All tests passed.")

"""
LC 153 - Find Minimum in Rotated Sorted Array
===============================================

Suppose an array of length `n` sorted in ascending order is rotated between 1
and n times. For example, the array nums = [0,1,2,4,5,6,7] might become
[4,5,6,7,0,1,2] if it was rotated 4 times.

Given the sorted rotated array `nums` of unique elements, return the minimum
element of this array.

You must write an algorithm that runs in O(log n) time.

Examples
--------
```text
Input:  nums = [3, 4, 5, 1, 2]
Output: 1

Input:  nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0

Input:  nums = [11, 13, 15, 17]
Output: 11
```

Constraints
-----------
- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All the integers of nums are unique
- nums is sorted and rotated between 1 and n times
"""

from typing import List


class Solution:
    def method_linear(self, nums: List[int]) -> int:
        # O(n) time | O(1) space
        return min(nums)

    def findMin(self, nums: List[int]) -> int:
        # If mid > hi, the minimum is in the right half (rotation point is there)
        # Otherwise minimum is in the left half including mid
        # O(log n) time | O(1) space
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1
            else:
                hi = mid
        return nums[lo]


if __name__ == "__main__":
    s = Solution()
    assert s.findMin([3, 4, 5, 1, 2]) == 1
    assert s.findMin([4, 5, 6, 7, 0, 1, 2]) == 0
    assert s.findMin([11, 13, 15, 17]) == 11
    assert s.method_linear([3, 4, 5, 1, 2]) == 1
    print("All tests passed.")

"""
LC 374 - Guess Number Higher or Lower
======================================

We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is
higher or lower than your guess.

You call a pre-defined API `guess(num: int) -> int` which returns three
possible results:
  -1 : Your guess is higher than the number I picked (i.e. num > pick)
   1 : Your guess is lower than the number I picked (i.e. num < pick)
   0 : Your guess is equal to the number I picked (i.e. num == pick)

Return the number that I picked.

Examples
--------
```text
Input:  n = 10, pick = 6
Output: 6

Input:  n = 1, pick = 1
Output: 1
```

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

_PICK = 0  # set before each test


def guess(num: int) -> int:
    if num > _PICK:
        return -1
    elif num < _PICK:
        return 1
    return 0


class Solution:
    def method_linear(self, n: int) -> int:
        # O(n) time | O(1) space
        for i in range(1, n + 1):
            if guess(i) == 0:
                return i
        return -1

    def guessNumber(self, n: int) -> int:
        # Binary search using the guess() API: -1 means too high, 1 means too low
        # O(log n) time | O(1) space
        lo, hi = 1, n
        while lo <= hi:
            mid = (lo + hi) // 2
            res = guess(mid)
            if res == 0:
                return mid
            elif res == 1:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1


if __name__ == "__main__":
    import sys
    s = Solution()

    for n, pick in [(10, 6), (1, 1), (2, 2)]:
        globals()["_PICK"] = pick
        assert s.guessNumber(n) == pick, f"guessNumber({n}) failed"
        globals()["_PICK"] = pick
        assert s.method_linear(n) == pick, f"method_linear({n}) failed"

    print("All tests passed.")

"""
LC 875 - Koko Eating Bananas
=============================

Koko loves to eat bananas. There are `n` piles of bananas, the i-th pile has
`piles[i]` bananas. The guards have gone and will come back in `h` hours.

Koko can decide her bananas-per-hour eating speed of `k`. Each hour, she
chooses some pile of bananas and eats `k` bananas from that pile. If the pile
has less than `k` bananas, she eats all of them instead and will not eat any
more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas
before the guards return. Return the minimum integer `k` such that she can eat
all the bananas within `h` hours.

Examples
--------
```text
Input:  piles = [3, 6, 7, 11], h = 8
Output: 4

Input:  piles = [30, 11, 23, 4, 20], h = 5
Output: 30

Input:  piles = [30, 11, 23, 4, 20], h = 6
Output: 23
```

Constraints
-----------
- 1 <= piles.length <= 10^4
- piles.length <= h <= 10^9
- 1 <= piles[i] <= 10^9
"""

import math
from typing import List


class Solution:
    def _hours_needed(self, piles: List[int], k: int) -> int:
        # Compute total hours needed at speed k: ceil(pile/k) per pile
        return sum(math.ceil(p / k) for p in piles)

    def method_linear(self, piles: List[int], h: int) -> int:
        # Try every speed from 1 upward — O(max(piles)*n)
        # O(max(piles) * n) time | O(1) space
        k = 1
        while self._hours_needed(piles, k) > h:
            k += 1
        return k

    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Binary search on speed: lo=1, hi=max(piles)
        # If hours_needed(mid) <= h, mid might be the answer — search left half
        # O(n * log(max(piles))) time | O(1) space
        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            if self._hours_needed(piles, mid) <= h:
                hi = mid
            else:
                lo = mid + 1
        return lo


if __name__ == "__main__":
    s = Solution()
    assert s.minEatingSpeed([3, 6, 7, 11], 8) == 4
    assert s.minEatingSpeed([30, 11, 23, 4, 20], 5) == 30
    assert s.minEatingSpeed([30, 11, 23, 4, 20], 6) == 23
    assert s.method_linear([3, 6, 7, 11], 8) == 4
    print("All tests passed.")

"""
LC 4 - Median of Two Sorted Arrays
=====================================

Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively,
return the median of the two sorted arrays.

The overall run time complexity should be O(log(m + n)).

Examples
--------
```text
Input:  nums1 = [1, 3], nums2 = [2]
Output: 2.0
Explanation: merged = [1, 2, 3], median = 2.0

Input:  nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Explanation: merged = [1, 2, 3, 4], median = (2 + 3) / 2 = 2.5
```

Constraints
-----------
- nums1.length == m
- nums2.length == n
- 0 <= m, n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6
"""

from typing import List


class Solution:
    def method_merge(self, nums1: List[int], nums2: List[int]) -> float:
        # Merge both arrays, sort, then find median by index — O(m+n)
        # O(m + n) time | O(m + n) space
        merged = sorted(nums1 + nums2)
        total = len(merged)
        mid = total // 2
        if total % 2 == 1:
            return float(merged[mid])
        return (merged[mid - 1] + merged[mid]) / 2.0

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # Binary search on partition of smaller array; derive partition of larger
        # Valid partition: left1<=right2 and left2<=right1 (cross-check boundaries)
        # Odd total: median is min of right halves; even: average of inner boundary
        # O(log(min(m, n))) time | O(1) space
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        half = (m + n) // 2

        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2  # partition in nums1
            j = half - i        # partition in nums2

            left1  = nums1[i - 1] if i > 0 else float('-inf')
            right1 = nums1[i]     if i < m else float('inf')
            left2  = nums2[j - 1] if j > 0 else float('-inf')
            right2 = nums2[j]     if j < n else float('inf')

            if left1 <= right2 and left2 <= right1:
                if (m + n) % 2 == 1:
                    return float(min(right1, right2))
                return (max(left1, left2) + min(right1, right2)) / 2.0
            elif left1 > right2:
                hi = i - 1
            else:
                lo = i + 1
        return 0.0


if __name__ == "__main__":
    s = Solution()
    assert s.findMedianSortedArrays([1, 3], [2]) == 2.0
    assert s.findMedianSortedArrays([1, 2], [3, 4]) == 2.5
    assert s.findMedianSortedArrays([], [1]) == 1.0
    assert s.method_merge([1, 3], [2]) == 2.0
    assert s.method_merge([1, 2], [3, 4]) == 2.5
    print("All tests passed.")

"""
LC 74 - Search a 2D Matrix
===========================

You are given an m x n integer matrix `matrix` with the following two
properties:
  - Each row is sorted in non-decreasing order.
  - The first integer of each row is greater than the last integer of the
    previous row.

Given an integer `target`, return true if `target` is in `matrix`, or false
otherwise.

Examples
--------
```text
Input:  matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Input:  matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
```

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

from typing import List


class Solution:
    def method_brute_force(self, matrix: List[List[int]], target: int) -> bool:
        # O(m*n) time | O(1) space
        for row in matrix:
            for val in row:
                if val == target:
                    return True
        return False

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Treat the 2D matrix as a 1D sorted array using index math
        # mid // n gives row, mid % n gives column
        # O(log(m*n)) time | O(1) space
        m, n = len(matrix), len(matrix[0])
        lo, hi = 0, m * n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = matrix[mid // n][mid % n]
            if val == target:
                return True
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return False


if __name__ == "__main__":
    s = Solution()
    mat = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
    assert s.searchMatrix(mat, 3) is True
    assert s.searchMatrix(mat, 13) is False
    assert s.method_brute_force(mat, 3) is True
    assert s.method_brute_force(mat, 13) is False
    print("All tests passed.")

"""
LC 33 - Search in Rotated Sorted Array
========================================

There is an integer array `nums` sorted in ascending order (with distinct
values). Prior to being passed to your function, `nums` is possibly rotated at
an unknown pivot index k such that the resulting array is
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].

Given the array `nums` after the possible rotation and an integer `target`,
return the index of `target` if it is in `nums`, or -1 if it is not in `nums`.

You must write an algorithm with O(log n) runtime complexity.

Examples
--------
```text
Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

Input:  nums = [1], target = 0
Output: -1
```

Constraints
-----------
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- All values of nums are unique
- nums is an ascending array that is possibly rotated
- -10^4 <= target <= 10^4
"""

from typing import List


class Solution:
    def method_linear(self, nums: List[int], target: int) -> int:
        # O(n) time | O(1) space
        for i, v in enumerate(nums):
            if v == target:
                return i
        return -1

    def search(self, nums: List[int], target: int) -> int:
        # Determine which half is sorted by comparing nums[lo] to nums[mid]
        # Check if target falls in the sorted half; if yes search there, else other half
        # O(log n) time | O(1) space
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[lo] <= nums[mid]:  # left half sorted
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:  # right half sorted
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1


if __name__ == "__main__":
    s = Solution()
    assert s.search([4, 5, 6, 7, 0, 1, 2], 0) == 4
    assert s.search([4, 5, 6, 7, 0, 1, 2], 3) == -1
    assert s.search([1], 0) == -1
    assert s.method_linear([4, 5, 6, 7, 0, 1, 2], 0) == 4
    print("All tests passed.")

"""
LC 81 - Search in Rotated Sorted Array II
==========================================

There is an integer array `nums` sorted in non-decreasing order (not
necessarily with distinct values). Before being passed to your function, `nums`
is rotated at an unknown pivot index k.

Given the array `nums` after the possible rotation and an integer `target`,
return true if `target` is in `nums`, or false if it is not in `nums`.

You must decrease the overall operation steps as much as possible.

Examples
--------
```text
Input:  nums = [2, 5, 6, 0, 0, 1, 2], target = 0
Output: true

Input:  nums = [2, 5, 6, 0, 0, 1, 2], target = 3
Output: false
```

Constraints
-----------
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- nums is sorted and rotated at some pivot
- -10^4 <= target <= 10^4
"""

from typing import List


class Solution:
    def method_linear(self, nums: List[int], target: int) -> bool:
        # O(n) time | O(1) space
        return target in nums

    def search(self, nums: List[int], target: int) -> bool:
        # Same as rotated search but duplicates can obscure which half is sorted
        # When nums[lo]==nums[mid]==nums[hi], shrink both ends by 1 to break tie
        # O(log n) average, O(n) worst time | O(1) space
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return True
            # can't determine sorted half — shrink bounds
            if nums[lo] == nums[mid] == nums[hi]:
                lo += 1
                hi -= 1
            elif nums[lo] <= nums[mid]:  # left half sorted
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:  # right half sorted
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return False


if __name__ == "__main__":
    s = Solution()
    assert s.search([2, 5, 6, 0, 0, 1, 2], 0) is True
    assert s.search([2, 5, 6, 0, 0, 1, 2], 3) is False
    assert s.search([1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 13) is True
    assert s.method_linear([2, 5, 6, 0, 0, 1, 2], 0) is True
    print("All tests passed.")

"""
LC 35 - Search Insert Position
================================

Given a sorted array of distinct integers and a target value, return the index
if the target is found. If not, return the index where it would be inserted in
order.

You must write an algorithm with O(log n) runtime complexity.

Examples
--------
```text
Input:  nums = [1, 3, 5, 6], target = 5
Output: 2

Input:  nums = [1, 3, 5, 6], target = 2
Output: 1

Input:  nums = [1, 3, 5, 6], target = 7
Output: 4
```

Constraints
-----------
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums contains distinct values sorted in ascending order
- -10^4 <= target <= 10^4
"""

from typing import List


class Solution:
    def method_linear(self, nums: List[int], target: int) -> int:
        # O(n) time | O(1) space
        for i, v in enumerate(nums):
            if v >= target:
                return i
        return len(nums)

    def searchInsert(self, nums: List[int], target: int) -> int:
        # Binary search; lo converges to the insertion point when target not found
        # O(log n) time | O(1) space
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return lo


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

"""
LC 410 - Split Array Largest Sum
==================================

Given an integer array `nums` and an integer `k`, split `nums` into `k`
non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

Examples
--------
```text
Input:  nums = [7, 2, 5, 10, 8], k = 2
Output: 18
Explanation: Split into [7,2,5] and [10,8]. Largest sum = max(14,18) = 18.

Input:  nums = [1, 2, 3, 4, 5], k = 2
Output: 9
```

Constraints
-----------
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 10^6
- 1 <= k <= min(50, nums.length)
"""

from typing import List


class Solution:
    def method_dp(self, nums: List[int], k: int) -> int:
        # O(n^2 * k) time | O(n * k) space
        n = len(nums)
        prefix = [0] * (n + 1)
        for i, v in enumerate(nums):
            prefix[i + 1] = prefix[i] + v

        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                for m in range(i):
                    dp[i][j] = min(dp[i][j], max(dp[m][j - 1], prefix[i] - prefix[m]))
        return dp[n][k]

    def splitArray(self, nums: List[int], k: int) -> int:
        # Binary search on the answer (max subarray sum): lo=max(nums), hi=sum(nums)
        # Check if we can split into <= m subarrays with max sum <= mid
        # O(n * log(sum(nums))) time | O(1) space
        def can_split(cap: int) -> bool:
            parts, curr = 1, 0
            for v in nums:
                if curr + v > cap:
                    parts += 1
                    curr = 0
                curr += v
            return parts <= k

        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if can_split(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo


if __name__ == "__main__":
    s = Solution()
    assert s.splitArray([7, 2, 5, 10, 8], 2) == 18
    assert s.splitArray([1, 2, 3, 4, 5], 2) == 9
    assert s.method_dp([7, 2, 5, 10, 8], 2) == 18
    assert s.method_dp([1, 2, 3, 4, 5], 2) == 9
    print("All tests passed.")

"""
LC 69 - Sqrt(x)
================

Given a non-negative integer `x`, return the square root of `x` rounded down
to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator (e.g., pow(x, 0.5)
or x ** 0.5).

Examples
--------
```text
Input:  x = 4
Output: 2

Input:  x = 8
Output: 2
Explanation: The square root of 8 is 2.828..., rounded down to 2.
```

Constraints
-----------
- 0 <= x <= 2^31 - 1
"""


class Solution:
    def method_linear(self, x: int) -> int:
        # O(sqrt(x)) time | O(1) space
        i = 0
        while (i + 1) * (i + 1) <= x:
            i += 1
        return i

    def mySqrt(self, x: int) -> int:
        # Binary search: find largest integer whose square <= x
        # When mid*mid <= x, record mid as candidate and search right for larger
        # O(log x) time | O(1) space
        if x < 2:
            return x
        lo, hi = 1, x // 2
        while lo <= hi:
            mid = (lo + hi) // 2
            sq = mid * mid
            if sq == x:
                return mid
            elif sq < x:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi


if __name__ == "__main__":
    s = Solution()
    for x, expected in [(0, 0), (1, 1), (4, 2), (8, 2), (9, 3), (2147395600, 46340)]:
        assert s.mySqrt(x) == expected, f"mySqrt({x}) = {s.mySqrt(x)}, expected {expected}"
        assert s.method_linear(x) == expected, f"method_linear({x}) failed"
    print("All tests passed.")

"""
LC 981 - Time Based Key-Value Store
=====================================

Design a time-based key-value data structure that can store multiple values
for the same key at different time stamps and retrieve the key's value at a
certain timestamp.

Implement the TimeMap class:
  - TimeMap() Initializes the object of the data structure.
  - void set(String key, String value, int timestamp) Stores the key with the
    value at the given time timestamp.
  - String get(String key, int timestamp) Returns a value such that set was
    called previously with timestamp_prev <= timestamp. If there are multiple
    such values, it returns the value associated with the largest
    timestamp_prev. If there are no values, it returns "".

Examples
--------
```text
Input:
  ["TimeMap","set","get","get","set","get","get"]
  [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output:
  [null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation:
  set("foo","bar",1)  -> stores foo=bar at t=1
  get("foo",1)        -> "bar"
  get("foo",3)        -> "bar"  (largest ts <= 3 is 1)
  set("foo","bar2",4) -> stores foo=bar2 at t=4
  get("foo",4)        -> "bar2"
  get("foo",5)        -> "bar2" (largest ts <= 5 is 4)
```

Constraints
-----------
- 1 <= key.length, value.length <= 100
- key and value consist of lowercase English letters and digits
- 1 <= timestamp <= 10^7
- All calls to set will have strictly increasing timestamp values
- At most 2 * 10^5 calls will be made to set and get
"""

import bisect
from collections import defaultdict


class TimeMapLinear:
    """Approach 1: linear scan — O(n) per get."""

    def __init__(self):
        self.store: dict = defaultdict(list)  # key -> [(ts, val)]

    def set(self, key: str, value: str, timestamp: int) -> None:
        # Append (timestamp, value) to the list for this key — timestamps are increasing
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        # Binary search for the largest timestamp <= given timestamp
        # bisect_right finds insertion point; step back one to get the floor
        # O(n) time | O(1) space per call
        result = ""
        for ts, val in self.store[key]:
            if ts <= timestamp:
                result = val
        return result


class TimeMap:
    """Approach 2: binary search — O(log n) per get."""

    def __init__(self):
        self.store: dict = defaultdict(list)  # key -> [(ts, val)]

    def set(self, key: str, value: str, timestamp: int) -> None:
        # Append (timestamp, value) to the list for this key — timestamps are increasing
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        # Binary search for the largest timestamp <= given timestamp
        # bisect_right finds insertion point; step back one to get the floor
        # O(log n) time | O(1) space per call
        entries = self.store[key]
        idx = bisect.bisect_right(entries, (timestamp, chr(127))) - 1
        return entries[idx][1] if idx >= 0 else ""


if __name__ == "__main__":
    for Cls in (TimeMapLinear, TimeMap):
        tm = Cls()
        tm.set("foo", "bar", 1)
        assert tm.get("foo", 1) == "bar"
        assert tm.get("foo", 3) == "bar"
        tm.set("foo", "bar2", 4)
        assert tm.get("foo", 4) == "bar2"
        assert tm.get("foo", 5) == "bar2"
        assert tm.get("foo", 0) == ""

    print("All tests passed.")