package main

import (
	"fmt"
	"os"
)

// time O(M + N)
// space O(1)
func merge(nums1 []int, m int, nums2 []int, n int) []int {
	for i, j, k := m-1, n-1, m+n-1; j >= 0; k -= 1 {
		if i >= 0 && nums1[i] > nums2[j] {
			nums1[k] = nums1[i]
			i--
		} else {
			nums1[k] = nums2[j]
			j--
		}
	}

	return nums1
}

func assertEqual(a int, b int) {
	if a != b {
		fmt.Printf("Expected %d, but got %d\n", a, b)
		os.Exit(1)
	}
}

func test() {
	testcase1 := merge([]int{1, 2, 3, 0, 0, 0}, 3, []int{2, 5, 6}, 3)
	assertEqual(testcase1[0], 1)
	assertEqual(testcase1[1], 2)
	assertEqual(testcase1[2], 2)
	assertEqual(testcase1[3], 3)
	assertEqual(testcase1[4], 5)
	assertEqual(testcase1[5], 6)
	assertEqual(len(testcase1), 6)

	testcase2 := merge([]int{1}, 1, []int{}, 0)
	assertEqual(testcase2[0], 1)
	assertEqual(len(testcase2), 1)

	testcase3 := merge([]int{0}, 0, []int{1}, 1)
	assertEqual(testcase3[0], 1)
	assertEqual(len(testcase3), 1)

	testcase4 := merge([]int{4, 5, 6, 0, 0, 0}, 3, []int{1, 2, 3}, 3)
	assertEqual(testcase4[0], 1)
	assertEqual(testcase4[1], 2)
	assertEqual(testcase4[2], 3)
	assertEqual(testcase4[3], 4)
	assertEqual(testcase4[4], 5)
	assertEqual(testcase4[5], 6)
	assertEqual(len(testcase4), 6)
}

func main() {
	test()
}