2
\$\begingroup\$

A = [9, 1, 4, 2, 5] k unique integers
B = [3, 1, 8, 7, 6, 5] n unique integers
Intersection => [1, 5]

Find an algorithm that uses \$O(1)\$ space (the space used by the return variable is not considered) and runs as fast as possible to find the intersection of the arrays.

private static List<Integer> getIntersectionO1Space(List<Integer> a, List<Integer> b)
{

    List<Integer> intersection = new ArrayList<Integer>();
    mergeSort(a); //Time O(k log k), space O(1)

    for (Integer n : b) //O(n log k)
    {
        int r = Collections.binarySearch(a, n); //O(log k)
        if (r > -1)
            intersection.add(n);
    }
    return intersection;
}

So the total time complexity is \$O(\max(k,n) \log k)\$.

But my solution doesn't utilize the property that "no duplicate elements in the array". I wonder whether there is an algorithm that uses the property and runs faster.

\$\endgroup\$
  • \$\begingroup\$ I think I made mistake on time complexity. I think it should be \$O(k\log k+n\log k)\$, not \$O(max(k,n)\log k)\$. \$\endgroup\$ – Gqqnbig Jan 15 '15 at 23:06
  • \$\begingroup\$ You can not do any type of sorting. You can not use any auxiliary collection besides a List<Integer>. They are forcing you to compare the arrays as they come. The algorithm that fits these requirments will run in O(n^2), if I'm not mistaken. \$\endgroup\$ – Bruno Costa Jan 15 '15 at 23:09
3
\$\begingroup\$

Your solution doesn't have explicit instructions to use the property that no duplicate elements in the array, but it naturally benefits from it. The binary search is slightly faster because it doesn't need to visit duplicate elements unnecessarily. The iteration is faster too for the same reason. Actually if there were duplicates it would be a lot tougher problem to solve.

The only way I see to make it faster won't be possible in \$O(1)\$ space: instead of sorting the first list, you could put it in a hash set. That way the binary search becomes a hash lookup, which is much faster, but at the expense of doubling the memory usage of one of the lists.

When you have two lists of very different sizes, I'm wondering if it can be said that making the shortest to be the first or the second will yield better performance in general.

\$\endgroup\$
2
\$\begingroup\$

Strictly speaking, the presence of merge sort disqualifies the solution: standard merge sort has \$O(n)\$ space complexity (an in-place merge sort still requires \$O(\log n)\$ space). Use heap sort instead.

EDIT.

There is no much you can do to speed it up in terms of asymptotical behavior. You can shave off some cycles by not using binary search (which is horribly referentially unlocal). Instead, sort both arrays and merge-intersect them, along the lines of

sort(a);
sort(b);
for (i = 0, j = 0; i < size(a) && j < size(b); ) {
    if (a[i] < b[j])
        ++i;
    else if (a[i] > b[j])
        ++j;
    else {
        handle_intersection();
        ++i;
        ++j;
    }
\$\endgroup\$
  • \$\begingroup\$ Yes, you are right. Merge sort for LinkedList is O(1), but for array is not. \$\endgroup\$ – Gqqnbig Jan 15 '15 at 22:40
  • \$\begingroup\$ @LoveRight I am not sure about LinkedList either. Anyway, see update. \$\endgroup\$ – vnp Jan 15 '15 at 22:44
  • \$\begingroup\$ What does "horribly referentially unlocal" means? Binary search is tail recursion, uses O(1) space. \$\endgroup\$ – Gqqnbig Jan 16 '15 at 0:23
  • 1
    \$\begingroup\$ It accesses an array (at least, initially) in locations very far apart, causing unnecessary and unpredictable cache misses (and possibly page faults). This would only show up in case of very large arrays though. \$\endgroup\$ – vnp Jan 16 '15 at 0:52
  • \$\begingroup\$ Anyway, thank you for pointing out my sort method is wrong which is a big mistake. \$\endgroup\$ – Gqqnbig Jan 17 '15 at 20:34
1
\$\begingroup\$

But my solution doesn't utilize the property that "no duplicate elements in the array".

But it does. Try adding a duplicate 5 to b:

A = [9, 1, 4, 2, 5]
B = [3, 1, 8, 7, 6, 5, 5]
Intersection => [1, 5, 5] Wrong!

You get an incorrect result. To handle that correctly, you'd have to do more work.

The bigger problem is that your solution uses \$O(\min(n, k))\$ space, not \$O(1)\$. To be precise, it uses size of the intersection space, which is limited by the smaller of \$n\$ and \$k\$. To use \$O(1)\$ space, you'd have to return either a or b as the result, not allocate new memory.

private static List<Integer> getIntersectionO1Space(List<Integer> a, List<Integer> b)
{
    // from janos' 3rd paragraph
    if ( a.size() > b.size() ) {
        getIntersectionO1Space(b, a);
    }

    mergeSort(a); //Time O(k log k), space O(1)

    for ( Iterator<Integer> iterator = b.iterator(); iterator.hasNext(); ) //O(n log k)
    {
        int r = Collections.binarySearch(a, iterator.next()); //O(log k)
        if (r < 0) {
            iterator.remove();
        }
    }

    return b;
}

To handle duplicates, you'd add

        } else {
            a.remove(r);

My test function looks like

public static void main(String[] args) {
    List<Integer> a = new ArrayList<Integer>();
    a.add(9);
    a.add(1);
    a.add(5);
    List<Integer> b = new ArrayList<Integer>();
    b.add(1);
    b.add(3);
    b.add(5);

    System.out.println(getIntersectionO1Space(a, b));
}

I didn't do much more testing than that.

\$\endgroup\$
  • \$\begingroup\$ Sorry I forgot to mention that the space used by the return variable is not considered in space complexity. But your suggestion is still valuable to me. \$\endgroup\$ – Gqqnbig Jan 15 '15 at 22:34

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.