Find Intersection of Two Arrays: A LeetCode Interview Question Breakdown

In this post, we'll dive into a popular LeetCode question—finding the intersection of two arrays. This problem is an important topic for Java developers preparing for coding interviews, as it tests your knowledge of data structures like arrays and sets. We'll review two solutions: a basic approach and a more efficient optimized version, demonstrating why the second approach is superior for larger data sets.

Problem Overview

Given two arrays, the task is to find the common elements between them, returning the intersection. Both arrays may contain unique or duplicate values, but the intersection should only return unique common elements.

Initial Approach: Basic Set Operations

import java.util.Arrays;

import java.util.HashSet;

import java.util.Set;

public class FindIntesectionOfArrays {

public static void main(String[] args) throws Exception {

int[] a = { 9, 6, 4, 2 };

int[] b = { 1, 6, 4, 3 };

System.out.println("Intersection of arrays is: "

+ Arrays.toString(findInterSection(a, b)));

}

private static int[] findInterSection(int[] a, int[] b) throws Exception {

if (a.length == 0 || b.length == 0) {

throw new Exception("Either of an array is empty!");

}

Set<Integer> set1 = new HashSet<Integer>();

Set<Integer> set2 = new HashSet<Integer>();

for (int i : a) {

set1.add(i);

}

for (int j : b) {

set2.add(j);

}

set1.retainAll(set2);

return set1.stream().mapToInt(i->i).toArray();

}

}

Explanation:

• Two HashSets (set1 and set2) are created, one for each array.
• Elements from both arrays are added to the respective sets.
• The retainAll() method is used to find the common elements between the two sets.
• Finally, the intersection is converted back into an integer array.

Limitations:

• Redundancy: Two sets are used, but only one is necessary. Storing both sets results in additional memory overhead.
• Efficiency: While this approach works well for small inputs, for larger datasets, the memory usage could become excessive.

Optimized Approach: Single Set for Efficiency

Now, let's look at an optimized solution that improves both memory usage and performance by utilizing a single set.

import java.util.Arrays;

import java.util.HashSet;

import java.util.Set;

public class FindIntesectionOfArrays {

public static void main(String[] args) throws Exception {

int[] a = { 9, 6, 4, 2 };

int[] b = { 1, 6, 4, 3 };

System.out.println("Intersection of arrays is: "

+ Arrays.toString(findInterSection(a, b)));

}

private static int[] findInterArraySectionEfficiently(int[] a, int[] b) {

if (a == null || b == null || a.length == 0 || b.length == 0) {

throw new IllegalArgumentException("Either of the arrays is null or empty!");

}

Set<Integer> set1 = new HashSet<>();

for (int i : a) {

set1.add(i);

}

Set<Integer> intersection = new HashSet<>();

for (int j : b) {

if (set1.contains(j)) {                 // Only add common elements to the intersection set

intersection.add(j);

}

}

return intersection.stream().mapToInt(i -> i).toArray();

}

}

Explanation:

• We use only one HashSet (set1) to store elements of the first array.
• Instead of storing both arrays, we loop through the second array (b) and check for common elements using set1.contains(j).
• Common elements are stored in a separate intersection set.
• This method optimizes memory usage by eliminating the need to store both arrays in sets.

Why is the Optimized Solution More Efficient?

1. Memory Efficiency: By using only one set (set1), we reduce memory usage by half. We avoid storing the second array as a set.

2. Performance: In the optimized solution, we only perform lookups for each element of the second array, rather than storing both arrays in sets. HashSet's contains() operation has an average time complexity of O(1), meaning this check is efficient.

3. Simplicity: The code is cleaner and easier to maintain. It also avoids unnecessary operations like creating and retaining two sets.

Time Complexity Comparison

• First Solution:

  • Time Complexity: O(n + m), where n is the size of the first array and m is the size of the second array. This is because we need to add all elements from both arrays into two sets and then perform an intersection.
  • Space Complexity: O(n + m), since we create two sets.

• Optimized Solution:

  • Time Complexity: O(n + m), the same as the first approach in terms of looping through both arrays.
  • Space Complexity: O(n), since we only store elements of the first array in a set and then store the common elements in another set.

Conclusion

In interview scenarios, demonstrating that you can optimize solutions based on both time and space complexity can give you a competitive edge. The second solution we discussed achieves the same goal—finding the intersection of two arrays—but does so more efficiently by using fewer resources.

Whether you're practicing on LeetCode or preparing for an important Java interview, understanding these optimizations can significantly enhance your problem-solving skills.

Tags:

#LeetCode #Java #DSA #CodingChallenges #ArrayManipulation #CodingInterview #TechInterview #InterviewPrep #Programming #LearnToCode