package dev.egonr.leetcode

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

Median: The middle number; found by ordering all data points and picking out the one in the middle
(or if there are two middle numbers, taking the mean of those two numbers)

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


Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.


Constraints:
    nums1.length == m
    nums2.length == n
    0 <= m <= 1000
    0 <= n <= 1000
    1 <= m + n <= 2000
    -106 <= nums1[i], nums2[i] <= 106
 */

class MedianTwoSortedArrays {
    fun test() {
        println(findMedianSortedArrays(intArrayOf(1,3), intArrayOf(2))) // merged 1,2,3 -> median 2
        println(findMedianSortedArrays(intArrayOf(1,2), intArrayOf(3,4))) // merged 1,2,3,4 -> median (2+3)/2 -> 2.5
    }

    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        val merged = arrayListOf<Int>()
        merged.addAll(nums1.toList())
        merged.addAll(nums2.toList())
        merged.sort()

        val mergedLen = merged.count()
        var median = 0.0
        if(mergedLen % 2 == 0) {
            median = (merged[mergedLen / 2] + merged[mergedLen / 2 - 1]) / 2.0
        } else {
            median = merged[mergedLen / 2].toDouble()
        }

        return median
    }
}