DataStructure for Everyone

Lots of Duplicate Data and the Data there are different list for that Data.

What would you do if You have to find the One element from 2 lists ?

List1 = [1,23,35,12,44,86,…….,n]

List2 = [22,35,12,55,78,90,…..,n]

Most People will use Two For Loop for that like this:

for(int i=0; i<list1.size();i++){

for(int j=0;int list2.size();j++){

if(list1.get(i) == list2.get(j)){

printf(“Congratulations! You find it.”);
break;
}

}

}

Really! after waiting for a this time

That’s what everyone thinks before knowing DataStructures. But that’s not the right approach to work with. I will show you why and how you can rethink it :

1. The Time and Space plays important role in Computer, so either you compromise with Time or Space it’s basically you choice and you must think which you are going to Drop for one. And in this Situation you time which program take for 2 loop is O(n2) means you are traversing each element in the loop which cost you a lot of time.

2. Now come to this program Space complexity so you gonna use normal O(1)Because you are not saving anything. So it’s just sweet and simple O(1). Every Programmer love O(1) because it’s doesn’t require anything just like 0 and 1.

Now we know this is not a Good approach so what be the Good approach

So if the problem is related with the Time and not the Space let’s sacrifice our Space, Sorry Space we don’t have to do it with you.

We can use just a Simple Map in our Program!

Now lets see how a Map will help us to make this Program from O(n2) to just O(n)

Wait what O(n)? Yes you are thinking it right.

Let see this Program:

List1 = [1,23,35,12,44,86,…….,n]

List2 = [22,35,12,55,78,90,…..,n]

// It’s just a java implementation of Map don’t look at it like what is written here

Map<Long, boolean> myMap = new HashMap<>();

//Ok here is what you love

const myMap = new Map();

//First we will Populate our Map and use the space as O(n)

for(int i=0;i<List1.size();i++ ){

if( !myMap.containsKey(List1.get(i)) ){

myMap.put(List1.get(i), true);

}

}

//Now here is your happy Program

for(int i=0; i<List2.size();j++){

if( myMap.containsKey(List2.get(j)) )

printf(“Congratulations! You find it.”);

}

Now let’s talk about Time and Space Complexity

Time complexity to our Optimal solution is O(n).

Space Complexity to our Solution is O(n).

But it is way better than having O(n2).

Thanks for Reading!