title
Set Matrix Zeroes | O(1) Space Approach | Brute - Better - Optimal

description
Problem Link: https://bit.ly/3CukQke Notes/C++/Java/Python codes: https://takeuforward.org/data-structure/set-matrix-zero/ We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition. Full Course: https://bit.ly/tufA2ZYt You can follow me across social media, all my handles are below: Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward 00:40: Problem statement 01:49: Brute-force solution 05:13: - Code 06:28: - Complexity 07:10: Better solution 12:16: - Code 13:49: - Complexity 14:17: Optimal solution 23:24: - Code 29:02: - Complexity

detail
{'title': 'Set Matrix Zeroes | O(1) Space Approach | Brute - Better - Optimal', 'heatmap': [{'end': 836.523, 'start': 810.865, 'weight': 0.723}, {'end': 870.916, 'start': 843.89, 'weight': 0.719}, {'end': 1105.784, 'start': 1082.7, 'weight': 0.852}, {'end': 1176.664, 'start': 1119.372, 'weight': 0.702}, {'end': 1536.183, 'start': 1517.687, 'weight': 0.764}, {'end': 1755.703, 'start': 1660.999, 'weight': 0.701}], 'summary': 'A2z dsa course offers 455 modules and 400+ problems, promising to clear any ds algorithms in any company. chapters cover zero marking in a binary matrix, optimizing time complexity to n square, array marking, and matrix operations with various algorithms and programming language options.', 'chapters': [{'end': 36.317, 'segs': [{'end': 36.317, 'src': 'embed', 'start': 3.22, 'weight': 0, 'content': [{'end': 4.441, 'text': 'Hey everyone, welcome back to the channel.', 'start': 3.22, 'duration': 1.221}, {'end': 6.003, 'text': 'I hope you guys are doing extremely well.', 'start': 4.461, 'duration': 1.542}, {'end': 9.167, 'text': 'So this is another lecture from the Strybos A2Z DSA course.', 'start': 6.363, 'duration': 2.804}, {'end': 13.371, 'text': "Just in case you're for the first time here, this is world's most in-depth course when it comes to DS Algo.", 'start': 9.447, 'duration': 3.924}, {'end': 16.414, 'text': 'Why do I say that? 455 modules.', 'start': 13.671, 'duration': 2.743}, {'end': 19.958, 'text': "By the end of the course, you're gonna solve more than 400 plus problems in DS Algo.", 'start': 16.715, 'duration': 3.243}, {'end': 21.74, 'text': 'You can go across the entire internet.', 'start': 20.239, 'duration': 1.501}, {'end': 23.142, 'text': 'You can buy any of the paid courses.', 'start': 21.76, 'duration': 1.382}, {'end': 26.125, 'text': 'none of them will be teaching you ds algo in such depth.', 'start': 23.542, 'duration': 2.583}, {'end': 29.669, 'text': 'something that i can give you as guarantee is, once you complete this entire course,', 'start': 26.125, 'duration': 3.544}, {'end': 33.694, 'text': 'you can clear any of the ds algorithms in any company in any part of the world.', 'start': 29.669, 'duration': 4.025}, {'end': 36.317, 'text': 'so till now we have covered uh till, this particular problem.', 'start': 33.694, 'duration': 2.623}], 'summary': "Strybos a2z dsa course offers 455 modules, and you'll solve 400+ problems, enabling you to clear any ds algorithms in any company worldwide.", 'duration': 33.097, 'max_score': 3.22, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M3220.jpg'}], 'start': 3.22, 'title': 'Strybos a2z dsa course', 'summary': "Introduces the strybos a2z dsa course, which claims to be the world's most in-depth with 455 modules and over 400 problems in ds algo, guaranteeing the ability to clear any ds algorithms in any company worldwide upon completion.", 'chapters': [{'end': 36.317, 'start': 3.22, 'title': 'Strybos a2z dsa course', 'summary': "Introduces the strybos a2z dsa course, claiming to be the world's most in-depth with 455 modules and over 400 problems in ds algo, guaranteeing the ability to clear any ds algorithms in any company worldwide upon completion.", 'duration': 33.097, 'highlights': ["By the end of the course, you're gonna solve more than 400 plus problems in DS Algo.", "This is world's most in-depth course when it comes to DS Algo with 455 modules.", 'Once you complete this entire course, you can clear any of the ds algorithms in any company in any part of the world.']}], 'duration': 33.097, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M3220.jpg', 'highlights': ["This is world's most in-depth course when it comes to DS Algo with 455 modules.", "By the end of the course, you're gonna solve more than 400 plus problems in DS Algo.", 'Once you complete this entire course, you can clear any of the ds algorithms in any company in any part of the world.']}, {'end': 315.204, 'segs': [{'end': 125.738, 'src': 'embed', 'start': 36.317, 'weight': 0, 'content': [{'end': 38.459, 'text': "now, in this video, i'll be covering the problem.", 'start': 36.317, 'duration': 2.142}, {'end': 40.341, 'text': 'set matrix zeros.', 'start': 38.459, 'duration': 1.882}, {'end': 41.903, 'text': 'now. what does the problem state?', 'start': 40.341, 'duration': 1.562}, {'end': 45.464, 'text': 'the problem states You will be given an n cross m matrix.', 'start': 41.903, 'duration': 3.561}, {'end': 47.325, 'text': 'n and m can be different, can be equal.', 'start': 45.704, 'duration': 1.621}, {'end': 51.145, 'text': 'Now, the matrix only has 0 and 1s.', 'start': 47.705, 'duration': 3.44}, {'end': 53.186, 'text': "That means it's a binary matrix.", 'start': 51.626, 'duration': 1.56}, {'end': 56.686, 'text': 'Your task is to find out 0s you have.', 'start': 53.606, 'duration': 3.08}, {'end': 59.807, 'text': 'Once you have figured out 0s, so there is a 0 over here.', 'start': 57.247, 'duration': 2.56}, {'end': 64.268, 'text': 'What you do is, you go to the entire column in which that 0 exists.', 'start': 60.147, 'duration': 4.121}, {'end': 68.209, 'text': 'You go to the entire row and you mark every 1 as 0.', 'start': 64.708, 'duration': 3.501}, {'end': 69.329, 'text': 'You mark every 1 as 0.', 'start': 68.209, 'duration': 1.12}, {'end': 71.991, 'text': 'Done Where is the next zero? Here.', 'start': 69.329, 'duration': 2.662}, {'end': 75.097, 'text': 'So you go, entire column, entire row.', 'start': 72.432, 'duration': 2.665}, {'end': 77.06, 'text': 'And you mark everyone as zero.', 'start': 75.538, 'duration': 1.522}, {'end': 80.186, 'text': 'Done Next, where is the next zero? Over here.', 'start': 77.922, 'duration': 2.264}, {'end': 83.271, 'text': 'So you go across the entire column and row.', 'start': 80.547, 'duration': 2.724}, {'end': 85.14, 'text': 'and mark everyone as zero.', 'start': 84.099, 'duration': 1.041}, {'end': 87.522, 'text': "Now remember one thing, over here there's a catch.", 'start': 85.48, 'duration': 2.042}, {'end': 91.445, 'text': "If there's a zero here, you go here, mark here, mark here, mark here, mark here.", 'start': 88.082, 'duration': 3.363}, {'end': 94.608, 'text': 'But from this marked zeros, you do not do anything.', 'start': 91.806, 'duration': 2.802}, {'end': 101.994, 'text': 'Only whatever zeros are there during the initial time, for those zeros, you go for the rows and columns.', 'start': 95.109, 'duration': 6.885}, {'end': 104.377, 'text': 'For those zeros, you go for the rows and columns.', 'start': 102.034, 'duration': 2.343}, {'end': 106.198, 'text': 'Nothing apart from them.', 'start': 105.077, 'duration': 1.121}, {'end': 108.481, 'text': 'Got it? So this question comes up in an interview.', 'start': 106.399, 'duration': 2.082}, {'end': 111.785, 'text': "The first solution that I'll give to the interviewer should be of the brute force solution.", 'start': 108.821, 'duration': 2.964}, {'end': 117.11, 'text': "What is the brute force solution that you can think of? That's let's do whatever is being told to us.", 'start': 112.165, 'duration': 4.945}, {'end': 122.556, 'text': "What is being told to us? If there's a zero, go across the entire column, mark everything as zero.", 'start': 117.651, 'duration': 4.905}, {'end': 125.738, 'text': 'and go across the entire row and mark everyone as 0.', 'start': 123.237, 'duration': 2.501}], 'summary': 'Given a binary matrix, find and mark all zeros in the rows and columns, following specific rules.', 'duration': 89.421, 'max_score': 36.317, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M36317.jpg'}, {'end': 253.043, 'src': 'embed', 'start': 227.55, 'weight': 3, 'content': [{'end': 233.914, 'text': 'Make sure you do not mark zeros as minus one because this zero will again be responsible for marking it.', 'start': 227.55, 'duration': 6.364}, {'end': 236.176, 'text': 'So if you mark it as minus one, there will be an issue.', 'start': 233.934, 'duration': 2.242}, {'end': 239.625, 'text': "So for this one, I've marked this, I've marked this.", 'start': 236.636, 'duration': 2.989}, {'end': 240.828, 'text': "I'll move forward.", 'start': 240.086, 'duration': 0.742}, {'end': 243.857, 'text': 'The moment I move forward to this, We have a zero.', 'start': 241.088, 'duration': 2.769}, {'end': 246.599, 'text': "So we'll go for this column and we'll go for this row.", 'start': 244.258, 'duration': 2.341}, {'end': 247.42, 'text': "So let's do it.", 'start': 246.879, 'duration': 0.541}, {'end': 248.4, 'text': 'Minus one.', 'start': 247.84, 'duration': 0.56}, {'end': 250.261, 'text': 'Again, do not mark this.', 'start': 249.041, 'duration': 1.22}, {'end': 251.162, 'text': 'Minus one.', 'start': 250.662, 'duration': 0.5}, {'end': 253.043, 'text': 'And this particular row is done.', 'start': 251.462, 'duration': 1.581}], 'summary': 'Avoid marking zeros as minus one to prevent issues. marked zero instances and progressed through the task.', 'duration': 25.493, 'max_score': 227.55, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M227550.jpg'}, {'end': 321.085, 'src': 'embed', 'start': 295.672, 'weight': 4, 'content': [{'end': 302.416, 'text': 'And once you have done this, I can say this is my final array and this will be my brute force solution.', 'start': 295.672, 'duration': 6.744}, {'end': 303.457, 'text': 'Quite simple.', 'start': 302.797, 'duration': 0.66}, {'end': 304.838, 'text': 'Just you have to be careful.', 'start': 303.817, 'duration': 1.021}, {'end': 308.22, 'text': "It's not about doing what they have said because that might cause an issue.", 'start': 305.218, 'duration': 3.002}, {'end': 312.663, 'text': 'So thereby we will just introduce something as minus one in the brute force solution.', 'start': 308.58, 'duration': 4.083}, {'end': 315.204, 'text': 'So, I have to write the code for the brute force solution.', 'start': 313.263, 'duration': 1.941}, {'end': 321.085, 'text': 'So, you know, in order to traverse, we first traverse from 0 to n, then we traverse from 0 to m.', 'start': 315.764, 'duration': 5.321}], 'summary': 'The brute force solution involves introducing -1 and traversing from 0 to n and 0 to m.', 'duration': 25.413, 'max_score': 295.672, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M295672.jpg'}], 'start': 36.317, 'title': 'Zero marking problem solutions', 'summary': 'Covers the problem of marking zeroes in a binary matrix and an array using brute force solutions. it emphasizes the importance of correct zero marking and introduces the use of minus one to address issues. it provides a thorough understanding of the process and its application.', 'chapters': [{'end': 145.789, 'start': 36.317, 'title': 'Set matrix zeros problem', 'summary': 'Covers the problem of finding and marking zeroes in a binary matrix using a brute force solution, iterating through the matrix to mark every 1 in the row and column containing a zero.', 'duration': 109.472, 'highlights': ['The task involves identifying and marking the positions of 0s in an n cross m binary matrix.', 'The process requires iterating through the entire column and row for each identified zero and marking every 1 as 0.', 'The brute force solution involves iterating through the entire matrix and marking every 1 in the row and column containing a zero.']}, {'end': 315.204, 'start': 145.789, 'title': 'Array zero marking solution', 'summary': 'Discusses the process of marking zeros in an array using a brute force solution, emphasizing the importance of avoiding incorrect zero markings and introducing the use of minus one to address the issue.', 'duration': 169.415, 'highlights': ['The importance of avoiding incorrect zero markings and introducing the use of minus one to address the issue The speaker emphasizes the need to avoid blindly marking everyone as zero in the array and introduces the concept of marking everyone as minus one to address the issue of incorrect zero markings.', 'Process of marking zeros in an array using a brute force solution The chapter discusses the process of marking zeros in an array using a brute force solution, where all non-zero elements are marked as minus one before converting them to zeros in a subsequent iteration.', 'Discussion on the importance of careful handling of zero markings The speaker emphasizes the importance of careful handling of zero markings in the array, highlighting the potential issues that can arise from blindly marking elements as zero and the need for a more cautious approach.']}], 'duration': 278.887, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M36317.jpg', 'highlights': ['The process requires iterating through the entire column and row for each identified zero and marking every 1 as 0.', 'The brute force solution involves iterating through the entire matrix and marking every 1 in the row and column containing a zero.', 'The task involves identifying and marking the positions of 0s in an n cross m binary matrix.', 'The importance of avoiding incorrect zero markings and introducing the use of minus one to address the issue.', 'The chapter discusses the process of marking zeros in an array using a brute force solution, where all non-zero elements are marked as minus one before converting them to zeros in a subsequent iteration.', 'The speaker emphasizes the importance of careful handling of zero markings in the array, highlighting the potential issues that can arise from blindly marking elements as zero and the need for a more cautious approach.']}, {'end': 558.955, 'segs': [{'end': 393.044, 'src': 'embed', 'start': 353.509, 'weight': 0, 'content': [{'end': 361.996, 'text': "Similarly, there'll be a column which takes the column number and iterates for every row and marks that column as minus one if it's a non-zero.", 'start': 353.509, 'duration': 8.487}, {'end': 368.121, 'text': 'So this code will make sure that everything that is a zero in that particular column, everything will be marked as minus one.', 'start': 362.316, 'duration': 5.805}, {'end': 372.245, 'text': 'And in that particular row, everything will be marked as minus one apart from the zeros.', 'start': 368.382, 'duration': 3.863}, {'end': 374.347, 'text': "Got it? So once we've done this.", 'start': 372.485, 'duration': 1.862}, {'end': 380.512, 'text': "What's the next job? The next job is just to iterate in the matrix and whoever is minus 1, turn it into 0.", 'start': 374.787, 'duration': 5.725}, {'end': 381.273, 'text': "So let's quickly do it.", 'start': 380.512, 'duration': 0.761}, {'end': 387.398, 'text': "So this will be the final piece of code where we iterate in the matrix and we say if it's a minus 1, please convert it into 0.", 'start': 381.833, 'duration': 5.565}, {'end': 393.044, 'text': "So what will be the time complexity of the brute force solution? Can I say over here it's n into m.", 'start': 387.398, 'duration': 5.646}], 'summary': 'Iterate through matrix to mark non-zero as -1, then convert -1 to 0. time complexity: o(n*m)', 'duration': 39.535, 'max_score': 353.509, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M353509.jpg'}, {'end': 461.045, 'src': 'embed', 'start': 432.734, 'weight': 1, 'content': [{'end': 437.376, 'text': 'So we gave a brute force solution to the interviewer, which was taking a time complexity in the order of n cube.', 'start': 432.734, 'duration': 4.642}, {'end': 439.757, 'text': 'And why was it taking a time?', 'start': 437.936, 'duration': 1.821}, {'end': 441.018, 'text': 'complexity in the order of n cube?', 'start': 439.757, 'duration': 1.261}, {'end': 448.021, 'text': 'Because we were traversing in the array and that was taking n square, like in the order of n square, n into m.', 'start': 441.058, 'duration': 6.963}, {'end': 451.883, 'text': 'And then what we did was for every zero, we went across the entire column.', 'start': 448.021, 'duration': 3.862}, {'end': 455.344, 'text': 'and the entire row and we marked everyone as zero.', 'start': 452.643, 'duration': 2.701}, {'end': 461.045, 'text': 'So this is where we were taking that extra time for going across the column and going across the row.', 'start': 455.644, 'duration': 5.401}], 'summary': 'Brute force solution had time complexity of n cube, due to traversing array and marking zeros.', 'duration': 28.311, 'max_score': 432.734, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M432734.jpg'}], 'start': 315.764, 'title': 'Optimizing time complexity', 'summary': 'Discusses how to optimize a solution from n cube to n square time complexity by rethinking the approach and introducing a new algorithm, as well as traversing a 2d matrix and marking certain elements to convert them into zeros with a time complexity of o(n*m).', 'chapters': [{'end': 413.861, 'start': 315.764, 'title': '2d matrix traversal and marking', 'summary': 'Discusses how to traverse a 2d matrix and mark certain elements, then iterates through the matrix to convert marked elements into zeros, with a time complexity of o(n*m).', 'duration': 98.097, 'highlights': ['The time complexity of the brute force solution is O(n*m) as it involves iterating through the matrix and marking elements, then converting marked elements into zeros.', 'The process involves traversing the matrix from 0 to n and 0 to m, marking rows and columns with non-zero elements as minus one, and then converting all minus one elements to zero.', 'Functions are written separately for marking rows and columns, with the mark row function iterating through columns and marking non-zero elements as minus one.']}, {'end': 558.955, 'start': 413.861, 'title': 'Optimizing time complexity in interview solutions', 'summary': 'Discusses the process of optimizing a solution presented to an interviewer from n cube to n square time complexity by rethinking the approach and introducing a new algorithm.', 'duration': 145.094, 'highlights': ['By rethinking the approach and introducing a new algorithm, the time complexity of the solution was optimized from n cube to n square.', 'The initial brute force solution had a time complexity in the order of n cube due to traversing the array, which took n square time for every zero to go across the entire column and row.', 'The approach to optimize involved eliminating the extra time taken to go across the column and row, and instead, marking the columns and rows with zeros as the algorithm progressed.']}], 'duration': 243.191, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M315764.jpg', 'highlights': ['The time complexity of the brute force solution is O(n*m) as it involves iterating through the matrix and marking elements, then converting marked elements into zeros.', 'By rethinking the approach and introducing a new algorithm, the time complexity of the solution was optimized from n cube to n square.', 'The process involves traversing the matrix from 0 to n and 0 to m, marking rows and columns with non-zero elements as minus one, and then converting all minus one elements to zero.']}, {'end': 818.707, 'segs': [{'end': 605.811, 'src': 'embed', 'start': 559.395, 'weight': 2, 'content': [{'end': 568.942, 'text': 'So there has to be four column array, correct, which will keep a track if the column is marked, and there will be a 4 over here, 4 size row array,', 'start': 559.395, 'duration': 9.547}, {'end': 571.744, 'text': 'which will again keep a track if the row is marked or not.', 'start': 568.942, 'duration': 2.802}, {'end': 575.668, 'text': "so i'll go ahead and create a m size.", 'start': 571.744, 'duration': 3.924}, {'end': 576.869, 'text': 'yes, very important.', 'start': 575.668, 'duration': 1.201}, {'end': 587.759, 'text': "i will create a column array of m size, because those many are the number of columns, and i'll create a row array of n size over here.", 'start': 576.869, 'duration': 10.89}, {'end': 593.863, 'text': "n and m are same And what I'll do is initially I will mark every one of them as 0..", 'start': 587.759, 'duration': 6.104}, {'end': 597.085, 'text': "0 means they're yet not touched.", 'start': 593.863, 'duration': 3.222}, {'end': 599.066, 'text': "And now I'll start iterating.", 'start': 597.525, 'duration': 1.541}, {'end': 601.588, 'text': 'First, no.', 'start': 600.167, 'duration': 1.421}, {'end': 602.369, 'text': '1, no.', 'start': 601.608, 'duration': 0.761}, {'end': 602.929, 'text': '1, no.', 'start': 602.389, 'duration': 0.54}, {'end': 603.409, 'text': '1, no.', 'start': 602.949, 'duration': 0.46}, {'end': 603.65, 'text': '1, no.', 'start': 603.429, 'duration': 0.221}, {'end': 605.811, 'text': "You will not do anything when there's a 1.", 'start': 604.39, 'duration': 1.421}], 'summary': 'Using a 4x4 column array and 4x4 row array to keep track of marked columns and rows. initializing arrays with 0s, and iterating through them to mark 1s.', 'duration': 46.416, 'max_score': 559.395, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M559395.jpg'}, {'end': 777.291, 'src': 'embed', 'start': 750.137, 'weight': 0, 'content': [{'end': 756.12, 'text': "so if we have to iterate in the matrix, first i'll go from zero to n, then i'll go from zero to m.", 'start': 750.137, 'duration': 5.983}, {'end': 758.301, 'text': 'perfect, then what is the next job?', 'start': 756.12, 'duration': 2.181}, {'end': 772.148, 'text': 'if that element at i j is zero, i know the row i, the row i will go ahead and get marked as 0 and the column j will go ahead and, sorry, marked as 1,', 'start': 758.301, 'duration': 13.847}, {'end': 773.969, 'text': 'rather marked as 1.', 'start': 772.148, 'duration': 1.821}, {'end': 777.291, 'text': 'both have been marked and this is how you can iterate and mark it.', 'start': 773.969, 'duration': 3.322}], 'summary': 'Iterate through matrix to mark rows and columns with zero elements.', 'duration': 27.154, 'max_score': 750.137, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M750137.jpg'}, {'end': 828.655, 'src': 'embed', 'start': 799.442, 'weight': 5, 'content': [{'end': 805.924, 'text': 'you will be zero for sure, because the entire sorry, the entire row is marked or the entire column is marked.', 'start': 799.442, 'duration': 6.482}, {'end': 810.185, 'text': "if that's the case, you will be this, and this is how the code will look like.", 'start': 805.924, 'duration': 4.261}, {'end': 810.865, 'text': 'got it?', 'start': 810.185, 'duration': 0.68}, {'end': 815.666, 'text': 'so in case you want to try out the problem, the link will be in the description, and if you want the c++, java and python code,', 'start': 810.865, 'duration': 4.801}, {'end': 817.567, 'text': 'all the links will be in the description.', 'start': 815.666, 'duration': 1.901}, {'end': 818.707, 'text': 'remember one thing.', 'start': 817.567, 'duration': 1.14}, {'end': 820.968, 'text': "uh, over here they're asking us to return a matrix.", 'start': 818.707, 'duration': 2.261}, {'end': 821.748, 'text': "that is why i'm returning.", 'start': 820.968, 'duration': 0.78}, {'end': 828.655, 'text': "If it's a void function, then you can just change to this particular matrix, which we are doing, and we do not need to return anything.", 'start': 822.288, 'duration': 6.367}], 'summary': 'The code returns a matrix in c++, java, and python, as explained in the problem-solving video.', 'duration': 29.213, 'max_score': 799.442, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M799442.jpg'}], 'start': 559.395, 'title': 'Array marking algorithm and optimizing matrix iteration', 'summary': 'Explains the algorithm for marking columns and rows in a 2d array, involving the creation of column and row arrays, and the initial marking of elements as 0. it also introduces an iterative approach to mark and convert elements in a matrix, resulting in a significant reduction of 0 elements, and provides programming language options for implementing the solution.', 'chapters': [{'end': 605.811, 'start': 559.395, 'title': 'Array marking algorithm', 'summary': 'Explains the algorithm for marking columns and rows in a 2d array, involving the creation of column and row arrays, and the initial marking of elements as 0, with the subsequent iteration process.', 'duration': 46.416, 'highlights': ['The algorithm involves creating a four-column array and a four-size row array to track the marking status of columns and rows, respectively.', 'The creation of a column array of size m and a row array of size n, both initialized with 0, is emphasized, where n and m are the same.', 'The importance of iterating through the array elements is highlighted, with a specific focus on handling the case when the element is 1.']}, {'end': 818.707, 'start': 605.811, 'title': 'Optimizing matrix iteration', 'summary': 'Introduces an iterative approach to mark and convert elements in a matrix, resulting in a significant reduction of 0 elements, as well as providing programming language options for implementing the solution.', 'duration': 212.896, 'highlights': ['The iterative approach involves marking and converting elements in the matrix, significantly reducing the number of 0 elements.', 'The process involves iterating through the matrix, marking rows and columns based on the presence of 0 elements, and then converting the marked elements to 0.', 'The chapter provides programming language options, including C++, Java, and Python, for implementing the solution.']}], 'duration': 259.312, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M559395.jpg', 'highlights': ['The iterative approach involves marking and converting elements in the matrix, significantly reducing the number of 0 elements.', 'The process involves iterating through the matrix, marking rows and columns based on the presence of 0 elements, and then converting the marked elements to 0.', 'The algorithm involves creating a four-column array and a four-size row array to track the marking status of columns and rows, respectively.', 'The creation of a column array of size m and a row array of size n, both initialized with 0, is emphasized, where n and m are the same.', 'The importance of iterating through the array elements is highlighted, with a specific focus on handling the case when the element is 1.', 'The chapter provides programming language options, including C++, Java, and Python, for implementing the solution.']}, {'end': 1797.831, 'segs': [{'end': 876.078, 'src': 'heatmap', 'start': 837.143, 'weight': 3, 'content': [{'end': 841.708, 'text': 'Remember the time complexity is b go of 2 cross n cross m for sure.', 'start': 837.143, 'duration': 4.565}, {'end': 843.89, 'text': 'what about the space complexity?', 'start': 842.188, 'duration': 1.702}, {'end': 851.5, 'text': "the space complexity is nothing but b go of n and b go of m for the two arrays that you're using for hashing.", 'start': 843.89, 'duration': 7.61}, {'end': 855.425, 'text': "this is where the interview will not be happy, because you're using an extra space,", 'start': 851.5, 'duration': 3.925}, {'end': 861.452, 'text': 'and he will ask you to optimize the better solution and you will move to the optimal one Over here.', 'start': 855.425, 'duration': 6.027}, {'end': 863.073, 'text': 'can you optimize the time complexity?', 'start': 861.452, 'duration': 1.621}, {'end': 865.894, 'text': 'We are already doing it in the order of n square.', 'start': 863.353, 'duration': 2.541}, {'end': 869.655, 'text': 'And we know the minimum in order to traverse a matrix can be n square.', 'start': 866.234, 'duration': 3.421}, {'end': 870.916, 'text': 'You cannot do better than that.', 'start': 869.775, 'duration': 1.141}, {'end': 876.078, 'text': "That's why we will be focusing to optimize the time complexity.", 'start': 871.316, 'duration': 4.762}], 'summary': 'The time complexity is o(2 * n * m), and space complexity is o(n + m). interviewers may not be happy with the extra space used and will ask for an optimized solution.', 'duration': 38.935, 'max_score': 837.143, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M837143.jpg'}, {'end': 1051.868, 'src': 'embed', 'start': 1023.625, 'weight': 2, 'content': [{'end': 1026.307, 'text': 'I will probably extend this to something like this.', 'start': 1023.625, 'duration': 2.682}, {'end': 1030.431, 'text': "Can I do this? I'll call it as a column variable.", 'start': 1027.028, 'duration': 3.403}, {'end': 1032.512, 'text': "I'll just call it as a column variable.", 'start': 1030.791, 'duration': 1.721}, {'end': 1035.396, 'text': 'Can I call this? Because this is an extra part.', 'start': 1032.914, 'duration': 2.482}, {'end': 1036.597, 'text': 'This is an extra part.', 'start': 1035.756, 'duration': 0.841}, {'end': 1038.039, 'text': 'So the row stays as row.', 'start': 1036.917, 'duration': 1.122}, {'end': 1039.7, 'text': 'And I take this much.', 'start': 1038.739, 'duration': 0.961}, {'end': 1043.604, 'text': 'And for this, since it is colliding, put it into a variable.', 'start': 1039.921, 'duration': 3.683}, {'end': 1045.025, 'text': 'Now there is no collision.', 'start': 1044.165, 'duration': 0.86}, {'end': 1048.347, 'text': 'works works fine, for me at least.', 'start': 1045.806, 'duration': 2.541}, {'end': 1051.868, 'text': "so now what i'll do is i'll try to probably draw the figure.", 'start': 1048.347, 'duration': 3.521}], 'summary': 'The process involves extending a column variable, addressing extra parts, and resolving collisions to achieve a successful outcome.', 'duration': 28.243, 'max_score': 1023.625, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M1023625.jpg'}, {'end': 1113.729, 'src': 'heatmap', 'start': 1082.7, 'weight': 0.852, 'content': [{'end': 1086.24, 'text': 'Agreed? This zero will mark everything here and mark everything here.', 'start': 1082.7, 'duration': 3.54}, {'end': 1089.661, 'text': 'Agreed? This zero will mark everything here and everything here.', 'start': 1086.38, 'duration': 3.281}, {'end': 1095.802, 'text': 'So if you remember, so if you see, everyone will be converted to zeros only apart from this corner guy.', 'start': 1089.681, 'duration': 6.121}, {'end': 1099.243, 'text': 'Keep this in mind that this corner guy will not be converted.', 'start': 1096.082, 'duration': 3.161}, {'end': 1099.963, 'text': 'Keep this in mind.', 'start': 1099.343, 'duration': 0.62}, {'end': 1103.444, 'text': 'It will be very, very useful in the next part when we figure some edge cases.', 'start': 1100.063, 'duration': 3.381}, {'end': 1105.784, 'text': 'Keep this in mind, the corner is not converted.', 'start': 1103.744, 'duration': 2.04}, {'end': 1107.705, 'text': "Okay, let's start on creating in the matrix.", 'start': 1106.185, 'duration': 1.52}, {'end': 1113.729, 'text': "We have a 1, right? What happens to this one? This one says, I'm a 1.", 'start': 1108.385, 'duration': 5.344}], 'summary': 'All values except the corner will be converted to zeros in the matrix.', 'duration': 31.029, 'max_score': 1082.7, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M1082700.jpg'}, {'end': 1176.664, 'src': 'heatmap', 'start': 1119.372, 'weight': 0.702, 'content': [{'end': 1120.413, 'text': "But he's a 0.", 'start': 1119.372, 'duration': 1.041}, {'end': 1123.014, 'text': "He's like, what did I do? I'll keep a track.", 'start': 1120.413, 'duration': 2.601}, {'end': 1123.935, 'text': "So I'll mark it here.", 'start': 1123.035, 'duration': 0.9}, {'end': 1125.096, 'text': "I'll mark it here.", 'start': 1124.495, 'duration': 0.601}, {'end': 1128.218, 'text': 'And I know who is this guy.', 'start': 1125.376, 'duration': 2.842}, {'end': 1129.459, 'text': 'Who is this? This one.', 'start': 1128.418, 'duration': 1.041}, {'end': 1132.18, 'text': 'So I will now go and convert them to 0s.', 'start': 1129.999, 'duration': 2.181}, {'end': 1136.342, 'text': 'Perfect Next, I have a 1, 1, 1, 1, 0.', 'start': 1132.721, 'duration': 3.621}, {'end': 1140.004, 'text': 'This zero was marking it here and marking it here.', 'start': 1136.343, 'duration': 3.661}, {'end': 1142.685, 'text': "So instead of this, I'll mark it here.", 'start': 1140.604, 'duration': 2.081}, {'end': 1145.286, 'text': 'Perfect Next one, zero.', 'start': 1143.205, 'duration': 2.081}, {'end': 1151.188, 'text': 'This zero was apparently marking it here and was apparently marking it here in the culinary.', 'start': 1145.926, 'duration': 5.262}, {'end': 1155.549, 'text': "So what will happen now? Instead of here, it'll mark here and it's already a zero.", 'start': 1151.668, 'duration': 3.881}, {'end': 1156.27, 'text': "So it's okay.", 'start': 1155.809, 'duration': 0.461}, {'end': 1158.29, 'text': "And instead of here, it'll mark here.", 'start': 1156.87, 'duration': 1.42}, {'end': 1160.291, 'text': 'So this will make it zero.', 'start': 1158.69, 'duration': 1.601}, {'end': 1164.294, 'text': 'Perfect Next, we have a 1, we have a 1, we have a 1.', 'start': 1160.911, 'duration': 3.383}, {'end': 1165.755, 'text': 'So, the iteration is completed.', 'start': 1164.294, 'duration': 1.461}, {'end': 1171.4, 'text': 'Once the iteration is completed, what is the next job? To convert all the 1s to 0s who are marked.', 'start': 1166.356, 'duration': 5.044}, {'end': 1174.542, 'text': 'Correct? To convert all the 1s who are 0s.', 'start': 1171.86, 'duration': 2.682}, {'end': 1176.664, 'text': 'This is where you have to remember.', 'start': 1175.543, 'duration': 1.121}], 'summary': 'Iteratively converting marked 1s to 0s, completing the iteration.', 'duration': 57.292, 'max_score': 1119.372, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M1119372.jpg'}, {'end': 1413.155, 'src': 'embed', 'start': 1381.695, 'weight': 1, 'content': [{'end': 1382.995, 'text': 'so this will be zero.', 'start': 1381.695, 'duration': 1.3}, {'end': 1384.896, 'text': 'convert it to zero for this portion.', 'start': 1382.995, 'duration': 1.901}, {'end': 1386.517, 'text': "it's zero, zero, zero.", 'start': 1384.896, 'duration': 1.621}, {'end': 1387.598, 'text': 'done so.', 'start': 1386.517, 'duration': 1.081}, {'end': 1391.46, 'text': 'first you solve here, here, here, here, here, here, here.', 'start': 1387.598, 'duration': 3.862}, {'end': 1394.782, 'text': 'then you solve this because it is dependent on this.', 'start': 1391.46, 'duration': 3.322}, {'end': 1397.194, 'text': 'then you solve this First.', 'start': 1394.782, 'duration': 2.412}, {'end': 1401.24, 'text': 'do not solve this, because if you change the values, that will impact the matrix.', 'start': 1397.194, 'duration': 4.046}, {'end': 1403.783, 'text': 'This was the thought process behind this particular algorithm.', 'start': 1401.68, 'duration': 2.103}, {'end': 1406.347, 'text': "So let's quickly code the optimal solution up.", 'start': 1404.424, 'duration': 1.923}, {'end': 1409.01, 'text': 'And this was the better solution if you can see in the editor.', 'start': 1406.587, 'duration': 2.423}, {'end': 1410.332, 'text': 'So let me remove this.', 'start': 1409.371, 'duration': 0.961}, {'end': 1413.155, 'text': 'And I will just comment this off.', 'start': 1411.213, 'duration': 1.942}], 'summary': 'Algorithm optimized to zero values, ensuring matrix integrity. better solution coded.', 'duration': 31.46, 'max_score': 1381.695, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M1381695.jpg'}, {'end': 1549.058, 'src': 'heatmap', 'start': 1517.687, 'weight': 0.764, 'content': [{'end': 1518.908, 'text': 'It could not mark in the column.', 'start': 1517.687, 'duration': 1.221}, {'end': 1523.491, 'text': "And if you see over here, what's the column? That's the matrix of 0 of something.", 'start': 1519.548, 'duration': 3.943}, {'end': 1525.232, 'text': 'Matrix of 0 of something.', 'start': 1523.871, 'duration': 1.361}, {'end': 1527.674, 'text': 'So remember, if j is.', 'start': 1525.672, 'duration': 2.002}, {'end': 1530.957, 'text': 'not equal to zero, then only you mark it.', 'start': 1528.454, 'duration': 2.503}, {'end': 1534.241, 'text': 'otherwise yes, otherwise, what will you do?', 'start': 1530.957, 'duration': 3.284}, {'end': 1536.183, 'text': 'you will say caller of zero.', 'start': 1534.241, 'duration': 1.942}, {'end': 1538.946, 'text': 'can you mark yourself if your j is zero?', 'start': 1536.183, 'duration': 2.763}, {'end': 1540.468, 'text': "let's go back again.", 'start': 1538.946, 'duration': 1.522}, {'end': 1543.872, 'text': 'if you are over here, you do not mark it here.', 'start': 1540.468, 'duration': 3.404}, {'end': 1545.314, 'text': 'instead of you mark it here.', 'start': 1543.872, 'duration': 1.442}, {'end': 1546.175, 'text': 'got it?', 'start': 1545.314, 'duration': 0.861}, {'end': 1549.058, 'text': 'do not mark anything on this Instead of go here.', 'start': 1546.175, 'duration': 2.883}], 'summary': 'Discussion on marking a matrix, emphasizing the condition of j not equal to zero for marking.', 'duration': 31.371, 'max_score': 1517.687, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M1517687.jpg'}, {'end': 1773.331, 'src': 'heatmap', 'start': 1660.999, 'weight': 0, 'content': [{'end': 1664.401, 'text': 'first we mark these three elements, then we mark this.', 'start': 1660.999, 'duration': 3.402}, {'end': 1666.743, 'text': 'so how will these three elements?', 'start': 1664.401, 'duration': 2.342}, {'end': 1668.804, 'text': 'when will these three elements be zero?', 'start': 1666.743, 'duration': 2.061}, {'end': 1670.925, 'text': 'when will these three elements be zero?', 'start': 1668.804, 'duration': 2.121}, {'end': 1679.05, 'text': "if this guy who has matrix of zero, zero, if this is zero, then everyone will be, because it's dependent on this.", 'start': 1670.925, 'duration': 8.125}, {'end': 1694.901, 'text': 'so the last step will be hey, if matrix of 0, 0 is equal to 0, everyone in the column, which is this matrix of zero, j,', 'start': 1679.05, 'duration': 15.851}, {'end': 1698.164, 'text': 'everyone in the first row will be zero.', 'start': 1694.901, 'duration': 3.263}, {'end': 1700.786, 'text': 'quite simple, and what about this one?', 'start': 1698.164, 'duration': 2.622}, {'end': 1703.749, 'text': 'this one will be dependent on the column.', 'start': 1700.786, 'duration': 2.963}, {'end': 1708.873, 'text': 'so please go ahead and say if column zero is equal to equal to zero, what will i do?', 'start': 1703.749, 'duration': 5.124}, {'end': 1716.76, 'text': 'i will do the same thing for i and d, i equal to zero, i less than n, i plus plus, because everyone on this portion will be marked as zero.', 'start': 1708.873, 'duration': 7.887}, {'end': 1725.064, 'text': 'So I will go and say matrix of zero, sorry, matrix of I, and everything on the first column will be zero.', 'start': 1717.461, 'duration': 7.603}, {'end': 1727.544, 'text': 'Once you have done this, you can return the matrix.', 'start': 1725.504, 'duration': 2.04}, {'end': 1729.005, 'text': "Now let's quickly go and run.", 'start': 1727.924, 'duration': 1.081}, {'end': 1731.366, 'text': 'I hope it runs at once.', 'start': 1729.345, 'duration': 2.021}, {'end': 1732.226, 'text': "I'll be super happy.", 'start': 1731.566, 'duration': 0.66}, {'end': 1733.206, 'text': 'Oh, I am.', 'start': 1732.826, 'duration': 0.38}, {'end': 1735.407, 'text': 'Quite simple.', 'start': 1734.727, 'duration': 0.68}, {'end': 1739.568, 'text': "The only way that you can write this is try to write this so that you don't get confused.", 'start': 1735.427, 'duration': 4.141}, {'end': 1741.649, 'text': 'This is how I approach usually a code.', 'start': 1739.588, 'duration': 2.061}, {'end': 1751.502, 'text': 'So what is the time complexity? N into M? And this overall is the total matrix iteration n into m, 2 into n into m.', 'start': 1742.129, 'duration': 9.373}, {'end': 1755.703, 'text': 'Are we using any extra space? Probably yes for this column.', 'start': 1751.502, 'duration': 4.201}, {'end': 1757.664, 'text': 'One variable, one variable.', 'start': 1756.563, 'duration': 1.101}, {'end': 1758.204, 'text': "That's it.", 'start': 1757.904, 'duration': 0.3}, {'end': 1758.784, 'text': "That's it.", 'start': 1758.464, 'duration': 0.32}, {'end': 1759.825, 'text': 'One variable.', 'start': 1759.245, 'duration': 0.58}, {'end': 1764.527, 'text': 'And I was able to solve the problem in place within the matrix itself.', 'start': 1760.045, 'duration': 4.482}, {'end': 1767.589, 'text': "So let's go back to the sheet and mark this as done.", 'start': 1764.867, 'duration': 2.722}, {'end': 1773.331, 'text': 'I hope you have understood all the three approaches and the buildup to the optimal solution.', 'start': 1768.149, 'duration': 5.182}], 'summary': 'Iteratively mark elements as zero based on specific conditions; time complexity is n*m, using minimal extra space', 'duration': 112.332, 'max_score': 1660.999, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M1660999.jpg'}], 'start': 818.707, 'title': 'Matrix operations', 'summary': 'Covers matrix return, time complexity, space complexity, optimizing time complexity for traversal, a transformation algorithm, and optimal matrix marking with time complexity of n*m.', 'chapters': [{'end': 861.452, 'start': 818.707, 'title': 'Matrix return and time complexity', 'summary': 'Discusses returning a matrix in a function, time complexity being b go of n cross m, and space complexity involving extra space usage, prompting the need for optimization.', 'duration': 42.745, 'highlights': ['The time complexity is b go of n cross m and the space complexity is b go of n and b go of m.', 'The interview will not be happy due to the usage of extra space, prompting the need for optimization.', "If it's a void function, then there is no need to return anything."]}, {'end': 1070.818, 'start': 861.452, 'title': 'Optimizing time complexity for matrix traversal', 'summary': 'Discusses the optimization of time complexity for matrix traversal, proposing the idea of using the matrix itself to track rows and columns, resulting in a more efficient approach.', 'duration': 209.366, 'highlights': ['The proposal to use the matrix itself to track rows and columns for optimization. The speaker discusses the idea of using the matrix itself to track rows and columns, aiming to optimize time complexity for matrix traversal.', 'Adapting the first column to represent the row and using a column variable to handle the extra part, resulting in reduced collision and improved efficiency. The speaker suggests adapting the first column to represent the row and using a column variable to handle the extra part, resulting in reduced collision and improved efficiency for matrix traversal.', 'Visual representation and explanation of the optimized approach using the matrix for tracking columns and rows. The speaker visually represents and explains the optimized approach of using the matrix for tracking columns and rows, aiming to optimize time complexity for matrix traversal.']}, {'end': 1403.783, 'start': 1071.399, 'title': 'Matrix transformation algorithm', 'summary': 'Explains a matrix transformation algorithm where specific elements are marked and converted to zeros based on certain conditions, ensuring that the algorithm is applied in a specific order to avoid impacting the matrix.', 'duration': 332.384, 'highlights': ['Specific elements in the matrix are marked and converted to zeros based on certain conditions. The algorithm involves marking specific elements and converting them to zeros.', 'The algorithm must be applied in a specific order to avoid impacting the matrix. The order of applying the algorithm is crucial to avoid impacting the original matrix.', 'The algorithm involves a step-by-step process of marking and converting elements to zeros, ensuring that certain elements are not altered to avoid impacting the matrix. The algorithm follows a meticulous step-by-step process to mark and convert elements, while ensuring that specific elements are not altered to avoid impacting the original matrix.']}, {'end': 1797.831, 'start': 1404.424, 'title': 'Optimal matrix marking', 'summary': 'Explains the optimal solution for matrix marking, involving row and column manipulations, with a time complexity of n*m and minimal extra space usage.', 'duration': 393.407, 'highlights': ['The optimal solution involves marking rows and columns in a matrix, with the time complexity of N*M and minimal extra space usage.', 'Iterating through the matrix involves ignoring the 0th row and column, and converting elements as necessary.', 'The final step involves marking elements in the first row and column based on the 0th element, resulting in an in-place solution within the matrix.']}], 'duration': 979.124, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/N0MgLvceX7M/pics/N0MgLvceX7M818707.jpg', 'highlights': ['The optimal solution involves marking rows and columns in a matrix, with the time complexity of N*M and minimal extra space usage.', 'The algorithm involves a step-by-step process of marking and converting elements to zeros, ensuring that certain elements are not altered to avoid impacting the matrix.', 'Adapting the first column to represent the row and using a column variable to handle the extra part, resulting in reduced collision and improved efficiency.', 'The time complexity is b go of n cross m and the space complexity is b go of n and b go of m.']}], 'highlights': ["This is world's most in-depth course when it comes to DS Algo with 455 modules.", "By the end of the course, you're gonna solve more than 400 plus problems in DS Algo.", 'Once you complete this entire course, you can clear any of the ds algorithms in any company in any part of the world.', 'The process requires iterating through the entire column and row for each identified zero and marking every 1 as 0.', 'The brute force solution involves iterating through the entire matrix and marking every 1 in the row and column containing a zero.', 'The task involves identifying and marking the positions of 0s in an n cross m binary matrix.', 'The time complexity of the brute force solution is O(n*m) as it involves iterating through the matrix and marking elements, then converting marked elements into zeros.', 'The iterative approach involves marking and converting elements in the matrix, significantly reducing the number of 0 elements.', 'The optimal solution involves marking rows and columns in a matrix, with the time complexity of N*M and minimal extra space usage.']}