Partition Array According to Given Pivot - Leetcode 2161 - Python

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

Key Takeaways

The video demonstrates how to solve the Leetcode 2161 problem, Partition Array According to Given Pivot, using Python, with a focus on systems design and intermediate-level coding techniques, including array manipulation, partitioning, and time and space complexity analysis.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem partition array according to given pivot oh boy am I excited to solve this very interesting problem today the idea is we are given an in paray of numbers and you know what I'm just not even going to bother with this explanation I'll just run through the examples so we're given an in paray of numbers in this example it could look like this we're also given a parameter which is the pivot in this case the pivot is 10 so what we want to do is partition the array so we want the array to look something like this where we have all the pivot values however many there are in this case it looks like there's two occurrences of the pivot value I don't think that's guaranteed there could have been maybe none of them or there could have been one of them or maybe more than two but either way we want all of those right in the middle or let's put it in the more General way we want the pivot like this and then we want the elements that are less than the pivot to be on the left side and we want the values that are greater than the pivot to be on the right side so when they say we're partitioning the array it is actually a pretty straightforward partition what about the relative order of these elements and these elements do they need to be in sorted order no because if we were doing that well we would just be sorting the array we wouldn't be calling this a partition so then can these elements be in any order what exactly do we want well the best way to show you is just to kind of go through this example so I'll try to color code it so the pivots are here and here and I'm just going to scan through this from left to right I'm going to circle all of the elements that are less than 10 so here we have nine here we have five here we have three so the order that these elements are going to be placed here is going to be the same order that they appear in the array meaning this is one this is two this is three fantastic similarly the elements that are greater than the pivot I see one here and I see another one here so one 2 they're going to be placed in that same order on this side so the output is going to be 95 and I think three and then we're going to have two 10 and then we're going to have 12 and then we're going to have 14 so these are the pivots these are the values greater in the same relative order that they appear in the input and these are the elements less so how do we code this up I mean one very trivial way would just be to scan through the input separate the elements into three different arrays I'm pretty sure you know what the three different arrays are one array for the elements less than one array for the elements greater and one array for the elements that are equal to the pivot and then at the end we just combine the arrays together could do that with a loop could do that with some built-in functions or some other ways python has a very easy way to do this so that's pretty much what we're going to do and the fact that we're using extra arrays means the space complexity is going to be linear as well as the time complexity let's code this up so I'm going to have an array for the elements that are less I'm going to have an array for the pivot elements I'll call that P to not have like a name conflict with that and then I'll have greater elements here then I just go through every number I have a few if statements is it less than the pivot if so we do this if it's uh greater than the pivot then we add it to the greater array otherwise it must be equal to the pivot in which case we add it to the pivot array at the end we can combine the two arrays python makes it easy for us so this kind of follows like the drawing that I kind of had earlier less plus P plus the greater array so this is basically concatenating those three arrays together and then we're returning that I'll give this a run you can see it works it's pretty efficient there is a way for us to solve this problem without having extra memory well we are going to need an array for the output we actually can't do this in place place your first thought might be like can we do the partition in place and it's not that we can't do a partition in place it's that then we would not be able to preserve the relative order of elements how do I know that because I have a pretty good understanding of DSA fundamentals let me show you what I mean quick sort I have a lesson for it on a neat code iio very fundamental algorithm it involves partitioning in a very similar way that we are in today's problem and one thing about quicksort is that it is not a stable sorting algorithm and that basically means that we do not preserve the relative order of elements as you know this States so yeah I mean I'm not saying you have to learn these fundamentals from n code. but I definitely I think it's worth your time to have a very very solid understanding of these fundamentals I think n Kio is a decent resource for that and uh I mean there's some other courses as as well that I think will definitely be worth your time especially if you like python like all these python tips and tricks can be learned in this python for coding interviews course has a lot of interactive lessons and whatnot uh but now to kind of solve this problem without using any additional space it's going to be similar to what we did here I guess one way to do it would be two pointers so what I'm going to do is like based on how many elements we have in the input I'm going to allocate an array like this one like of the same size so I have the space for all the elements we could just fill it in with all zeros initially and then I'm going to have two pointers I could call them I and J and so what those two pointers are going to do is it's going to start here and here I'm basically going to iterate from left to right and right to left at the same time you could consider this a single pass algorithm but I mean technically it's double passing the fact that we combine it into a single Loop doesn't really change the fact that we're iterating over the input twice uh but anyways what we're going to do is from left to right we're going to fill in the values that are less than so anytime I see a value from left to right that's less than so one 2 3 I'm going to add those values here a boom uh boom and boom so in terms of this array we're also going to be keeping track of pointers so I could call that let's say I2 that tells me like the insertion point and then eventually that pointer is going to end up over here and I'm going to have maybe J2 as well doing something similar so anytime I see a number that is bigger than 10 so as I iterate my J pointer from right to left I'm going to see 14 and I'm going to see 12 and I'm going to add those like this 14 and 12 so okay so then my J2 pointer will stop here and so however much space is left here in this case there's going to be two spaces I'm then just going to fill all of these in with the pivot element which is 10 so 10 and 10 so nothing super fancy here knowing this we can code this up with allocating only a single array okay so I just initialized a few pointers I and J are going to be at the beginning and the end of the array same with I2 and J2 these are going to tell us like the insertion positions of the result array here that we've declared and we've created it to be of the same size as the input array that's what we are going to end up returning and so then the first part can just be like this while I is less than the input even though I have this as my condition inside of the loop we're actually going to be manipulating both I and J we just know that we only have to check one of these conditions we just have to make sure this is less than that or we could make sure that J is greater than or equal to zero as long as one of those pointers is in bounds we are good because we then know that the other pointer must also be in bounds because they're iterating over the exact same array just in reverse order anyways you'll see what I mean here we're going to check if the number at index I is less than in the pivot in which case then we will say in the result not at index I but at I2 we're going to set this number and then we will increment I2 otherwise maybe the number is greater than the pivot in which case then we will assign it to J2 uh this part we're actually going to be using the J pointer for that so let me check if the number at J starting from the right side cuz the order that we process these elements and place them in the output is going to be important so the number at J if that's the case then we do this and then we can decrement our J2 pointer now either way regardless of which of these executes maybe both will execute maybe only one will maybe neither either way we are always going to be shifting our I and our J pointers so we can do this I and J are going to be I + one and J minus one so that's the first phase of the algorithm the last phase is to actually get the pivot elements however many there happened to be could do that many ways you could do that like this while I2 is less than or equal to J2 we could do this kind of like the two-pointer approach take the number for I 2's position and j2's position and assign it to the pivot element then update both of the pointers like this I2 + 1 J2 - one so I do believe that this will work let's give it a quick run yep and as you can see here it does work and funny enough even the memory efficiency is actually lower than the previous solution I'm not entirely sure why that is I can understand a little bit why the runtime would be lower but anyways if you found this helpful check out n code iio for a lot more 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/ 🐦 Twitter: https://twitter.com/neetcode1 ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf Problem Link: https://leetcode.com/problems/partition-array-according-to-given-pivot/description/ 0:00 - Read the problem 0:30 - Drawing Explanation 3:30 - Coding Explanation 4:50 - Drawing Explanation 2 7:30 - Coding Explanation 2 leetcode 2161 #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 2161 problem, Partition Array According to Given Pivot, using Python, with a focus on systems design and intermediate-level coding techniques. The problem requires partitioning an array around a given pivot element, while preserving the relative order of elements. The video provides a step-by-step solution, including code implementation and explanation.

Key Takeaways
  1. Scan through the input array and separate elements into three arrays: less than the pivot, equal to the pivot, and greater than the pivot
  2. Combine the three arrays into a single output array
  3. Use two pointers to fill in values less than pivot in a single array
  4. Fill in values greater than pivot in the same array
  5. Fill remaining space with pivot element
  6. Initialize pointers I and J at the beginning and end of the array
  7. Initialize two pointers I2 and J2 to keep track of insertion positions
  8. Fill in values less than pivot from left to right
  9. Fill in values greater than pivot from right to left
💡 The two-pointer technique can be used to solve the problem in a single pass, without using extra memory, and while preserving the relative order of elements.

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 (5)

Read the problem
0:30 Drawing Explanation
3:30 Coding Explanation
4:50 Drawing Explanation 2
7:30 Coding Explanation 2
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →