Finding the median of two sorted arrays in O(log(m+n) time

In theLeetCode [Problem #4](leetcode.com/problems/median-of-two-sorted-.. the inputs are two arrays sorted in an ascending order. The constraints in the problems are.

1. Each of the arrays may have 0 to 1000 elements.
2. Each elements can have value ranging from -10⁶ to 10⁶.
3. And finally, the algorithm should find the median in O(log(m+n)) time, where m and n are lengths of the input arrays.

Median

In statistics, the median is the middle number in the set of sorted numbers. For example, in the set of numbers [1,2,3,4,5], 3 is the median. But if there are even numbers in the set, then we find the average of the middle number and the next number. For example, in the set of numbers [1,2,3,4,5,6], the median is (3+4)/2 i.e., 3.5.

Solution

One of the solutions for this problem is we create a new array with a length equal to the sum of the lengths of two input arrays. Copy both arrays into the new array and then sort it to find the median. In this solution copying each array into the new array would take O(m+n) and sorting the new array would take O(log(m+n)). This could be an acceptable solution.

However, we can do better with a double-linked list. In this list, we insert elements such that smaller numbers are always pushed to the left side of the node and larger elements are always inserted to the right. But we would always return the mid-value node. The implementation is given below.

type Node struct {
    Value int
    next  *Node
    prev  *Node
}

func (node *Node) LastNode() *Node {
    if node.next == nil {
        return node
    }
    return node.next.LastNode()
}

func (node *Node) FirstNode() *Node {
    if node.prev == nil {
        return node
    }
    return node.prev.FirstNode()
}

func (node *Node) Next(value int) *Node {
    if value < node.Value {
        newNode := &Node{Value: value, next: node, prev: node.prev}
        node.prev.next = newNode
        node.prev = newNode
        return node.LastNode()
    }

    if node.next == nil {
        node.next = &Node{Value: value, next: nil, prev: node}
        return node.next
    }

    return node.next.Next(value)
}

func (node *Node) Prev(value int) *Node {

    if value > node.Value {
        newNode := &Node{Value: value, next: node.next, prev: node}
        node.next.prev = newNode
        node.next = newNode
        return node.FirstNode()

    }

    if node.prev == nil {
        node.prev = &Node{Value: value, next: node, prev: nil}
        return node.prev
    }

    return node.prev.Prev(value)
}

func Push(node *Node, value int) *Node {
    if node == nil {
        return &Node{Value: value}
    }
    if value >= node.Value {
        return node.Next(value)
    }
    node.Prev(value)
    return node
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    var endNode *Node
    maxLen := len(nums1)
    if maxLen < len(nums2) {
        maxLen = len(nums2)
    }

    for i := 0; i < maxLen; i++ {
        if i < len(nums1) {
            endNode = Push(endNode, nums1[i])
        }
        if i < len(nums2) {
            endNode = Push(endNode, nums2[i])
        }

    }

    lenOfArrs := len(nums1) + len(nums2)
    median := int((lenOfArrs-lenOfArrs%2)/2) + 1

    for i := lenOfArrs; i > median && endNode.prev != nil; i-- {
        endNode = endNode.prev
    }

    if lenOfArrs%2 == 0 {
        return (float64(endNode.Value+endNode.prev.Value) / 2.0)
    }

    return float64(endNode.Value)
}