Article type: Video

Find Intersection Solution

mrdaniel published this on 7/6/20

In this video, we will walk through the Find Intersection Challenge. We'll analyze various solutions, their time complexities and how to find a linear time solution using hash tables. Link to challenge Link to an article walkthrough


Comments (17)

20
Time complexity will be O(n^2)
BicoOloo commented on 07/30/20
0
O(mn)
NerseKirjak commented on 09/01/20
3
1.What if 2 strings are of different length, 10,20,30,40 10,20,25,30,40 or vise versa, by pushing longer string in to a map, we will miss possible elements in intersection set. 2. Resulting array could be just a string builder.Thanks
NerseKirjak commented on 09/01/20
3
@NerseKirjak You bring up some great points on how we can further explore this problem. The current implementation makes assumptions that 1. both arrays of strings are sorted 2. each string has unique numbers 3. both strings are of equal length
We could do a few things to account for this:
  1. Instead of saving true in the map, we instead save the count to account for duplicates
  2. We can check the lengths of the two strings and use the smaller string to make the map

Any further thoughts on what you could do with this?
cindytongcoderbyte commented on 09/01/20
-1
Really useful info, thanks!
ollyds commented on 09/16/20
0
O(n^2)
ericrius1 commented on 09/18/20
1
this solution is iterating through the array multiple times to get to the actual problem. while we can create the numbers and compare them just in 1 time and to lower the time complexity we can push the starting index of nested loop to the last index we found a match, since the list is sorted.
hakoo commented on 09/21/20
5
For me, a simpler approach would be to add the 2 strings, create a set of unique numbers from the concatenated string and then loop through the set checking for strings that appear more than once in the string and voila!
function FindIntersection(strArr) {
  let singleItems = [];
  let repeatItems = [];
  strArr = strArr
    .join(",")
    .split(",")
    .sort((a, b) => {
      return a - b;
    });
  strArr.forEach((str) => {
    if (singleItems.indexOf(str) > -1) repeatItems.push(str);
    singleItems.push(str);
  });
  repeatItems.join(",");
  return repeatItems;
}
chigozieorunta commented on 09/24/20
4
Also, the main method code needs to be changed. I get a syntax error stating that FindIntersection method type (String[]) is not applicable for the arguments (String). Does anyone else see it?
devdascb commented on 10/19/20
-1
very useful
SivaNaveen commented on 10/22/20
-1
Question also includes about returning the 'resultArray" as sorted. That's missed here.
dexter2305 commented on 12/14/20
0
some of the test cases fail but in fact it's working. Example as below, it returns "false" as expected but fail in the test case. Kindly reply
package basic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

public class StringRetain {

	public static String FindIntersection(String[] strArr) {
		try {
			String list1 = strArr[0];
			String[] list1Array = list1.split(", ");

			String list2 = strArr[1];
			String[] list2Array = list2.split(", ");

			Collection<String> listOne = new ArrayList<String>(Arrays.asList(list1Array));

			Collection<String> listTwo = new ArrayList<String>(Arrays.asList(list2Array));

			listOne.retainAll(listTwo);
			// System.out.println("listOne----->" + listOne);

			if (!listOne.isEmpty()) {
				String separatedStr = String.join(",", listOne);

				// System.out.println("separatedStr----->" + listOne);
				return separatedStr;
			} else {
				return "false";
			}

		} catch (Exception e) {
			return "false";
		}

	}

	public static void main(String[] args) {

		String[] strArr = new String[] { "11, 12, 14, 16, 20", "11, 12, 13, 18, 21" };

		System.out.println("strArr--->" + FindIntersection(strArr));

	}
}
pcyuen98 commented on 03/05/21
0
Would be Big O(n^2)
PabloRSanchez commented on 03/31/21
0
function FindIntersection(strArr{
  let chooseArray = 0;
  let result = [];
  let arr1 = strArr[0].split(',').map(a => Number(a));
  let arr2 = strArr[1].split(',').map(a => Number(a));
  if (arr1.length > arr2.length) {
    chooseArray = 0;
  } else { chooseArray = 1 }


  let n = chooseArray === 0 ? arr1.length : arr2.length;
  for (let i = 0; i < n; i++) {
    if (chooseArray === 0) {
      if (arr2.includes(arr1[i])) {
        result.push(arr1[i]);
      }
    } else if (chooseArray === 1) {
      if (arr1.includes(arr2[i])) {
        result.push(arr2[i]);
      }
    }
  }


  // code goes here  
  return result && result.length ? result.join(',') : false;


}


// keep this function call here 
console.log(FindIntersection(readline()));
Bilalusuf93 commented on 08/22/21
-2
O(n^2)
aabwalter commented on 10/06/21
0
public static string FindIntersection(string[] strArr)
        {
			try
			{
                string list1 = strArr[0];
                string[] list1Array = list1.Split(',');


                string list2 = strArr[1];
                string[] list2Array = list2.Split(',');


                Collection<string> listOne = new Collection<string>(list1Array);
                Collection<string> listTwo = new Collection<string>(list2Array);


                listOne.Intersect(listTwo);
                if(listOne.Count > 0)
                {
                    string separatedStr = string.Join(",", listOne);
                    return separatedStr;
                }
                else
                {
                    return "false";
                }


            }
			catch (Exception)
			{
                return "false";
			}
        }
        public static void main(string[] args)
        {


            string[] strArr = new string[] { "11, 12, 14, 16, 20", "11, 12, 13, 18, 21" };


            Console.WriteLine("strArr--->" + FindIntersection(strArr));


        }
billymganda commented on 07/29/22
0
I type the same exact code, but for me, it says strArr.split is not a function, makes no sense when it works for you.
eshwar1212 commented on 02/05/23
Log in to submit a comment.