Convert an Array Into a 2D Array With Conditions - Leetcode 2610 - Python

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

Key Takeaways

The video demonstrates a solution to the Leetcode problem 2610, converting an array into a 2D array with conditions, using Python and a hashmap to minimize the number of rows and ensure unique integers in each row.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem convert an array into a 2d array with conditions so the idea is we're given an input array of nums which can contain duplicate values but we need to create a two-dimensional array from all of these numbers and basically the Restriction is that every Row in the 2D array has to have unique integers meaning there can't be any duplicates we have to do that while minimizing the number of rows and I think the reason why they even say this is because the easiest thing that we could do if this restriction didn't exist is just put every single number in its own row cuz that would guarantee that there aren't any duplicates in any of the rows but they want us to minimize the number of rows so basically we will be building a 2d Matrix and we'll only be adding a new row if we have to so one thing that you might notice about a a problem like this one is that the number of rows that we're going to have is going to be bounded by the number of copies the most frequent number is let's say the most frequent number is 10 and there are let's say four copies of 10 then we're going to end up having four rows because we have to put one of the copies of 10 in each different row suppose we're iterating over this input array how would we know if we have found a duplicate integer well we'd have to keep track of it and probably the best way to do that would be using some kind of hash data structure either a hash set or a hash map then we would know okay like this is a one and we've seen one before but knowing that we've seen a number before actually isn't enough it would be good if we actually had a hash map where we could count the number of times that we've seen a number before for example if I've seen one three times and now now it's the fourth time I'm seeing it that is significant because that means we put each of these ones in its own row so we had three rows at least for these three ones but now we see a fourth one so we have to either create a fourth row or just insert the one in the fourth row if it already exists and you might kind of notice a pattern with this this is the zeroth row this is the first row this is the second row and this is the third row if this this is the fourth time we're seeing this number then we're going to put it in the fourth minus one row or if we've already seen this number three times as you can see over here then we're going to put the next copy in the third row and of course if we hadn't seen that value at all before if we' only seen it like this is the first time we're seeing a one we'd put it in the zeroth row so that's pretty much the idea of solving this problem what we're going to do is we're going to iterate over the input array we're going to count the number of times we've seen each number so here we see one this is the first time that we're seeing it so we add it to the first row now we see a three it's the first time that we're seeing it so we add it to the first row four same thing add it to the first row now we see one for the second time and we know that cuz we're counting it in our hashmap so then we add it to a new row that we have to create and we can set the count now to two sor about the handwriting now we see two for the first time so we can just add it to the first row and set its count to one and we see three for the second time so we have to put three here we'll set its count to two as well and now we see one for the third time so we do have to create a third row for one so here you can see solving it that way we get the same thing that they did in the output so this is going to be our 2D Matrix notice that every row doesn't have to be the same length so it's not actually a matrix it's a 2d array sorry about that in terms of time complexity clearly we only have to iterate over the input once for memory complexity we are technically building the 2D array but even if that doesn't count we do have a hash map which can be in the worst case the size of the input array so time and memory complexity is going to be Big O of n where n is the size of the input array now let's code this up so I'm going to create a hashmap I'm going to call it a default dict in Python and the default value is going to be an integer so this will basically like if we haven't inserted a key yet into this like one for example the value of this will still be considered zero so even if we haven't inserted a key we're not going to get a key does an exist error we will get zero as the default value also going to declare the result which is going to be the 2D Matrix that we ultimately end up returning and before we can return it we have to build it so let's go through every number in the input array we don't care about the index we just just want the number itself now let's figure out what is the row that we want to insert this number into so I'm going to say for our hashmap let's get how many times we've seen this number before initially it's definitely going to be zero so that would mean we insert it into the zeroth row but we haven't even added the zeroth row yet so what we would do here is check if the length of result is equal to the row that means we're going to get an index out of bounds error if we try to do result of row we're going to get index out of bounds so what we do is to result we append this empty row this is the new row that we're adding now we can say result at index row let's append the current number that we just saw we're adding this number to this row and before we forget we should probably increment the count of the number before this Loop iteration is finished so let's do that so this actually is the entire code notice we only insert a row if it doesn't already exist otherwise we just append the current number to the relevant row the row comes from how many times we've already seen that number before because we don't ever want any duplicates in the same row now let's just run this to make sure that it works as you can see on the left yes it does it's pretty efficient even though the run time is pretty random on lead code if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🧑‍💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/ 🥷 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/convert-an-array-into-a-2d-array-with-conditions/ 0:00 - Read the problem 0:50 - Drawing Explanation 4:22 - Coding Explanation leetcode 2610 #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

The video teaches how to solve Leetcode problem 2610 by converting an array into a 2D array with conditions, using a hashmap to minimize rows and ensure unique integers. This problem requires algorithmic thinking, data structures, and systems design skills.

Key Takeaways
  1. Create a hashmap to count the occurrences of each number
  2. Iterate over the input array and insert each number into the relevant row based on its count
  3. Append a new row to the result if it doesn't exist
  4. Increment the count of the number before moving to the next iteration
  5. Return the resulting 2D array
💡 Using a hashmap to count the occurrences of each number allows for efficient insertion of numbers into the relevant rows, minimizing the number of rows and ensuring unique integers in each row.

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:50 Drawing Explanation
4:22 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →