Skip to content

Instantly share code, notes, and snippets.

@tsak
Created June 18, 2019 15:57
Show Gist options
  • Save tsak/452ab2efffbd3b035a8439b6197ca80f to your computer and use it in GitHub Desktop.
Save tsak/452ab2efffbd3b035a8439b6197ca80f to your computer and use it in GitHub Desktop.
For each element in 1st array count elements less than or equal to it in 2nd array
package main
import "fmt"
// Complexity O(m * n), possible complexity O(m log n + n log n)
func counts(nums []int32, maxes []int32) []int32 {
var result []int32
for _, m := range maxes {
var c int32 = 0
for _, n := range nums {
if n <= m {
c++
}
}
result = append(result, c)
}
return result
}
func main() {
fmt.Println(counts([]int32{1, 4, 2, 4}, []int32{3, 5}), []int32{2, 4})
fmt.Println(counts([]int32{2, 10, 5, 4, 8}, []int32{3, 1, 7, 8}), []int32{1, 0, 3, 4})
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment