arcbjorn

thoughtbook

RSS Feed

Sunday, March 5, 2023

Sliding window median

Leetcode 480 problem.

Go

Min & Max Heaps

  • Time complexity: O(n)O(n) - n is a length of a number array
  • Auxiliary space: O(n)O(n) - n is a length of a number array`
func medianSlidingWindow(nums []int, k int) []float64 {
    smallNumbers := new(maxheap)
    largeNumbers := new(minheap)

    heap.Init(smallNumbers)
    heap.Init(largeNumbers)

    var medians []float64

    hashMap := make(map[int]int)

    i := 0
    for i < k {
        heap.Push(smallNumbers, nums[i])
        i++
    }

    for j := 0; j < k/2; j++ {
        heap.Push(largeNumbers, smallNumbers.Top())
        heap.Pop(smallNumbers)
    }

    for {
        if k % 2 == 1{ 
            medians = append(medians,float64(smallNumbers.Top()))
        } else {
            temp := (float64(smallNumbers.Top()) + float64(largeNumbers.Top())) * 0.5
            medians = append(medians,float64(temp))
        }

        if i >= len(nums) {
            break
        }  

        
        input := nums[i]
        output := nums[i-k]
        i++

        balance := 0  

        if output <= smallNumbers.Top(){
            balance -= 1
        } else {
            balance += 1
        }

        if _, ok := hashMap[output]; ok {  
            hashMap[output]++
        } else{
            hashMap[output] = 1
        }

        if !smallNumbers.Empty() && input <= smallNumbers.Top() {
            balance++
            heap.Push(smallNumbers, input)
        } else {
            balance--
            heap.Push(largeNumbers, input)
        }

        if balance < 0 {
            heap.Push(smallNumbers, largeNumbers.Top())
            heap.Pop(largeNumbers)
            balance++
        }

        if balance > 0 {
            heap.Push(largeNumbers, smallNumbers.Top())
            heap.Pop(smallNumbers)
            balance--
        }

        num, _ := hashMap[smallNumbers.Top()]
        for num > 0 {
            hashMap[smallNumbers.Top()]--
            heap.Pop(smallNumbers)
            num, _ = hashMap[smallNumbers.Top()]
        }

        num, _ = hashMap[largeNumbers.Top()]
        for !largeNumbers.Empty() && num > 0 {
            hashMap[largeNumbers.Top()]--
            heap.Pop(largeNumbers)
            num, _ = hashMap[largeNumbers.Top()]
        }
    }

    return medians
}

Heaps implementation

// Max heap

type maxheap []int

func (h maxheap) Len() int {
    return len(h)
}

func (h maxheap) Less(i int, j int) bool {
    return h[i] > h[j]
}

func (h maxheap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *maxheap) Pop() interface{} {
    a := *h
    res := a[len(a)-1]
    *h = a[:len(a)-1]
    return res
}

func (h *maxheap) Push(i interface{}) {
    *h = append(*h, i.(int))
}

func (h maxheap) Top() int {
    if h.Empty() {
        return 0
    } else {
        return h[0]
    }
}

func (h maxheap) Empty() bool {
    return len(h) == 0
}

// Min heap

type minheap []int

func (h minheap) Len() int {
    return len(h)
}

func (h minheap) Less(i int, j int) bool {
    return h[i] < h[j]
}

func (h minheap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *minheap) Pop() interface{} {
    a := *h
    res := a[len(a)-1]
    *h = a[:len(a)-1]
    return res
}

func (h *minheap) Push(i interface{}) {
    *h = append(*h, i.(int))
}

func (h minheap) Top() int {
    if h.Empty() {
        return 0
    } else {
        return h[0]
    }
}

func (h minheap) Empty() bool {
    return len(h) == 0
}
Creative Commons Licence