Find the Difference of Two Arrays

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

1. answer[0] is a list of all distinct integers in nums1 which are not present in nums2.

2. answer[1] is a list of all distinct integers nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

 

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

Approach

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class DiffTwoArray {
    public static void main(String[] args) {

        int nums1[] = { 1, 2, 3 }, nums2[] = { 2, 4, 6 };

        System.out.println(findDifference(nums1, nums2));

    }

    public static List<List<Integer>> findDifference(int[] nums1, int[] nums2) {

        // creating the sets
        Set<Integer> st1 = new HashSet<Integer>();
        Set<Integer> st2 = new HashSet<Integer>();

        // add all the elements of first arrays into the set 1
        for (int i = 0; i < nums1.length; i++) {
            st1.add(nums1[i]);
        }

        // add all the elements of second arrays into the set 2
        for (int i = 0; i < nums2.length; i++) {
            st2.add(nums2[i]);
        }

        // remove the element which present in the set 1 and from array 2
        for (int i = 0; i < nums2.length; i++) {
            if (st1.contains(nums2[i]))
                st1.remove(nums2[i]);
        }

        // remove the element which present in the set 2 and from array 1
        for (int i = 0; i < nums1.length; i++) {
            if (st2.contains(nums1[i]))
                st2.remove(nums1[i]);
        }

        // creating the lists
        List<Integer> answer1 = new ArrayList<Integer>();

        List<Integer> answer2 = new ArrayList<Integer>();

        Iterator<Integer> value1 = st1.iterator();
        // add the set 1 element into list 1
        while (value1.hasNext()) {
            answer1.add(value1.next());
        }

        Iterator<Integer> value2 = st2.iterator();

        // add the set 1 element into list 1
        while (value2.hasNext()) {
            answer2.add(value2.next());
        }

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        // add both the list into one list
        result.add(answer1);
        result.add(answer2);

        // return the final list
        return result;

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> findDifference(vector<int> &nums1, vector<int> &nums2)
{
    set<int> st1, st2;

    // insert the first array elements into set 1
    for (int i = 0; i < nums1.size(); i++)
    {

        st1.insert(nums1[i]);
    }

    // insert the second array elements into set 2
    for (int i = 0; i < nums2.size(); i++)
    {
        st2.insert(nums2[i]);
    }

    // remove the element from set 1 which present in second array
    for (int i = 0; i < nums2.size(); i++)
    {
        if (st1.find(nums2[i]) != st1.end())
            st1.erase(nums2[i]);
    }

    // remove the element from set 2 which present in first array
    for (int i = 0; i < nums1.size(); i++)
    {
        if (st2.find(nums1[i]) != st2.end())
            st2.erase(nums1[i]);
    }

    vector<int> answer1, answer2;
    for (auto it = st1.begin(); it != st1.end(); ++it)
    {
        answer1.push_back(*it);
    }

    for (auto it = st2.begin(); it != st2.end(); ++it)
    {
        answer2.push_back(*it);
    }

    vector<vector<int>> result;
    result.push_back(answer1);
    result.push_back(answer2);

    return result;
}
int main()
{
    vector<int> nums1 = {1, 2, 3}, nums2 = {2, 4, 6};

    vector<vector<int>> result = findDifference(nums1, nums2);

    cout << "[";
    for (int i = 0; i < result.size(); i++)
    {
        cout << "[";
        for (int j = 0; j < result[i].size(); j++)
        {
            cout << result[i][j];
            if (j != result[i].size() - 1)
                cout << ",";
        }
        cout << "]";
        if (i != result.size() - 1)
            cout << ",";
    }
    cout << "]";
}

Output:

[[1, 3], [4, 6]]

Validate Stack Sequences

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Approach

Java

import java.util.Stack;

public class ValidateStackSequence {
    public static void main(String[] args) {

        int pushed[] = { 1, 2, 3, 4, 5 }, popped[] = { 4, 5, 3, 2, 1 };

        System.out.println(validateStackSequences(pushed, popped));
    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {

        Stack<Integer> st = new Stack<Integer>();

        int j = 0;

        // iterate through the whole array
        for (int i = 0; i < pushed.length; i++) {

            // insert the current element into stack
            st.push(pushed[i]);

            // iterate till the size of stack is greater than 0 and
            // current element is the stack top element
            while (st.size() > 0) {
                if (popped[j] == st.peek()) {
                    st.pop();
                    j++;
                } else
                    break;
            }

        }

        // iterate through the remaining elements of the popped
        // array
        for (int i = j; i < popped.length; i++) {

            // if at any point top element is not
            // equal to the current element then
            // return false
            if (st.peek() != popped[i]) {
                return false;
            }
        }

        // at the end return true
        return true;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
                int j=0;
        // iterate through the whole array
        for (int i = 0; i < pushed.size(); i++) {

            // insert the current element into stack
            st.push(pushed[i]);

            // iterate till the size of stack is greater than 0 and
            // current element is the stack top element
            while (st.size() > 0) {
                if (popped[j] == st.top()) {
                    st.pop();
                    j++;
                } else
                    break;
            }

        }

        // iterate through the remaining elements of the popped
        // array
        for (int i = j; i < popped.size(); i++) {

            // if at any point top element is not
            // equal to the current element then
            // return false
            if (st.top() != popped[i]) {
                return false;
            }
        }

        // at the end return true
        return true;
    }
int main()
{
    vector<int> pushed = { 1, 2, 3, 4, 5 }, 
             popped = { 4, 5, 3, 2, 1 };
    cout << validateStackSequences(pushed,popped);
    return 0;
}

Number of Strings That Appear as Substrings in Word

Given an array of strings patterns and a string word, return the number of strings in patterns that exist as a substring in the word.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Explanation:
- "a" appears as a substring in "abc".
- "abc" appears as a substring in "abc".
- "bc" appears as a substring in "abc".
- "d" does not appear as a substring in "abc".
3 of the strings in patterns appear as a substring in word.

Example 2:

Input: patterns = ["a","b","c"], word = "aaaaabbbbb"
Output: 2
Explanation:
- "a" appears as a substring in "aaaaabbbbb".
- "b" appears as a substring in "aaaaabbbbb".
- "c" does not appear as a substring in "aaaaabbbbb".
2 of the strings in patterns appear as a substring in word.

Approach

Java

public class NumberOfStrings {
    public static void main(String[] args) {

        String[] patterns = { "a", "abc", "bc", "d" };
        String word = "abc";

        System.out.println(numOfStrings(patterns, word));

    }

    static int numOfStrings(String[] patterns, String word) {
        int totalCount = 0;

        for (int i = 0; i < patterns.length; i++) {
            if (word.contains(patterns[i]))
                totalCount++;
        }
        return totalCount;
    }

}

Output:

3

C++

#include <bits/stdc++.h>
using namespace std;

int numOfStrings(vector<string> &patterns, string word)
{
    int totalCount = 0;

    for (int i = 0; i < patterns.size(); i++)
    {
        if (word.find(patterns[i]) != string::npos)
            totalCount++;
    }
    return totalCount;
}

int main()
{
    vector<string> patterns = {"a", "abc", "bc", "d"};
    string word = "abc";

    cout << numOfStrings(patterns, word) << "\n";

    return 0;
}

Output:

3

Find Greatest Common Divisor of Array

Given an integer array, nums return the greatest common divisor of the smallest number and the largest number in nums

The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

Example 1:

Input: nums = [2,5,6,9,10]
Output: 2
Explanation:
The smallest number in nums is 2.
The largest number in nums is 10.
The greatest common divisor of 2 and 10 is 2.

Example 2:

Input: nums = [7,5,6,8,3]
Output: 1
Explanation:
The smallest number in nums is 3.
The largest number in nums is 8.
The greatest common divisor of 3 and 8 is 1.

Approach 1:

Using Sorting (min element will be the first element and max element will be the last element).

Time Complexity: O(Nlog(N))

Java

import java.util.Arrays;

public class GCDArrayUsingSorting {
    public static void main(String[] args) {

        int[] nums = { 2, 5, 6, 9, 10 };

        System.out.println(findGCD(nums));

    }

    static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static int findGCD(int[] nums) {

        Arrays.sort(nums);
        int minElement = nums[0], maxElement = 
               nums[nums.length - 1];

        return gcd(minElement, maxElement);
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int findGCD(vector<int> &nums)
{

    sort(nums.begin(), nums.end());
    int minElement = nums[0], maxElement = nums[nums.size() - 1];

    return gcd(minElement, maxElement);
}

int main()
{
    vector<int> nums = {2, 5, 6, 9, 10};

    cout << findGCD(nums) << "\n";

    return 0;
}

Approach 2: 

Find minimum element and maximum element by iterating through all elements of the array.

Time Complexity: O(N)

Java

public class GCDArray {
    public static void main(String[] args) {
        int[] nums = { 2, 5, 6, 9, 10 };

        System.out.println(findGCD(nums));

    }

    static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static int findGCD(int[] nums) {

        int minElement = nums[0], maxElement = nums[0];

        for (int i = 1; i < nums.length; i++) {
            minElement = Math.min(minElement, nums[i]);
            maxElement = Math.max(maxElement, nums[i]);
        }

        return gcd(minElement, maxElement);
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int findGCD(vector<int> &nums)
{

    int minElement = nums[0], maxElement = nums[0];

    for (int i = 1; i < nums.size(); i++)
    {
        minElement = min(minElement, nums[i]);
        maxElement = max(maxElement, nums[i]);
    }

    return gcd(minElement, maxElement);
}

int main()
{
    vector<int> nums = {2, 5, 6, 9, 10};

    cout << findGCD(nums) << "\n";

    return 0;
}