Problem overview
The method intersection(int[] first, int[] second) returns the numbers that appear in both arrays. Each number appears once in the result, however often it occurs in the inputs, and the result is sorted in ascending order. Both arrays have between 1 and 1,000 elements, with values from -1000 to 1000.
For first = [1, 2, 2, 1] and second = [2, 2] the answer is [2]. For first = [4, 9, 5] and second = [9, 4, 9, 8, 4] the answer is [4, 9]: both numbers are in both arrays, and the repeats in second don't count twice.
The lesson asks for O(n + m) time, plus the time to sort the shared numbers, where n and m are the two lengths.
Approach: remember one array, scan the other
Checking every number of first against every number of second costs O(n * m). A hash map answers "is this number present?" in constant time on average, so remembering one array lets you scan the other in a single pass.
The lesson stores the numbers of the shorter array as map keys, each with a count of 0, and then walks the longer array. Whenever a number from the longer array is a key, its count goes up. At the end, a key with a count above 0 was seen in both arrays. Keys that were never matched stay at 0 and are ignored. Putting the shorter array in the map keeps the map small. Because a key is stored once, duplicates in the shorter array collapse automatically, and the result has no repeats.
A HashMap gives no promise about the order of its entries, and the expected answer is sorted. So the shared numbers are collected in a list and sorted at the end. Sorting k shared numbers costs O(k log k), which is the extra time the statement mentions.
For first = [4, 9, 5] and second = [9, 4, 9, 8, 4], first is shorter, so the map starts as {4=0, 9=0, 5=0}. Scanning second raises 9 to 2, then 4 to 2, ignores 8, so the map ends as {4=2, 9=2, 5=0} in some order. Keys 4 and 9 have positive counts, and the sorted result is [4, 9].
Step by step
- Name the two arrays
nums1andnums2as aliases of the parameters. Both names refer to the original arrays: nothing is copied. The aliases let the next step swap them without touchingfirstandsecond. - Create the map
dfromIntegertoInteger: a number mapped to how many times the other array contains it. - Make
nums1the shorter array. If it is longer, swap the two references usingtmp. Only the references move, so the swap costs nothing. - Loop over
nums1. - Store each number with a count of 0. A repeated number just overwrites its own entry.
- Loop over
nums2to look for matches. - Skip numbers that aren't keys.
containsKeytells you whether the number came fromnums1. If it didn't,continuemoves to the next number. - Count the matches. Otherwise the number is in both arrays, and
d.put(i, d.get(i) + 1)raises its count. - Prepare the result list as an
ArrayListofInteger. - Walk the map's entries with
entrySet(), reading each key askand each count asval. - Keep the shared numbers. A positive count means the number was found in both arrays, so add it to
result. - Sort and convert.
Collections.sortorders the list. The method must returnint[], andresult.stream().mapToInt(x -> x).toArray()unboxes eachIntegerinto a new primitive array.
The solution in Java
class Solution {
public int[] intersection(int[] first, int[] second) {
int[] nums1 = first, nums2 = second;
Map<Integer, Integer> d = new HashMap<>();
if (nums1.length > nums2.length) {
int[] tmp = nums1;
nums1 = nums2;
nums2 = tmp;
}
for (int i : nums1) {
d.put(i, 0);
}
for (int i : nums2) {
if (!d.containsKey(i)) continue;
else d.put(i, d.get(i) + 1);
}
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : d.entrySet()) {
int k = e.getKey();
int val = e.getValue();
if (val > 0) result.add(k);
}
Collections.sort(result);
return result.stream().mapToInt(x -> x).toArray();
}
}
The code uses java.util types (Map, HashMap, List, ArrayList, Collections), so a standalone file needs import java.util.*;.
The Java details worth a look:
- Boxing. A map holds objects, not primitives, so it is declared with
Integer.d.put(i, 0)boxes theintvalues automatically, andint k = e.getKey()unboxes them. Unboxing anullwould throw, but every key here comes with a value. getaftercontainsKey.d.get(i)returnsnullfor a missing key, andnull + 1would throw aNullPointerException. ThecontainsKeycheck before it guarantees the key exists.- Loop variables named
itwice. Eachfor-each declares its owniwith scope limited to that loop, so reusing the name is legal. HashMaporder is unspecified. Never return the numbers in the order the entries come out. The sort at the end makes the output deterministic.- The stream line.
mapToInt(x -> x)turns a stream ofIntegerinto anIntStreamofint, andtoArray()returns a newint[]. CallingtoArray()on the list itself would give anObject[], not anint[].
Complexity
Time: O(n + m) plus the sort. Filling the map takes one pass over the shorter array, and counting takes one pass over the longer one. Each put, get and containsKey is O(1) on average. Walking the map costs time proportional to its size. Sorting k shared numbers adds O(k log k), and k is at most the length of the shorter array.
Space: O(min(n, m)). The map holds at most one entry per distinct number of the shorter array. The result list is no larger than that.
Edge cases and common mistakes
- No shared numbers.
[1, 2]and[3, 4]give an empty array, because every count stays 0. - Duplicates.
[1, 2, 2, 1]and[2, 2]give[2], not[2, 2]. The map has one entry per number, so the result can't repeat. - Negative numbers.
[-3, 0, 5, -3]and[5, -3, 7]give[-3, 5]. Sorting puts negatives first. - Keeping every key. Adding all keys instead of only those with a positive count would return numbers that appear in just one array.
- Skipping the sort. The numbers come out in whatever order the map holds them, which may differ from ascending order.
Testing
[1, 2, 2, 1],[2, 2]gives[2].[4, 9, 5],[9, 4, 9, 8, 4]gives[4, 9].[-3, 0, 5, -3],[5, -3, 7]gives[-3, 5].[1, 2],[3, 4]gives[].
