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

Answer 3

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]