1
\$\begingroup\$

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]]
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ i made my algorithm use the x and y variable names of the question to make it more clear. Now it should work \$\endgroup\$ – Maarten Fabré Mar 16 '18 at 14:01
0
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ 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]]. \$\endgroup\$ – Gareth Rees Mar 16 '18 at 13:37
  • 1
    \$\begingroup\$ this can be fixed to return [[y + k, y] for y in arr if y + k in numbers] \$\endgroup\$ – Maarten Fabré Mar 16 '18 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.