Divide Array Into Arrays With Max Difference - Leetcode 2966 - Python

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

Key Takeaways

The video solves the LeetCode problem 2966, Divide Array Into Arrays With Max Difference, using a sorting approach. It first checks if the input array can be divided into subarrays of size 3, then sorts the array and checks each subarray to ensure the max minus min difference is within the given limit K.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem divide array into arrays with a particular Max difference we are given an array of nums of size n and we want to divide it into arrays where each of those arrays are going to be of size three immediately the first question you should ask or at least the first question I personally asked is is this n number going to at least be greater than or equal to three because if not then obviously we can't really do that so I quickly scroll down to the bottom of the problem and it actually turns out that N is a multiple of three so that actually works out pretty nicely so at the very least we should be able to take whatever input that we are given suppose the size is six and we should be able to break it down into multiples of three and split it up into arrays so is there any other criteria that we have to worry about there probably is because we're given a second parameter a positive integer K the guarantee about every single one of these subarrays is going to be that the max minus the minimum or whatever the absolute difference is between the Max and the minimum is going to be less than or equal to K so that's the guarantee that we have to make so let me just walk you through my thought process when I solved this problem first I asked myself what's the Brute Force solution I kind of do that for every problem and in this case The Brute Force is not even trivial if you were to kind of approach it with backtracking it would be pretty difficult cuz you'd have to create every single possible sub Beret of size 3 as soon as I realized that I didn't even consider the Brute Force anymore then I started asking is there any sort of pattern is there any sort of shortcut among these elements it doesn't take long to notice if you even just stare at the output because you quickly notice that the output is sorted but that's actually not how I solved the problem I didn't even look at that I just thought to myself we have a window of size K we want for this particular subarray all those numbers to fall within that window so the first value that we pick doesn't matter at all I'm going to pick the first value is one just the first element in the array okay now the next values I pick do matter I want them to be within that window so I could kind of brute force it in a way by just iterating over every element in the remaining portion of the array and trying to figure out if they're within that window but then you realize well the placement of one matters is one going to be the first element in that window is it going to be the last element and then you realize that ideally we want similar elements to be grouped together how can we do that well by definition that's sorting when I say similar elements I meant elements that are close together in value should be placed close together in their position in the array and as soon as I realized that I thought sorting is a possible solution but still how do we guarantee that sorting works well think of it this way let me introduce you to a way of thinking that you can actually apply to other problems as well this is called a proof by contradiction and this is not a formal proof this is just kind of the thought process that you can use suppose I sort the array we know that this is the solution but what if it wasn't what if I actually tried taking these two values and instead of taking the three I take a bigger value I actually take four instead because maybe it's possible by not choosing an element here we can somehow make the rest of the array valid as well but that's very much not the case as you can see if I take this and then I take this and put it in one subarray and actually to improve the example let's say I put this in a subarray and then I took these and actually skip an element I don't go in sorted order then the other subarray would look like this and this doesn't work and the reason is by us choosing an element further to the right now this subarray has to choose an element even further to the left so we kind of just expanded both of the arrays by condensing one array over here we also condense the other array as well when I say condense I mean condense the AR the range of values so all we really have to do is just look at every size K subarray compare the end points take the difference we can always take the right element and subtract the left element because we're guaranteed that this is in sorted order we check that that is less than or equal to K if it is we throw it into a subarray if it's not we can return an empty array that's what we're told to do if it's not possible for us to build this result so by doing it this way it looks like the soltion is Big O of n time but don't forget we actually had to sort the array in the first place normally that is Big O of n log n now let's code it up so I'm going to declare well I guess first let's just sort the input array before we forget let's sort that now I'm going to declare the output it's going to be an empty array initially we know that's what we want to ultimately return and then we can start chunking this array into size three subarrays and for the first time I'm going to go like this in Python so we're going to go from the beginning to the end of the array and we're going to increment by three each time so in Python that's what this is doing it's going from here to here not including this this would be out of bounds and it's going to increment I by 3 every single time so now what we check is the end points of the subarray starting at I and it's going to be of size three so what we want to do is take I the Right value is going to be at I + 2 and we're going to subtract from it the left which is I check if it's less than or equal to K or actually let's check if it's greater than K let's do the opposite because if it's greater than K we can then immediately return and if it's not greater than K we can then take our actual logic and place it outside of the if statement I just prefer to generally not Nest my code if I don't have to so that's why I'm doing it like that out here we can create a copy of the subarray going from I to I + 2 in Python that's pretty easy to do start at I go up until I + 2 but this would actually not include I + 2 so we actually want to do I + 3 so this is a copy that's what python is doing a deep copy and we want to append it to the result like this and let's go ahead and run this as you can see on the left it's hella efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. 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/ 🐦 Twitter: https://twitter.com/neetcode1 ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf Problem Link: https://leetcode.com/problems/divide-array-into-arrays-with-max-difference/description/ 0:00 - Read the problem 0:10 - Drawing Explanation 4:38 - Coding Explanation leetcode 2966 #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 the LeetCode problem 2966 using a sorting approach, ensuring the max minus min difference in each subarray is within the given limit K. It covers problem analysis, algorithm design, and Python implementation.

Key Takeaways
  1. Check if the input array can be divided into subarrays of size 3
  2. Sort the input array
  3. Iterate over the sorted array in steps of 3
  4. Check if the max minus min difference in each subarray is within the limit K
  5. Return the divided subarrays if the condition is met
💡 Sorting the input array allows for efficient checking of the max minus min difference in each subarray, ensuring the problem's constraints are met.

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