Find the minimum absolute value between 2 elements of an array with minimum complexity

Issue

My goal is to find the minimum absolute value between 2 elements of an array, in the example below the min absolute value is beetwen 1 and 4 and the result is 3

Here is my implementation of the solution:

    input := [6]int{8,1,13,30,4,20} 
    minAbsVal := math.MaxFloat64 
    
    for i := 0; i < len(input); i++ {
        for j := i+1; j < len(input); j++ {
                if math.Abs(float64(input[i] - input[j])) < minAbsVal {
            minAbsVal = math.Abs(float64(input[i] - input[j]))
            }
        }
    }
    
    fmt.Println("Result", minAbsVal)

You can find the implémetation here : https://play.golang.org/p/D2DGy7YcVSv

I want to know if there is a solution with less complexity ?

Solution

You algorithm is currently O(n^2).

When sorted, smallest absolute difference must be between 2 sequential elements.

You can sort integers in O(n log n), with quick sort, merge sort etc. , and after having it sorted, you could have a final step with O(n)

There might be a better implementation with dynamic programming, maybe a single sorting algorithm where you also find the smallest difference, however, this is what I thought

    
    sortedArray = sorted(array) // implement a sorted function
    n := sortedArray[len(sortedArray) - 1)]
    minDif := 2^32 // chose a better initial value like infinity
  
    for i := range n-1 {
        if sortedArray[i+1] - sortedArray[i] < minDif{
           minDif = sortedArray[i + 1] - sortedArray[i]
        }
    }

   
    return minDif

Answered By – keser

Answer Checked By – Mary Flores (GoLangFix Volunteer)

Leave a Reply

Your email address will not be published.