# Leetcode interview questions 16.06. Minimum difference

Solution step description

• Sort the two arrays first
• Minimize the interval to be traversed
• Double pointer traversal calculation result

You can think of two arrays as two intervals on the integer number axis (each is a discrete interval defined by the maximum and minimum of the array, but you can think of them as continuous intervals or line segments). By analyzing the positional relationship between these two intervals, the process of "reducing the interval to be traversed" can be clarified.

• There are cases where the boundaries of the intervals are equal
• There is no intersection between the two intervals
• One of the two intervals completely contains the other
• Two intervals have a partial intersection

For this question, I spent a lot of effort on "minimize the interval to be traversed as much as possible" . It should be emphasized that the time complexity of sorting is$O(nlogn)$ , the time complexity of the subsequent traversal calculation result is$O(n)$ , time is mainly spent on sorting, so the optimization of "minimize the interval to be traversed as much as possible" has little effect on the overall performance improvement. I just find it interesting, just write and read. Assuming that there is such a problem, the two input arrays (intervals) are already in order, and the arrays (intervals) are required to be merged, or the merge is part of the calculation process. At this time, it makes sense to reduce the length of the arrays (intervals) to be traversed. .
Readers can modify it by themselves and remove the part that reduces the traversal interval to simplify the code. For details, please see the code and comments below.

import  "math"
import  "sort"

func  smallestDifference (a [] int , b [] int )  int {
la := len (a)
if la == 0 {
panic ( "a is empty" )
}
lb := len (b)
if lb == 0 {
panic ( "b is empty" )
}
//la != 0 && lb != 0
sort.Sort(sort.IntSlice(a))
sort.Sort(sort.IntSlice(b))

//Let s see if we can get the results quickly

//End points are equal, 4 cases
if a[ 0 ] == b[ 0 ] ||
a[ 0 ] == b[lb -1 ] ||
a[la -1 ] == b[ 0 ] ||
a[la -1 ] == b[lb -1 ] {
return  0
}

//disjoint, two cases
if a[la -1 ] <b[ 0 ] {
return b[ 0 ]-a[la -1 ]
}
if b[lb -1 ] <a[ 0 ] {
return a[ 0 ]-b[lb -1 ]
}

//Next, try to narrow the traversal interval, find the maximum value smaller than the minimum value, and find the minimum value larger than the maximum value.

//First judge the complete inclusion, in two cases
//a <b && b[lb-1] <a[la-1]
//a contains b
minDiff, ok := handleInclusion(a, b)
if ok {
return minDiff
}
//b <a && a[la-1] <b[lb-1]
//b contains a
minDiff, ok = handleInclusion(b, a)
if ok {
return minDiff
}

//Then judge the intersection (not completely included), two cases
//a[la-1]> b && a[la-1] <b[lb-1]
//the right end of a is in b
minDiff, ok = handleIntersection(a, b)
if ok {
return minDiff
}
//the right end of b is in a
minDiff, ok = handleIntersection(b, a)
if ok {
return minDiff
}

//
Bottom of the pocket return getMinAbsDiff(a, b)
}

//Try to handle the case of intersection
func  handleIntersection (a, b [] int )  ( int , bool ) {
var (
la = len (a)
lb = len (b)
)
//Intersect (not completely included)
if a[la -1 ]> b[ 0 ] && a[la -1 ] <b[lb -1 ] { //The right end of a is in b
//Try to narrow the point of b The interval to traverse.
//Find the smallest value in b that is greater than a[la-1].
bRight, equal := searchMinValueGreaterThanX(b, a[la -1 ])
if equal {
return  0 , true
}
//Try to narrow the range of a to be traversed.
//Find the maximum value in a that is smaller than b.
aLeft, equal := searchMaxValueSmallerThanX(a, b[ 0 ])
if equal {
return  0 , true
}
return getMinAbsDiff(a[aLeft:], b[:bRight+ 1 ]), true
}
return  0 , false
}

//Try to handle the included case
func  handleInclusion (a, b [] int )  ( int , bool ) {
var (
la = len (a)
lb = len (b)
)
//Fully contain
if a[ 0 ] <b[ 0 ] && b[lb -1 ] <a[la -1 ] { //a contains b
//Reduce the range of a to be traversed
//Find the ratio in a b Small maximum
aLeft, equal := searchMaxValueSmallerThanX(a, b[ 0 ])
if equal {
return  0 , true
}
//Find the smallest value in a that is greater than b[lb-1]
aRight, equal := searchMinValueGreaterThanX(a, b[lb -1 ])
if equal {
return  0 , true
}
return getMinAbsDiff(a[aLeft:aRight+ 1 ], b), true
}
return  0 , false
}

//Double pointer traversal, calculation result
func  getMinAbsDiff (a, b [] int )  int {
var (
ia       int
ib       int
la = len (a)
lb = len (b)
minDiff = math.MaxInt32
)
for ia <la && ib <lb {
if a[ia] == b[ib] {
return  0
}
if a[ia] <b[ib] {
x := b[ib]-a[ia]
if x <minDiff {
minDiff = x
}
ia++
} else {
x := a[ia]-b[ib]
if x <minDiff {
minDiff = x
}
ib++
}
}
return minDiff
}

//Find the largest value smaller than x in the ordered array a.
//If found, return the index of that element.
//If both are greater than x, return 0.
//If the bool in the return value is true, it means that a value equal to x has been found.
func  searchMaxValueSmallerThanX (a [] int , x int )  ( int , bool ) {
var (
low int
high = len (a) -1
maxVal int
i = -1
)
for low <= high {
mid := low + (high-low)>> 1
v := a[mid]
if v == x {
return mid, true
}
if v <x {
if i != -1 {
if v> maxVal {
maxVal = v
i = mid
}
} else {
maxVal = v
i = mid
}
low = mid+ 1
} else {
high = mid -1
}
}
//are greater than x
if high == -1 {
return low, false
}
return i, false
}

//Find the smallest value greater than x in the ordered array a.
//If found, return the index of that element.
//If both are smaller than x, return the largest index of a.
//If the bool in the return value is true, it means that a value equal to x is found.
func  searchMinValueGreaterThanX (a [] int , x int )  ( int , bool ) {
var (
low int
high = len (a) -1
minVal int
i = -1
)
for low <= high {
mid := low + (high-low)>> 1
v := a[mid]
if v == x {
return mid, true
}
if v <x {
low = mid+ 1
} else {
if i != -1 {
if v <minVal {
minVal = v
i = mid
}
} else {
minVal = v
i = mid
}
high = mid -1
}
}
//Both are smaller than x
if low == len (a) {
return high, false
}
return i, false
}
Copy code

Sorting (assuming quick sort based) time complexity$O(nlogn)$ , space complexity$O(logn)$ (system stack overhead).
The operation to try to reduce the traversal interval is based on binary search, and the time complexity is$O(logn)$ .
Time complexity of traversing calculation results$O(n)$ .
Overall, the time complexity$O(nlogn)$ , space complexity$O(logn)$ .