Problem Link - Largest Common Element in Two Arrays
Problem Statement:
You are given two arrays of positive integers, arr1 and arr2, of sizes n and m respectively. Your task is to find the largest common element that appears in both arrays. If no common element exists, return -1.
Approach:
The key idea to solve this problem efficiently is to first sort both arrays and then use a two-pointer technique to find the largest common element. Here’s how it works:
-
Sort the Arrays: Start by sorting both arrays. This helps us easily compare the largest elements first.
-
Set Up Two Pointers: Place one pointer at the end of the first array (pointing to the largest element) and another pointer at the end of the second array.
-
Compare Elements: Compare the elements at the positions of the two pointers:
- If they are equal, we’ve found a common element, and we can return it since it’s the largest.
- If the element in the first array is larger, move the pointer in the first array to the left (to the next smaller element).
- If the element in the second array is larger, move the pointer in the second array to the left.
-
Repeat the Process: Keep comparing until you either find a common element or reach the start of either array.
-
No Common Elements: If you finish the process without finding a common element, return
-1.
This method is efficient because it only compares elements when necessary, taking advantage of the fact that the arrays are sorted.
Time Complexity:
-
The time complexity is
O(n log n + m log m + n + m), wherenandmare the sizes of the arrays for sorting and two-pointer traversal. -
so the Overall time complexity:
O(n log n + m log m).
Space Complexity:
- The space complexity is
O(1), assuming sorting is done in-place and no additional space is used apart from the input arrays.