HT: Finding Common Elements

We have two arrays, arr1 = {1, 2, 3} and arr2 = {4, 5, 6}, and we want to check if they have any common elements.

---

1️⃣ Using a for Loop (Brute Force)

🔹 Code

public class ArrayComparison {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3};
        int[] arr2 = {4, 5, 6};

        boolean hasCommon = false;

        // Nested for-loop to compare elements
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr2.length; j++) {
                if (arr1[i] == arr2[j]) {
                    hasCommon = true;
                    break; // Exit inner loop if a common element is found
                }
            }
            if (hasCommon) break;
        }

        System.out.println("Common element exists: " + hasCommon);
    }
}

🔹 Time Complexity

• O(N × M) (nested for loop, where N and M are the array lengths)
• Performance decreases significantly as the arrays grow larger.

---

2️⃣ Using a HashSet (Optimized Approach)

🔹 Code

import java.util.HashSet;

public class HashSetComparison {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3};
        int[] arr2 = {4, 5, 6};

        HashSet<Integer> set = new HashSet<>();

        // Store first array elements in HashSet
        for (int num : arr1) {
            set.add(num);
        }

        // Check if any element from the second array exists in HashSet
        boolean hasCommon = false;
        for (int num : arr2) {
            if (set.contains(num)) {
                hasCommon = true;
                break; // Stop if a common element is found
            }
        }

        System.out.println("Common element exists: " + hasCommon);
    }
}

🔹 Time Complexity

• O(N) + O(M) = O(N + M)
  • Adding elements to HashSet: O(N)
  • Checking for common elements: O(M)
• This approach is significantly faster than the brute force method.