Searching two arrays for matches, no extra memory

Question

I had an interview the other day with Amazon, and a question they asked me was pertaining to the following problem.

Given 2 integer arrays, containing any number of elements both positive and negative, find numbers that appear in both arrays.

I was able to solve this problem very easily with HashMaps so it would have O(n) computational complexity, but unfortunately this will also have O(n) space complexity. This could be done with no extra memory by iterating through all elements in each array, but this would be O(n^2).

The interviewer, after I finished explaining the HashMap method, asked if I could think of a method that would be O(n) computationally, but would not use any extra memory. I could not think of any on the fly, and have not been able to find a solution for this. Is there a way of finding these values without using extra memory, in linear time?

Note: I have posted this question on CareerCup, but everyone on there does not seem to get the concept that I need it to not use extra space, and that it has to be O(n) computationally.

Here is the code I used during the interview. It works, but just is not O(1) for space.

import java.util.*;
public class ArrayFun {
    public static void main(String[] args) {

        int[] a = {1,2,3,4};
        int[] b = {2,5,6,7,3,2,2,2,2,1,2,2,2,2};
        ArrayList<Integer> matches = ArrayFun.findMatches(a,b);
        for (int i = 0;i<matches.size();++i) {
            System.out.println(matches.get(i));
        }
    }

    public static ArrayList<Integer> findMatches(int[] a, int[] b) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        ArrayList<Integer> matches = new ArrayList<Integer>();
        for (int i = 0;i<a.length;++i) {
            map.put(a[i],0);
        }
        for (int i = 0;i<b.length;++i) {
            if (map.get(b[i]) != null && map.get(b[i]) == 0) {
                map.put(b[i],1);
                matches.add(b[i]);
            }
        }
        return matches;
    }
}

This code will return

1,2,3

EDIT: also when I say no additional space, and O(1), I am kind of using them interchangeably. By no additional space I mean small placeholder variables are fine but allocating new arrays is not.

Answer 1

There is no O(1) space method for finding the intersection of two unsorted sets in O(n) time.

For a data type with an unlimited range, the minimum sorting price is O(n ln n).

For a data type with a limited range radix sort provides the ability to do an in-place radix sort in O(n ln n' n") time, where n is the size of the data, n' is the number of values that can be represented, and n" has to do with the cost of checking whether two values are in the same radix group. The n" time price can be dropped in return for an O(ln n) space price.

In the special case of 32-bit integers, n' is 2^32 and n" is 1, so this would collapse to O(n) and provide a winning solution for multi-billion record sets.

For integers of unlimited size, n' and n" preclude an O(n) time solution via radix.