nextgreatest.go

package main

import "fmt"

// 0 1  2 3 4 5 6  7 - indexes
// 8 10 8 6 8 8 11 9 - array (input)
// 1 5  4 1 2 1 -1 -1 - differences (desired result)

var arr = []int{8, 10, 8, 6, 8, 8, 11, 9} // - array (input)
type pair struct {
	value int
	index int
}

func main() {
	fmt.Println("starting vals:", arr)
	sortedPairs := []pair{}
	dist := make([]int, len(arr))
	for i := len(arr) - 1; i >= 0; i-- {
		idx := binarySearch(sortedPairs, pair{arr[i], i})
		//fmt.Println("sorted val/last seen idx:", sortedPairs, "binsearch result:", idx, "val:", arr[i])
		if len(sortedPairs) > 0 {
			if idx >= 0 {
				sortedPairs[idx].index = i
				sortedPairs = sortedPairs[idx:]
			} else {
				idx = -idx - 1
				sortedPairs = sortedPairs[idx:]
				sortedPairs = append([]pair{pair{arr[i], i}}, sortedPairs...)
			}
		} else {
			sortedPairs = append(sortedPairs, pair{arr[i], i})
		}
		if len(sortedPairs) == 1 {
			dist[i] = -1
		} else {
			dist[i] = sortedPairs[1].index - i
		}
		fmt.Println("sorted val/last seen idx:", sortedPairs, "distances:", dist)
	}
	fmt.Println("solution: ", dist)
}

func binarySearch(sorted []pair, p pair) int {
	min := 0
	max := len(sorted) - 1
	var mid int
	for max >= min {
		mid = (min + max) / 2
		if p.value == sorted[mid].value {
			return mid
		} else if sorted[mid].value > p.value {
			max = mid - 1
		} else {
			min = mid + 1
		}
	}
	return -min - 1
}

samplerun.sh

starting vals: [8 10 8 6 8 8 11 9]
sorted val/last seen idx: [{9 7}] distances: [0 0 0 0 0 0 0 -1]
sorted val/last seen idx: [{11 6}] distances: [0 0 0 0 0 0 -1 -1]
sorted val/last seen idx: [{8 5} {11 6}] distances: [0 0 0 0 0 1 -1 -1]
sorted val/last seen idx: [{8 4} {11 6}] distances: [0 0 0 0 2 1 -1 -1]
sorted val/last seen idx: [{6 3} {8 4} {11 6}] distances: [0 0 0 1 2 1 -1 -1]
sorted val/last seen idx: [{8 2} {11 6}] distances: [0 0 4 1 2 1 -1 -1]
sorted val/last seen idx: [{10 1} {11 6}] distances: [0 5 4 1 2 1 -1 -1]
sorted val/last seen idx: [{8 0} {10 1} {11 6}] distances: [1 5 4 1 2 1 -1 -1]
solution:  [1 5 4 1 2 1 -1 -1]