Find Pair with given sum and maximum shortest distance from end in Python

In this given problem we have to find a pair with a given sum and maximum shortest distance from the end.

Here we have an array size A with contains all A integer values and another variable  M which is also an integer, first, we choose two distinct values whose sum is equal to the value of M (we have given) then we calculate the maximum possible shortest distance of the two chosen values from the endpoints of the given array.

Let us understand with the help of an example:

Example:

In: arr[8] = {1, 2, 3, 4, 5, 6, 7, 9} 
        M = 12
Out:  The maximum distance came out to be: 3
Working:
1.Choose the pair the pair(3,9) 
2.Shortest distance of from 3 end = 3
Shortest distance of 9 from ends = 1
Therefore, answer is max(3,1) = 3

For the end element, the distance from the end will be considered 1 and not 0

This problem can be solved in two ways:

1. Normal approach: In this approach, we run two loops, the inner loop checks whether the two chosen values’ sum is equal to  M. If equal, then we make the shortest distances of two elements as the maximum answer then we compare the previous pair’s answer with the new pair and choose a minimum of the two pairs. Once the loop ends we get the output.

2. Advance approach: If we think, we can see that the distance from left and from right end is actually the shortest distance which is min(1+j, A-j). Let us denote the shortest distance of jth element as D. Now Run a loop and calculate the shortest distance of all the values in the array in another array(let it be D[]). Hence we will get the shortest distances for all the elements.

At last, we run the loop. If Z is picked, then the other value should be M-Z. Check the answer with max(D[Z], D[M-Z]) and at every update, select the minimum of the previous and present answer. If M-Z is not a value in the given array, then D[M-Z] will be set to a great value, as we have set already.

def search_max(l, a, M):    
     # store element in array
   
    d = dict()       
    for j in range(a): 
        z = l[j] 
        # calculate shortest distance from end points
        dst = min(1 + j, a - j) 
        if z not in d.keys(): 
            d[z] = dst
        else:  
            d[z] = min(dst, d[z]) 
    res = 8**5

    for j in range(a): 
        z = l[j]          
        # if elements similar, ignore the element     
        if (z != (M - z) and (M- z)in d.keys()):          
            res = min(max(d[z], d[M - z]), res)    
    return res
  
# Main code 
l = [1, 2, 3, 4, 5, 6, 7, 9] 
M = 12
a = len(l) 
print("The maximum distance came out to be :",search_max(l, a, M))

Output:

The maximum distance came out to be : 3
[Program finished]

I hope you understand the concept and the topic. Try running the code, if you have any doubts you can drop a comment. Your feedback will be appreciated.