Three arrays algorithm bug

Question

Given three sorted (non-empty) arrays A, B, and C. It is necessary to find a triplet of numbers A[i], B[j], C[k] for which the expression (max(A[i], B[j], C[k]) - min(A[i], B[j], C[k])) would be the minimum of all possible triples. If there are several triplets with the same value, print the one closest to the beginning of the arrays (priority A, B, C).

I'm trying to implement this algorithm problem, but I'm getting runtime error at the second testcase.

A = []
x = int(input())
for i in range(0, x):
    ele = int(input())
    A.append(ele)

fnum = A[0]

B = []
y = int(input())
for i in range(0, y):
    ele2 = int(input())
    B.append(ele2)

C = []
z = int(input())
for i in range(0, z):
    ele3 = int(input())
    C.append(ele3)


def solve(A, B, C):
    i = len(A) - 1
    j = len(B) - 1
    k = len(C) - 1

    min_diff = abs(max(A[i], B[j], C[k]) -
                   min(A[i], B[j], C[k]))

    while i != -1 and j != -1 and k != -1:
        current_diff = abs(max(A[i], B[j],
                               C[k]) - min(A[i], B[j], C[k]))

        if current_diff < min_diff:
            min_diff = current_diff

        max_term = max(A[i], B[j], C[k])

        if A[i] == max_term:
            i -= 1
        elif B[j] == max_term:
            j -= 1
        else:
            k -= 1
    return min_diff


print("Numbers =", fnum, ele2, ele3)
print("Result =", solve(A, B, C))

I'd pass generator returned by itertools.product() directly into a min() with custom key function: (i, el1), (j, el2), (k, el3) = min(product(enumerate(A), enumerate(B), enumerate(C)), key=lambda x: max(x[0][1], x[1][1], x[2][1]) - min(x[0][1], x[1][1], x[2][1])). If you don't need indexes it will look more elegant: el1, el2, el3 = min(product(A, B, C), key=lambda x: max(x) - min(x)) — Olvin Roght
– Olvin Roght, Commented Jan 24, 2022 at 20:58
If you need just minimum difference - min(max(x) - min(x) for x in product(A, B, C)) — Olvin Roght
– Olvin Roght, Commented Jan 24, 2022 at 21:04

abc · Accepted Answer · 2022-01-25 07:37:37Z

Given that the input lists are sorted, you could solve it in linear time by iterating over them and advancing the index on the list with the minimum element (with the goal of increasing its value), until you don't reach the end on one of the input lists.

Example:

def min_diff(l1, l2, l3):

    best_min = float("inf")
    best_tuple = None

    i = j = k = 0
    while i < len(l1) and j < len(l2) and k < len(l3):
        curr_sol = l1[i], l2[j], l3[k]
        curr_diff = max(curr_sol) - min(curr_sol)
        
        curr_min = min(curr_sol)
        if l1[i] == curr_min:
            i += 1
        elif l2[j] == curr_min:
            j += 1
        else:
            k += 1

        if curr_diff < best_min:
            best_min = curr_diff
            best_tuple = curr_sol

    return best_tuple, best_min


>>> print(min_diff([10, 11, 12, 13, 14], [1, 2, 3, 4, 5], [8]))
((10, 5, 8), 5)

For 3 lists with 10k elements, the time taken would be milliseconds vs several minutes of a bruteforce approach.

Alain T. · Accepted Answer · 2022-01-24 23:40:11Z

You could use the product function (from itertools) to "brute force" the combination analysis picking the triplet that has the lowest difference between max and min:

from itertools import product
def maxmin(A,B,C):
    return min((max(p)-min(p),p) for p in product(A,B,C))

output:

A = [10, 11, 12, 13, 14]
B = [1, 2, 3, 4, 5]
C = [8]

print(*maxmin(A,B,C))
    
5 (10, 5, 8)

The equivalent logic, without using libraries, would require 3 nested loops:

def maxmin(A,B,C):
    n, abc = None, None
    for a in A:
        for b in B:
            for c in C:
                d = max(a,b,c)-min(a,b,c)
                if not abc or d<n:
                    n, abc = d, (a,b,c)
    return n, abc

although you could place that in a comprehension:

def maxmin(A,B,C):
    return min(((max(a,b,c)-min(a,b,c),(a,b,c)) 
                 for a in A for b in B for c in C))

maxmin(A,B,C)
5 (10, 5, 8)

Collectives™ on Stack Overflow

Three arrays algorithm bug

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related