CareerCup

how about converting the Inputs to BST then storing the root as base and moving to other elements to search that whether the difference id K if it finds it delete the root and and node and continues the process. otherwise if it reaches end of tree without any term matching the difference then it only deletes the root and moves on. the cost in this will only be O(log n) as we keep on deleting

in Python

[ (i-k,i) for i in array if i-k in array]

There are several approaches here.

1. Put values of array to Hash (HashSet for instance). Iterate through array and for current a[i] check if (a[i] - k) exists in Hash. It takes O(n) complexity, O(n) space.

2. Sort array. Iterate through array and for current a[i] find (a[i] - k) item using binary search.
It takes O(n log n) complexity without additional space.

So final chose depends on your requirements

Here the fisrt approach:

public class SubtractResult {

    public static void main(String[] args) {
        new SubtractResult().solve();
    }

    public void solve() {
        Integer a[] = {3,6,10,13};
        int k = 3;

        printPairs(a, k);
    }

    public void printPairs(Integer[] a, int k) {
        Set<Integer> set = new HashSet<Integer>(Arrays.asList(a));

        for (Integer i : a) {
            if (set.contains(i - k)) {
                System.out.println(i + ", " + (i - k));
            }
        }
    }
}

If the input is {4, 4, 1, 1, 4, 5} and k = 0, is the correct answer (1,1) (4,4) or is it okay to have (1,1), (4,4) and (4,4) ?