Master Basic Hashing Techniques for Efficient Data Structures

Introduction to Hashing

Hashing is a pivotal technique in data structures and algorithms that helps optimize search queries, especially frequency counting in arrays and strings. For a foundational understanding, you may want to explore the Introduction to Data Structures and Algorithms.

Problem Context: Counting Frequencies

Given an array, determine how many times a specific number appears.
Naive approach: Iterate over the array for each query, resulting in O(Q*N) complexity, which is inefficient for large inputs.

Basic Array Hashing

Create a frequency array (hash array) where indices represent possible numbers.
Pre-compute frequencies by iterating once over the input array.
Answer frequency queries in constant time by accessing the hash array.
Limitations:
- Array size constrained by maximum element value.
- Memory issues arise for very large maximum values (e.g., 10^9).
- Declaring large arrays globally allows bigger sizes (up to 10^7), inside functions limited to 10^6.

Character Hashing

Use a frequency array of size 26 for lowercase letters.
Map characters to indices using ASCII subtraction: index = character - 'a'.
For all ASCII characters, use an array of size 256.
Precompute once; queries answered in O(1).

Handling Large and Arbitrary Keys: Maps

Use C++ map or unordered_map for key-value storage where keys are values e.g., integers or characters.
map stores keys sorted; operations take O(log n) time.
unordered_map offers average O(1) time complexity for insertions and lookups, but worst-case O(n) due to collisions.

Understanding Map vs Unordered_Map

| Feature | map | unordered_map | |------------------------|-------------------|-------------------| | Ordering | Sorted by key | No guaranteed order| | Average time complexity| O(log n) | O(1) | | Worst-case time | O(log n) | O(n) due to collisions|

For a more detailed comparison and practical implications, check Understanding Data Structures Through C Language: A Comprehensive Guide.

Hashing Internals and Collisions

When numeric keys are huge, division method hashing is used: store key mod table size.
Collisions occur when multiple keys hash to the same index.
Collisions managed by chaining (linked lists) or other methods.
Collisions can degrade unordered_map to O(n) time, though rare.

Practical Tips

Prefer unordered_map for most use cases due to average O(1) complexity.
If facing timeouts, switch to map for stable O(log n) time.
Use ASCII-based indexing for character hashing.
For large numeric ranges beyond feasible arrays, use maps/unordered_maps.

Integrating this knowledge within a broader context, you might find the Comprehensive Overview of Data Structures and Algorithms Using Python useful.

Homework Challenge

Find the character or number with the highest and lowest frequency using map or array hashing.

Summary

This session wraps up basic hashing techniques crucial for efficient frequency queries and sets the foundation for advanced DS & Algo modules. Applying these concepts accelerates your problem-solving skills in coding interviews and competitive programming.

For a complete structured learning path covering algorithms and data structures, refer to Comprehensive Overview of Algorithms and Data Structures Course.

Remember to subscribe and comment "understood" if this helped you, and share your solutions to the homework problem!

hey everyone welcome back to the channel I hope you guys are doing extremely well so this is yet another lecture from the

stripers A to Z DSA course and this is India's most in-depth DS algo course why do I see that because you can check out

all the free courses all the paid batches you will not find any courses any batches with poor 55 modules or 455

problems sold in it this is the reason I'm saying that this is India's probably world's most in-depth es algo course

then the previous lectures we have covered till step 1.5 in this lecture we will be covering basic hashing once I

cover this we will be covering everything related to Basics that we require in order to start with Ds algo

so without waiting let's get started with the hashing lecture so we're solving a lot of interview problems

isn't it but whenever you go for interviews the first round will always be coding around so in order to clear

that coding round you have to actually give a lot of similar coding rounds in your preparation so one such coding

round is go Rush X by Newton School this is India's biggest competitive programming contest that is happening in

the year why do I say that because it has prices worth 10 lakh Rupees so what you need to do is there's a link in the

description go to that and you can click on register the moment you click on register you will get a form you can

post that you will be participating there will be eight questions that you have to solve in three hours after that

there will be a thorough plagiarism check and the results will be announced the first prize is one lakh rupees the

second is 50 000 and so on and there are a lot of prices for other people as well till the top 100 you can get a lot of

goodies and going forward you will also be getting a lot of gift vouchers so the prices are worth 10 lakh Rupees so what

I will recommend you is the link in the description make sure you go and register and participate in such

contests because this will help you in your preparation Journey so without waiting let's get back to the video now

when I talk about hashing it is one of the most important topics in DS algo if you do not understand hashing you will

not be able to solve a lot of problems in data structures and algorithms so please do not miss this lecture because

I'm going to teach you hashing and I'll be using pseudo code so language will not matter everything that I'll be

teaching will be in terms of pseudocode because for Loops are similar in C plus plus similar in Java and python so once

you understand the pseudo code once you understand the concept you can actually code it in any of the languages that you

are following this particular course in so in order to understand hashing let's take a initial problem imagine you're

given this particular array and now suddenly I come up and say hey can you tell me how many times does one appear

in the array and you can say that hey one appears twice in the array right because one is appearing once here and

one is appearing once here so one appears twice in the array and again come up and say hey can you please tell

me how many times does three appear in the array I will be saying three appears once I imagine I again come up and say

hey can you tell me how many times over appears in the array you'll be saying it doesn't appears in the array imagine I

again come up and say hey can you tell me how many times does 2 appear in the array you'll be like 2 appears twice

imagine again come up and say hey how many times does 10 appear in the array you'll be like okay listen 10 doesn't

appears in the array the trend is appearing zero times so given an array and you ask a lot of times very very

important points very very important point you asked a lot of times first you might be asked for any given number then

any other number then again the same number you could be asked for any given number of times for any number and they

might ask you how many times it appears and you have to tell me what is the first approach that comes to your mind

when you think about it because you know four Loops right the first approach that comes up is hey if I have given if

someone says the number is 1 the first approach that comes up to my mind is I will I trade through the entire array

what I'll do is I'll take this one and I'll compare it with the first guy one and I say yes and I'll take a counter

variable which is 0 I'll say this is equal to this so I update it to one next I'll go to two and I'll see is this

equal to one I'll send next I'll go to one and I'll say this is equal to this the counter which was one previously

will be updated to two next I'll go to this and I'll say is this equal to this no next I'll go to this and I'll say is

this equal to this and no so the counter stays at two so if I have to write the brute force method in order to find how

many times it appears can I say it will be a function which takes a number riding a play in pseudocode it will be a

function which takes a number probably an integer function because it has to return how many times it appears and you

can be like ball loop I and the I or rather you also need the array in the function so go ahead and take the array

as well end function and probably array again I'm writing the pseudo code guys I'm

just writing the pseudo code please focus on the logic so can I say probably I'll take a counter equal to 0

and I'll say fall I will loop from 0 and I'll Loop till the last of the array you already know this how do you Loop in the

array right and you will say hey if array of I is equal to equal to number can I say counter equal to counter plus

1 and I can end this for Loop and I'll say return counter and this will be my code can I

see this yes I can say this why does this work because it's very simple if you are given a number 1 that number one

is given over here and the array is given over here and you iterate through the entire array what is 0th Index this

is this what is after this first Index this is this and what are you doing you're saying array of 0 equal to equal

to 1 then you are increasing the counter So eventually you will iterate through the entire array and the counter value

will be updated at the end of the for Loop once it is updated you return the counter correct so in order to find how

many times one appears in the array what you can say is hey function take one and take this particular array and tell me

how many times it appears and it will return you to now to find out how many times three appears it will say a

function T3 and take this particular array and say how many times does three appear and it does a linear iteration it

goes to every element and checks if it is equal and it counts it and then end of the day it Returns the count simple

so if I have to ask you what is the time complexity can I say I'm running a loop for Biko of 10 times and there are

certain number of operations that we are doing but we do not calculate that in time complexity so can I say I'm running

the loop for n times there by the time that I am taking in order to compute how many times a number appears is bigger of

n so for this I will take we go of n for this I will take another big oven for this I'll take another big oven for this

I'll take another big oven for this I'll take another big oven so can I say for five times if I have to do

five times like these are five numbers five numbers if I have to find how many times each of these numbers appear can I

say the time complexity is 5 into B go often I can say and imagine if I give you a lot of such numbers

like a lot of such numbers if I give you a lot of such numbers and imagine there are Q numbers I give you Q

numbers and for every queue number sorry for every number you have to tell me how many times it appears can I see the time

complexity will be Q into n can I say the time complexity will be Q into n because every time you are taking

a for Loop and Computing it so thereby the time complexity will be Q because there are Q numbers and for every time

you are Computing in the time complexity boils down to Q into n and this is something which might not be good if you

imagine Q is very large imagine just imagine I am giving you Q to B 10 to the power 5 I'm giving you 10 to

the power 5 numbers and imagine I give you an array size I give you a huge array of 10 to the power 5 size and what

will happen then it will be B go of 10 to the power of 5 because 10 to the 5 numbers will be there and the array size

is 10 to the power 5 because it's a huge array to the number of operations will be 10 to the power 10 and the number of

operations is 10 to the power 10 how many time like how much time will it take if you remember I told you 10 to

the power 8 roughly takes around one second most of the problems you'll find on DS algo will be taking one second or

two second so if I'm taking 10 to the power 10 operations how many time how much time will it take it will take 10

to the power 10 seconds will take approximately 100 seconds how do I get that very simple if 10 to the power 8

takes one second then one operation will take one second by 10 to the power 8 10 times 10 operate addition will take 1 by

10 to the power 8 into 10 to the power 10 which is nothing but 10 to the power Square which is nothing but 100 seconds

so 10 to the power 10 will take 100 seconds which is a lot of time you cannot wait for one and a half minutes

for your program to execute this is where is something like hashing comes in it's a technique which will help you to

do it in a much faster way so if I have to Define hashing in extremely naive touch what is it it is something like

pre-storing and fetching this is what hashing is restore

something and fetch when required let's understand this in-depth now this is an array okay imagine the problem statement

States the array will add to Max have numbers till 12 or 15. let's say 12. at Max it will have 12.

what does it mean over here you're seeing 1 2 1 3 so at Max over here it is 3 but imagine a problem statement where

I State I'll give you an array and the array at Max will have 12. over here it is having 3 at Max but the array can

have at Max of 12. so what hashing says is okay I know I can have numbers from 0 1 to 3 till 12. so what I will do is I

will create another array okay remember this I'll create another array and I'll call this as

hashary and in this hashtag what I'll do is I'll say 0 1 2

so what I'll do is I'll create an array of size 13 and I know the indexing starts from 0 and the indexing will go

on till 12 and I'll assign everything as 0 initial and this is something which I'll call as hash array this is

something which I'll call as hash array or you can call it as a frequency array as well now what I will do is I will do

some pre-calculation remember this I will do some pre-calculation now what is this

pre-calculation it's very simple I go to the first number which is one and I say okay you are one so I will go to the

first index and I'll say hey can you just remember that I have one one so he will say okay I'll remember you have one

next I'll go to this too so it will come to this too and say hey can you remember I have one two I'll say okay next we'll

go to this one and you'll see go to one and say that he has one more one he goes to one and says you have one more one

this is okay I know I have two ones he'll go to three and say me go and remember you have one three he will do

that he goes to two again says go and remember you have one two so two increases to two so apparently the

moment you have traveled for all the elements in the array the hash array if you properly observe in one index

because one is the number representation in one it states I'm appearing twice in two it states I'm appearing twice in

three it states I'm appearing once and all the others are marked as zero because they do not appear so now this

is the pre-store that you have done this is the pre-store this is a pre-fetching that you have done now what will happen

now you come over here and you say Hey listen how many times one appears now you do

not Loop and find out how many times one appears what do you say is hey how many times one appear I don't I have done a

prefetching I'll go to one and I'll say I'll paste twice I get twice for this one I go and say how many times it

appears and I'll get this value at hash of one instead of I trading in the entire array I say hash

of one and it tells tells me 2. for those three I'll say hash of three and it will give me one for this 4 I'll say

hash of four and it'll tell me zero pour this two I'll do hash of two it'll give me two for this 10 I'll do hash of 10

it'll give me 0 for this 12 I'll do hash of 12 it will give me 0. so can I say I just did a single can I say I just did a

single pre-computation and that apparently solved all of my queries in one go so I have to code this up can I

say I'll first be given the size of the array imagine this is five size array and one three two one and three so given

this array then probably I'll give you the number of numbers for whom I require how many times they appear I tell you I

need for five numbers and the number is first I'll say how many times one appears next I'll say how many times

let's say four appears next time how many times two appears next time how many times three appears X how many

times 12 FPS so five numbers for which I have to find how many times they appear so this is the size of the array this is

the array how many numbers like how many queries are you giving and these are the queries one four two three twelve tell

me how many times one appears tell me how many times four appears tell me how many times two or Ps tell me how many

times three appears tell me how many times twelve up so I need to take all of these inputs so it's a very simple way

first n and then C enough n when you declare the array of size n and then you say for INT I equal to 0 I

lesser than I plus plus then you go across and say scene of array of five perfect

you've done this what's the next step if you take the query let's first I'm taking up all the inputs okay scene of Q

so you can run a while loop like Q minus minus and then you can say take me the number

and see enough number so this is what is the input first the array then the queries and for

every query the number you need to tell me how many times the number appears so this is where you do some pre-compute

and this is the fetch method this is where you fetch so can I say for pre-computation I need hash I need a

hash and over here for Simplicity purpose let's take 13 because I know at Max the size can be till 12. whatever

the problem States if the problem States the maximum size can be till 10 to the power 5 then you will go across and say

10 to the power 5 if the problem States 10 to the power 6 you go across and declare it over here kept it simple apps

that that maximum size will be 12 so I require a size 13 because in order to have the 12th index I need a size of 13

because the last array index is 12 all of us know that now the pre competition was very simple I will go like this to

the array this is the iteration of the array now I know for array element I have to go to that index and do a plus

one so I say hey go to that index which is array of I because that is the index where I have to go and I will tell him

can you increase your value by 1 and increases because previously it was 0 and he will for every number it goes to

that index and says plus equal to once this is done now I have my hash added so if I go back

to the iPad can I say I have this particular hashtag ready after the pre competition because 1 means hash of 1

plus equal to 1 that goes to this and does a one and similarly for this number similarly for this for this and for this

this hash array is ready the input is different but it's okay once the hashara is ready you have the

number you just fetch it so it says C out of hash of number this is the number of

times it appears and you can just go ahead and do this I'll go ahead and quickly run this and

see if it is running fine so if you see this these are the answers how many times one appears twice hundred

times four appears 0 how many times two appears once how many times three appears twice how many times 12 appears

zero depending on what is the maximum size of the array you declare the hash now a question that might come up to

your mind striver in this you said the attic could be having a Max element l12 so it was very

obvious that you declare an array of size 13 because the last index then we will get as 12 and we can keep how many

times 12 RPS but what I tell you that the maximum array element can be till 10 to the power 9

like it can have numbers till 10 to the power 9 or maybe 10 to the power 12 or maybe 10 to the power 15. what if they

have larger numbers can we declare an array of size 10 to the power 9 plus 1 because apparently that is what we are

seeing if there was an array of size at Max till 12 we declared a size 13. so if the array has Max Elemental 10 to the

power 9. can we declare an array of size 10 to the power 9 plus 1 the answer to that is no you cannot the maximum size

array that you can declare is 10 to the power 6 if it is of integer inside very important inside Main

inside main what does it mean if I go back to the code this is where you declare if you are declaring it inside

mean it can only go up to 10 to the power 6 like somewhere near about you cannot declare something like 10 to the

power 7 this will throw you segmentation fault it will not be able to allocate that much memory but but if you go

across and declare it somewhere globally which means over here if I go across and declare somewhere globally I can

actually do it till 1 E7 which is 10 to the power 7. so if you declare globally the array the array can go till 10 to

the power 7 as well if it is declared globally like 25 7 plus 1 might also work near about 10 to the power 7 it

will go but if it is declared globally very very important this is something which I'm talking for integers because

we are dealing with hashing for Boolean yes for Boolean this value will be if you are declaring

a Boolean array inside intervene you can go till 10 to the power 7 globally you can go till 10 to the party

you can run them and see if you declare anything like 10 to the power 8 Inside Yes inside your intervene it is going to

throw you a segmentation part so let's let's go into the code editor and imagine instead of 13 I said 10 to the

power 7 okay and I'll let's try to uh run this and see if it is taking 10 to the power 7. so if you look at the

terminal it actually says there is a problem because the memory size is something which it cannot allocate but

the moment I reduce one zero and I try to rerun you will see that this is actually

running fine let's run this you see it is running fine

and if I add one more zero and I go across and declare this globally you will actually see this is like you don't

need to give 0 because if you declare globally everything is initialized as 0 instead of garbage values

if you go over there I declared it hey what is the problem with skipping

question let's run this Ash is ambiguous because let's do double

hash because the name is something which is already taken it's not on it

you see it is working fine if I declared it globally as 10 to the power 7 it did run fine so this is something

which I wanted to tell you this is something which I wanted to tell you if you are using array in order to do

hashing you can only go up to 10 to the power 6 inside a mean or 10 to the power 7 globally not beyond that for something

like 10 to the power 9 what will we be using that is something which we'll be discussing in the later half of the

video so make sure you watch the video till the end so till now what have we learned we kind

of learned about number hashing if there is a problem which requires number hashing we can use

arrays to Hash them right what was the next thing that we will be learning there is something as character hashing

can we do character hashing using arrays yes we can and that is something which we will be learning imagine I give you a

string uh like a b c d a b e f c and I give you certain queries and I ask you how many times does a appear can I say

once twice is what a appears how many times does c appear to ask you how many times C appears it will be one and again

twice how many times Z appears it will be zero if you look at over here that doesn't

appears and similarly I can give you a lot of other things like Q queries

I can ask you Q times a b c I can I can give you any character and it is your task to tell me how many times does that

character appear in this particular again what is the standard procedure the standard procedure is very simple you

pick up a and you iterate in the string and you say a equal to a yes counter equal to 1 a equal to a here count equal

to 2 so you just basically I trade through the string and in a similar way you compare the character with each of

the characters and you count it so if I have to write the pseudo code this is how the pseudo code will look like

you take the character C and you probably take the string C and what you do is you keep a counter zero and now

you go through the string I equal to zero imagine the size of the string is n you go till that and you say F if s of I

is equal to character C then I will do a counter plus plus and at the end of the day I can return that counter so this is

what the simple pseudo code will be for every character you go ahead again if you do the similar thing for Q queries

how much time will you end up taking every query you are taking n so for Q queries you will be taking big O of Q

into n time similar to the previous problem so the question is can you hash them into arrays and the answer to that

is yes so the question comes up how do you hash them using arrays because if we remember the arrays have indexes like 0

1 2 3 and if I have to talk about these characters imagine I'm strictly stating imagine the array only has lower

case letters imagine the array only has lower case letters in that case how can you hide now I know lowercase means it

will have a b till set how many elements I know there will be 26 elements because those many

elements is what we 25 for 26. so I know there will be 26 characters 26 lower case carrying so if I have to

practically think can I have an array of size 26 I I'll be like yes I can so imagine if you have an

array of size 26. what will it be indexed from it'll be index from 0 then to 1 then to 2 then to

3 and probably to four then probably to 5 then probably to six and so on till 25. can I say this this will be the r

indexing can I see this since I know there are 26 alphabets can I correspond a to zero can I correspond B to 1

basically I'm mapping them in my memory I'm saying okay wait can I say A to B the zeroth index I do not have any

relation but I will say I will assume unless you may to be this I'll assume B to be this C to be this this and this

and this to be said can I see this every character I will have an index I will [Music]

if I can do that I think my problem will be solved now you might have a question in your head so striver you are saying

it will be this B will be the civil with this this will be this and how do I program it because in program I cannot

visualize I need something which works programmatically code wise so if I have to talk about f

I can visualize over here that f is five but how do I do that in program this is where something like ASCII value comes

in if you do not know about ASCII it's basically American Standard code for information interchange so if I have to

show you the ASCII so there are 256 characters and these this is how the ASCII looks like so if I just scroll

across these are the ASCII values so everyone the digit 0 has an ASCII value of 48 the digit 1 has an ASCII value of

49 going across the upper case at a the upper case a has an ASCII of 65 I go across uh the lowercase a has an ASCII

of 97 the lowercase z has an ASCII of 122 what do I mean by ASCII so imagine if you are writing a code where you say

int x equal to character a so what will X store because you are storing a character into x and x is in integer

data type so what happens is this a is converted yes this a is converted into its ASCII and this is a small a the

ASCII is 97 the X tows the ASCII of a that is 97 got it it will not throw us in tactical error

instead it will Typecast it so we know about ASCII so something I know for sure is small a is 97 and small Z is

122. so how can you represent now it's very simple so imagine you have to represent for f

these f minus a what is F's ASCII value if I look at the F's ASCII value that's 102

because when you're doing a subtraction subtraction happens between two integers so computer sees what's the integer he

says 102 because that is my ASCII what is the ASCII of smaller a 97 so I get 5. you get 5 and that is what you required

if you require for a that's a minus a equal to 0 if you require for B that's B minus b equal to one if you require

sorry B minus equal to one if you require for C that's C minus a equal to 2 so apparently the formula that you

need is character minus a if you do this you get the corresponding index in the hash array

and then you can easily index it you can easily hash it so imagine you are having at a you do a minus a you get zero so

you go to zero and you say one right next is B Theta V minus a that is one so you divide one next is C there's

a c minus a that's two you do One X is d That's D minus a so you go into over here next is a that says a minus a equal

to zero zero two next is B you do what two and X is e e minus E is nothing but four so if e minus a is four you go to

four and do a f f minus a is five take one to one c c minus a is nothing but two so you do a two done as simple as

that this is how you hash it you require 26 and imagine if the string contains uppercase as well you you just saw that

you have 256 characters into you can just go across and create an array till 256 size

and this time you don't have to subtract anything or smaller a the value is 97 so the

smaller a will get at 97 or smaller B the value is 98 so it goes to 98

simple just because you just had lowercase letters that is the reason you took a 26

size array you could have taken a 256 size array that would have worked as well I'll show you that in code so let's

look at the input we're given the string we're given the queries and these are the number of queries that we are given

and we have to print the output so what is the first thing that we are given string so let's see X string and we say

C enough s I've taken the string now we need the query so let's take all the queries

very simple and I say while Q minus points and now we need the character so let's

take the character and that's it these are the inputs that we have to do we know we need to do some pre-compute

because we're performing hashing and we know we have to fetch it over here in order to print the answer let's

do the pre-computation can I say that I require a hash because we are sure that it will be of size 26. I require an hash

of basic size and now I will go across the string so in order to go across the

string this is one of the ways you say s dot size and then you go across I plus plus and you say hash of s of I minus a

plus plus now what this will do is this is your indexing character minus a will give you the index at which you have to

do it for the hash and over here in order to fetch you say C out hash of

C minus a because the index in order to get the index it's character minus a that's what you do

you go across and do an angle I'll go across and let's quickly run this off and see if it is running fine

it is we saw that it is giving us the correct answers now we took hash of 26. I know that was done because we knew

that they were just lower case letters imagine it doesn't State you that it has just lower case letters in that case we

know the number of characters that exist is that exist is 246. I do 256. instead of

doing this I'll do s of I if it's a it goes to 97 if it's B it goes to 98

so and over here also I don't do anything even if you do this this is still gonna run fine

because it's it's taking a bigger size but it's mapping it correctly just because we did not require uppercase and

all the other characters I took it of size 26. if it doesn't States about the exclusivity of the characters

you have to take 256 this is are you hash all the characters so are there any complications in order to Hash

characters because in number hashing we saw that if the number goes till 10 to the power 9 there might be a problem but

in character there will never be a problem because at Max there are 256 characters and array can store 256

elements so for character hashing you don't have to think much always prefer arrays always and always use this logic

character minus a for lowercase if there are uppercase it will be character minus capital A and if there are all

characters 256 and simply hash the character it will be Auto converted yes if I'm saying s of I this Auto converts

itself to its ASCII because hash of hash needs an index and the index is an integer s of I is a character but it

auto casts itself into an image got it so this is a character s of I but the hash

inside its bracket hash inside its brackets needs an integer so even if you write a character it will auto cast

itself to its integer value which is the ASCII value this is why coming back to the problem that we had

in number hashing so in number hashing when we were trying to Hash it into the arrays we saw that we can at match do it

till 10 to the power 7 that also if we declare the array globally and for numbers exceeding 10 to the power 7 like

10 to the power 9 or 10 to the power 12 or 10 to the power 18 we cannot hash it using arrays that is not possible this

is something that we need to solve and that is where in C plus plus

STL comes in if you have not seen the STL video please go back and watch it and in Java The Collection comes in so

in STL there are two things one is the map well the other one is the unordered map which I'll be talking in depth and

most of the concepts that I'll be talking about map in another map also apply to the hash mark it is just the

same stuff just the writing format is different and the concept inside it is the same so

let's understand map and unordered map so till now we were taking an array right if you remember we we took an

array of size 13 and then we hash it and in C plus plus let's talk about map so what happens is imagine you're given an

array something like 1 comma two comma three comma 1 comma three comma two imagine a given something like this

so in C plus plus what happens is map is a data store so I'll just represent this with a bucket

as well so what do you do is you say okay I know there has to be a key

what is the key over here so this is the key the number is the key

so the number is the key remember this and there has to be a corresponding value to it and the value over here is

the frequency so this is how it is defined you basically say okay what is your key is

your number how many times it appears is the value this is what you do as simple as that so what I do is okay I know one

thing at the first step I have one so I will say can you go ahead and if if remember

one thing before before I trading in there before I trading in the array if you say MPP of one this will return you

zero because it doesn't exist in the map so the value the corresponding value will be zero right

so the moment you go to one you say MPP of one plus plus so what will happen if it doesn't exist in the map it will go

to the map and say one you do not exist that's zero it's zero zero plus plus is one

so it will store a key value key mapped to a value of next it goes to 2 and does a map 2 plus

and it says it doesn't stores too so what happens is it goes and stores two next it goes to three again goes and

sees doesn't stores three so three plus plus goes to one and sees okay I already have

let's go back to that one and say can you please increase my value so it just increases its value to 2. next goes to

three again increases its value to two next goes to two again increases its value two so what do you need to do is

MPP of array of I plus plus that's what you need to do and imagine I'll just erase this imagine I had a number like

12. then what would have happened she would have done npp12 plus plus so 12 would

have gone as 1. quite simple very very soon

so something to observe over here even if the number was still 12 and you would

have used array hashing you would have ended up taking a size 13 array in the array hashing

and over here how many elements are you storing we're just storing the elements that are required because you require

one two three and twelve so four elements are stored whereas in Array hashing you had to declare a 13 size

array if the maximum was still 12 in order to get the 12th index so this is where map is slightly beneficial it

takes a little less memory because it will just store the elements that are required

if you do for mppo4 it is not there in the map it will automatically throw you a zero but it doesn't stores for it

doesn't store sport got it so if I go back to the code you see that you have a n you have the array you have the

queries and then you have all the queries so it's quite simple you say N is a scene of N and then you say int

array of n then you say 4 I and the I equal to 0 I lesser than n i plus plus and then you go across and say

let's take these arrays values array of I and now you need the queries

let's take the queries intq CN of Q and now you do while Q minus minus and then you take the number

and you take number over here and you say C out this is where you fetch so you pre-compute here

and then you catch it over here so we have to do the pre-compute so what you do is map of Key and you know the

key is a number which will be integer if the number goes till like 10 to the power 9 or 10 to the power 12 then you

could also go out and take along because there will be bigger numbers or you can take long long as well depending on the

size of the numbers you can Define your keys data type done and now what you do is you go across since I into I equal to

0 I lesser than n i plus plus and you say map of array of I need to do a plus plus

quite simple and in order to fetch it you say C out of map of number

and once you've done this you can go ahead and say can you please run this and if you run this you will see that

everything is fine for appears 0 that's why 12 appears once it does run fine so remember one thing

the map stores all the values in sorted order this is something which you have to keep in mind the map stores all the

values in sorted out what does that mean this will be at the first place in the map this will be at the second place

this will be the third place this will be at the fourth how can I prove it what I'll do is I'll go ahead and say let's

iterate in the map so if you just iterate in the map this is how you iterate in the map and Auto iterator on

the map and if you do see out of it dot first up something like this and do ID dot second

this is how you can get it so if I just try to run this you will see what will happen

before printing all of this it actually shows you one appears twice and this is how it is stored in the map this is how

you can also iterate in the map very so let's quickly comment this off now you might have a question your pre-computing

hairs driver that's like running a loop or taking the input and then doing the pre-compute you can also do this over

here it is okay like you can declare this before this and itself

and you can just omit the pre-computation can be done while taking the input as well it doesn't matters it

will save you one for Loop but that is okay that won't change anything or that won't make your problem super fast why

won't it make super fast because it's n plus n and not n into n n into n generates a bigger value n plus n is

like 2N and if you remember the time complexity we ignore 2 3 and all these smaller values remember

so we did learn about map can this map be used in something else yes you can also use map in string hashing now what

is the key over here if you remember the key is a character so what you can do is you can say map of

character and store its frequency so instead of using a array for hashing you can go ahead and see map of character

and now you can say map of whatever is your character s of I plus plus this will not be converted

into integer now your map will be storing something like this a appears twice B appears once C appears once so

depending on what you are trying to Hash that will become your key and what are you storing that will become your value

over here we are storing the frequency that's why it's ring plus plus all right in Java so in Java there is something as

hashmap you can use it it works in the similar fashion now let's talk about something very what is the time

complexity of this map so in order to do something like map of something plus plus that is basically storing in the

map now to fetch from the map that is MPP of you're doing array of I or something

like this so that's fetching from the map the story of Patrick famous storing or fetching both of them in a

map in a map takes logarithmic of n takes logarithmic of n in all cases in best in average in

worst in all cases takes logarithmic of n remember this but there is something as

unordered map there's something as unordered map which we will be talking

about now so let's go back to the code so even if I write this unordered will it run and if I go ahead and run this

it will actually run you see the values are getting printed so even if you take unordered map it does run now what is

the meaning of unordered map so the name recommends unordered so imagine now I go across the map and try to print it

so if you remember in the map it was storing everything in this sorted fashion but over here by the way yes my

bad let's amend the song in the map everything was stored in the sorted order but over here if you see there is

no particular order there is absolutely no order it can change on every program like overheads three twelve to one if

you run it if you run the same code on some other compiler it might be having some different order so the order is

something which you cannot decide so as the name recommends it is unordered but then you might ask what is the advantage

of using this let's talk about this when you are storing something in the map which you are doing and when you're

fetching in the map the average and the best time complexity is a constant one

the average and the best is average again most of the cases in most

of the cases maybe go of one for storing and fetching but there is something as the worst case

and that ends up taking linear time linear time what do you mean by linear time this is nothing but the number of

elements in the map this is nothing but the number of elements in the map when I talk about n I'm talking about

be computed so the average in the best case will be week of one in most of the cases it will be B go of one in very

minor cases it will happen once in a blue moon if the problem setup is extremely like it just wants to make

your code fail it might end up giving a worst case it might end up taking week of N and a code apparently

will take n Square because imagine if this line is taking we go of N and you're running a loop over it so it's

like n and this is n so n into n n into n happens but if this line is Big O of 1 then it becomes n into one most of the

times what you need to do is you need to do you need to use unordered map yes if it fails if it gives you a time limit

exceeded that means taking a lot of time then you switch back to map but first preference should be unordered map

because the worst case very rarely happens I know it's it is a worst case but it very very rarely happens why does

the worst case happens because of internal collisions because of internal collisions so since we are

talking about collisions let's understand how does hashing go because if you remember I told you

that the moment it crosses 10 to the power 7 an array hashing cannot be done so how does how the map data structure

created will someone ask you might not like in interviews they generally don't ask that much even if they ask

only telling them about division method will work these two methods are something which you just need to know

the names might come up in a semesters but this is the method that you have to understand

so how is the internal map designed because if I'm talking about design I know I can

design an array hash but for numbers like 10 to the by 18 how do I store it this is where internally you might see

like these map data structures are implemented in different different ways they might be using division method they

might be using folding mid Square they are implemented in a very complex way you don't need to know it let's

understand what is the division method because we take the division method then I might be able to explain you what is

collisions so let's understand the division method so imagine imagine I'm giving you numbers like in an array I'm

giving you numbers like 2 5. and then 15. and then 55 not 55 uh not 15 let's take 16 and let's say

28 and let's take 139 okay so these are the numbers that I've given so you can do array hashing because

I'm not talking about map if you have to do array hash you can actually go ahead and create an array of size 140 where

you go like 0 1 and Del till 139 because if you create an array of size 140 you'll get 113 and then you can hash it

but imagine I tell you imagine I tell you you cannot create an array for a time being you cannot create an array of

size greater than 10 this is not allowed an array of greater than size 10 is not allowed I'm taking very small values in

order to explain you can map this to bigger values so you can map this to the bigger problem that we are trying to

solve in the bigger problem imagine you have number like 100 and 18 and then 25 16 and then 25 4 and the maximum size

allowed is 10 to the power 7 Beyond this it's not allowed right so same problem we are solving we have bigger numbers

but as of now we have a restriction that you cannot create an array greater than size

10 greater than equal to like at Max 10 is allowed not more than how will you do it so this is where something like a

division method comes in yes this is where something like a division method comes what does division method say

division says okay I just have 10 size are allowed which means I Can Only Store

0 to 9 right so it's like 0 1 2 so as I said an array of greater than

size 10 is not allowed so this is what we can have at Max so 0 9 and we will be using the division method in order to

Hash it how will we use the division method it's very simple if we have two whatever number we have we will try to

modulate it with 10. so for 2 the corresponding value will be two so I'll go to 2 and I'll say data PS1 5 will

modulated with 10 I'll get 5. for 16 I'll modulate with 10 I'll get 6. for 28 I'll modulate with 10 and I will

get something like what will I get I'll get 8. for 139 I will modulate with 9 and I'll

get 9. I'll do a 1. right now what I do is I have

used a division method to kind of trim down the number and have been able to somehow array hash

it right so this is what the division

but your brain might be thinking a lot of things I'll come to that one don't worry

so this is how the division method works if someone does ask you and someone just comes up and asks you hey how many times

139 appears so you say 139 modulo 10 is equal to 9 what is the value at 9 it's 1 so it appears one time that's how you

retrieve the division method is modulating so that's how you put it and that's how you retrieve it so that's how

you trim down the number and you might have a lot of questions I'll come to each of these questions now

now what I've done is I have kind of drawn the array in the vertical fashion and the first question that might come

to your headers what if on modulo 10 they are same numbers because this is two

so now I'll do it a slightly different this is 2 30 okay we have one two we have one

we have five we have one file we have 16 we have 1 6. so I'll probably store the numbers in

some chaining in some chaining this is what you call as linear chaining again these things will be done using

linked list you don't need to know just understand the logic and concept 28 modulo 10 is 8. it's an 80 to 28 139

modular 10 is 9. say 9 you say 139 38 here comes the Collision Factor this was also modular 8 this was also

modulated so you cannot stole you see I have one more 30 next

48 again you do a modulo 10 and you're getting so you go and say chain it and the same

again you get eight but this time you get 28 they chain it but you do not chain it in the back instead of that you

chain it somewhere like this 28 and back over here and you kind of break this this is something which can be done

using linked list and in a very simple way to be learning it it learning this in linked list so you change it 28 is

there twice and then again you get 18. so you chain it something like 18 and then you big you make 28 that's like 18

28 28 38 they've changed it right so this is how it works now if someone does comes up and asks

you how many times 28 appears so what what we do is we say 28 module 8 we go to 8 Direct

and we know there will be limited numbers and we know it is sorted

so there are a lot of search algorithms which are applied internally and you can easily do a binary search on it and

you'll find that there are two numbers and it can be done in minimal time minimal time got it so this was the

division method that I did talk about so you can do some chaining and you can keep it in certain ways imagine you had

22 then this will be changed here so chaining can be done and you can always keep them in limited memory storage

so do you need to implement this no you just need to understand the concept what then but sorry then what is

Collision so in order to find out how many times 28 appeared what did you do you just

went to eight and then you figured out 28 appears twice because it was chained in a sorted order because it has changed

in or sorted out so it is quite easy to find out 28 twice but but if if

just just realize this eight this chain would have been Ultra huge

do they use the division method intern no they use some method which is a mixture of everything

depending on your input they find out some method and they use it imagine they're using a method internally which

falls under Collision what is Collision you're given an array imagine they're

using differently just imagine they are not just imagine and I give you something like 18 28 38 48 and all that

is are ending with eight so how will the chain look like a chain will be on a you

will have all the numbers all the numbers so apparently

all the other memories are not used and in eight you had all the numbers it's a huge chain Collision happened everyone

went to the same hash Place Collision is this everyone went to the same hash place so if everyone went to the same

hash place you have to find it out it's gonna be tough It's Gonna Take a lot of time got it this is what we mean as

Collision whatever hash they're using remember this whatever hash they're using

internally can be anything you cannot say what they're using whatever hash they're using

it ends up that all your keys all your keys end up at the same hash value hash index

ends up at the same hash Index this is when the worst case will happen and be governed now you understand why I said

it's a very very minor case it might not happen it like the the problems it has to be extremely brilliant has to find

out and then he might be able to do it but it's an extremely rare case to happen this is why in interviews when

you talk about the time complexity you tell them in the best in the average if I'm using another map it's big of one if

I go across the worst case it will be B Co of n so this is how it works so I hope you've understood the division

method this is the normal simple division method and linear chaining is done if there are multiple values

folding and mid Square method not required not required I just told you the division method because I wanted to

explain you what is collision and in order to explain Collision then I could have explained you why we go often is

such a like it never happens it just happens once in a blue moon uh quick another thing

can the key be an integer yes can can it be double can it be a character can it be a string it can be anything it can

even be a pair of integers it can be pair of two guys as well this can also be a key key can be anything any data

structure can be a key in a map but when it comes to unordered map you can only have individual data types

you cannot say pair of end comma int to be a key and the value to be into this cannot be a key in unordered map this

cannot but in map any data structure any particular data type can be a key in on ordered map it's limited to integer

double character string you cannot take like pair of end comma and or something like a vector of it it will not allow

you remember this in mind a lot of you might be thinking uh this chaining stuff and everything no need to

worry no one is going to ask you in interviews it's just for understanding what are collisions and if someone will

ask you about this complexity just for explaining no one is going to ask you to implement this no one no one trust me on

this so coming back to the course you can do this can you do this find the highest

and lowest frequency I'll give you this as homework it's quite simple the hinters you can use map or you can use

array hashing and then depending on how many times they appear in map you can iterate like this and this is what has

to be maximum if you're finding highest frequency so try to do this it's quite simple some if else statements will do

this will be your homework once you've done this you can put the code in the comments I'll check it out and the other

people will also get help from it so with this I can say that the learn the basic stuff module is completed from the

scribers A to Z goals the next module we will go to step two so guys I hope you've understood everything I thought

just in case you did please hit that like button and uh yeah to follow our tradition make sure you comment

understood in the comments so that I get to know that you've understood everything and if you're new to our

Channel what are you waiting for hit that subscribe button because that is the only thing that keeps you motivated

to me such kind of content and I do get disheartened because nearly 60 of the users who watch my video do not hit that

subscribe button I know I know a lot of people watch videos they do not consider hitting it so please please do consider

hitting it because it does motivate me a lot and if you haven't followed me on Instagram Twitter LinkedIn all the links

will be in the description make sure you follow me across everywhere and do share your learnings using the hashtag with

this I'll be wrapping up this video let's put in some other videos [Music]

Heads up!

This summary and transcript were automatically generated using AI with the Free YouTube Transcript Summary Tool by LunaNotes.

Generate a summary for free

Related Summaries

Comprehensive Guide to Data Structures: Arrays to Graphs Explained

Explore fundamental concepts of data structures from arrays, lists, stacks, queues to trees and graphs. Learn definitions, real-world examples, implementation strategies, and algorithmic insights for efficient data organization and manipulation.

Understanding Data Structures Through C Language: A Comprehensive Guide

This video introduces the concept of data structures using the C programming language, explaining the importance of algorithms in structuring information. It covers various types of data structures, including linear and nonlinear types, and emphasizes the significance of arrays, stacks, queues, and linked lists in effective data storage and processing.

Introduction to Data Structures and Algorithms

This video provides a comprehensive introduction to data structures and algorithms, explaining key concepts such as data, data structures, their purpose, classifications, and operations. It also covers algorithms, their properties, and practical implementation examples.

Comprehensive Overview of Data Structures and Algorithms Using Python

This video provides an in-depth exploration of data structures and algorithms using Python, covering essential topics such as linked lists, stacks, queues, and sorting algorithms. The session includes practical coding examples, theoretical explanations, and insights into the efficiency of various algorithms.

Comprehensive Overview of Algorithms and Data Structures Course

This course provides an in-depth exploration of algorithms and data structures, focusing on sorting and searching algorithms. It covers key concepts such as recursion, big O notation, and the implementation of various algorithms including merge sort, quick sort, and linear search, using Python as the primary programming language.