LC: 1128: Number of Equivalent Domino Pairs

Solution 1

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

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

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

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
}