Nearest neighbor distance for k=1 in units of time

This base up on the groupby to split your original df into small unique key dataframe , then we using numpy broadcast to speed up the whole calculation

df.Date=pd.to_datetime(df.Date)
l=[]
for _, x in df.groupby('A_key'):
    s=np.abs((x['Date'].values - x['Date'].values[:,None])).astype('timedelta64[D]').astype(int)
    s[[np.arange(len(s))] * 2]=9999
    l.append(np.min(s,1))

df['New']=np.concatenate(l)
df
Out[501]: 
  A_key       Date  New
0    A1 2016-05-03  145
1    A1 2016-09-25  145
2    A2 2015-02-25    0
3    A2 2015-02-25    0
4    A3 2015-10-04  163
5    A3 2016-03-15   26
6    A3 2016-04-10   26
7    A4 2015-09-26    0
8    A4 2015-09-26    0

You could convert the dates to Epoch using this code:

import time
date_time = '2016-05-03 00:00:00'
pattern = '%Y-%m-`enter code here`%d %H:%M:%S'
epoch = int(time.mktime(time.strptime(date_time, pattern)))

Then, simply subtract the value from its neighbor value. Note, the result is going to be in milliseconds, so you will have to divide by (1000*60*60*24) to convert it to days.

You have already sorted by date in each key. So all you need is compute the distance to the next and previous date in the same key. I tried this (in Swift) to compute distance between 2 dates as formatted as 2015-05-22

func dist(_ d1: String, _ d2: String) -> Int {
    let dateFormatter = DateFormatter()
    dateFormatter.dateFormat = "YYYY-MM-DD"

    if let date1 = dateFormatter.date(from: d1), let date2 = dateFormatter.date(from: d2) {
        let distance = date1.timeIntervalSince(date2) / 86400
        return abs(Int(distance))
    } else { return 0 }
}

print(dist("2015-05-25", "2015-05-22"))

You can now loop through the values in one key to compute the minimum distance for a given key (except itself of course)

Hi here is a possible solution using only Pandas

Let's give the current index a name (for convenience and be sure that we recover everything well)

df['Date'] = df['Date'].astype('datetime64[ns]')
df.index.name = 'id'

We are first going to sort by date and apply a function to each group, it is important to note that we are going to rely on the fact that pandas preserve the row order inside a group (see documentation)

sorted_df = sorted_df = df.sort_values('Date')
result_df = sorted_df.groupby('A_key').apply(nearest_date_distance)

So now let see what we have inside the nearest_date_distance function The function relies on the fact that the Date will be sorted , therefore we compute the time to the date before and the time to the date after, the difference between the current day and the next day is negative that's why we add the .abs().Finally we take the minimum between these two distances (btw the min operator won't take the missing value (NaT) that you have for the first row of time_to_before and last row of time to after)

def nearest_date_distance(sub):
    time_to_before = sub['Date'].diff()
    time_to_after = sub['Date'].diff(-1).abs()
    nearest_date_distance = pd.concat([time_to_before, time_to_after],axis=1).min(axis=1)
    nearest_date_distance.name = 'Distance'
    return nearest_date_distance

Finally I lied a bit result_df will be a MultiIndex Serie (not a dataframe) of this form:

A_key  id
A1     0    145 days
       1    145 days
A2     2      0 days
       3      0 days
A3     4    163 days
       5     26 days
       6     26 days
A4     7      0 days
       8      0 days

We can easily convert it to a DataFrame and having a proper naming for our original index helps to see that everything is indexed the same as in the original df.

result_df =sorted_df.groupby('A_key').apply(nearest_date_distance).reset_index(level=0)

    A_key   Distance
id      
0   A1  145 days
1   A1  145 days
2   A2  0 days
3   A2  0 days
4   A3  163 days
5   A3  26 days
6   A3  26 days
7   A4  0 days
8   A4  0 days

and if you need the Date on the resulting Dataframe result_df['Date'] = df['Date']should do the trick :)