// 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("CASE A SHOULD BE 2:", medianOfArrays(
		[]int{1, 3},
		[]int{2},
	))
	log.Println("CASE B SHOULD BE 2.5:", 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 // [1, 2, 3]  vs  [2, 2, 2]
		}
	}

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

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]
}