Maximum Odd Binary Number - Leetcode 2864 - Python

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

Key Takeaways

The video demonstrates how to solve the Maximum Odd Binary Number problem on LeetCode using Python, with a focus on systems design and efficient algorithms.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum odd binary number we're given a binary string s that contains at least a single one and that's going to be pretty important because we want to arrange the bits in such a way that the binary number is as large as it can be and it's also an odd number and as you may know you can't really have an odd number unless you have at least one bit because to make a binary number odd all we have to say is that the least significant bit is going to be one that guarantees that the number is going to be odd because every other significant bit is going to represent an even number for example this is going to represent two this represents four this is eight etc etc that's why we focus on this to make it odd that's pretty much the entire problem so let's take a look at some examples you look at this example 0 1 0 this is the input string that we're given we only have a single one we are forced to put it in this spot and everything else is going to be zero so this is the largest number that we can get and this is what we actually return in the form of a string we don't have to convert this to an integer or anything like that the second example is a bit more interesting here we have two ones so we keep one of them here and then the other one where should we put it we have a choice we can either put it here or we can put it here or we can put it here well we're trying to maximize the result so of course we're going to put it in the most significant spot you can think of additional examples as having more ones and every time we have a choice we always want to fill the ones starting from the left position so if we had additional ones we'd put two of them here and then maybe a zero here and at least one of them is going to go here so conceptually this problem isn't super crazy one thing that we could do is just count the number of ones that we have put one of them here and then the remaining number let's say the count represents how many we have we subtract one from the count and then we take this many however many it happens to be and start filling them in from the left and the way I'm going to do that like the filling in portion modifying a string generally creates a new string so strings are immutable in most languages I'm actually going to use this count to construct a new string and then that's what we're going to return so that's one way I'm going to solve the problem and then I'll show you another way after that so I'm to have a variable to count the number of ones initially it's going to be zero and let's just leave a comment to make this descriptive and then I'm going to go through every character in s and I'm going to say if C that character is equal to one let's go ahead and increment the number of ones now we could easily do this with a built-in function I think we could have just assigned count equal to s. count of one that would have done the exact same thing but I feel like for a problem this easy it almost feels like cheating to use a built-in method like that but I mean if your interviewer allows it in a real interview definitely go ahead and do that now that we have this I want to construct the new string what we know is that there's going to be a portion of ones in the string and then there's going to be some portion of zeros and then at the end it's going to have a one for sure so let's start with that one for sure it's going to end with a one like this now how many ones can we put over here well it's going to depend how many ones we have and since we're already using one of them over here we're going to put count minus one that many ones at the beginning and in Python it's really easy you can actually do it like this so this is the quantity and then we're going to multiply that by the string which is one and this will create that string like this however many count minus one is lastly how many zeros are going to go in here well it depends on the length of the input string so let's let's say we have five ones and we put one of them here and then the remaining four go there well if the length of the input string like here is nine then we want n or the length of the string minus whatever the count happened to be and that's how many zeros we want we can take this quantity and then multiply it whoops by zero and so this is a long formula but it is basically building the string exactly in the form that we want it so let let's go ahead and run this as you can see on the left it works it's pretty efficient but there is another solution actually if you are deeply familiar with the quick sort algorithm specifically the portion of quick sort that is concerned with partitioning the array this algorithm will be trivial for you I talk about this I think in the DSA for beginners course partition is a pretty important algorithm and it's relatively easy Once you understand it so the idea is this suppose we are given a string like this one we're going to have a pointer one pointer let's say I is going to be used to iterate over the array another pointer I'm going to call it left is going to tell us where we should insert the next one so what this partition algorithm is going to do is it's going to take an input array like this one and convert it like this it's going to put all the ones at the beginning and then all the zeros at the end now we could achieve this if we wanted to via sort but sort is something that runs typically in N log end time but partitioning is more efficient it's going to run in linear time and that's possible because we know everything in the input is either a one or a zero so we don't have to worry about like a continuous range of values once we have done this this is not what we want right this is not the solution we want to take at least one bit and put it here which one of these are we going to take of course the least significant one we're going to take this and swap it with this first we partition and then we perform that last swap and then we're good let me quickly show you how this algorithm is going to run starting here we see it's a zero okay so then we ignore it we move our ey pointer over here left still stays over here left tells us where we're going to move the one to now we see a one we're going to swap the values in these two indexes so this is going to become a zero this is going to become a one now our ey pointer is going to be over here and our left pointer is going to be over here in the second spot because that's where the next one is going to go this is a zero so move I over here this is a one we're going to put one over there we're kind of running out of space and then the zero is going to end up over here and now left is going to be in this spot let me kind of use a different color I guess to make this easier but left is here I is here this is a zero don't worry about it I is here now one swap it over here here and then this becomes zero and then here we have a one so if you were to redraw this in a cleaner way you'd see that we've ended up with the string 111 0 0 0 and our ey pointer first of all would be out of bounds so we are going to stop at that point but our left pointer would be over here so it's going to be right after the last one it's possible that the entire input could have been all ones in that case our left pointer would be over here it would be out of bounds so always we're going to take left minus one in the other case it would be here left is here left minus one is going to tell us this bit should be swapped with the last bit and then once we perform that we will pretty much have our result so the only thing I didn't talk about in the drawing explanation a second ago is that strings are immutable how are we going to perform swaps in a string well we're actually going to clone the string and put it in the form of an array so in pyth Pyon you can do that like this it's called list comprehension we're taking every character adding it to a list and then setting that equal to S so with an array like this it's easy to swap now we'll declare our left pointer it will initially be at the beginning at zero and then we'll have an i pointer iterating over the length of s and then we'll check for every character if it's equal to one let's perform a swap in Python that's easy we don't even need a temporary variable we can do it in a single line like this s of I and S of left is going to be set to S of left and S of I so just reversing the order of these two to swap them and let's make sure to increment our left pointer whenever we do that now at the end what do we do well we want to make sure that we swap left minus one with the value at the end of the list length of s minus one and since we're swapping them we have to put both of them on the left side and then both of them on the right side so let's copy that and put it here so this is just performing a swap between these two elements and after we're done with that we can return but we can't return s it's technically an array of strings and we want to return a string so we can join all of the strings within this list by doing this this is the delimiter an empty string and so dot join with everything in s this will create a string and then that's what we want to return so let's go ahead and run this and as you can see on the left it works it's also the same efficiency but this time it just ran quicker on leak code if you're preparing for coding interviews check out NE code iio 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/maximum-odd-binary-number/description/ 0:00 - Read the problem 0:27 - Drawing Explanation 2:29 - Coding Explanation 4:36 - Drawing Explanation 7:44 - Coding Explanation leetcode 2864 #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 the Maximum Odd Binary Number problem on LeetCode using Python, with a focus on systems design and efficient algorithms. The problem requires maximizing the binary number represented by a given binary string, with the constraint that the number must be odd. The solution involves using a partition algorithm and a two-pointer technique to efficiently sort the input string and construct the maximum odd binary number.

Key Takeaways
  1. Count the number of 1s in the string
  2. Determine the number of 1s to place at the beginning of the new string
  3. Construct the new string by placing the determined number of 1s at the beginning, followed by the remaining 1s, and ending with a 1
  4. Use a partition algorithm to sort the input string in linear time
  5. Swap values in the input string to separate ones from zeros
  6. Implement a two-pointer technique to find the maximum odd binary number
  7. Handle edge cases where the input string is all ones or has a length of one
💡 The key insight is to use a partition algorithm and a two-pointer technique to efficiently sort the input string and construct the maximum odd binary number, while ensuring that the resulting number is odd.

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:27 Drawing Explanation
2:29 Coding Explanation
4:36 Drawing Explanation
7:44 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →