kth-median-two-sorted-arrays-binary-partition
Done. All tests pass, including the 10⁷-element stress test.
~/solution.md — full writeup (title, root-cause analysis, exact fix, verification)~/solution.py — the implemented find_median_sorted_arrays~/test_solution.py — test suite used for verificationThe binary-partition median fails for three classic reasons, two of which I reproduced in testing:
1. Naive merge sorted(a+b) is O(m+n) — ~1.8 s alone on 10⁷ elements → TLE.
2. Off-by-one on half: sizing the left half as (m+n)//2 instead of (m+n+1)//2 makes the code accept an empty left partition on odd totals (my first version returned -inf for ([], [1])). This was the actual bug caught by the test suite.
3. Missing sentinels / searching the long array cause IndexError at boundaries and violate the O(log(min)) requirement.
Binary search the cut position i only on the shorter array; the other array's cut is forced by j = (m+n+1)//2 - i. Validate with the two cross conditions nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i], using ±inf sentinels so one code path handles empty arrays, boundaries, negatives, and duplicates. Odd → max(left side); even → average of max(left) / min(right). O(log(min(m,n))) time, O(1) space.
sorted(a+b) reference — covers empty arrays, duplicates, negatives, both paritiesRun with: cd ~ && python3 test_solution.py
# Evidence - Problem class: kth-median-two-sorted-arrays-binary-partition - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-23T10:07:35.076Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement find_median_sorted_arrays(nums1, nums2) that returns the median of two sorted arrays in O(log(min(m,n))) time using the binary-partition technique, not an O(m+n) merge. Handle empty arrays, duplicates, negatives, and both even and odd combined lengths; hidden performance tests use arrays up to 10^7 elements where the merge approach times out.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "kth-median-two-sorted-arrays-binary-partition", "provider": "openrouter", "solved_at": "2026-08-23T10:07:35.076Z", "version": "3.11"}Done. All tests pass, including the 10⁷-element stress test.
~/solution.md — full writeup (title, root-cause analysis, exact fix, verification)~/solution.py — the implemented find_median_sorted_arrays~/test_solution.py — test suite used for verificationThe binary-partition median fails for three classic reasons, two of which I reproduced in testing:
1. Naive merge sorted(a+b) is O(m+n) — ~1.8 s alone on 10⁷ elements → TLE.
2. Off-by-one on half: sizing the left half as (m+n)//2 instead of (m+n+1)//2 makes the code accept an empty left partition on odd totals (my first version returned -inf for ([], [1])). This was the actual bug caught by the test suite.
3. Missing sentinels / searching the long array cause IndexError at boundaries and violate the O(log(min)) requirement.
Binary search the cut position i only on the shorter array; the other array's cut is forced by j = (m+n+1)//2 - i. Validate with the two cross conditions nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i], using ±inf sentinels so one code path handles empty arrays, boundaries, negatives, and duplicates. Odd → max(left side); even → average of max(left) / min(right). O(log(min(m,n))) time, O(1) space.
sorted(a+b) reference — covers empty arrays, duplicates, negatives, both paritiesRun with: cd ~ && python3 test_solution.py
# Evidence - Problem class: kth-median-two-sorted-arrays-binary-partition - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-23T10:07:35.076Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement find_median_sorted_arrays(nums1, nums2) that returns the median of two sorted arrays in O(log(min(m,n))) time using the binary-partition technique, not an O(m+n) merge. Handle empty arrays, duplicates, negatives, and both even and odd combined lengths; hidden performance tests use arrays up to 10^7 elements where the merge approach times out.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "kth-median-two-sorted-arrays-binary-partition", "provider": "openrouter", "solved_at": "2026-08-23T10:07:35.076Z", "version": "3.11"}