Solution 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | func numEquivDominoPairs(dom [][]int) int { Xdom := make(map[string]int) var pairs int Xdom[fmt.Sprintf("%d%d",dom[0][0],dom[0][1])]=1 for i:=1;i<len(dom);i++{ Xdom[fmt.Sprintf("%d%d",dom[i][0],dom[i][1])]+=1 } for ab,abFreq:=range Xdom{ if abFreq==0{ continue } if abFreq>1{ pairs+=(abFreq*(abFreq-1))/2 } Xdom[ab]=0 if baFreq,ok := Xdom[string(ab[1])+string(ab[0])];ok && baFreq>0{ pairs+=abFreq*baFreq } } return pairs} |
Solution 2 – Optimise frequency map build using 2 pointers
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | func numEquivDominoPairs(dom [][]int) int { Xdom := make(map[string]int) var i,revI,pairs int revI = len(dom)-1 if len(dom)%2>0{ Xdom[fmt.Sprintf("%d%d",dom[revI][0],dom[revI][1])]+=1 revI-- } for i<revI{ Xdom[fmt.Sprintf("%d%d",dom[i][0],dom[i][1])]+=1 Xdom[fmt.Sprintf("%d%d",dom[revI][0],dom[revI][1])]+=1 i++ revI-- } for ab,abFreq:=range Xdom{ if abFreq>1{ pairs+=abFreq*(abFreq-1)/2 } Xdom[ab]=0 if baFreq,_ := Xdom[string(ab[1])+string(ab[0])];baFreq>0{ pairs+=abFreq*baFreq } } return pairs} |
Possible optimisation : Implementing without string keys using array[a,b] as key, saves space and less time computing rune to string casting
Solution 3 – Replace string keys with array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | func numEquivDominoPairs(dom [][]int) int { Xdom := make(map[[2]int]int) var i,revI,pairs int revI = len(dom)-1 if len(dom)%2>0{ Xdom[[2]int{dom[revI][0],dom[revI][1]}]+=1 revI-- } for i<revI{ Xdom[[2]int{dom[i][0],dom[i][1]}]+=1 Xdom[[2]int{dom[revI][0],dom[revI][1]}]+=1 i++ revI-- } for ab,abFreq:=range Xdom{ if abFreq>1{ pairs+=abFreq*(abFreq-1)/2 } Xdom[ab]=0 if baFreq,_ := Xdom[[2]int{ab[1],ab[0]}];baFreq>0{ pairs+=abFreq*baFreq } } return pairs} |
Possible optimisation: Instead of counting combinations of a set and it’s complement, turn the complement into a set (swap the complement) and use n(n+1)/2 instead
Solution 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | func numEquivDominoPairs(dom [][]int) int { Xdom := make(map[[2]int]int) var i,revI,pairs int revI = len(dom)-1 if len(dom)%2>0{ if dom[revI][0] > dom[revI][1]{ dom[revI][0], dom[revI][1]= dom[revI][1], dom[revI][0] } Xdom[[2]int{dom[revI][0],dom[revI][1]}]+=1 revI-- } for i<revI{ if dom[i][0] > dom[i][1]{ dom[i][0], dom[i][1]= dom[i][1], dom[i][0] } Xdom[[2]int{dom[i][0],dom[i][1]}]+=1 if dom[revI][0] > dom[revI][1]{ dom[revI][0], dom[revI][1]= dom[revI][1], dom[revI][0] } Xdom[[2]int{dom[revI][0],dom[revI][1]}]+=1 i++ revI-- } for _,abFreq:=range Xdom{ abFreq-- pairs+=abFreq*(abFreq+1)/2 } return pairs} |
