Matrix Diagonal Sum - Leetcode 1572 - Python

NeetCodeIO · Intermediate ·⚡ Algorithms & Data Structures ·3y ago

Key Takeaways

The video demonstrates a Python solution to Leetcode 1572, Matrix Diagonal Sum, using a single loop to calculate the sum of the primary and secondary diagonals of a square matrix, with a time complexity of Big O of n and constant memory complexity.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem Matrix diagonal sum even though this is an easy one it can be a little tricky to code it up in a pretty like concise way so I'm really going to break down my thought process for you in this problem and by the end of the video I really want you to feel like you could have solved this problem by yourself so we're given a square Matrix and we want to return the sum of the diagonals so just to blow this up a little we can see here we have this diagonal I guess this is called the primary diagonal and we also have the secondary diagonal and at this point a naive thing to do would be to just jump into the code and try to think about what variables we're going to do how we're going to be iterating through like the grid are we just going to iterate over the entire grid maybe that would be N squared that's not a bad thought to have though and honestly if you can just jump into the code and solve this problem that's not a bad idea but if you can't I definitely recommend just looking at the picture and actually thinking about the problem don't just stare at it and do nothing the first step is a pretty easy one let's just try to see what would the total be for this example it's pretty simple let's just go value by value we would start here that's one plus the next value we're going down and to the right now we have five and then we continue down here to nine and then we're pretty much done we're out of bounds we can't really go any further so we noticed some observations immediately this diagonal is of length three and at this position we're starting at zero zero and then we're going to the next position which is one one next position which is two two and just keep going like that until we go out of bounds which we will know we went out of bounds because really we're only iterating n times where n is one of the dimensions of the square Matrix so pretty straightforward there this pretty much tells me that we can calculate this by creating a loop a for Loop or a while loop where we have maybe I as the index and to access like each value we just say Matrix at index I and the second index is also going to be index I so pretty simple there now let's go to the secondary diagonal I guess we could start over here or we could start over here which one do you think is better are there any trade-offs we could make well immediately I would personally rather start over here because yes these two positions do have a different column but they actually have the exact same row and the next value is also going to have the same Row the next value here is also going to have the same row so I'd rather start from over here so we're starting here all the way at the right and as we go to the next position we're kind of doing a similar thing where we started at row I and then we go to row I plus one but what about the column it's obviously we're doing the opposite here right column is two but for the next value over here now the column is being decremented so that's something we'll have to keep in mind and then we'll get to the last value 7 and let's assume we added them up as we were doing it so plus three plus five plus seven we got a total of 30 but when we look at the solution the actual output is 25 which just reminds us that we double counted this value over here this five we double counted it so that's just something we have to remember it's probably something you know when you first read the problem but sometimes it can slip your mind so once we do all of this we have to subtract this value or just not add it in the first place in my opinion it's easier to subtract it after the fact because this is obviously always going to be in the middle right when these two lines intersect it's going to be usually in the middle so how can we kind of calculate that is it possible for us to exactly calculate that middle value I just cleaned this up a little bit but obviously it's the halfway point right we take the halfway point of this demand mention which will give us this because if you take 2 and divide it by 2 you get 1 and we take the halfway point of this you take two divide it by two you get one and I think we wouldn't actually use the two value we would use the length of the Matrix the length of this is obviously three three divided by two will also round down to one well assuming we are rounding down so obviously that's what we would want to do but this only seems to work in the odd case right if our Dimension is odd because our Dimension is currently of length three does this also work for even Dimensions like four let's test it out so I just drew a four by four Matrix over here now I'm going to draw a line going from the top right going down so obviously these are the four cells that that's going to visit let's try the other diagonal now starting from here where here then here then here and then here did you notice something you probably did if you have eyes that these two lines don't enter intersect each other when the grid is of an even Dimension I don't know that because I'm smart I know that because I have decent problem solving skills because I spent a lot of time building up these habits so now we realize that we'll be iterating like this iterating like this and if the grid is odd length we're going to find the middle value and subtract it from our total our total was 30 we're going to minus five then we get 25 and clearly that is the result that they were expecting and I'm gonna end up solving this problem with just a single Loop that's going to iterate n times and we didn't really need any extra memory so the time complexity is going to be Big O of n memory complexity is going to be constant so now let's code this up so we know we're calculating the sum so I'm going to create a variable for that result and then we're just going to start iterating through the array we know we're probably going to need the index so I'm going to say for I in range the length of this Matrix and then we want to Total stuff up so let's start with the primary diagonal how do we get that that was the straightforward part it's always going to be at index I at index I and then we just take that and add it to the result now what about the secondary diagonal well let's start with what we know we know it's always going to be in the same row as the primary diagonal so we're going to start at index I for the row what about the column we know initially it's going to be the length of Matrix minus one we know that's what it's initially going to be and next time it's going to be -1 again and minus 1 again and minus 1 again do you know a way we can repeatedly do a minus one operation well with a loop that's what Loops are for can we use this Loop or do we have to create a second Loop to do this we can actually use this Loop because what we can say here is length of Matrix -1 1 minus I because I is already being incremented but we want to use it in a negative way so we subtract that value so this is going to be the index of the column of the secondary diagonal not the row okay and now finally we are ready to go ahead and return our result but we know that we might have to subtract from it now we could do that in like an if statement up over here and that's perfectly fine but the way I like to code I I like to personally use a lot of ternary operators when like it's possible and it makes sense and I think in this case it does because we might want to subtract by zero or we might want to subtract by this value The Matrix value all the way in the middle so n divided by 2 and N divided by 2 here the reason I'm doing double slashes is because in Python by default it does decimal division so I want to do integer division here but in other languages I think most languages by default do integer division where we round down that's what we want to do here but we only want to subtract this value if n modded by 2 is positive is one if n is odd in other words otherwise we are going to subtract zero and that is all of the code now let's run it to make sure that it works well I just failed an easy problem did you catch my mistake I tried using n as the length of the Matrix before I actually created that variable so let's do that up here I'm going to say n is going to be equal to the length of the Matrix and since we already used uh the length of the Matrix down here I'm just going to replace that with n to make this a bit more concise and then rerun this and now it does work I personally wouldn't pay attention to this runtime I don't know how you can speed it up but if you found this helpful please like And subscribe if you're preparing for coding interviews check out neat code.io I just released a new review feature that I'm going to be actively working on so I would love your feedback on that and I'll see you soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews Solving Leetcode 1572, Matrix Diagonal Sum, today's daily leetcode problem on May 7. 🥷 Discord: https://discord.gg/ddjKRXPqtk 🐦 Twitter: https://twitter.com/neetcode1 🐮 Support the channel: https://www.patreon.com/NEETcode ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf 💡 DYNAMIC PROGRAMMING PLAYLIST: https://www.youtube.com/watch?v=73r3KWiEvyk&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO&index=1 Problem Link: https://leetcode.com/problems/matrix-diagonal-sum/ 0:00 - Read the problem 0:30 - Drawing Explanation 5:40 - Coding Explanation leetcode 1572 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 0 of 60

← Previous Next →
1 Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 14 Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 49 Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

This video teaches how to solve Leetcode 1572, Matrix Diagonal Sum, using a Python solution with a single loop and constant memory complexity. The solution involves calculating the sum of the primary and secondary diagonals of a square matrix.

Key Takeaways
  1. Iterate over the matrix and add the elements at the corresponding positions on the diagonals
  2. Calculate the sum of the primary diagonal
  3. Calculate the sum of the secondary diagonal
  4. Subtract the middle value to avoid double counting
  5. Use a ternary operator for conditional subtraction
  6. Perform integer division using double slashes
💡 The solution uses a single loop to calculate the sum of the primary and secondary diagonals, reducing time complexity to Big O of n and memory complexity to constant.

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python

Chapters (3)

Read the problem
0:30 Drawing Explanation
5:40 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →