Array Subset problem [least space with O(n) time complexity]

Question

I want to write a function in java which takes 2 arrays as inputs & return true if smaller array is a subset of larger array

Is there a way to make this below code succint & more space efficient (while maintaining O(n) time complexity?

public boolean isArraySubset(int[] arr1, int arr2[]) {
    Set<Integer> set = new HashSet<>();

    int largeArr[];
    int smallArr[];
    if (arr1.length > arr2.length) {
        largeArr = arr1;
        smallArr = arr2;
    } else {
        largeArr = arr2;
        smallArr = arr1;
    }
    for (int i : largeArr) {
        set.add(i);
    }
    for (int i : smallArr) {
        if (!set.contains(i)) {
            return false;
        }
    }

    return true;
}

I'm not a Java developer, but just thinking about it, you could add the items of the smaller array to the set, then remove each item of the larger array. If the set is non-empty at the end, the smaller array not a subset of the larger. This would only be a significant improvement if the one array is *much* smaller than the other. — p.s.w.g, Feb 13 '19 at 23:22
definitely makes sense, if one array is much smaller than the other. Would also like to know how can this code be written more succintly. Thank you @p.s.w.g — Vik, Feb 13 '19 at 23:28
For one, there are more expressive ways to initialise a set from an array, e.g. https://stackoverflow.com/questions/2041778/how-to-initialize-hashset-values-by-construction. As far a I'm aware (I'm not a Java developer), you can make it even shorter with newer versions of Java. — Eli Korvigo, Feb 13 '19 at 23:29

LppEdd · Accepted Answer · 2019-02-14T06:35:38.320

3

Why not using a Set<T>? Just use the removeAll method and check the size of the smaller Set. This kind of thing is already done for you.

smallerSet.removeAll(largerSet);

if (smallerSet.isEmpty()) {
   // It's a subset
}

edited Feb 14 '19 at 06:35

answered Feb 13 '19 at 23:41

LppEdd

20,274
11
84
139

I am not sure if your solution works. Let us take an example viz. smallerSet={1,2} & largerSet={1,2,400}. Per your logic smallerSet will be {1,2} after retainAll operation. smallerSet is not empty, but still remains subset of the largerSet – Vik Feb 14 '19 at 04:37
1

@Vik I edited the question to change retainaAll > removeAll. Sorry, my bad, I don't know why I wrote retainAll (probably tiredness from the day) – LppEdd Feb 14 '19 at 06:36
Thanks @LppEdd. That makes perfect sense ! – Vik Feb 18 '19 at 18:08

Array Subset problem [least space with O(n) time complexity]

1 Answers1