CODEWITHSUNDEEP
pythonarrayspython-3.xalgorithm
Mahmoud
Mahmoud

Reputation: 95

Three arrays algorithm bug

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.

enter image description here

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))

Upvotes: 0

Views: 94

Answers (2)

abc
abc

Reputation: 11929

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.

Upvotes: 1

Alain T.
Alain T.

Reputation: 42143

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)

Upvotes: 0

Related Questions