Is there an efficient way to lower time complexity of this problem ? current T(n) = O(N^3)-CodePudding

need to choose the value such that the value of the equation abs('a' - 'b') abs('b' - 'c') abs('c' - 'a') is minimized.

def minimumValue(n: int, a: List[int], b: List[int], c: List[int]) -> int :
    # Write your code here.
    ans=10000000000000
    for i in range (n):
        for j in range (n):
            for k in range (n):
                ans = min(ans, abs(a[i] - b[j])   abs(b[j] - c[k])   abs(c[k] - a[i]))
                
    return ans

CodePudding user response：

Without any further knowledge/assumption on the content of the 3 lists, and if you need to obtain the true minimum value (and not an approximate value), then there's no other choice than using brute force. Some optimisations are possible, but still with a N^3 complexity (and without any speed-up in the worst case).

for i in range (n):
    for j in range (n):
        v = abs(a[i] - b[j])
        if v < ans:
            for k in range (n):
                ans = min(ans, v   abs(b[j] - c[k])   abs(c[k] - a[i]))

CodePudding user response：

Here is a O(nlogn) solution. You can sort the three lists, and then do this:

get the first value from each of the three lists
Repeat while we have three values:
- sort these three values (and keep track of where they came from)
- calculate the target expression with those three, and check if it improves on the best result so far
- replace the least of these three values with the next value from the same list as this value came from. If there is no more next value in that list, return the result (quit)

Note also that the formula of the expression to evaluate is the same as doing (max(x,y,z)-min(x,y,z))*2, and this is easy to do when the values x, y and z are sorted, as then it becomes (z-x)*2. To find the minimum that this expression can take, we can leave out the *2 and only do that multiplication at the very end.

Here is the code for implementing that idea:

def minimumValue(n: int, a: List[int], b: List[int], c: List[int]) -> int:
    queues = map(iter, map(sorted, (a, b, c)))
    three = [[next(q), q] for q in queues]
    least = float("inf")
    while True:
        three.sort()    
        least = min(least, three[2][0] - three[0][0])
        try:
            three[0][0] = next(three[0][1])
        except:
            return least*2

The time complexity for initially sorting the three input lists is O(nlogn). The loop will iterate 3n-2 times, which is O(n). Each of the actions in one loop iteration executes in constant time.

So the overall complexity is determined by the initial sorting: O(nlogn)