You thought I was gone?

Well, it's been more than a year since I last blogged, time passed in the blink of an eye, memories to foster, all like a roller coaster.

The same place where I had written my first ever blog, the same old feeling, but still, nothing is the same, the feeling of nostalgia hits me, the lingering excitement beckons me, and that my friend, is called inspiration. 

______________________________________________________________________

                                       ______________________________________________________________________

Coming to the Problem squatting inside my mind rent free. 

Problem Statement:

You are given two integer arrays, arr1 and arr2, and an integer d.

The task is to find the maximum number of magic pairs possible.

A magic pair is defined as (i,j) where i belongs to arr1 and j belongs to arr2,

such that j lies in the range [i,i+d] and you can use an integer only once.

Example 1:-

arr1=[1,5,3,6], arr2=[2,4,6], d=5

Output: 3

Explanation: We can have 3 pairs as follows, (1,2),(3,4), and (5,6)

Example 2:-

arr1=[10,7,13,18], arr2=[4,23,15], d=10

Output: 3

Explanation: We can have 3 pairs as follows, (7,4),(10,15),(13,23)

You should think of an idea that pops up in your mind before moving on to see my approach.

I am not entirely sure about the solution to this problem but I have an idea, that might be correct. Till now I couldn't think of anything that would prove this solution to be wrong, if you have a corner case or something that I am missing then suggestions are always welcome.

MY APPROACH:-

A simple greedy approach where first I sort the arrays, then create the intervals and store them in a list. After that we'll just go through the intervals one by one and for each interval, will try to find an integer in arr2 which lies in the required range, as soon as we find the integer, we somehow mark that now that integer is used up (won't use this integer again) and move to the next interval to repeat the same process again.

Code:-

def solve(arr1,arr2,d):

    arr1.sort()

    arr2.sort()

   

    n=len(arr1)

    m=len(arr2)

    count=0

    intervals=[]

    check=dict()

   

    for i in arr1:

        intervals.append([i,i+d])

   

    for j in arr2:

        check[j]=0

    for ins in intervals:

        for j in arr2:

            # means if the element hasn't yet been used and lies in the desired range

            if(check[j]!=1 and j>=ins[0] and j<=ins[1]):

                count+=1

                # mark this integer as used and break out of this loop, cz we are

                # done with this interval

                check[j]=1

                break

    return count