Union if Two Sorted Array

Input: a[] = {13, 15, 18}
b[] = {12, 18, 19, 20, 25}
Output: c[] = {12, 13, 15, 18, 19, 20, 25}

Input: a[] = {12, 13, 13, 13, 14, 14}
b[] = {14, 14}
Output: c[] = {12, 13, 14}

Naive Approach

package main

import (
    "fmt"
    "sort"
)

func main() {
    a := []int{3, 5, 10, 10, 10, 15, 15, 20}
    b := []int{5, 10, 10, 15, 30}
    res := union(a, b)
    fmt.Println(res) //[3 5 10 15 20 30]
}

func union(a, b []int) (res []int) {
    c := make([]int, len(a)+len(b))
    for i := 0; i < len(a); i++ {
        c[i] = a[i]
    }
    m := len(a)
    for j := 0; j < len(b); j++ {
        c[m+j] = b[j]
    }
    sort.Ints(c)
    for i := 0; i < len(c); i++ {
        if i == 0 || c[i] != c[i-1] {
            res = append(res, c[i])
        }
    }
    return res
}

Time Complexity: O((m+n)*log(m+n))

Dry Run:
a[] = {3, 5, 5}
b[] = {1, 5, 7, 7}

After 1st loop: c[] = {3, 5, 5, , , , }
After 2nd loop: c[] = {3, 5, 5, 1, 5, 7, 7}
After sorting: c[] = {1, 3, 5, 5, 5, 7, 7}
3rd loop: res[] = {1, 3, 5, 7}

Efficient Solution

Implementation Idea

if i > 0 && a[i] == a[i-1] { i++; continue; }
if j > 0 && b[j] == b[j-1] { j++; continue; }
if a[i] < b[j] { c=append(c,a[i]); i++ }
if a[i] > b[j] { c=append(c,b[j]); j++ }
if a[i] == b[j] { c=append(c,a[i]); i++; j++ }

Implementation

package main

import (
    "fmt"
)

func main() {
    a := []int{3, 5, 10, 10, 10, 15, 15, 20}
    b := []int{5, 10, 10, 15, 30}
    res := union(a, b)
    fmt.Println(res) //[3 5 10 15 20 30]
}

func union(a, b []int) (res []int) {
    m := len(a)
    n := len(b)
    i, j := 0, 0
    for i < m && j < n {
        if i > 0 && a[i] == a[i-1] {
            i++
            continue
        }
        if j > 0 && b[j] == b[j-1] {
            j++
            continue
        }
        if a[i] < b[j] {
            res = append(res, a[i])
            i++
        } else if a[i] > b[j] {
            res = append(res, b[j])
            j++
        } else {
            res = append(res, a[i])
            i++
            j++
        }
    }
    for i < m {
        if i == 0 || a[i] != a[i-1] {
            res = append(res, a[i])
        }
        i++
    }
    for j < n {
        if j == 0 || b[j] != b[j-1] {
            res = append(res, b[j])
        }
        j++
    }
    return
}

Dry Run

a[] = {12, 20, 30, 30}
b[] = {13, 30, 40}
i=0; j=0;
1st Iteration: c[] = {12}, i=1
2nd Iteration: c[] = {12, 13}, j=1
3rd Iteration: c[] = {12, 13, 20}, i=2
4th Iteration: c[] = {12, 13, 20, 30}, i=3, j=2
5th Iteration: c[] = {12, 13, 20, 30}, i=4
Next Loop for(j < n): c[] = {12, 13, 20, 30, 40}, j=3