leetcode-go/leetcode/hard/315.count-of-smaller-numbers-after-self.go

func countSmaller(nums []int) []int {
	n := len(nums)
	res := make([]int, n)
	if n < 1 {
		return res
	}
	arr := []int{nums[n-1]}
	for i := n - 2; 0 <= i; i-- {
		l, r, target := 0, n-1-i, nums[i]
		for l < r {
			m := l + (r-l)/2
			if arr[m] < target {
				l = m + 1
			} else if target < arr[m] {
				r = m
			} else {
				l = m
				break
			}
		}
		for 0 < l && arr[l-1] == target {
			l-- // Filter out same elements
		}
		res[i] = l
		if l == n-1-i {
			arr = append(arr, target)
		} else {
			tmp := make([]int, n-i)
			copy(tmp, arr[:l])
			copy(tmp[l+1:], arr[l:])
			tmp[l] = target
			arr = tmp
		}
	}
	return res
}