LeetCode: Random Point in Non-overlapping Rectangles

// https://code.dennyzhang.com/random-point-in-non-overlapping-rectangles
// Basic Ideas: dynamic programming
//
// Complexity: Time O(log(n)), Space O(n)
import "math/rand"

type Solution struct {
    rects [][]int
    nums []int
}

func Constructor(rects [][]int) Solution {
    nums := make([]int, len(rects))
    sum := 0
    for i, rect := range rects {
        sum += (rect[2]-rect[0]+1)*(rect[3]-rect[1]+1)
        nums[i] = sum
    }
    return Solution{rects:rects, nums:nums}
}

func (this *Solution) Pick() []int {
    total := this.nums[len(this.nums)-1]
    num := rand.Intn(total)
    // search insert position
    // 100, 10, 20, 8, 20
    left, right := 0, len(this.nums)-1
    for left<right {
        mid := (right-left)/2+left
        if this.nums[mid] <= num {
            // right half
            left = mid+1
        } else {
            right = mid
        }
    }
    // left
    x, y := this.rects[left][0], this.rects[left][1]
    width := this.rects[left][2]-this.rects[left][0]+1
    height := this.rects[left][3]-this.rects[left][1]+1

    offset := num-(this.nums[left]-width*height)
    x += offset%width
    y += offset/width
    return []int{x, y}
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(rects);
 * param_1 := obj.Pick();
 */