How to find whether an array is a subset of another array

An array is a simple data structure that stores a collection of elements. Each element in the array is referenced by its unique identifier using an index to the contiguous memory locations where the elements are stored.

Note: To learn more about arrays, click here

Understanding the problem

Consider array1 and array2 are two integer arrays of size m and n, respectively (n <= m). We need to determine whether array2 is a subset of array1 or not. A subset of an array is one in which every element of array2 is present within array1. Assume that, in neither of the arrays, any elements are repeated.

Subset array

Simple solution

This solution is known as the Brute force approach using two loops. Using a linear search, look for each element of array2 in array1. The array2 is a subset of array1 only if all of its elements are present in array1.

# Function to find subset in array
def subset(array1, array2, size1, size2):
    i = 0
    for i in range(size2):
        j=0
        while(j < size1):
            if(array2[i] == array1[j]):
                break #if broken then element is present
            j=j+1
            
        if (j == size1):
            return False               
    #return true as all elements of arr2[] are present in arr1[]
    return True
 
#driver code  
array1 = [20, 12, 13, 21, 5, 8]
array2 = [20, 5, 8, 12]
size1 = len(array1)
size2 = len(array2)
if(subset(array1, array2, size1, size2)):
    print("Array2[] is subset of Array1[] ")
else:
    print("array2[] is not a subset of array1[]")

Explanation

  • Lines 1–6: We define the subset function in which we initialize the loop variables, i and j . We create two loops, an inner and outer loop.

  • Lines 7–10: If we find the same element in both arrays, break the inner loop.

  • Lines 10–13: We return False if j gets equal to the size1. Otherwise, we return True.

Time complexity: For this approach, the time complexity is O(m∗n)O(m*n).

Space complexity: For this approach, the space complexity is O(1)O(1).

Efficient Solution

In this method, we sort both array1 and array2 arrays, which helps in reducing the time complexity compared to the aforementioned method.

To verify that each element in sorted array2 is also present in sorted array1, we perform a merge type of process.

def subset(array1, array2, size1, size2):
    i = 0
    j = 0
    if size1 < size2: #subset not exist
        return False
    #sorting both arrays
    array1.sort() 
    array2.sort()
 
    while i < size2 and j < size1: #traversing arrays
        if array1[j] < array2[i]: 
            j += 1
        elif array1[j] == array2[i]: #if equal, go to next index            j += 1
            i += 1
        elif array1[j] > array2[i]: #if array1 element is greater
            return False 
    return False if i < size2 else True
 
 
# Driver code
array1 = [20, 12, 13, 21, 5, 8]
array2 = [20, 5, 8, 12]
size1 = len(array1)
size2 = len(array2)
if subset(array1, array2, size1, size2) == True:
    print("Array2 is subset of Array1 ")
else:
    print("Array2 is not a subset of Array1 ")

Explanation

  • Lines 1–5: We define the function subset in which we initialize loop variables i and j. We return False if size1 is smaller than size2.

  • Lines 6–14: We sort both arrays and in while loop. We check whether the current element of array1 is less than or equal to the array2. If yes, increment the loop variable.

  • Lines 15–17: We return False if the current element of array1 is greater and True if size1 is greater than i.

Time complexity: For this approach, the time complexity is O(mlogm+nlogn)O(mlogm + nlogn), which is much better. Keep in mind that if a nlognnlogn algorithm, merge sort, is used to sort both arrays, then this will be the time complexity.

Space complexity: For this approach, the space complexity is O(1)O(1).

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved