title
Hashing | Maps | Time Complexity | Collisions | Division Rule of Hashing | Strivers A2Z DSA Course

description
Register for free in Coding Contest: https://bit.ly/RV_CodeRushX Full Course: https://takeuforward.org/strivers-a2z-dsa-course/strivers-a2z-dsa-course-sheet-2/ Notes: https://takeuforward.org/hashing/hashing-maps-time-complexity-collisions-division-rule-of-hashing-strivers-a2z-dsa-course/ You can follow me across social media, all my handles are below: Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward 0:00 Introduction 2:01 Why Hashing ? 10:43 Problem 1 - Count elements of array 14:00 Problem 1 - Code 18:06 Maximum hash Array size (Main Vs Global) 22:06 Character Hashing & Problem - 2 30:16 Problem - 2 Code 33:52 Map / Hash Map 38:39 Problem - 1 Code by map 42:03 Problem - 2 Code by map 43:00 Time Complexity (map), unordered_map 47:00 Hashing Methods 54:30 Collision 58:30 Homework 59:56 Outro

detail
{'title': 'Hashing | Maps | Time Complexity | Collisions | Division Rule of Hashing | Strivers A2Z DSA Course', 'heatmap': [{'end': 1083.586, 'start': 969.068, 'weight': 0.941}, {'end': 2093.038, 'start': 1869.651, 'weight': 0.701}, {'end': 2204.172, 'start': 2124.388, 'weight': 0.819}, {'end': 2458.55, 'start': 2415.53, 'weight': 1}, {'end': 2639.012, 'start': 2594.038, 'weight': 0.753}, {'end': 2849.77, 'start': 2812.084, 'weight': 0.855}], 'summary': 'Course offers a comprehensive dsa program with 455 modules and a competitive programming contest with 10 lakh rupees in prizes. it covers hashing, array pre-computation, character hashing, stl in c++ and java collections, and map data structure time complexity, emphasizing time complexity, frequency counting, and efficient computation.', 'chapters': [{'end': 122.805, 'segs': [{'end': 33.327, 'src': 'embed', 'start': 3.271, 'weight': 0, 'content': [{'end': 4.572, 'text': 'hey, everyone, welcome back to the channel.', 'start': 3.271, 'duration': 1.301}, {'end': 6.392, 'text': 'i hope you guys are doing extremely well.', 'start': 4.572, 'duration': 1.82}, {'end': 14.536, 'text': "so this is yet another lecture from the strivers a2z dsa course and this is india's most in-depth ds algo course.", 'start': 6.392, 'duration': 8.144}, {'end': 15.457, 'text': 'why do i say that?', 'start': 14.536, 'duration': 0.921}, {'end': 19.098, 'text': 'because you can check out all the free courses, all the paid batches.', 'start': 15.457, 'duration': 3.641}, {'end': 26.422, 'text': 'you will not find any courses, any batches with 455 modules or 455 problems solved in it.', 'start': 19.098, 'duration': 7.324}, {'end': 33.327, 'text': "this is the reason i'm saying that this is india's probably world's most in-depth ds algo course.", 'start': 26.422, 'duration': 6.905}], 'summary': "India's most in-depth ds algo course with 455 modules and problems solved.", 'duration': 30.056, 'max_score': 3.271, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g3271.jpg'}, {'end': 81.861, 'src': 'embed', 'start': 50.18, 'weight': 1, 'content': [{'end': 52.302, 'text': "we're solving a lot of interview problems, isn't it?", 'start': 50.18, 'duration': 2.122}, {'end': 55.404, 'text': 'but whenever you go for interviews, the first round will always be coding round.', 'start': 52.302, 'duration': 3.102}, {'end': 61.408, 'text': 'so in order to clear that coding round, you have to actually give a lot of similar coding rounds in your preparation.', 'start': 55.404, 'duration': 6.004}, {'end': 64.95, 'text': 'so one such coding round is code rush x by newton school.', 'start': 61.408, 'duration': 3.542}, {'end': 68.253, 'text': "this is india's biggest competitive programming contest.", 'start': 64.95, 'duration': 3.303}, {'end': 69.855, 'text': 'that is happening in the year.', 'start': 68.253, 'duration': 1.602}, {'end': 70.555, 'text': 'why do i say that?', 'start': 69.855, 'duration': 0.7}, {'end': 72.917, 'text': 'because it has prices worth 10 lakh rupees.', 'start': 70.555, 'duration': 2.362}, {'end': 75.538, 'text': "so what you need to do is there's a link in the description.", 'start': 73.257, 'duration': 2.281}, {'end': 77.219, 'text': 'go to that and you can click on register.', 'start': 75.538, 'duration': 1.681}, {'end': 81.861, 'text': 'the moment you click on register, you will get a form you can sign up with google or you can fill up your details,', 'start': 77.219, 'duration': 4.642}], 'summary': "Code rush x by newton school is india's biggest competitive programming contest with prizes worth 10 lakh rupees.", 'duration': 31.681, 'max_score': 50.18, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g50180.jpg'}, {'end': 114.363, 'src': 'embed', 'start': 85.503, 'weight': 2, 'content': [{'end': 89.165, 'text': 'now just need to register, post that you will be participating.', 'start': 85.503, 'duration': 3.662}, {'end': 92.066, 'text': 'there will be eight questions that you have to solve in three hours.', 'start': 89.165, 'duration': 2.901}, {'end': 96.088, 'text': 'after that, there will be a thorough plagiarism check and the results will be announced.', 'start': 92.066, 'duration': 4.022}, {'end': 103.514, 'text': 'the first price is one lakh rupees, the second is 50 000 and so on, and there are a lot of prices for other people as well.', 'start': 96.388, 'duration': 7.126}, {'end': 104.455, 'text': 'till the top 100.', 'start': 103.514, 'duration': 0.941}, {'end': 109.619, 'text': 'you can get a lot of goodies and going forward you will also be getting a lot of gift vouchers.', 'start': 104.455, 'duration': 5.164}, {'end': 111.24, 'text': 'so the prices are worth 10 lakh rupees.', 'start': 109.619, 'duration': 1.621}, {'end': 114.363, 'text': 'so what i will recommend you is the link in the description.', 'start': 111.24, 'duration': 3.123}], 'summary': 'Register for competition, 8 questions in 3 hours, 10 lakh rupees in prizes', 'duration': 28.86, 'max_score': 85.503, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g85503.jpg'}], 'start': 3.271, 'title': 'Dsa lecture and coding contest', 'summary': "Covers india's most in-depth ds algo course with 455 modules and promotes a competitive programming contest with prizes worth 10 lakh rupees, encouraging participation for interview preparation.", 'chapters': [{'end': 122.805, 'start': 3.271, 'title': 'Dsa lecture and coding contest', 'summary': "Covers india's most in-depth ds algo course with 455 modules, and promotes a competitive programming contest with prizes worth 10 lakh rupees, encouraging participation for interview preparation.", 'duration': 119.534, 'highlights': ["The course is India's most in-depth DS Algo course with 455 modules or 455 problems solved in it. The course is highlighted as the most in-depth in India, offering 455 modules or problems for solving.", "Code Rush X by Newton School is promoted, which is India's biggest competitive programming contest with prizes worth 10 lakh rupees. The promotion of Code Rush X, India's biggest competitive programming contest with prizes worth 10 lakh rupees, is emphasized.", 'The contest is scheduled for 28th of January, with eight questions to solve in three hours, offering prizes worth 10 lakh rupees. Details about the contest are provided, including the date, duration, and the total prizes worth 10 lakh rupees.']}], 'duration': 119.534, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g3271.jpg', 'highlights': ["India's most in-depth DS Algo course with 455 modules", "Promotion of Code Rush X, India's biggest competitive programming contest with prizes worth 10 lakh rupees", 'Contest scheduled for 28th of January, with eight questions to solve in three hours']}, {'end': 568.684, 'segs': [{'end': 160.972, 'src': 'embed', 'start': 122.805, 'weight': 0, 'content': [{'end': 127.987, 'text': 'when I talk about hashing, it is one of the most important topics in DS Algo.', 'start': 122.805, 'duration': 5.182}, {'end': 135.049, 'text': 'If you do not understand hashing, you will not be able to solve a lot of problems in data structures and algorithms.', 'start': 128.447, 'duration': 6.602}, {'end': 140.57, 'text': "So please do not miss this lecture because I'm going to teach you hashing and I'll be using pseudocode.", 'start': 135.409, 'duration': 5.161}, {'end': 142.291, 'text': 'So language will not matter.', 'start': 140.931, 'duration': 1.36}, {'end': 149.6, 'text': "Everything that I'll be teaching will be in terms of pseudocode because for loops are similar in C++ similar in Java and Python.", 'start': 142.771, 'duration': 6.829}, {'end': 152.844, 'text': 'So, once you understand the pseudocode, once you understand the concept,', 'start': 149.86, 'duration': 2.984}, {'end': 157.209, 'text': 'you can actually code it in any of the languages that you are following this particular course in.', 'start': 152.844, 'duration': 4.365}, {'end': 160.972, 'text': "in order to understand hashing, let's take a initial problem.", 'start': 157.97, 'duration': 3.002}], 'summary': 'Understanding hashing is essential for solving data structure and algorithm problems, and can be expressed in pseudocode for implementation in various programming languages.', 'duration': 38.167, 'max_score': 122.805, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g122805.jpg'}, {'end': 300.897, 'src': 'embed', 'start': 268.619, 'weight': 4, 'content': [{'end': 271.219, 'text': "Next, I'll go to this and I'll say, is this equal to this? No.", 'start': 268.619, 'duration': 2.6}, {'end': 274, 'text': "Next, I'll go to this and I'll say, is this equal to this? And no.", 'start': 271.539, 'duration': 2.461}, {'end': 276.36, 'text': 'The counter stays at 2.', 'start': 274.36, 'duration': 2}, {'end': 285.522, 'text': '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.', 'start': 276.36, 'duration': 9.162}, {'end': 287.948, 'text': "I'm writing a plain pseudocode.", 'start': 286.647, 'duration': 1.301}, {'end': 295.333, 'text': 'It will be a function which takes a number and probably an integer function, because it has to return how many times it appears,', 'start': 288.388, 'duration': 6.945}, {'end': 300.897, 'text': 'and you can be like for loop int i, or rather you also need the array in the function.', 'start': 295.333, 'duration': 5.564}], 'summary': 'The counter stays at 2 after checking for equality multiple times.', 'duration': 32.278, 'max_score': 268.619, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g268619.jpg'}, {'end': 517.961, 'src': 'embed', 'start': 471.274, 'weight': 2, 'content': [{'end': 477.443, 'text': 'I give you Q numbers, and for every Q number, sorry, for every number, you have to tell me how many times it appears.', 'start': 471.274, 'duration': 6.169}, {'end': 481.488, 'text': 'Can I say the time complexity will be Q into N?', 'start': 477.984, 'duration': 3.504}, {'end': 490.229, 'text': 'Can I say the time complexity will be Q into N because for every time you are taking a for loop and computing it,', 'start': 483.066, 'duration': 7.163}, {'end': 493.57, 'text': 'so thereby the time complexity will be Q because there are Q numbers.', 'start': 490.229, 'duration': 3.341}, {'end': 499.972, 'text': 'And for every time you are computing N, the time complexity boils down to Q into N.', 'start': 493.89, 'duration': 6.082}, {'end': 502.713, 'text': 'And this is something which might not be good.', 'start': 499.972, 'duration': 2.741}, {'end': 510.176, 'text': 'If you imagine Q is very large, imagine, just imagine I am giving you Q to be 10 to the power 5.', 'start': 503.053, 'duration': 7.123}, {'end': 512.557, 'text': "I'm giving you 10 to the power 5 numbers.", 'start': 510.176, 'duration': 2.381}, {'end': 514.558, 'text': 'And imagine I give you an array size.', 'start': 512.897, 'duration': 1.661}, {'end': 517.961, 'text': 'I give you a huge array of 10 to the power 5 size.', 'start': 514.999, 'duration': 2.962}], 'summary': 'Time complexity is q*n, where q=10^5 and array size is 10^5.', 'duration': 46.687, 'max_score': 471.274, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g471274.jpg'}], 'start': 122.805, 'title': 'Understanding hashing and counting numbers', 'summary': 'Emphasizes the significance of understanding hashing in data structures and algorithms and discusses the process of counting the occurrences of numbers in an array, highlighting the time complexity of the brute force method as q*n for q numbers and an array of size n.', 'chapters': [{'end': 160.972, 'start': 122.805, 'title': 'Importance of hashing in ds algo', 'summary': 'Emphasizes the significance of understanding hashing in data structures and algorithms, highlighting its impact on problem-solving and the use of pseudocode for universal applicability.', 'duration': 38.167, 'highlights': ['The chapter emphasizes the significance of understanding hashing in data structures and algorithms, highlighting its impact on problem-solving and the use of pseudocode for universal applicability.', 'Hashing is crucial for solving a lot of problems in data structures and algorithms, making it an essential topic to grasp.', 'The lecture will focus on teaching hashing and using pseudocode, ensuring language independence for implementing the concepts in C++, Java, or Python.', 'Understanding pseudocode and the concept of hashing enables coding in multiple programming languages, enhancing flexibility and applicability.']}, {'end': 568.684, 'start': 160.972, 'title': 'Counting numbers in array', 'summary': 'Discusses the process of counting the occurrences of numbers in an array using a brute force method, examining the time complexity and concluding that for q numbers and an array of size n, the time complexity is q*n, which may be inefficient for large inputs.', 'duration': 407.712, 'highlights': ['The time complexity for counting the occurrences of Q numbers in an array of size N using a brute force method is Q*N, which may be inefficient for large inputs. The time complexity for counting the occurrences of Q numbers in an array of size N using a brute force method is Q*N. This may be inefficient for large inputs, as illustrated by the example of 10^5 numbers in an array of size 10^5 resulting in 10^10 operations, which would take approximately 100 seconds.', 'The process of counting the occurrences of a number in the array involves iterating through the entire array and incrementing the counter for each match, resulting in a time complexity of O(N) for each number. The process of counting the occurrences of a number in the array involves iterating through the entire array and incrementing the counter for each match, resulting in a time complexity of O(N) for each number. This is due to the linear iteration and counting of occurrences in the array, which contributes to the overall time complexity.', 'The brute force method of iterating through the array to count the occurrences of a number results in a time complexity of O(N). The brute force method of iterating through the array to count the occurrences of a number results in a time complexity of O(N). This approach involves a linear iteration through the array and updating the counter for each match, leading to a time complexity proportional to the size of the array.']}], 'duration': 445.879, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g122805.jpg', 'highlights': ['Understanding hashing is crucial for problem-solving in data structures and algorithms.', 'Hashing and pseudocode enable language-independent implementation in C++, Java, or Python.', 'Counting occurrences of Q numbers in an array of size N using brute force has a time complexity of Q*N, which may be inefficient for large inputs.', 'The process of counting occurrences of a number in the array has a time complexity of O(N) for each number due to linear iteration and counting.', 'Brute force method of counting occurrences of a number in the array results in a time complexity of O(N) due to linear iteration and counter updates.']}, {'end': 1309.369, 'segs': [{'end': 619.724, 'src': 'embed', 'start': 589.738, 'weight': 1, 'content': [{'end': 592.82, 'text': "It's a technique which will help you to do it in a much faster way.", 'start': 589.738, 'duration': 3.082}, {'end': 602.346, 'text': 'So if I have to define hashing in extremely naive terms, what is it? It is something like pre-storing and fetching.', 'start': 593.34, 'duration': 9.006}, {'end': 605.535, 'text': 'This is what hashing is.', 'start': 604.534, 'duration': 1.001}, {'end': 608.657, 'text': 'Restore something and fetch when required.', 'start': 606.075, 'duration': 2.582}, {'end': 610.278, 'text': "Let's understand this in depth.", 'start': 608.797, 'duration': 1.481}, {'end': 612.159, 'text': 'Now this is an array.', 'start': 610.898, 'duration': 1.261}, {'end': 619.724, 'text': 'Imagine the problem statement states the array will at max have numbers till 12 or 15.', 'start': 612.599, 'duration': 7.125}], 'summary': 'Hashing is a technique for faster data retrieval, useful for arrays with numbers up to 12 or 15.', 'duration': 29.986, 'max_score': 589.738, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g589738.jpg'}, {'end': 707.068, 'src': 'embed', 'start': 675.258, 'weight': 0, 'content': [{'end': 678.08, 'text': "And this is something which I'll call as hash array.", 'start': 675.258, 'duration': 2.822}, {'end': 680.883, 'text': "This is something which I'll call as hash array.", 'start': 678.461, 'duration': 2.422}, {'end': 683.405, 'text': 'Or you can call it as a frequency array as well.', 'start': 681.143, 'duration': 2.262}, {'end': 687.488, 'text': 'Now what I will do is I will do some pre-calculation.', 'start': 683.665, 'duration': 3.823}, {'end': 687.869, 'text': 'Remember this.', 'start': 687.508, 'duration': 0.361}, {'end': 691.332, 'text': 'I will do some pre-calculation.', 'start': 688.429, 'duration': 2.903}, {'end': 693.774, 'text': 'now, what is this pre-calculation?', 'start': 691.332, 'duration': 2.442}, {'end': 695.196, 'text': "it's very simple.", 'start': 693.774, 'duration': 1.422}, {'end': 700.081, 'text': 'i go to the first number, which is one, and i say okay, you are one.', 'start': 695.196, 'duration': 4.885}, {'end': 707.068, 'text': "so i'll go to the first index and i'll say hey, can you just remember that i have one one.", 'start': 700.081, 'duration': 6.987}], 'summary': 'Introduction of hash array and pre-calculation for frequency array.', 'duration': 31.81, 'max_score': 675.258, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g675258.jpg'}, {'end': 1098.41, 'src': 'heatmap', 'start': 969.068, 'weight': 3, 'content': [{'end': 978.574, 'text': '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.', 'start': 969.068, 'duration': 9.506}, {'end': 979.354, 'text': 'All of us know that.', 'start': 978.574, 'duration': 0.78}, {'end': 981.596, 'text': 'Now, the pre-computation was very simple.', 'start': 979.835, 'duration': 1.761}, {'end': 984.238, 'text': 'i will go, like this, to the array.', 'start': 982.396, 'duration': 1.842}, {'end': 986.039, 'text': 'this is the iteration of the array.', 'start': 984.238, 'duration': 1.801}, {'end': 990.383, 'text': 'now i know for array element i have to go to that index and do a plus one.', 'start': 986.039, 'duration': 4.344}, {'end': 995.968, 'text': 'so i say hey, go to that index, which is array of i, because that is the index where i have to go.', 'start': 990.383, 'duration': 5.585}, {'end': 1002.853, 'text': 'and i have to tell him can you increase your value by one and increases, because previously it was zero.', 'start': 995.968, 'duration': 6.885}, {'end': 1005.035, 'text': 'now he will for every number.', 'start': 1002.853, 'duration': 2.182}, {'end': 1008.378, 'text': 'it goes to that index and says plus equal to one.', 'start': 1005.035, 'duration': 3.343}, {'end': 1009.099, 'text': 'once this is done.', 'start': 1008.378, 'duration': 0.721}, {'end': 1012.035, 'text': 'Now I have my hash array ready.', 'start': 1010.014, 'duration': 2.021}, {'end': 1017.078, 'text': 'So if I go back to the iPad, can I say I have this particular hash array ready after the pre-competition?', 'start': 1012.235, 'duration': 4.843}, {'end': 1020.959, 'text': 'Because 1 means hash of 1 plus equal to 1.', 'start': 1017.098, 'duration': 3.861}, {'end': 1023.041, 'text': 'that goes to this and does a 1..', 'start': 1020.959, 'duration': 2.082}, {'end': 1025.622, 'text': 'And similarly for this number, similarly for this, for this, and for this.', 'start': 1023.041, 'duration': 2.581}, {'end': 1027.963, 'text': 'This hash array is ready.', 'start': 1026.202, 'duration': 1.761}, {'end': 1030.144, 'text': "The input is different, but it's okay.", 'start': 1028.502, 'duration': 1.642}, {'end': 1033.205, 'text': 'Once the hash array is ready, you have the number.', 'start': 1031.085, 'duration': 2.12}, {'end': 1034.126, 'text': 'You just fetch it.', 'start': 1033.486, 'duration': 0.64}, {'end': 1036.721, 'text': 'So, you say cout of 1.', 'start': 1034.506, 'duration': 2.215}, {'end': 1039.463, 'text': 'hash of number.', 'start': 1036.721, 'duration': 2.742}, {'end': 1043.566, 'text': 'this is the number of times it appears, and you can just go ahead and do this.', 'start': 1039.463, 'duration': 4.103}, {'end': 1047.209, 'text': "i'll go ahead and quickly run this and see if it is running fine.", 'start': 1043.566, 'duration': 3.643}, {'end': 1050.374, 'text': 'So if you see, these are the answers.', 'start': 1048.492, 'duration': 1.882}, {'end': 1052.295, 'text': 'How many times 1 appears? Twice.', 'start': 1050.734, 'duration': 1.561}, {'end': 1054.216, 'text': 'How many times 4 appears? Zero.', 'start': 1052.695, 'duration': 1.521}, {'end': 1055.776, 'text': 'How many times 2 appears? Once.', 'start': 1054.256, 'duration': 1.52}, {'end': 1057.717, 'text': 'How many times 3 appears? Twice.', 'start': 1055.816, 'duration': 1.901}, {'end': 1059.498, 'text': 'How many times 12 appears? Zero.', 'start': 1057.797, 'duration': 1.701}, {'end': 1064.98, 'text': 'Depending on what is the maximum size of the array, you declare the hash.', 'start': 1060.058, 'duration': 4.922}, {'end': 1067.762, 'text': 'Now a question that might come up to your mind.', 'start': 1065.801, 'duration': 1.961}, {'end': 1074.041, 'text': 'Striver, In this, you said the array could be having a max element till 12.', 'start': 1068.262, 'duration': 5.779}, {'end': 1083.586, 'text': 'So it is 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 appears.', 'start': 1074.041, 'duration': 9.545}, {'end': 1093.247, 'text': 'But what if 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,', 'start': 1084.086, 'duration': 9.161}, {'end': 1095.989, 'text': 'or maybe 10 to the power 12, or maybe 10 to the power 15?', 'start': 1093.247, 'duration': 2.742}, {'end': 1098.41, 'text': 'what if they have larger numbers?', 'start': 1095.989, 'duration': 2.421}], 'summary': 'Algorithmic explanation of hash array usage, iteration, and fetching using a size 13 array and sample input data.', 'duration': 24.369, 'max_score': 969.068, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g969068.jpg'}, {'end': 1148.542, 'src': 'embed', 'start': 1122.643, 'weight': 5, 'content': [{'end': 1128.666, 'text': 'The maximum size array that you can declare is 10 to the power 6 if it is of integer.', 'start': 1122.643, 'duration': 6.023}, {'end': 1131.207, 'text': 'Inside very important.', 'start': 1129.266, 'duration': 1.941}, {'end': 1134.672, 'text': 'inside, main, inside, main.', 'start': 1131.207, 'duration': 3.465}, {'end': 1135.733, 'text': 'what does it mean?', 'start': 1134.672, 'duration': 1.061}, {'end': 1144.159, 'text': "if i go back to the code, this is where you declare, if you're declaring it inside, mean it can only go up to 10 to the power 6,", 'start': 1135.733, 'duration': 8.426}, {'end': 1145.48, 'text': 'like somewhere near about.', 'start': 1144.159, 'duration': 1.321}, {'end': 1148.542, 'text': 'you cannot declare something like 10 to the power 7.', 'start': 1145.48, 'duration': 3.062}], 'summary': 'Maximum integer array size is 10^6, must be declared inside main.', 'duration': 25.899, 'max_score': 1122.643, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g1122643.jpg'}, {'end': 1309.369, 'src': 'embed', 'start': 1289.614, 'weight': 6, 'content': [{'end': 1300.662, 'text': '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.', 'start': 1289.614, 'duration': 11.048}, {'end': 1307.447, 'text': "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.", 'start': 1301.063, 'duration': 6.384}, {'end': 1309.369, 'text': 'So make sure you watch the video till the end.', 'start': 1307.467, 'duration': 1.902}], 'summary': 'Arrays for hashing are limited to 10^6 locally and 10^7 globally.', 'duration': 19.755, 'max_score': 1289.614, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g1289614.jpg'}], 'start': 568.684, 'title': 'Hashing and array pre-computation', 'summary': 'Introduces the concept of hashing and array pre-computation to optimize data retrieval, with an example of creating a frequency array and using pre-calculation to efficiently answer queries about the frequency of numbers in an array. it covers the determination of array size, hash array creation, limitations of array size for integer and boolean arrays, and emphasizes further discussions in the video.', 'chapters': [{'end': 938.204, 'start': 568.684, 'title': 'Introduction to hashing', 'summary': 'Introduces the concept of hashing as a technique to optimize data retrieval by pre-storing and fetching, with an example of creating a frequency array and using pre-calculation to efficiently answer queries about the frequency of numbers in an array.', 'duration': 369.52, 'highlights': ['Hashing as a technique to optimize data retrieval Hashing is introduced as a technique to optimize data retrieval by pre-storing and fetching, enabling faster execution by avoiding repetitive computations.', 'Example of creating a frequency array and using pre-calculation An example of creating a frequency array and using pre-calculation to efficiently answer queries about the frequency of numbers in an array is provided, showcasing the practical application of hashing for data retrieval optimization.', 'Explanation of pre-storing and fetching using hashing The concept of pre-storing and fetching using hashing is explained with the process of creating a frequency array and pre-calculations, demonstrating how hashing enables efficient data retrieval without repetitive computations.']}, {'end': 1309.369, 'start': 938.965, 'title': 'Array pre-computation and hashing', 'summary': 'Covers the concept of array pre-computation and hashing, including the determination of array size, hash array creation, and the limitations of array size for integer and boolean arrays. it also emphasizes the importance of watching the video till the end for further discussions.', 'duration': 370.404, 'highlights': ["Array size declaration based on maximum element size The speaker emphasizes the need to declare the array size based on the maximum element size, such as using a size of 13 for a maximum element of 12, and highlights the importance of considering the problem's maximum size requirement.", "Creation of hash array through pre-computation The process of creating a hash array is described, where each element's frequency is incremented, and the example of fetching the frequency of specific numbers (1, 4, 2, 3, 12) is demonstrated, providing a practical application of the hash array.", 'Limitation on the maximum array size declaration for integers The restriction on the maximum array size declaration for integers is explained, with a limit of 10^6 if declared inside main and up to 10^7 if declared globally, highlighting the potential segmentation fault for larger sizes and the significance of global declaration.', 'Illustration of memory allocation constraints for array size declaration The code editor is used to demonstrate the memory allocation constraints, showing an error when attempting to declare an array size of 10^7 inside main, and success when reducing the size to 10^6 or declaring it globally, emphasizing the importance of considering memory limitations.', 'Importance of watching the video till the end for further discussions The speaker emphasizes the importance of watching the video till the end for further discussions on the use of 10^9 array size, indicating the continuation of valuable information beyond the current content.']}], 'duration': 740.685, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g568684.jpg', 'highlights': ['Example of creating a frequency array and using pre-calculation to efficiently answer queries about the frequency of numbers in an array is provided, showcasing the practical application of hashing for data retrieval optimization.', 'Hashing as a technique to optimize data retrieval by pre-storing and fetching, enabling faster execution by avoiding repetitive computations.', "Creation of hash array through pre-computation, where each element's frequency is incremented, and the example of fetching the frequency of specific numbers (1, 4, 2, 3, 12) is demonstrated, providing a practical application of the hash array.", "Array size declaration based on maximum element size is emphasized, highlighting the importance of considering the problem's maximum size requirement.", 'Explanation of pre-storing and fetching using hashing is explained with the process of creating a frequency array and pre-calculations, demonstrating how hashing enables efficient data retrieval without repetitive computations.', 'Limitation on the maximum array size declaration for integers is explained, with a limit of 10^6 if declared inside main and up to 10^7 if declared globally, highlighting the potential segmentation fault for larger sizes and the significance of global declaration.', 'Importance of watching the video till the end for further discussions on the use of 10^9 array size, indicating the continuation of valuable information beyond the current content.', 'Illustration of memory allocation constraints for array size declaration is demonstrated, showing an error when attempting to declare an array size of 10^7 inside main, and success when reducing the size to 10^6 or declaring it globally, emphasizing the importance of considering memory limitations.']}, {'end': 2057.447, 'segs': [{'end': 1462.216, 'src': 'embed', 'start': 1425.953, 'weight': 0, 'content': [{'end': 1428.115, 'text': 'And at the end of the day, I can return that counter.', 'start': 1425.953, 'duration': 2.162}, {'end': 1431.717, 'text': 'So this is what the simple pseudo code will be.', 'start': 1428.595, 'duration': 3.122}, {'end': 1433.819, 'text': 'For every character, you go ahead.', 'start': 1431.957, 'duration': 1.862}, {'end': 1440.643, 'text': 'Again, if you do the similar thing for Q queries, how much time will you end up taking? For every query, you are taking n.', 'start': 1434.179, 'duration': 6.464}, {'end': 1446.167, 'text': 'So for Q queries, you will be taking big O of Q into n time, similar to the previous problem.', 'start': 1440.643, 'duration': 5.524}, {'end': 1451.891, 'text': 'So the question is, can you hash them into arrays? And the answer to that is yes.', 'start': 1446.427, 'duration': 5.464}, {'end': 1462.216, 'text': 'The question comes up, how do you hash them using arrays? Because if we remember, The arrays have indexes like 0, 1, 2, 3.', 'start': 1452.651, 'duration': 9.565}], 'summary': 'Pseudo code for handling q queries in o(q*n) time, hashable into arrays with indexes 0, 1, 2, 3.', 'duration': 36.263, 'max_score': 1425.953, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g1425953.jpg'}, {'end': 1510.899, 'src': 'embed', 'start': 1478.363, 'weight': 3, 'content': [{'end': 1484.365, 'text': 'In that case, how can you hash? Now, I know lowercase means it will have A, B till Z.', 'start': 1478.363, 'duration': 6.002}, {'end': 1492.513, 'text': 'How many elements? I know there will be 26 elements because those many elements is what we 25 or 26.', 'start': 1485.29, 'duration': 7.223}, {'end': 1498.696, 'text': 'So I know there will be 26 characters, 26 lowercase characters.', 'start': 1492.513, 'duration': 6.183}, {'end': 1506.46, 'text': "So if I have to practically think, can I have an array of size 26? I'll be like, yes, I can.", 'start': 1499.336, 'duration': 7.124}, {'end': 1510.899, 'text': 'So imagine if you have an array of size 26.', 'start': 1507.1, 'duration': 3.799}], 'summary': 'Practically, an array of size 26 can hash 26 lowercase characters.', 'duration': 32.536, 'max_score': 1478.363, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g1478363.jpg'}, {'end': 2007.158, 'src': 'embed', 'start': 1963.129, 'weight': 4, 'content': [{'end': 1966.411, 'text': 'so are there any complications in order to hash characters?', 'start': 1963.129, 'duration': 3.282}, {'end': 1971.714, 'text': 'because in number hashing we saw that if the number goes till 10 to the power 9, there might be a problem.', 'start': 1966.411, 'duration': 5.303}, {'end': 1979.519, 'text': 'but in character there will never be a problem, because at max there are 256 characters and array can store 256 elements.', 'start': 1971.714, 'duration': 7.805}, {'end': 1982.181, 'text': "so for character hashing you don't have to think much.", 'start': 1979.519, 'duration': 2.662}, {'end': 1988.525, 'text': 'always prefer arrays always and always use this logic character minus a for lowercase.', 'start': 1982.181, 'duration': 6.344}, {'end': 1991.827, 'text': 'if there are uppercase it will be character minus capital a.', 'start': 1989.105, 'duration': 2.722}, {'end': 1997.811, 'text': 'and if there are all characters 256 and simply hash the character, it will be auto converted.', 'start': 1991.827, 'duration': 5.984}, {'end': 2007.158, 'text': "yes, if i'm saying s of i, this auto converts itself to its ascii because hash of r hash needs an index and the index is an integer.", 'start': 1997.811, 'duration': 9.347}], 'summary': 'Character hashing is straightforward due to limited characters (256) and array storage, ensuring no complications and easy conversion to ascii.', 'duration': 44.029, 'max_score': 1963.129, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g1963129.jpg'}], 'start': 1310.27, 'title': 'Character hashing and efficient computation', 'summary': 'Covers character hashing into arrays, using ascii values to map characters, and reducing time complexity to o(qn). it also discusses hashing characters for efficient computation, emphasizing the use of arrays and differences between character and number hashing.', 'chapters': [{'end': 1815.421, 'start': 1310.27, 'title': 'Character hashing using arrays', 'summary': 'Covers character hashing using arrays, hashing characters into arrays, and using ascii values to map characters to array indices, enabling efficient character count queries and reducing time complexity to o(qn).', 'duration': 505.151, 'highlights': ['Hashing characters into arrays using ASCII values Explains using ASCII values to map characters to array indices, enabling efficient character count queries and reducing time complexity to O(QN).', 'Efficient character count queries Discusses the process of efficiently counting the appearance of characters in a string using array indices, providing a time complexity reduction to O(QN).', 'Utilizing arrays for character hashing Describes the use of arrays for character hashing to efficiently count appearances of characters in a string, improving time complexity to O(QN).']}, {'end': 2057.447, 'start': 1815.601, 'title': 'Hashing characters for efficient computation', 'summary': "Discusses the process of hashing characters for efficient computation, emphasizing the use of arrays and the character minus 'a' logic for lowercase characters, and highlights the differences between character and number hashing in terms of storage limitations and array usage.", 'duration': 241.846, 'highlights': ['Character hashing using arrays requires a hash of size 26 for lowercase letters, but if the number of characters is not exclusively lowercase, a hash of size 256 is needed, emphasizing that the hashing logic should be adjusted accordingly. 26, 256', 'detail In character hashing, there are no complications regarding the storage limitations, as the array can store 256 elements, allowing for efficient hashing without concerns for large numbers.', "detail The logic of character minus 'a' for lowercase characters and character minus capital 'A' for uppercase characters is emphasized, highlighting the automatic conversion of characters to their ASCII values for efficient hashing.", 'detail In contrast to number hashing, character hashing does not face storage limitations, as the array can accommodate 256 elements, allowing for efficient hashing without concerns for large numbers.']}], 'duration': 747.177, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g1310270.jpg', 'highlights': ['Hashing characters into arrays using ASCII values to map characters for efficient character count queries and reducing time complexity to O(QN).', 'Utilizing arrays for character hashing to efficiently count appearances of characters in a string, improving time complexity to O(QN).', 'Efficient character count queries process discussed, providing a time complexity reduction to O(QN).', 'Character hashing using arrays requires a hash of size 26 for lowercase letters, and a hash of size 256 for non-exclusively lowercase characters, emphasizing the need to adjust hashing logic accordingly.', 'In character hashing, there are no complications regarding storage limitations, as the array can store 256 elements, allowing for efficient hashing without concerns for large numbers.', "The logic of character minus 'a' for lowercase characters and character minus capital 'A' for uppercase characters is emphasized, highlighting the automatic conversion of characters to their ASCII values for efficient hashing."]}, {'end': 2700.213, 'segs': [{'end': 2089.335, 'src': 'embed', 'start': 2057.766, 'weight': 0, 'content': [{'end': 2061.789, 'text': 'And that is where, in C++, stl comes in.', 'start': 2057.766, 'duration': 4.023}, {'end': 2065.391, 'text': 'if you have not seen the stl video, please go back and watch it.', 'start': 2061.789, 'duration': 3.602}, {'end': 2067.993, 'text': 'and in java the collection comes in.', 'start': 2065.391, 'duration': 2.602}, {'end': 2075.097, 'text': "so in stl there are two things one is the map, while the other one is the unordered map, which i'll be talking in depth,", 'start': 2067.993, 'duration': 7.104}, {'end': 2081.521, 'text': "and most of the concepts that i'll be talking about map and another map also apply to the hash map.", 'start': 2075.097, 'duration': 6.424}, {'end': 2089.335, 'text': 'it is just the same stuff, just the writing format is different and the concept inside it is the same.', 'start': 2081.521, 'duration': 7.814}], 'summary': 'C++ stl includes map and unordered map, while java uses collections.', 'duration': 31.569, 'max_score': 2057.766, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2057766.jpg'}, {'end': 2204.172, 'src': 'heatmap', 'start': 2124.388, 'weight': 0.819, 'content': [{'end': 2128.271, 'text': 'So what do you do is you say, okay, I know there has to be a key.', 'start': 2124.388, 'duration': 3.883}, {'end': 2132.754, 'text': 'What is a key over here? So this is the key.', 'start': 2129.452, 'duration': 3.302}, {'end': 2134.855, 'text': 'The number is the key.', 'start': 2133.895, 'duration': 0.96}, {'end': 2136.877, 'text': 'So the number is the key.', 'start': 2135.896, 'duration': 0.981}, {'end': 2137.417, 'text': 'Remember this.', 'start': 2136.917, 'duration': 0.5}, {'end': 2141.62, 'text': 'And there has to be a corresponding value to it.', 'start': 2139.258, 'duration': 2.362}, {'end': 2144.202, 'text': 'And the value over here is the frequency.', 'start': 2142.22, 'duration': 1.982}, {'end': 2147.491, 'text': 'So this is how it is defined.', 'start': 2146.189, 'duration': 1.302}, {'end': 2150.775, 'text': 'You basically say, okay, what is your key? Key is your number.', 'start': 2148.191, 'duration': 2.584}, {'end': 2153.718, 'text': 'How many times it appears is the value.', 'start': 2151.355, 'duration': 2.363}, {'end': 2154.9, 'text': 'This is what you do.', 'start': 2154.259, 'duration': 0.641}, {'end': 2155.941, 'text': 'As simple as that.', 'start': 2155.38, 'duration': 0.561}, {'end': 2158.204, 'text': 'So what I do is, okay, I know one thing.', 'start': 2156.341, 'duration': 1.863}, {'end': 2160.754, 'text': 'At the first step, I have 1.', 'start': 2159.073, 'duration': 1.681}, {'end': 2173.317, 'text': 'So I will say can you go ahead and if remember one thing before iterating in the array, if you say MPP of 1, this will return you 0,', 'start': 2160.754, 'duration': 12.563}, {'end': 2174.738, 'text': "because it doesn't exist in the map.", 'start': 2173.317, 'duration': 1.421}, {'end': 2184.756, 'text': 'So the value, the corresponding value will be 0, right? So, the moment you go to 1, you say MPP of 1++.', 'start': 2175.338, 'duration': 9.418}, {'end': 2191.222, 'text': "So, what will happen? If it doesn't exist in the map, it will go to the map and say, 1, you do not exist.", 'start': 2184.756, 'duration': 6.466}, {'end': 2192.644, 'text': "It's 0.", 'start': 2191.763, 'duration': 0.881}, {'end': 2194.265, 'text': "It's 0.", 'start': 2192.644, 'duration': 1.621}, {'end': 2194.526, 'text': '0++ is 1.', 'start': 2194.265, 'duration': 0.261}, {'end': 2197.248, 'text': 'So, it will store a key value.', 'start': 2194.526, 'duration': 2.722}, {'end': 2204.172, 'text': 'Key mapped to a value of Next, it goes to 2 and does a map 2++.', 'start': 2198.069, 'duration': 6.103}], 'summary': 'Mapping numbers to their frequency using key-value pairs.', 'duration': 79.784, 'max_score': 2124.388, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2124388.jpg'}, {'end': 2191.222, 'src': 'embed', 'start': 2159.073, 'weight': 3, 'content': [{'end': 2160.754, 'text': 'At the first step, I have 1.', 'start': 2159.073, 'duration': 1.681}, {'end': 2173.317, 'text': 'So I will say can you go ahead and if remember one thing before iterating in the array, if you say MPP of 1, this will return you 0,', 'start': 2160.754, 'duration': 12.563}, {'end': 2174.738, 'text': "because it doesn't exist in the map.", 'start': 2173.317, 'duration': 1.421}, {'end': 2184.756, 'text': 'So the value, the corresponding value will be 0, right? So, the moment you go to 1, you say MPP of 1++.', 'start': 2175.338, 'duration': 9.418}, {'end': 2191.222, 'text': "So, what will happen? If it doesn't exist in the map, it will go to the map and say, 1, you do not exist.", 'start': 2184.756, 'duration': 6.466}], 'summary': 'Using mpp, iterating through array, returns 0 for non-existent value.', 'duration': 32.149, 'max_score': 2159.073, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2159073.jpg'}, {'end': 2301.394, 'src': 'embed', 'start': 2275.897, 'weight': 1, 'content': [{'end': 2283.29, 'text': "And over here, how many elements are you storing? We're just storing the elements that are required because you require 1, 2, 3, and 12.", 'start': 2275.897, 'duration': 7.393}, {'end': 2287.351, 'text': 'So four elements are stored.', 'start': 2283.29, 'duration': 4.061}, {'end': 2298.053, 'text': '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.', 'start': 2287.911, 'duration': 10.142}, {'end': 2301.394, 'text': 'So this is where map is slightly beneficial.', 'start': 2298.453, 'duration': 2.941}], 'summary': 'Using map for storing elements is beneficial as it only stores required elements, like 1, 2, 3, and 12, totaling to four elements, unlike array hashing which requires a size of 13 even if the maximum is 12.', 'duration': 25.497, 'max_score': 2275.897, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2275897.jpg'}, {'end': 2458.55, 'src': 'heatmap', 'start': 2415.53, 'weight': 1, 'content': [{'end': 2417.791, 'text': 'and if you run this, you will see that everything is fine.', 'start': 2415.53, 'duration': 2.261}, {'end': 2418.792, 'text': 'four appears zero.', 'start': 2417.791, 'duration': 1.001}, {'end': 2420.053, 'text': "that's why 12 appears.", 'start': 2418.792, 'duration': 1.261}, {'end': 2422.554, 'text': 'once it does run, fine.', 'start': 2420.053, 'duration': 2.501}, {'end': 2427.679, 'text': 'so remember one thing The map stores all the values in sorted order.', 'start': 2422.554, 'duration': 5.125}, {'end': 2429.602, 'text': 'This is something which you have to keep in mind.', 'start': 2428.22, 'duration': 1.382}, {'end': 2432.266, 'text': 'The map stores all the values in sorted order.', 'start': 2430.023, 'duration': 2.243}, {'end': 2436.553, 'text': 'What does that mean? This will be at the first place in the map.', 'start': 2432.607, 'duration': 3.946}, {'end': 2437.815, 'text': 'This will be at the second place.', 'start': 2436.853, 'duration': 0.962}, {'end': 2438.716, 'text': 'This will be at the third place.', 'start': 2437.835, 'duration': 0.881}, {'end': 2439.718, 'text': 'This will be at the fourth place.', 'start': 2438.736, 'duration': 0.982}, {'end': 2444.715, 'text': "How can I prove it? What I'll do is, I'll go ahead and say, let's iterate in the map.", 'start': 2440.27, 'duration': 4.445}, {'end': 2447.798, 'text': 'So if you just iterate in the map, this is how you iterate in the map.', 'start': 2444.795, 'duration': 3.003}, {'end': 2450.241, 'text': 'An auto iterator on the map.', 'start': 2448.379, 'duration': 1.862}, {'end': 2458.55, 'text': 'And if you do cout of it.first, something like this, and do it.second, this is how you can get it.', 'start': 2450.982, 'duration': 7.568}], 'summary': 'Map stores all values in sorted order, as seen when iterating through it.', 'duration': 43.02, 'max_score': 2415.53, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2415530.jpg'}, {'end': 2639.012, 'src': 'heatmap', 'start': 2594.038, 'weight': 0.753, 'content': [{'end': 2597.06, 'text': "so that's fetching from the map, the storing of fetching.", 'start': 2594.038, 'duration': 3.022}, {'end': 2598.221, 'text': 'remember this.', 'start': 2597.06, 'duration': 1.161}, {'end': 2615.101, 'text': 'storing or fetching both of them in a map, in a map takes logarithmic often, takes logarithmic often in all cases, in best in average, in worst,', 'start': 2598.221, 'duration': 16.88}, {'end': 2619.404, 'text': 'in all cases, takes logarithmic often.', 'start': 2615.101, 'duration': 4.303}, {'end': 2620.445, 'text': 'remember this.', 'start': 2619.404, 'duration': 1.041}, {'end': 2623.508, 'text': 'but there is something as unordered map.', 'start': 2620.445, 'duration': 3.063}, {'end': 2629.566, 'text': "There's something as unordered map which we will be talking about now.", 'start': 2624.343, 'duration': 5.223}, {'end': 2630.967, 'text': "So let's go back to the code.", 'start': 2629.847, 'duration': 1.12}, {'end': 2639.012, 'text': 'So even if I write this unordered, will it run? And if I go ahead and run this, it will actually run.', 'start': 2631.388, 'duration': 7.624}], 'summary': 'Storing or fetching from a map takes logarithmic time in all cases, but unordered map can also run successfully.', 'duration': 44.974, 'max_score': 2594.038, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2594038.jpg'}, {'end': 2630.967, 'src': 'embed', 'start': 2598.221, 'weight': 5, 'content': [{'end': 2615.101, 'text': 'storing or fetching both of them in a map, in a map takes logarithmic often, takes logarithmic often in all cases, in best in average, in worst,', 'start': 2598.221, 'duration': 16.88}, {'end': 2619.404, 'text': 'in all cases, takes logarithmic often.', 'start': 2615.101, 'duration': 4.303}, {'end': 2620.445, 'text': 'remember this.', 'start': 2619.404, 'duration': 1.041}, {'end': 2623.508, 'text': 'but there is something as unordered map.', 'start': 2620.445, 'duration': 3.063}, {'end': 2629.566, 'text': "There's something as unordered map which we will be talking about now.", 'start': 2624.343, 'duration': 5.223}, {'end': 2630.967, 'text': "So let's go back to the code.", 'start': 2629.847, 'duration': 1.12}], 'summary': 'Storing or fetching in map takes logarithmic time, unordered map coming up.', 'duration': 32.746, 'max_score': 2598.221, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2598221.jpg'}, {'end': 2708.617, 'src': 'embed', 'start': 2678.098, 'weight': 4, 'content': [{'end': 2683.682, 'text': 'If you run the same code on some other compiler, it might be having some different order.', 'start': 2678.098, 'duration': 5.584}, {'end': 2686.304, 'text': 'So the order is something which you cannot decide.', 'start': 2683.902, 'duration': 2.402}, {'end': 2689.506, 'text': 'So as the name recommends, it is unordered.', 'start': 2686.884, 'duration': 2.622}, {'end': 2695.75, 'text': "But then you might ask, what is the advantage of using this? Let's talk about this.", 'start': 2689.986, 'duration': 5.764}, {'end': 2700.213, 'text': "When you are storing something in the map which you are doing, and when you're fetching in the map,", 'start': 2696.23, 'duration': 3.983}, {'end': 2708.617, 'text': 'the average and the best time complexity is a constant one.', 'start': 2701.894, 'duration': 6.723}], 'summary': 'Using unordered map provides constant time complexity for storing and fetching data.', 'duration': 30.519, 'max_score': 2678.098, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2678098.jpg'}], 'start': 2057.766, 'title': 'Stl in c++ and java collections', 'summary': 'Discusses the usage of map and unordered map in c++ stl and java collections, emphasizing key-value pairing and frequency counting, with benefits such as reduced memory usage and logarithmic time retrieval.', 'chapters': [{'end': 2247.794, 'start': 2057.766, 'title': 'Stl in c++ and java collections', 'summary': 'Discusses the usage of map and unordered map in c++ stl, and the corresponding concept in java collections, emphasizing the key-value pairing and frequency counting, illustrated with an example of mapping elements from an array.', 'duration': 190.028, 'highlights': ['The map in C++ STL is used to store key-value pairs, where the key is the number and the value is its frequency, with the concept being applicable to the hash map as well.', 'When iterating through an array, the frequency of each element is updated using the MPP of array[i++] operation, resulting in a key-value mapping of elements and their frequencies.', 'The discussion emphasizes the usage of map and unordered map in C++ STL, and their relevance to hash map, providing a clear understanding of how key-value pairs and frequency counting are implemented in the context of array elements.']}, {'end': 2700.213, 'start': 2247.914, 'title': 'Map and unordered map in c++', 'summary': 'Explains the concept of map and unordered map in c++ and highlights the benefits of using map over array hashing, emphasizing that map stores required elements, reducing memory usage, and retrieves in logarithmic time, while unordered map has no specific order and can be beneficial in certain scenarios.', 'duration': 452.299, 'highlights': ['The map stores required elements, reducing memory usage by not requiring a larger array size, and retrieves in logarithmic time.', 'The concept of unordered map is explained, highlighting that it has no specific order and can change on every program, offering advantages in certain scenarios.', 'Storing or fetching in a map takes logarithmic time in all cases, and there is an alternative called unordered map, which has no specific order and can change on every program.']}], 'duration': 642.447, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2057766.jpg', 'highlights': ['The map in C++ STL is used to store key-value pairs, where the key is the number and the value is its frequency, with the concept being applicable to the hash map as well.', 'The map stores required elements, reducing memory usage by not requiring a larger array size, and retrieves in logarithmic time.', 'The discussion emphasizes the usage of map and unordered map in C++ STL, and their relevance to hash map, providing a clear understanding of how key-value pairs and frequency counting are implemented in the context of array elements.', 'When iterating through an array, the frequency of each element is updated using the MPP of array[i++] operation, resulting in a key-value mapping of elements and their frequencies.', 'The concept of unordered map is explained, highlighting that it has no specific order and can change on every program, offering advantages in certain scenarios.', 'Storing or fetching in a map takes logarithmic time in all cases, and there is an alternative called unordered map, which has no specific order and can change on every program.']}, {'end': 3596.6, 'segs': [{'end': 2759.653, 'src': 'embed', 'start': 2701.894, 'weight': 0, 'content': [{'end': 2708.617, 'text': 'the average and the best time complexity is a constant one.', 'start': 2701.894, 'duration': 6.723}, {'end': 2715.501, 'text': 'the average and the best is average, like in most of the cases.', 'start': 2708.617, 'duration': 6.884}, {'end': 2727.24, 'text': 'in most of the cases it will be big of one for storing and fetching, but there is something is the worst case And that ends up taking linear time.', 'start': 2715.501, 'duration': 11.739}, {'end': 2732.065, 'text': 'What do you mean by linear time? This is nothing but the number of elements in the map.', 'start': 2727.661, 'duration': 4.404}, {'end': 2734.888, 'text': 'This is nothing but the number of elements in the map.', 'start': 2732.205, 'duration': 2.683}, {'end': 2739.557, 'text': "When I talk about n, I'm talking about log n.", 'start': 2736.394, 'duration': 3.163}, {'end': 2745.021, 'text': 'This is nothing but the number of elements in map data structure.', 'start': 2739.557, 'duration': 5.464}, {'end': 2748.845, 'text': 'Depending on the number of elements, the time will be computed.', 'start': 2745.582, 'duration': 3.263}, {'end': 2752.648, 'text': 'So the average in the best case will be VCO.', 'start': 2749.145, 'duration': 3.503}, {'end': 2754.91, 'text': 'In most of the cases it will be VCO.', 'start': 2752.648, 'duration': 2.262}, {'end': 2759.653, 'text': 'In very minor cases it will happen once in a blue moon.', 'start': 2754.91, 'duration': 4.743}], 'summary': 'Map data structure has constant average and best time complexity, but linear worst case time complexity based on the number of elements.', 'duration': 57.759, 'max_score': 2701.894, 'thumbnail': ''}, {'end': 2812.084, 'src': 'embed', 'start': 2785.806, 'weight': 2, 'content': [{'end': 2791.39, 'text': 'but if this line is, we go of one, then it becomes n into one most of the times.', 'start': 2785.806, 'duration': 5.584}, {'end': 2794.513, 'text': 'what you need to do is you need to do?', 'start': 2791.39, 'duration': 3.123}, {'end': 2796.534, 'text': 'you need to use unordered map?', 'start': 2794.513, 'duration': 2.021}, {'end': 2804.419, 'text': 'yes, if it fails, if it gives you a time limit exceeded, that means taking a lot of time.', 'start': 2796.534, 'duration': 7.885}, {'end': 2805.9, 'text': 'then you switch back to map.', 'start': 2804.419, 'duration': 1.481}, {'end': 2812.084, 'text': 'but the first preference should be unordered map, because the worst case very rarely happens.', 'start': 2805.9, 'duration': 6.184}], 'summary': 'Prefer unordered map over map for better efficiency and performance.', 'duration': 26.278, 'max_score': 2785.806, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2785806.jpg'}, {'end': 2849.77, 'src': 'heatmap', 'start': 2812.084, 'weight': 0.855, 'content': [{'end': 2816.487, 'text': "i know it's it is a worst case, but it very, very rarely happens.", 'start': 2812.084, 'duration': 4.403}, {'end': 2817.908, 'text': 'why does the worst case happens?', 'start': 2816.487, 'duration': 1.421}, {'end': 2821.411, 'text': 'Because of internal collisions.', 'start': 2818.769, 'duration': 2.642}, {'end': 2824.194, 'text': 'Because of internal collisions.', 'start': 2821.992, 'duration': 2.202}, {'end': 2828.658, 'text': "So, since we are talking about collisions, let's understand how does hashing work.", 'start': 2824.334, 'duration': 4.324}, {'end': 2837.12, 'text': 'Because, if you remember, I told you that the moment it crosses 10 to the power 7, an array hashing cannot be done.', 'start': 2829.098, 'duration': 8.022}, {'end': 2840.523, 'text': 'so how does, how is a map data structure created?', 'start': 2837.12, 'duration': 3.403}, {'end': 2841.123, 'text': 'will someone ask?', 'start': 2840.523, 'duration': 0.6}, {'end': 2842.965, 'text': 'you might not like.', 'start': 2841.123, 'duration': 1.842}, {'end': 2846.928, 'text': "in interviews they generally don't ask that much, even if they ask.", 'start': 2842.965, 'duration': 3.963}, {'end': 2849.77, 'text': 'only telling them about division method will work.', 'start': 2846.928, 'duration': 2.842}], 'summary': 'Rare worst case due to internal collisions in hashing. division method used for map data structure.', 'duration': 37.686, 'max_score': 2812.084, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KEs5UyBJ39g/pics/KEs5UyBJ39g2812084.jpg'}, {'end': 2911.928, 'src': 'embed', 'start': 2881.433, 'weight': 3, 'content': [{'end': 2883.374, 'text': 'they are implemented in a very complex way.', 'start': 2881.433, 'duration': 1.941}, {'end': 2884.615, 'text': "you don't need to know it.", 'start': 2883.374, 'duration': 1.241}, {'end': 2893.222, 'text': "but let's understand what is the division method, because if we take the division method, then i might be able to explain you what is collisions.", 'start': 2884.615, 'duration': 8.607}, {'end': 2894.663, 'text': "so let's understand the division method.", 'start': 2893.222, 'duration': 1.441}, {'end': 2899.381, 'text': "So imagine, imagine I'm giving you numbers like in an array.", 'start': 2895.239, 'duration': 4.142}, {'end': 2908.906, 'text': "I'm giving you numbers like 2, 5, and then 15, and then 55, not 55, not 15, let's take 16, and let's take 28, and let's take 139..", 'start': 2899.381, 'duration': 9.525}, {'end': 2911.928, 'text': "Okay, so these are the numbers that I've given.", 'start': 2908.906, 'duration': 3.022}], 'summary': 'Explanation of division method using array of numbers.', 'duration': 30.495, 'max_score': 2881.433, 'thumbnail': ''}], 'start': 2701.894, 'title': 'Map data structure time complexity', 'summary': 'Discusses the time complexity in map data structure, emphasizing the average and best case time complexity of o(1) and the worst case time complexity of o(n). it also recommends using unordered map over map for lower likelihood of worst-case occurrences and covers collision handling through chaining.', 'chapters': [{'end': 2837.12, 'start': 2701.894, 'title': 'Time complexity in map data structure', 'summary': 'Explains the time complexity in map data structure, where the average and best case time complexity is o(1), while the worst case time complexity can be o(n), with a preference for unordered map over map due to its lower likelihood of worst-case occurrences.', 'duration': 135.226, 'highlights': ['The worst case time complexity for storing and fetching in a map data structure can be O(n), while the average and best case time complexity is O(1), with a preference for using unordered map over map to mitigate the worst-case scenario.', "The probability of encountering the worst case scenario is very rare, occurring 'once in a blue moon', attributed to internal collisions in hashing, which affects the time complexity.", 'The suggestion to use unordered map as the first preference and switch back to map only if time limit exceeds due to the rare occurrence of worst case scenarios, highlighting the rarity of worst case time complexity.']}, {'end': 3596.6, 'start': 2837.12, 'title': 'Map data structure overview', 'summary': 'Explains the division method in map data structure, where numbers are modulated to fit into an array of limited size, and collision handling through chaining is discussed, highlighting the potential worst-case time complexity of o(n) due to collisions.', 'duration': 759.48, 'highlights': ['The division method in map data structure involves modulating numbers to fit into an array of limited size, exemplifying how to handle collisions through chaining. The division method is explained in detail, demonstrating how numbers are modulated to fit into an array of limited size, and addressing collision handling through chaining. This method is used to overcome the restriction of creating an array of size greater than 10.', 'Collision in map data structure occurs when multiple keys end up at the same hash index, potentially resulting in a worst-case time complexity of O(n). Collision is discussed, highlighting the scenario where multiple keys end up at the same hash index, leading to potential worst-case time complexity of O(n). This is explained in the context of the division method and the challenges it presents.', 'The potential worst-case time complexity of O(n) due to collisions in the map data structure is emphasized, with the rarity of such occurrences noted in practical applications and interviews. The worst-case time complexity of O(n) due to collisions is emphasized, with a note on its rarity in practical applications and interviews. This highlights the importance of understanding and addressing collision handling in map data structures.']}], 'duration': 894.706, 'thumbnail': '', 'highlights': ['The worst case time complexity for storing and fetching in a map data structure can be O(n), while the average and best case time complexity is O(1), with a preference for using unordered map over map to mitigate the worst-case scenario.', 'The potential worst-case time complexity of O(n) due to collisions in the map data structure is emphasized, with the rarity of such occurrences noted in practical applications and interviews. The worst-case time complexity of O(n) due to collisions is emphasized, with a note on its rarity in practical applications and interviews. This highlights the importance of understanding and addressing collision handling in map data structures.', 'The suggestion to use unordered map as the first preference and switch back to map only if time limit exceeds due to the rare occurrence of worst case scenarios, highlighting the rarity of worst case time complexity.', 'The division method in map data structure involves modulating numbers to fit into an array of limited size, exemplifying how to handle collisions through chaining. The division method is explained in detail, demonstrating how numbers are modulated to fit into an array of limited size, and addressing collision handling through chaining. This method is used to overcome the restriction of creating an array of size greater than 10.']}], 'highlights': ["India's most in-depth DS Algo course with 455 modules", "Promotion of Code Rush X, India's biggest competitive programming contest with prizes worth 10 lakh rupees", 'Understanding hashing is crucial for problem-solving in data structures and algorithms', 'Example of creating a frequency array and using pre-calculation to efficiently answer queries about the frequency of numbers in an array is provided, showcasing the practical application of hashing for data retrieval optimization', 'Hashing as a technique to optimize data retrieval by pre-storing and fetching, enabling faster execution by avoiding repetitive computations', 'Hashing characters into arrays using ASCII values to map characters for efficient character count queries and reducing time complexity to O(QN)', 'The map in C++ STL is used to store key-value pairs, where the key is the number and the value is its frequency, with the concept being applicable to the hash map as well', 'The worst case time complexity for storing and fetching in a map data structure can be O(n), while the average and best case time complexity is O(1), with a preference for using unordered map over map to mitigate the worst-case scenario']}