Pairs with Specific Difference python

Question

Given an array arr of distinct integers and a nonnegative integer k, write a function findPairsWithGivenDifference that returns an array of all pairs [x,y] in arr, such that x - y = k. If no such pairs exist, return an empty array.

In your solution, try to reduce the memory usage while maintaining time efficiency. Prove the correctness of your solution and analyze its time and space complexities.

Note: the order of the pairs in the output array should maintain the order of the y element in the original array.

Examples:

input: arr = [0, -1, -2, 2, 1], k = 1 output: [[1, 0], [0, -1], [-1, -2], [2, 1]]

input: arr = [1, 7, 5, 3, 32, 17, 12], k = 17

output: []

Constraints:

[time limit] 5000ms

[input] array.integer arr

0 ≤ arr.length ≤ 100 [input]integer k

k ≥ 0 [output] array.array.integer

def find_pairs_with_given_difference(arr, k):
 numbers = set()
 output = []
 # insert arr element into set
 for i in range(len(arr)):
 numbers.add(arr[i])
 # loop through the entire array
 for i in range(len(arr)):
 difference = arr[i]
 if difference - k in numbers:
 output.append([difference,(difference - k)])
 return output
Test case #1
Input: [4,1], 3
Expected: [[4,1]]
Actual: [[4, 1]]
Test Case #2
Input: [1,5,11,7], 4
Expected: [[5,1],[11,7]]

Answer 1

The code in the post (and in WolframH's answer) has a bug:

>>> find_pairs_with_given_difference([1], 0)
[[1, 1]]

There is no pair of items [1, 1] in the input array.

Answer 2

If the array were longer, I word first sort it to a list of tuples (item, original_position), and then for each element, start iterating forwards, until the threshold k is passed

sorted_items = [(item, pos) for pos, item in sorted(enumerate(arr), key=lambda x: x[1])]

[(-2, 2), (-1, 1), (0, 0), (1, 4), (2, 3)]

def find_pairs(sorted_items):
 for i, (y, pos) in enumerate(sorted_items):
 for x, pos2 in takewhile(lambda x: x[0] - y <= k, sorted_items[i+1:]):
 if x - y == k:
 yield pos, [x, y]

[(2, [-1, -2]), (1, [0, -1]), (0, [1, 0]), (4, [2, 1])]

list(pair for _, pair in sorted(find_pairs(sorted_items)))

[[1, 0], [0, -1], [-1, -2], [2, 1]]

This way you eliminate the quadratic growth of the iterations

• Maarten Fabré: i made my algorithm use the x and y variable names of the question to make it more clear. Now it should work

Answer 3

I would try to optimize by iterating through the list while adding to the set at the same time rather than building a set separately. See my answer below:

#Time: O(n)
#Space: O(n)
def solveSet(arr, k):
 memo = set()
 answer = []
 for i in range(len(arr)):
 ldiff = arr[i] - k
 rdiff = k + arr[i]
 if ldiff in memo:
 answer.append([ldiff,arr[i]])
 if rdiff in memo:
 answer.append([arr[i],rdiff])
 memo.add(arr[i])
 return answer
print(solveSet(arr, k))

Answer 4

The set numbers can be created directly from an iterable, in this case

numbers = set(arr)

You should iterate over the items of arr, not indices:

for y in arr:
 if y - k in numbers:
 output.append([y, y - k])

Or use a list comprehension, which is more or less made for things like this:

output = [[y, y - k] for y in arr if y - k in numbers]

Put everything together and your function becomes very short and readable:

def find_pairs_with_given_difference(arr, k):
 numbers = set(arr)
 return [[y, y - k] for y in arr if y - k in numbers]

• Gareth Rees: This produces the output in the wrong order. The problem description says that find_pairs_with_given_difference([0, -1, -2, 2, 1], 1) should return [[1, 0], [0, -1], [-1, -2], [2, 1]], but the code in this answer returns [[0, -1], [-1, -2], [2, 1], [1, 0]].
• Maarten Fabré: this can be fixed to return [[y + k, y] for y in arr if y + k in numbers]