Java program to determine the array is a subset of another array

Array is a subset of another array in Java

In this section we will determine the program to find if an Array is a subset of another array in Java which is discussed here. If all the elements of array 2 are found in array 1, then array 2 is said to be a subset of array 1.

Array is subset of another array

Method Discussed :

  • Method 1 : Using nested loops
  • Method 2 : Using sorting and binary search.
  • Method 3 : Using sorting and merging.
  • Method 4 : Using Hashing

Method 1 :

  • Run a loop for loo from index 0 to length of arr2
  • Run a inner loop from index 0 to length of arr2
  • If(arr2[i]==arr1[j]), then break the inner loop
  • Check if(j==m) then return 0.
  • Otherwise, return 1.

Method 1 : Code in Java

class Main{

   static boolean isSubset(int arr1[], int arr2[], int m, int n)
    {
        int i = 0;
        int j = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < m; j++) {
                if (arr2[i] == arr1[j])
                    break;
            }
 
            if (j == m)
            return false;
        }
 
        return true;
    }
 
    public static void main(String args[])
    {
        int arr1[] = { 11, 10, 13, 21, 30, 70 };
        int arr2[] = { 11, 30, 70, 10 };
    
        int m = arr1.length;
        int n = arr2.length;
 
        if (isSubset(arr1, arr2, m, n))
            System.out.print("arr2[] is subset of arr1[] ");
        else
            System.out.print("arr2[] is not subset of arr1[] ");
 
    }
}

Output :

arr2[] is subset of arr1[]

Method 2 :

In this method we first sort arr1 then, using binary search we find the elements of arr2 in arr1

  • Sort arr1[] using inbuilt sort function.
  • For each element of arr2[], do binary search for it in sorted arr1[].
  • If the element is not found then return 0.
  • If all elements are present then return 1.

Method 2 : Code in Java

import java.util.Arrays;
class Main{

   static boolean isSubset(int arr1[], int arr2[], int m, int n)
    {
        int i = 0;
 
        for (i = 0; i < n; i++) {
            if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
                return false;
        }
 
        return true;
    }
 
    static int binarySearch(int arr[], int low, int high, int x)
    {
        if (high >= low)
        {
            /*low + (high - low)/2;*/
            int mid = (low + high)/ 2;
 
            if ((mid == 0 || x > arr[mid - 1])&& (arr[mid] == x))
                return mid;
            else if (x > arr[mid])
                return binarySearch(arr,(mid + 1), high,x);
            else
                return binarySearch(arr, low,(mid - 1), x);
        }
        return -1;
    }
    public static void main(String args[])
    {
        int arr1[] = { 11, 10, 13, 21, 30, 70 };
        int arr2[] = { 11, 30, 70, 10 };
    
        int m = arr1.length;
        int n = arr2.length;
        
        Arrays.sort(arr1);
 
        if (isSubset(arr1, arr2, m, n))
            System.out.print("arr2[] is subset of arr1[] ");
        else
            System.out.print("arr2[] is not subset of arr1[] ");
 
    }
}

Output :

arr2[] is subset of arr1[]

Method 3 :

  • Sort both arrays: arr1[] and arr2[] using inbuilt sort function.
  • Use Merging process to see if all elements of sorted arr2[] are present in sorted arr1[].

Method 3 : Code in Java

import java.util.Arrays;
class Main{

   static boolean isSubset(int arr1[], int arr2[], int m, int n)
    {
        int i = 0, j = 0;
 
        if (m < n)
            return false;
 
        Arrays.sort(arr1); // sorts arr1
        Arrays.sort(arr2); // sorts arr2
 
        while (i < n && j < m) {
            if (arr1[j] < arr2[i])
                j++;
            else if (arr1[j] == arr2[i]) {
                j++;
                i++;
            }
            else if (arr1[j] > arr2[i])
                return false;
        }
 
        if (i < n)
            return false;
        else
            return true;
    }
 
    
    public static void main(String args[])
    {
        int arr1[] = { 11, 10, 13, 21, 30, 70 };
        int arr2[] = { 11, 30, 70, 10 };
    
        int m = arr1.length;
        int n = arr2.length;
        
        if (isSubset(arr1, arr2, m, n))
            System.out.print("arr2[] is subset of arr1[] ");
        else
            System.out.print("arr2[] is not subset of arr1[] ");
 
    }
}

Output :

arr2[] is subset of arr1[]

Method 4 :

In this method we will use the concept of hashing.

Method 4 : Code in Java

import java.util.Arrays;
import java.util.HashSet;
class Main{

   static boolean isSubset(int arr1[], int arr2[], int m, int n)
    {
        HashSet set = new HashSet<>();
 
        for (int i = 0; i < m; i++) {
            if (!set.contains(arr1[i]))
                set.add(arr1[i]);
        }
 
        
        for (int i = 0; i < n; i++)
        {
            if (!set.contains(arr2[i]))
                return false;
        }
        return true;
    }
 
    
    public static void main(String args[])
    {
        int arr1[] = { 11, 10, 13, 21, 30, 70 };
        int arr2[] = { 11, 30, 70, 10 };
    
        int m = arr1.length;
        int n = arr2.length;
        
        if (isSubset(arr1, arr2, m, n))
            System.out.print("arr2[] is subset of arr1[] ");
        else
            System.out.print("arr2[] is not subset of arr1[] ");
 
    }
}

Output :

arr2[] is subset of arr1[]

3 comments on “Java program to determine the array is a subset of another array”


  • sandesh

    import java.util.Scanner;

    public class arrayIsSubsetOfOtherArray {
    public static boolean isSubset(int[] array1, int[] array2,int len1,int len2) {
    int i,j;

    for (i=0; i < len1; i++){
    if (array1[i] ==array2[0]){
    int count=1;
    for (j=1; j < len2; j++){
    if (array1[i+j] == array2[j]){
    count++;
    }
    }
    System.out.println(count);
    if (count ==len2){
    return true;
    }
    }
    }
    return false;
    }
    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int len1=scanner.nextInt();
    int len2=scanner.nextInt();
    int[] array1=new int[len1];
    int[] array2=new int[len2];
    for(int i=0; i<len1; i++) {
    array1[i] =scanner.nextInt();
    }
    for(int i=0; i<len2; i++) {
    array2[i] =scanner.nextInt();
    }
    if(isSubset(array1, array2, len1, len2)) {
    System.out.println("yes");
    }
    else {
    System.out.println("no");
    }
    scanner.close();
    }

    }


  • Ayushi

    #Python Program

    arr1 = list(map(int, input(“Enter array 1: “).split()))
    arr2 = list(map(int, input(“Enter array 2: “).split()))

    count = 0
    for i in arr1:
    for j in arr2:
    if i == j:
    count+=1
    continue

    if count == len(arr2):
    print(“{} is a subset of {}”.format(arr2, arr1))
    else:
    print(“{} is not a subset of {}”.format(arr2, arr1))


  • Anurag

    int[] arr1 = {1,2,3,4,5};
    int[] arr2 = {3,4,5};
    int subset=0;
    for(int i=0;i<arr1.length;i++)
    {
    for(int j=0;j0)
    System.out.println(“true”);
    else
    System.out.println(“false”);