Verification: a143cc29221c9be0

Php array of an union

We strongly recommend that you click here and practice it, before moving on to the solution.

Union of arrays arr1[] and arr2[]

To find union of two sorted arrays, follow the following merge procedure : 
 



1) Use two index variables i and j, initial values i = 0, j = 0 
2) If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i. 
3) If arr1[i] is greater than arr2[j] then print arr2[j] and increment j. 
4) If both are same then print any of them and increment both i and j. 
5) Print remaining elements of the larger array.

Below is the implementation of the above approach : 
 

C++

#include

using namespace std;

void printUnion(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

    while (i

        if (arr1[i]

            cout " ";

        else if (arr2[j]

            cout " ";

        else {

            cout " ";

            i++;

        }

    }

    while (i

        cout " ";

    while (j

        cout " ";

}

int main()

{

    int arr1[] = { 1, 2, 4, 5, 6 };

    int arr2[] = { 2, 3, 5, 7 };

    int m = sizeof(arr1) / sizeof(arr1[0]);

    int n = sizeof(arr2) / sizeof(arr2[0]);

    printUnion(arr1, arr2, m, n);

    return 0;

}

C

#include

void printUnion(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

    while (i

        if (arr1[i]

            printf(" %d ", arr1[i++]);

        else if (arr2[j]

            printf(" %d ", arr2[j++]);

        else {

            printf(" %d ", arr2[j++]);

            i++;

        }

    }

    while (i

        printf(" %d ", arr1[i++]);

    while (j

        printf(" %d ", arr2[j++]);

}

int main()

{

    int arr1[] = { 1, 2, 4, 5, 6 };

    int arr2[] = { 2, 3, 5, 7 };

    int m = sizeof(arr1) / sizeof(arr1[0]);

    int n = sizeof(arr2) / sizeof(arr2[0]);

    printUnion(arr1, arr2, m, n);

    getchar();

    return 0;

}

Java

class FindUnion {

    static int printUnion(int arr1[], int arr2[], int m, int n)

    {

        int i = 0, j = 0;

        while (i

            if (arr1[i]

                System.out.print(arr1[i++] + " ");

            else if (arr2[j]

                System.out.print(arr2[j++] + " ");

            else {

                System.out.print(arr2[j++] + " ");

                i++;

            }

        }

        while (i

            System.out.print(arr1[i++] + " ");

        while (j

            System.out.print(arr2[j++] + " ");

        return 0;

    }

    public static void main(String args[])

    {

        int arr1[] = { 1, 2, 4, 5, 6 };

        int arr2[] = { 2, 3, 5, 7 };

        int m = arr1.length;

        int n = arr2.length;

        printUnion(arr1, arr2, m, n);

    }

}

Python

def printUnion(arr1, arr2, m, n):

    i, j = 0, 0

    while i and j

        if arr1[i]

            print(arr1[i])

            i += 1

        elif arr2[j]

            print(arr2[j])

            j+= 1

        else:

            print(arr2[j])

            j += 1

            i += 1

    while i

        print(arr1[i])

        i += 1

    while j

        print(arr2[j])

        j += 1

arr1 = [1, 2, 4, 5, 6]

arr2 = [2, 3, 5, 7]

m = len(arr1)

n = len(arr2)

printUnion(arr1, arr2, m, n)

C#

using System;

class GFG {

    static int printUnion(int[] arr1,

                          int[] arr2, int m, int n)

    {

        int i = 0, j = 0;

        while (i

            if (arr1[i]

                Console.Write(arr1[i++] + " ");

            else if (arr2[j]

                Console.Write(arr2[j++] + " ");

            else {

                Console.Write(arr2[j++] + " ");

                i++;

            }

        }

        while (i

            Console.Write(arr1[i++] + " ");

        while (j

            Console.Write(arr2[j++] + " ");

        return 0;

    }

    public static void Main()

    {

        int[] arr1 = { 1, 2, 4, 5, 6 };

        int[] arr2 = { 2, 3, 5, 7 };

        int m = arr1.Length;

        int n = arr2.Length;

        printUnion(arr1, arr2, m, n);

    }

}

PHP

function printUnion($arr1, $arr2,

                         $m, $n)

{

    $i = 0; $j = 0;

    while ($i $m && $j $n)

    {

        if ($arr1[$i] $arr2[$j])

            echo($arr1[$i++] . " ");

        else if ($arr2[$j] $arr1[$i])

            echo($arr2[$j++] . " ");

        else

        {

            echo($arr2[$j++] . " ");

            $i++;

        }

    }

    while($i $m)

        echo($arr1[$i++] . " ");

    while($j $n)

        echo($arr2[$j++] . " ");

}

$arr1 = array(1, 2, 4, 5, 6);

$arr2 = array(2, 3, 5, 7);

$m = sizeof($arr1);

$n = sizeof($arr2);

printUnion($arr1, $arr2, $m, $n);

?>

Output: 
 

1 2 3 4 5 6 7 

Time Complexity : O(m + n)
Handling duplicates in any of the array : Above code does not handle duplicates in any of the array. To handle the duplicates, just check for every element whether adjacent elements are equal. 
Below is the implementation of this approach. 
 

Java

class FindUnion {

    static void UnionArray(int arr1[],

                           int arr2[])

    {

        int m = arr1[arr1.length - 1];

        int n = arr2[arr2.length - 1];

        int ans = 0;

        if (m > n) {

            ans = m;

        }

        else

            ans = n;

        int newtable[] = new int[ans + 1];

        System.out.print(arr1[0] + " ");

        ++newtable[arr1[0]];

        for (int i = 1; i

            if (arr1[i] != arr1[i - 1]) {

                System.out.print(arr1[i] + " ");

                ++newtable[arr1[i]];

            }

        }

        for (int j = 0; j

            if (newtable[arr2[j]] == 0) {

                System.out.print(arr2[j] + " ");

                ++newtable[arr2[j]];

            }

        }

    }

    public static void main(String args[])

    {

        int arr1[] = { 1, 2, 2, 2, 3 };

        int arr2[] = { 2, 3, 4, 5 };

        UnionArray(arr1, arr2);

    }

}

Python3

def UnionArray(arr1, arr2):

    m = arr1[-1]

    n = arr2[-1]

    ans = 0

    if m > n:

        ans = m

    else:

        ans = n

    newtable = [0] * (ans + 1)

    print(arr1[0], end = " ")

    newtable[arr1[0]] += 1

    for i in range(1, len(arr1)):

        if arr1[i] != arr1[i - 1]:

            print(arr1[i], end = " ")

            newtable[arr1[i]] += 1

    for j in range(0, len(arr2)):

        if newtable[arr2[j]] == 0:

            print(arr2[j], end = " ")

            newtable[arr2[j]] += 1

if __name__ == "__main__":

    arr1 = [1, 2, 2, 2, 3]

    arr2 = [2, 3, 4, 5]

    UnionArray(arr1, arr2)

C#

using System;

class GFG {

    static void UnionArray(int[] arr1,

                           int[] arr2)

    {

        int m = arr1[arr1.Length - 1];

        int n = arr2[arr2.Length - 1];

        int ans = 0;

        if (m > n)

            ans = m;

        else

            ans = n;

        int[] newtable = new int[ans + 1];

        Console.Write(arr1[0] + " ");

        ++newtable[arr1[0]];

        for (int i = 1; i

            if (arr1[i] != arr1[i - 1]) {

                Console.Write(arr1[i] + " ");

                ++newtable[arr1[i]];

            }

        }

        for (int j = 0; j

            if (newtable[arr2[j]] == 0) {

                Console.Write(arr2[j] + " ");

                ++newtable[arr2[j]];

            }

        }

    }

    public static void Main()

    {

        int[] arr1 = { 1, 2, 2, 2, 3 };

        int[] arr2 = { 2, 3, 4, 5 };

        UnionArray(arr1, arr2);

    }

}

Thanks to Rajat Rawat for suggesting this solution.
 

Intersection of arrays arr1[] and arr2[]

To find intersection of 2 sorted arrays, follow the below approach : 
 



1) Use two index variables i and j, initial values i = 0, j = 0 
2) If arr1[i] is smaller than arr2[j] then increment i. 
3) If arr1[i] is greater than arr2[j] then increment j. 
4) If both are same then print any of them and increment both i and j.

Below is the implementation of the above approach :
 

C++

#include

using namespace std;

void printIntersection(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

    while (i

        if (arr1[i]

            i++;

        else if (arr2[j]

            j++;

        else

        {

            cout " ";

            i++;

            j++;

        }

    }

}

int main()

{

    int arr1[] = { 1, 2, 4, 5, 6 };

    int arr2[] = { 2, 3, 5, 7 };

    int m = sizeof(arr1) / sizeof(arr1[0]);

    int n = sizeof(arr2) / sizeof(arr2[0]);

    printIntersection(arr1, arr2, m, n);

    return 0;

}

C

#include

void printIntersection(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

    while (i

        if (arr1[i]

            i++;

        else if (arr2[j]

            j++;

        else

        {

            printf(" %d ", arr2[j++]);

            i++;

        }

    }

}

int main()

{

    int arr1[] = { 1, 2, 4, 5, 6 };

    int arr2[] = { 2, 3, 5, 7 };

    int m = sizeof(arr1) / sizeof(arr1[0]);

    int n = sizeof(arr2) / sizeof(arr2[0]);

    printIntersection(arr1, arr2, m, n);

    getchar();

    return 0;

}

Java

class FindIntersection {

    static void printIntersection(int arr1[], int arr2[], int m, int n)

    {

        int i = 0, j = 0;

        while (i

            if (arr1[i]

                i++;

            else if (arr2[j]

                j++;

            else {

                System.out.print(arr2[j++] + " ");

                i++;

            }

        }

    }

    public static void main(String args[])

    {

        int arr1[] = { 1, 2, 4, 5, 6 };

        int arr2[] = { 2, 3, 5, 7 };

        int m = arr1.length;

        int n = arr2.length;

        printIntersection(arr1, arr2, m, n);

    }

}

Python

def printIntersection(arr1, arr2, m, n):

    i, j = 0, 0

    while i and j

        if arr1[i]

            i += 1

        elif arr2[j]

            j+= 1

        else:

            print(arr2[j])

            j += 1

            i += 1

arr1 = [1, 2, 4, 5, 6]

arr2 = [2, 3, 5, 7]

m = len(arr1)

n = len(arr2)

printIntersection(arr1, arr2, m, n)

C#

using System;

class GFG {

    static void printIntersection(int[] arr1,

                                  int[] arr2, int m, int n)

    {

        int i = 0, j = 0;

        while (i

            if (arr1[i]

                i++;

            else if (arr2[j]

                j++;

            else {

                Console.Write(arr2[j++] + " ");

                i++;

            }

        }

    }

    public static void Main()

    {

        int[] arr1 = { 1, 2, 4, 5, 6 };

        int[] arr2 = { 2, 3, 5, 7 };

        int m = arr1.Length;

        int n = arr2.Length;

        printIntersection(arr1, arr2, m, n);

    }

}

PHP

function printIntersection($arr1, $arr2,

                                $m, $n)

{

    $i = 0 ;

    $j = 0;

    while ($i $m && $j $n)

    {

        if ($arr1[$i] $arr2[$j])

            $i++;

        else if ($arr2[$j] $arr1[$i])

            $j++;

        else

        {

            echo $arr2[$j], " ";

            $i++;

            $j++;

        }

    }

}

$arr1 = array(1, 2, 4, 5, 6);

$arr2 = array(2, 3, 5, 7);

$m = count($arr1);

$n = count($arr2);

printIntersection($arr1, $arr2, $m, $n);

?>

Output: 
 

2 5

Time Complexity : O(m + n)

Handling duplicate in Arrays :
Above code does not handle duplicate elements in arrays. The intersection should not count duplicate elements. To handle duplicates just check whether current element is already present in intersection list. Below is the implementation of this approach.

Python3

def IntersectionArray(a, b, n, m):

    Intersection = []

    i = j = 0

    while i and j

        if a[i] == b[j]:

            if len(Intersection) > 0 and Intersection[-1] == a[i]:

                i+= 1

                j+= 1

            else:

                Intersection.append(a[i])

                i+= 1

                j+= 1

        elif a[i]

            i+= 1

        else:

            j+= 1

    if not len(Intersection):

        return [-1]

    return Intersection

if __name__ == "__main__":

    arr1 = [1, 2, 2, 3, 4]

    arr2 = [2, 2, 4, 6, 7, 8]

    l = IntersectionArray(arr1, arr2, len(arr1), len(arr2))

    print(*l)

Output: 
 

2 4

Time Complexity : O(m + n) 
Auxiliary Space : O(min(m, n))
Another approach that is useful when difference between sizes of two given arrays is significant. 
The idea is to iterate through the shorter array and do a binary search for every element of short array in big array (note that arrays are sorted). Time complexity of this solution is O(min(mLogn, nLogm)). This solution works better than the above approach when ratio of larger length to smaller is more than logarithmic order.

See following post for unsorted arrays. 
Find Union and Intersection of two unsorted arrays
Please write comments if you find any bug in above codes/algorithms, or find other ways to solve the same problem.
 

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.


C++

#include

using namespace std;

void printUnion(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

    while (i

        if (arr1[i]

            cout " ";

        else if (arr2[j]

            cout " ";

        else {

            cout " ";

            i++;

        }

    }

    while (i

        cout " ";

    while (j

        cout " ";

}

int main()

{

    int arr1[] = { 1, 2, 4, 5, 6 };

    int arr2[] = { 2, 3, 5, 7 };

    int m = sizeof(arr1) / sizeof(arr1[0]);

    int n = sizeof(arr2) / sizeof(arr2[0]);

    printUnion(arr1, arr2, m, n);

    return 0;

}

C

#include

void printUnion(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

    while (i

        if (arr1[i]

            printf(" %d ", arr1[i++]);

        else if (arr2[j]

            printf(" %d ", arr2[j++]);

        else {

            printf(" %d ", arr2[j++]);

            i++;

        }

    }

    while (i

        printf(" %d ", arr1[i++]);

    while (j

        printf(" %d ", arr2[j++]);

}

int main()

{

    int arr1[] = { 1, 2, 4, 5, 6 };

    int arr2[] = { 2, 3, 5, 7 };

    int m = sizeof(arr1) / sizeof(arr1[0]);

    int n = sizeof(arr2) / sizeof(arr2[0]);

    printUnion(arr1, arr2, m, n);

    getchar();

    return 0;

}

Java

class FindUnion {

    static int printUnion(int arr1[], int arr2[], int m, int n)

    {

        int i = 0, j = 0;

        while (i

            if (arr1[i]

                System.out.print(arr1[i++] + " ");

            else if (arr2[j]

                System.out.print(arr2[j++] + " ");

            else {

                System.out.print(arr2[j++] + " ");

                i++;

            }

        }

        while (i

            System.out.print(arr1[i++] + " ");

        while (j

            System.out.print(arr2[j++] + " ");

        return 0;

    }

    public static void main(String args[])

    {

        int arr1[] = { 1, 2, 4, 5, 6 };

        int arr2[] = { 2, 3, 5, 7 };

        int m = arr1.length;

        int n = arr2.length;

        printUnion(arr1, arr2, m, n);

    }

}

Python

def printUnion(arr1, arr2, m, n):

    i, j = 0, 0

    while i and j

        if arr1[i]

            print(arr1[i])

            i += 1

        elif arr2[j]

            print(arr2[j])

            j+= 1

        else:

            print(arr2[j])

            j += 1

            i += 1

    while i

        print(arr1[i])

        i += 1

    while j

        print(arr2[j])

        j += 1

arr1 = [1, 2, 4, 5, 6]

arr2 = [2, 3, 5, 7]

m = len(arr1)

n = len(arr2)

printUnion(arr1, arr2, m, n)

C#

using System;

class GFG {

    static int printUnion(int[] arr1,

                          int[] arr2, int m, int n)

    {

        int i = 0, j = 0;

        while (i

            if (arr1[i]

                Console.Write(arr1[i++] + " ");

            else if (arr2[j]

                Console.Write(arr2[j++] + " ");

            else {

                Console.Write(arr2[j++] + " ");

                i++;

            }

        }

        while (i

            Console.Write(arr1[i++] + " ");

        while (j

            Console.Write(arr2[j++] + " ");

        return 0;

    }

    public static void Main()

    {

        int[] arr1 = { 1, 2, 4, 5, 6 };

        int[] arr2 = { 2, 3, 5, 7 };

        int m = arr1.Length;

        int n = arr2.Length;

        printUnion(arr1, arr2, m, n);

    }

}

PHP

function printUnion($arr1, $arr2,

                         $m, $n)

{

    $i = 0; $j = 0;

    while ($i $m && $j $n)

    {

        if ($arr1[$i] $arr2[$j])

            echo($arr1[$i++] . " ");

        else if ($arr2[$j] $arr1[$i])

            echo($arr2[$j++] . " ");

        else

        {

            echo($arr2[$j++] . " ");

            $i++;

        }

    }

    while($i $m)

        echo($arr1[$i++] . " ");

    while($j $n)

        echo($arr2[$j++] . " ");

}

$arr1 = array(1, 2, 4, 5, 6);

$arr2 = array(2, 3, 5, 7);

$m = sizeof($arr1);

$n = sizeof($arr2);

printUnion($arr1, $arr2, $m, $n);

?>

Java

class FindUnion {

    static void UnionArray(int arr1[],

                           int arr2[])

    {

        int m = arr1[arr1.length - 1];

        int n = arr2[arr2.length - 1];

        int ans = 0;

        if (m > n) {

            ans = m;

        }

        else

            ans = n;

        int newtable[] = new int[ans + 1];

        System.out.print(arr1[0] + " ");

        ++newtable[arr1[0]];

        for (int i = 1; i

            if (arr1[i] != arr1[i - 1]) {

                System.out.print(arr1[i] + " ");

                ++newtable[arr1[i]];

            }

        }

        for (int j = 0; j

            if (newtable[arr2[j]] == 0) {

                System.out.print(arr2[j] + " ");

                ++newtable[arr2[j]];

            }

        }

    }

    public static void main(String args[])

    {

        int arr1[] = { 1, 2, 2, 2, 3 };

        int arr2[] = { 2, 3, 4, 5 };

        UnionArray(arr1, arr2);

    }

}

Python3

def UnionArray(arr1, arr2):

    m = arr1[-1]

    n = arr2[-1]

    ans = 0

    if m > n:

        ans = m

    else:

        ans = n

    newtable = [0] * (ans + 1)

    print(arr1[0], end = " ")

    newtable[arr1[0]] += 1

    for i in range(1, len(arr1)):

        if arr1[i] != arr1[i - 1]:

            print(arr1[i], end = " ")

            newtable[arr1[i]] += 1

    for j in range(0, len(arr2)):

        if newtable[arr2[j]] == 0:

            print(arr2[j], end = " ")

            newtable[arr2[j]] += 1

if __name__ == "__main__":

    arr1 = [1, 2, 2, 2, 3]

    arr2 = [2, 3, 4, 5]

    UnionArray(arr1, arr2)

C#

using System;

class GFG {

    static void UnionArray(int[] arr1,

                           int[] arr2)

    {

        int m = arr1[arr1.Length - 1];

        int n = arr2[arr2.Length - 1];

        int ans = 0;

        if (m > n)

            ans = m;

        else

            ans = n;

        int[] newtable = new int[ans + 1];

        Console.Write(arr1[0] + " ");

        ++newtable[arr1[0]];

        for (int i = 1; i

            if (arr1[i] != arr1[i - 1]) {

                Console.Write(arr1[i] + " ");

                ++newtable[arr1[i]];

            }

        }

        for (int j = 0; j

            if (newtable[arr2[j]] == 0) {

                Console.Write(arr2[j] + " ");

                ++newtable[arr2[j]];

            }

        }

    }

    public static void Main()

    {

        int[] arr1 = { 1, 2, 2, 2, 3 };

        int[] arr2 = { 2, 3, 4, 5 };

        UnionArray(arr1, arr2);

    }

}

C++

#include

using namespace std;

void printIntersection(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

    while (i

        if (arr1[i]

            i++;

        else if (arr2[j]

            j++;

        else

        {

            cout " ";

            i++;

            j++;

        }

    }

}

int main()

{

    int arr1[] = { 1, 2, 4, 5, 6 };

    int arr2[] = { 2, 3, 5, 7 };

    int m = sizeof(arr1) / sizeof(arr1[0]);

    int n = sizeof(arr2) / sizeof(arr2[0]);

    printIntersection(arr1, arr2, m, n);

    return 0;

}

C

#include

void printIntersection(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

    while (i

        if (arr1[i]

            i++;

        else if (arr2[j]

            j++;

        else

        {

            printf(" %d ", arr2[j++]);

            i++;

        }

    }

}

int main()

{

    int arr1[] = { 1, 2, 4, 5, 6 };

    int arr2[] = { 2, 3, 5, 7 };

    int m = sizeof(arr1) / sizeof(arr1[0]);

    int n = sizeof(arr2) / sizeof(arr2[0]);

    printIntersection(arr1, arr2, m, n);

    getchar();

    return 0;

}

Java

class FindIntersection {

    static void printIntersection(int arr1[], int arr2[], int m, int n)

    {

        int i = 0, j = 0;

        while (i

            if (arr1[i]

                i++;

            else if (arr2[j]

                j++;

            else {

                System.out.print(arr2[j++] + " ");

                i++;

            }

        }

    }

    public static void main(String args[])

    {

        int arr1[] = { 1, 2, 4, 5, 6 };

        int arr2[] = { 2, 3, 5, 7 };

        int m = arr1.length;

        int n = arr2.length;

        printIntersection(arr1, arr2, m, n);

    }

}

Python

def printIntersection(arr1, arr2, m, n):

    i, j = 0, 0

    while i and j

        if arr1[i]

            i += 1

        elif arr2[j]

            j+= 1

        else:

            print(arr2[j])

            j += 1

            i += 1

arr1 = [1, 2, 4, 5, 6]

arr2 = [2, 3, 5, 7]

m = len(arr1)

n = len(arr2)

printIntersection(arr1, arr2, m, n)

C#

using System;

class GFG {

    static void printIntersection(int[] arr1,

                                  int[] arr2, int m, int n)

    {

        int i = 0, j = 0;

        while (i

            if (arr1[i]

                i++;

            else if (arr2[j]

                j++;

            else {

                Console.Write(arr2[j++] + " ");

                i++;

            }

        }

    }

    public static void Main()

    {

        int[] arr1 = { 1, 2, 4, 5, 6 };

        int[] arr2 = { 2, 3, 5, 7 };

        int m = arr1.Length;

        int n = arr2.Length;

        printIntersection(arr1, arr2, m, n);

    }

}