Q21. Check if the given array is a subset of another array.

A21. To check this we transfer the elements of the array to a set, hence removing duplicates. And now we compare the set elements with the second array to check if it contains those elements. If any set element is not in the array we return false, otherwise, we return true.

public class SubsetOfArr{
    static boolean sub(int[] a, int[] b){
        HashSet<Integer> set = new HashSet<>();
        for(int i=0; i<a.length; i++){
            if(!set.contains(a[i])){
                set.add(a[i]);
            }
        }
        for(int i=0; i<b.length;i++){
            if(!set.contains(a[i])){
                return false;
            }
        }
        return true;
    }
}

The time complexity of this algorithm is O(n) and the space complexity is also O(n).

Q22. Return the numbers in the array that occur more than n/k times, where n is the length of the array and k is a given number.

A22. For this question, we use a hashmap to map out the occurrences and then traverse the map and check if the frequency is larger than n/k.

public class OccurranceMoreThan{
    static void occurrance(int[] a, int n, int k){
        int temp = n/k;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<n;i++){
            if(!map.containsKey(a[i])){
                map.put(a[i], 1);
            }
            else{
                int count = map.get(a[i]);
                map.put(a[i], count+1);
            }
        }
        for(Map.Entry m: map.entrySet()){
            Integer x =(Integer)m.getValue();
            if(x>temp){
                System.out.println(m.getKey());
            }
        }
    }   
}

The time and space complexity of this algorithm is O(n).

Q23. Find 3 numbers in the array that equate to a given sum.

A23. There are 3 ways to solve this problem, one is a brute force solution, i.e. using three loops and comparing the sum each time we add three values. The second way is to use a set, and two loops, one loop to point at one constant value and subtract it from the given sum, then use the other loop and subtract it from this current value and check if the result is in the set, if it is in the set return true. The third way is without using extra space, a 3-pointer method. Firstly we sort the array and using a loop, place two pointers on the first two array elements, and a third pointer on the last. Using an internal while loop we will compare the sum values of these three elements, if the sum is less than the current sum, we will increment the pointer on the second element, else we will decrement the pointer at the last index.

public class ThreeSum {
    static void sum(int[] a, int s){
        Arrays.sort(a);
        for(int j=0; j< a.length-2; j++) {
            int l= j+1;
            int r = a.length-1;
            while (l < r) {
                if (a[j] + a[l] + a[r] == s) {
                    System.out.println(a[j] + " " + a[l] + " " + a[r]);
                    break;
                } else if (a[j] + a[l] + a[r] < s) {
                    l++;
                } else {
                    r--;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,4,6,7};
        int sum = 9;
        sum(a,sum);
    }
}

The time complexity is O(n^2) and the space complexity is O(1).

Q24. Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after rain.

A24. In this question, we will use two-pointers. Water can only fill in if the corresponding heights of towers are larger. We will mark the first and last towers as max, with variables maxLeft and maxRight for the left and right towers respectively. Then we will take a left pointer pointing to the next element of the maxLeft and a right pointer pointing to the previous element of maxRight. We will iterate through the array until the left pointer passes the right. We will check which side is bigger, left or right by comparing maxLeft or maxRight, depending on that we will change the left or right pointer.

public class TrappingRainWater{
    static int trap(int[] height){
        if(height<=2){
            return 0;    }
        int n = height.length;
        int maxLeft = height[0], maxRight = height[n-1], int left= 1, int right = n-2, ans=0;
        while(left<=right){
            if(maxLeft> maxRight){
                if(left>maxLeft){
                    maxLeft = left;    }
                else{
                    ans+= maxLeft-height[left];  
                    left++;   } 
            }
            else{
                if(right>maxRight){
                    maxRight = right;    }
                else{
                    ans+= maxRight-height[right];
                    right++    }
            }
        }
        return ans;
    }
}

The time complexity is O(n) and the space complexity is O(1).

We will now move to searching algorithms, but we will do more questions on array soon.