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

// Input: nums1 = [1,3], nums2 = [2]
// Output: 2.00000
// Explanation: merged array = [1,2,3] and median is 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.

package main

import "log"

func main() {
	log.Println(medianOfArrays(
		[]int{1, 3},
		[]int{2},
	))
	log.Println(medianOfArrays(
		[]int{1, 2},
		[]int{3, 4},
	))
}

func medianOfArrays(a, b []int) float64 {
	valueCount := len(a) + len(b)
	mustGetAverage := (valueCount%2 == 0)
	needToSkip := valueCount / 2
	if !mustGetAverage {
		needToSkip += 1
	}
	needToSkip -= 1

	skippedA, skippedB := 0, 0
	for needToSkip > skippedA+skippedB {
		log.Println(needToSkip, skippedA, skippedB)
		aExhausted := skippedA >= len(a)
		bExhausted := skippedB >= len(b)
		if aExhausted || b[skippedB] < a[skippedA] {
			skippedB += 1
		} else if bExhausted || a[skippedA] < b[skippedB] {
			skippedA += 1
		} else if !aExhausted && !bExhausted {
			skippedA += 1
		}
	}

	log.Println(needToSkip, a, skippedA, b, skippedB)
	if bothArraysHaveValues := skippedA < len(a) && skippedB < len(b); bothArraysHaveValues {
		if mustGetAverage {
			log.Println("need to avg lowest of", a[:skippedA], b[:skippedB])
			fromA, lowest := getLowestOfArrays(a[skippedA:], b[skippedB:])
			if fromA {
				skippedA += 1
			} else {
				skippedB += 1
			}
			_, secondLowest := getLowestOfArrays(a[skippedA:], b[skippedB:])
			return float64(lowest) + float64(secondLowest)/2
		}
		_, lowest := getLowestOfArrays(a[skippedA:], b[skippedB:])
		return float64(lowest)
	}

	if aExhausted := skippedA >= len(a); aExhausted {
		if mustGetAverage {
			panic("not impl")
		}
		return float64(b[skippedB])
	}
	if mustGetAverage {
		panic("not impl")
	}
	return float64(a[skippedA])
}

func getLowestOfArrays(a, b []int) (fromA bool, lowest int) {
	if len(a) == 0 {
		return false, b[0]
	}
	if len(b) == 0 {
		return true, a[0]
	}
	if a[0] > b[0] {
		return true, a[0]
	}
	return false, b[0]
}