CODEWITHSUNDEEP
algorithmgo
mbbo128
mbbo128

Reputation: 49

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

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 ?

Upvotes: 1

Views: 342

Answers (2)

keser
keser

Reputation: 2642

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

Upvotes: 1

Zombo
Zombo

Reputation: 1

You could also use a Heap, it sorts itself:

package main

import (
   "container/heap"
   "sort"
)

type slice struct { sort.IntSlice }
func (s slice) Pop() interface{} { return 0 }
func (s slice) Push(x interface{}) {}

func main() {
   s := slice{
      sort.IntSlice{8, 1, 13, 30, 4, 20},
   }
   heap.Init(s)
   println("Result", s.IntSlice[0])
}

https://golang.org/pkg/container/heap

Upvotes: 1

Related Questions