Home » Technical Interview Questions » Array Interview Questions » Find whether an array is subset of another array

Find whether an array is subset of another array


The problem “Find whether an array is subset of another array” states that you are given two arrays arra1[] and array2[]. The arrays given are in an unsorted manner. Your task is to find whether the array2[] is a subset of array1[].

Example

Find whether an array is subset of another array

arr1= [1,4,5,7,8,2]
arr2= [1,7,2,4]
arr2 [] is a subset of arr1 [].
arr1= [21,4,5,2,18,3]
arr2= [1,4,2,3]
arr2 [] is not a subset of arr1 [].

Algorithm

  1. Open a nested loop.
  2. Set i to 0, j to 0.
  3. While i is less than the length of array2[].
    1. While j is less than the length of array1[].
      1. If arr2[i] is equal to arr[j], then break.
  4. If j is equal to m, return false.
  5. Return true.

Explanation

Our task is to find whether the array second is a subset of array1. So our main idea is to use the nested loop and check each element and array2’s every element is found in array1, which means array2 is a subset of array1.

Let us take an example as our input in array1 and array2

Example

arr1[] = {11, 1, 13, 21, 3, 7}; arr2[] = {11, 3, 7, 1};

Starting with the 0th index of array2, we are going to check if the 0th index of arrays2 finds a similar number in array1[i], and yes it found it as 11. So we are going to break the loop and do i++.

READ  Check if X can give change to every person in the Queue

Starting with the 1st index of array2[], we are going to check if the 1st index of arrays2 finds a similar number in array1[i], and yes it found it as 3. So we are going to break the loop and do i++.

Starting with the 2nd index of array2[], we are going to check if the 2nd index of arrays2 finds a similar number in array1[i] and it found it as 7. So we are going to break the loop and do i++.

Starting with the 1st index of array2[], we are going to check if the 1st index of arrays2 finds a similar number in array1[i] and 1 found it. So we are going to break the loop and do i++.

And about if condition which is represented as if ( j = = m ) this means, if in any of the iteration if any of array2’s element is not found in array1[], means it comes out of the loop without breaking it means ‘j’ with a value equal to the length of the array1[] that means we didn’t find one of the elements similar in array1[] and we return false because subset consists all of the element of the given set and we didn’t find one.

Code

C++ code to find whether an array is subset of another array

#include <iostream>
using namespace std;

bool isSubset(int arr1[], int arr2[], int l1, int l2)
{
    int i,j;
    for(i=0; i<l2; i++)
    {

        for(j=0; j<l1; j++)
        {
            if(arr2[i]==arr1[j])
                break;
        }
        if(j==l1)
            return false;
    }
    return true;
}
int main()
{
    int arr1[] = {1, 2, 3, 4, 5, 6};
    int arr2[] = {1, 3, 5};

    int l1=sizeof(arr1)/sizeof(arr1[0]);
    int l2=sizeof(arr2)/sizeof(arr2[0]);
    if(isSubset(arr1,arr2,l1,l2))
    {
        cout<<"arr2[] is a subset of arr1[]";
    }
    else
    {
        cout <<"arr2[] is not a subset of arr1[]"<<endl;
    }
    return 0;
}
arr2[] is a subset of arr1[]

Java code to find whether an array is subset of another array

class isArraySubset
{
    public static boolean isSubset(int arr1[],int arr2[], int l1, int l2)
    {
        int i = 0;
        int j = 0;
        for (i = 0; i < l2; i++)
        {
            for (j = 0; j < l1; j++)
            {
                if(arr2[i] == arr1[j])
                {
                    break;
                }
            }
            if (j == l1)
                return false;
        }
        return true;
    }
    public static void main(String args[])
    {
        int arr1[] = {1, 2, 3, 4, 5, 6};
        int arr2[] = {1, 3, 5};

        int l1 = arr1.length;
        int l2 = arr2.length;

        if(isSubset(arr1, arr2, l1, l2))
        {
            System.out.println("arr2[] is a subset of arr1[]");
        }
        else
        {
            System.out.println("arr2[] is not a subset of arr1[]");
        }
    }
}
arr2[] is a subset of arr1[]

Complexity Analysis

Time Complexity

O(m*n) where “m” is the size of arr1 and “n” is the size of arr2. Because we have used nested loops, making the time complexity polynomial.

READ  Count Subarrays with Same Even and Odd Elements

Space Complexity

O(1), because we have not used any extra array/vector.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup