Common Elements In 3 Sorted Array

Lecture 51 :- Common Elements In 3 Sorted Array

To find the common elements in three sorted arrays, you can use a three-pointer approach. Here's the algorithm to achieve this:

1. Initialize three pointers ptr1, ptr2, and ptr3, each pointing to the beginning of each array (index 0).
2. While all three pointers are within the array bounds: a. If the elements at all three pointers are equal, add the element to the result vector and increment all three pointers. b. If the element at ptr1 is smaller than the elements at ptr2 and ptr3, increment ptr1. c. If the element at ptr2 is smaller than the elements at ptr1 and ptr3, increment ptr2. d. If the element at ptr3 is smaller than the elements at ptr1 and ptr2, increment ptr3.
3. Continue until any one of the pointers reaches the end of its respective array.

Here's the C++ code to find the common elements in three sorted arrays:

cppCopy code

#include <iostream> #include <vector> std::vector<int> findCommonElements(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3) {    std::vector<int> result;    int ptr1 = 0, ptr2 = 0, ptr3 = 0;    while (ptr1 < nums1.size() && ptr2 < nums2.size() && ptr3 < nums3.size()) {        if (nums1[ptr1] == nums2[ptr2] && nums2[ptr2] == nums3[ptr3]) {            result.push_back(nums1[ptr1]);            ptr1++;            ptr2++;            ptr3++;        } else if (nums1[ptr1] <= nums2[ptr2] && nums1[ptr1] <= nums3[ptr3]) {            ptr1++;        } else if (nums2[ptr2] <= nums1[ptr1] && nums2[ptr2] <= nums3[ptr3]) {            ptr2++;        } else {            ptr3++;        }    }    return result; } int main() {    std::vector<int> nums1 = {1, 5, 10, 20, 40, 80};    std::vector<int> nums2 = {6, 7, 20, 80, 100};    std::vector<int> nums3 = {3, 4, 15, 20, 30, 70, 80, 120};    std::vector<int> commonElements = findCommonElements(nums1, nums2, nums3);    if (!commonElements.empty()) {        std::cout << "Common elements in three sorted arrays:";        for (int element : commonElements) {            std::cout << " " << element;        }        std::cout << std::endl;    } else {        std::cout << "No common elements found." << std::endl;    }    return 0; }

Example Output:

pythonCopy code

Common elements in three sorted arrays: 20 80

In this code, the findCommonElements function finds the common elements using the three-pointer approach. The time complexity of this approach is O(n), where n is the total number of elements in the three arrays.