Given two arrays a[] and b[] of size m and n respectively, the task is to determine whether b[] is a subset of a[]. Both arrays are not sorted, and elements are distinct.
Examples:
Input: a[] = [11, 1, 13, 21, 3, 7], b[] = [11, 3, 7, 1]
Output: trueInput: a[]= [1, 2, 3, 4, 5, 6], b = [1, 2, 4]
Output: trueInput: a[] = [10, 5, 2, 23, 19], b = [19, 5, 3]
Output: false
Try it on GfG Practice
Table of Content
[Naive approach] Using Nested Loops - O(m*n) Time and O(1) Space
The very basic approach is to use two nested loops, the outer loop picks each element from b[], and the inner loop searches for this element in a[] and check for all elements in b[].
#include <iostream>
#include <vector>
using namespace std;
bool isSubset(vector<int> &a, vector<int> &b)
{
// Iterate over each element in the second array
int m = a.size(), n = b.size();
for (int i = 0; i < n; i++)
{
bool found = false;
// Check if the element exists in the first array
for (int j = 0; j < m; j++)
{
if (b[i] == a[j])
{
found = true;
a[j] = -1;
break;
}
}
// If any element is not found, return false
if (!found)
return false;
}
// If all elements are found, return true
return true;
}
int main()
{
vector<int> a = {11, 1, 13, 21, 3, 7};
vector<int> b = {11, 3, 7, 1};
if (isSubset(a, b))
{
cout << "true" << endl;
}
else
{
cout << "false" << endl;
}
return 0;
}
class GfG {
public static boolean isSubset(int[] a, int[] b)
{
int m = a.length, n = b.length;
for (int i = 0; i < n; i++) {
boolean found = false;
for (int j = 0; j < m; j++) {
if (b[i] == a[j]) {
found = true;
// mark as visited
a[j] = -1;
break;
}
}
// If any element is not found, return false
if (!found)
return false;
}
// If all elements are found, return true
return true;
}
public static void main(String[] args)
{
int[] a = {11, 1, 13, 21, 3, 7};
int[] b = {11, 3, 7, 1};
if (isSubset(a, b)) {
System.out.println("true");
}
else {
System.out.println("false");
}
}
}
def isSubset(a, b):
m, n = len(a), len(b)
for i in range(n):
found = False
for j in range(m):
if b[i] == a[j]:
found = True
# mark as visited
a[j] = -1
break
# If any element is not found, return false
if not found:
return False
# If all elements are found, return true
return True
if __name__ == '__main__':
a = [11, 1, 13, 21, 3, 7]
b = [11, 3, 7, 1]
if isSubset(a, b):
print("true")
else:
print("false")
using System;
class GfG {
public static bool isSubset(int[] a, int[] b)
{
int m = a.Length, n = b.Length;
for (int i = 0; i < n; i++) {
bool found = false;
for (int j = 0; j < m; j++) {
if (b[i] == a[j]) {
found = true;
// mark as visited
a[j] = -1;
break;
}
}
// If any element is not found, return false
if (!found)
return false;
}
// If all elements are found, return true
return true;
}
public static void Main()
{
int[] a = {11, 1, 13, 21, 3, 7};
int[] b = {11, 3, 7, 1};
if (isSubset(a, b)) {
Console.WriteLine("true");
}
else {
Console.WriteLine("false");
}
}
}
function isSubset(a, b)
{
let m = a.length, n = b.length;
for (let i = 0; i < n; i++) {
let found = false;
for (let j = 0; j < m; j++) {
if (b[i] === a[j]) {
found = true;
// mark as visited
a[j] = -1;
break;
}
}
// If any element is not found, return false
if (!found)
return false;
}
// If all elements are found, return true
return true;
}
// Driver Code
const a = [ 11, 1, 13, 21, 3, 7 ];
const b = [ 11, 3, 7, 1 ];
if (isSubset(a, b)) {
console.log("true");
}
else {
console.log("false");
}
Output
true
[Better Approach] Using Sorting and Two Pointer - O(m log m + n log n) Time and O(1) space
Sort both arrays and use two pointers to traverse them. If the current element of a[] is smaller, move the pointer in a. If the elements match, move both pointers. If the current element of a[] is greater than b[], then b[j] is missing in a[], so return false.
#include <iostream>
using namespace std;
bool isSubset(vector<int>& a, vector<int>& b) {
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int i = 0, j = 0;
int m = a.size(), n = b.size();
while (i < m && j < n) {
if (a[i] < b[j]) {
// move in a to catch up
i++;
}
else if (a[i] == b[j]) {
i++;
// matched one element from b
j++;
}
else {
// a[i] > b[j] → means b[j] is missing
return false;
}
}
// all b[] matched
return (j == n);
}
int main() {
vector<int> a = {11, 1, 13, 21, 3, 7};
vector<int> b = {11, 3, 7, 1};
if (isSubset(a, b)) cout << "true\n";
else cout << "false\n";
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void sort(int arr[], int n) {
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
bool isSubset(int a[], int b[], int m, int n) {
sort(a, m);
sort(b, n);
int i = 0, j = 0;
while (i < m && j < n) {
if (a[i] < b[j]) {
// move in a to catch up
i++;
}
else if (a[i] == b[j]) {
i++;
// matched one element from b
j++;
}
else {
// a[i] > b[j] → means b[j] is missing
return false;
}
}
// all b[] matched
return (j == n);
}
int main() {
int a[] = {11, 1, 13, 21, 3, 7};
int b[] = {11, 3, 7, 1};
int m = sizeof(a)/sizeof(a[0]);
int n = sizeof(b)/sizeof(b[0]);
if (isSubset(a, b, m, n)) printf("true\n");
else printf("false\n");
return 0;
}
import java.util.Arrays;
class GfG {
public static boolean isSubset(int[] a, int[] b) {
Arrays.sort(a);
Arrays.sort(b);
int i = 0, j = 0;
int m = a.length, n = b.length;
while (i < m && j < n) {
if (a[i] < b[j]) {
// move in a to catch up
i++;
}
else if (a[i] == b[j]) {
i++;
// matched one element from b
j++;
}
else {
// a[i] > b[j] → means b[j] is missing
return false;
}
}
// all b[] matched
return (j == n);
}
public static void main(String[] args) {
int[] a = {11, 1, 13, 21, 3, 7};
int[] b = {11, 3, 7, 1};
if (isSubset(a, b)) System.out.println("true");
else System.out.println("false");
}
}
def isSubset(a, b):
a.sort()
b.sort()
i = 0
j = 0
m = len(a)
n = len(b)
while i < m and j < n:
if a[i] < b[j]:
# move in a to catch up
i += 1
elif a[i] == b[j]:
i += 1
# matched one element from b
j += 1
else:
# a[i] > b[j] → means b[j] is missing
return False
# all b[] matched
return j == n
# Custom Input
a = [11, 1, 13, 21, 3, 7]
b = [11, 3, 7, 1]
if isSubset(a, b):
print('true')
else:
print('false')
using System;
public class GfG
{
public static bool isSubset(int[] a, int[] b)
{
Array.Sort(a);
Array.Sort(b);
int i = 0, j = 0;
int m = a.Length, n = b.Length;
while (i < m && j < n)
{
if (a[i] < b[j])
{
// move in a to catch up
i++;
}
else if (a[i] == b[j])
{
// matched one element from b
i++;
j++;
}
else
{
// a[i] > b[j] → means b[j] is missing
return false;
}
}
// all elements of b[] matched
return (j == n);
}
public static void Main()
{
int[] a = {11, 1, 13, 21, 3, 7};
int[] b = {11, 3, 7, 1};
if (isSubset(a, b))
Console.WriteLine("true");
else
Console.WriteLine("false");
}
}
function isSubset(a, b) {
a.sort((x, y) => x - y);
b.sort((x, y) => x - y);
let i = 0, j = 0;
let m = a.length, n = b.length;
while (i < m && j < n) {
if (a[i] < b[j]) {
// move in a to catch up
i++;
}
else if (a[i] == b[j]) {
i++;
// matched one element from b
j++;
}
else {
// a[i] > b[j] → means b[j] is missing
return false;
}
}
// all b[] matched
return (j == n);
}
// Driver code
let a = [11, 1, 13, 21, 3, 7];
let b = [11, 3, 7, 1];
if (isSubset(a, b)) console.log('true');
else console.log('false');
Output
true
[Expected Approach] Using Hashing - O(m + n) Time and O(m) Space
We can use a hash set to store elements of a[], this will help us in constant time complexity searching. We first insert all elements of a[] into a hash set. Then, for each element in b[], we check if it exists in the hash set.
#include <iostream>
using namespace std;
bool isSubset( vector<int>& a, vector<int>& b) {
// Create a hash set and insert all elements of a
multiset<int> hashSet(a.begin(), a.end());
// Check each element of b in the hash set
for (int num : b) {
if (hashSet.find(num) == hashSet.end()) {
return false;
}
hashSet.erase(hashSet.find(num));
}
// If all elements of b are found in the hash set
return true;
}
int main() {
vector<int> a = {11, 1, 13, 21, 3, 7};
vector<int> b = {11, 3, 7, 1};
if (isSubset(a, b)) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}
import java.util.HashSet;
import java.util.Set;
class GfG {
static boolean isSubset(int[] a,int[] b) {
// Create a hash set and insert all elements of a
Set<Integer> hashSet = new HashSet<>();
for (int num : a) {
hashSet.add(num);
}
// Check each element of b in the hash set
for (int num : b) {
if (!hashSet.contains(num)) {
return false;
}
}
// If all elements of b are found in the hash set
return true;
}
public static void main(String[] args){
int[] a = { 11, 1, 13, 21, 3, 7 };
int[] b = { 11, 3, 7, 1 };
if (isSubset(a, b)) {
System.out.println("true");
}
else {
System.out.println("false");
}
}
}
def isSubset(a, b):
# Create a hash set and insert all elements of a
hash_set = set(a)
# Check each element of b in the hash set
for num in b:
if num not in hash_set:
return False
# If all elements of b are found in the hash set
return True
if __name__ == "__main__":
a = [11, 1, 13, 21, 3, 7]
b = [11, 3, 7, 1]
if isSubset(a, b):
print("true")
else:
print("false")
using System;
using System.Collections.Generic;
class GfG
{
static bool isSubset(int[] a, int[] b)
{
// Create a hash set and insert all elements of array a
HashSet<int> hashSet = new HashSet<int>(a);
// Check each element of array b in the hash set
foreach (int num in b)
{
if (!hashSet.Contains(num))
{
return false;
}
}
// If all elements of b are found in the hash set
return true;
}
public static void Main(string[] args)
{
int[] a = {11, 1, 13, 21, 3, 7};
int[] b = {11, 3, 7, 1};
if (isSubset(a, b))
{
Console.WriteLine("true");
}
else
{
Console.WriteLine("false");
}
}
}
function isSubset(a, b) {
// Create a hash set and insert all elements of a
const hashSet = new Set(a);
// Check each element of b in the hash set
for (const num of b) {
if (!hashSet.has(num)) {
return false;
}
}
// If all elements of b are found in the hash set
return true;
}
// Driver code
const a = [11, 1, 13, 21, 3, 7];
const b = [11, 3, 7, 1];
if (isSubset(a, b)) {
console.log("true");
} else {
console.log("false");
}
Output
true