Sqrt(x) - Leetcode 69 - Python

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

Key Takeaways

The video solves the LeetCode problem Sqrt(x) using a binary search approach in Python, achieving a time complexity of log n, and provides a detailed explanation of the problem and the solution.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problems square root of x we're given a non-negative integer X and we want to return the square root of x rounded down to the nearest integer so for example the number four what's the square root it's 2 2 squared is equal to 4. what about 8 well it doesn't have like an integer value square root it's something like 2.82 you take that number and square it you get eight but in this case we would want to still return the value 2 because it's the square root rounded down so how can we solve this problem well given an integer let's say x equals 7 how do we find the square root we know it's going to be two point something something and we're going to round that down to two but how would we determine that well the brute force would be to just iterate four in range let's say starting at 1 and going all the way up until the x value which is in this case seven we're going to Brute Force this and find the square root we know the square root is going to be less than 7 and probably greater than or equal to 1 though it probably wouldn't hurt to start at zero because in this case our input value X could be zero and the square root of zero I guess is also zero but that's a minor detail let's say we start at one we square one that's equal to one is that the square root well let's try the next value two two squared is equal to four is that the square root of 7 well let's keep trying we get to 3 now 3 squared is equal to nine so we went too high we are now greater than seven so three is not going to be the square root because we know we're going to round down anyway the last value that we saw that did not go over was two two squared was equal to 4 so so 2 is going to be the square root of 7 rounded down now the downside with this solution is that it is a Brute Force solution it's actually not Big O of n even though it kind of looks like it because we know that the loop is going to terminate before we get to n it's going to terminate by the time we reach the value which is the square root of n which makes sense because let's say you know in terms of n n is the input value X we know we're going to stop by the time we get to the value which is the square root of n because we know that value squared is going to be equal to n so in reality this for Loop is going to run in Big O of the square root of n time but we can actually do even better than this as well because we can use a binary search approach which is going to be log n now before I explain it you might be wondering how do we know that this is more efficient than the square root of n because it's not super obvious well I won't give you like a super long mathematical proof but intuitively we can think about this in terms of big n values what is the square root of n if n is equal to a million well the square root of a million is going to be a thousand well what is log base 2 of a million well it's going to be an integer value I don't know the exact value but I know it's in the magnitude of like 20 or something maybe 21 or 19 something like that but clearly that's a big difference square root of a million is a thousand log base 2 of a million is 20. you can clearly see that log grows a lot slower so log is going to be much more efficient if we can achieve a solution like this which we can using binary search we know our search space is going to be between let's say zero all the way up until X it's a range of values we're going to calculate the Midway point so 0 plus x divided by 2 is going to give us some Midway value we're going to check M squared is it greater than x because if it's greater we know that this can't be the square root of x and we need to now decrease our search space so if this is true what we would say then is we're going to cut our search space in half and now start searching between 0 and M minus one whatever that previous M value happened to be and we're going to continue doing this suppose next time we calculate the mid value and mid squared is actually less than x then then we would do the opposite we would increase our search space and then search on the values on the right side of that and we would keep doing this but the difference here is that when our M squared value is less than x this is going to be a candidate for our result because we basically want the largest value the largest M value where this is true that's assuming though that the square root is going to be a non-integer value it's also possible that the M squared value actually is equal to X if this was the case suppose like an example like this where 2 squared is equal to 4. if this is the case we basically return immediately so that's the idea of how we're going to solve this with binary search in login time it's going to make even more sense when I show you the code right now so first things first let's initialize our search base left is going to be set to zero right is going to be set to X we're also going to initialize our result it doesn't really matter what value we give it I'm just going to give it a zero and then we're going to run our binary search while left is less than or equal to right while our pointers haven't crossed each other we're going to continue searching you could say m is equal to left plus right divided by 2 but that could possibly overflow a better way to do it is to say left plus the halfway distance between right minus left so taking right minus left and dividing that by two this also gives us the same value as before it's a different math equation for the same value the only difference is that this will never overflow it's a minor detail but I think it's worth knowing next we're going to run our equalities so we're going to check is M squared you can square it like this in Python is it greater than x what happens if it's greater than x then we're going to decrease our search space we're going to say right is equal to M minus 1. we're going to search on the left side else if the opposite if M squared is less than x then we're going to search on the right side we're going to say left is equal to M plus 1. but also if this is the case we possibly want to set our result to this value because this could be the result this mid value could be the result so we're going to set it like that now the third case and this might not always execute is that M squared is equal to X we can just use an else condition for that and then we would want to immediately return the mid value because we found the exact square root otherwise we know that the loop is eventually going to terminate and by the time it terminates our result will be set to basically the gray latest mid value that was less than x well the greatest value that we could square that is less than x which is basically the square root rounded down so in that case we would want to return the result outside of the loop just like this so now let's run the code to make sure that it works as you can see it does it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neco.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews Problem Link: https://neetcode.io/problems/sqrtx 0:00 - Read the problem 0:30 - Drawing Explanation 5:50 - Coding Explanation leetcode 69 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 58 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
 ▶ 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 Sqrt(x) problem on LeetCode using a binary search approach in Python, and explains the problem and the solution in detail.

Key Takeaways
  1. Read and understand the problem
  2. Initialize the search space
  3. Implement the binary search algorithm
  4. Handle the cases where M squared is greater than, less than, or equal to X
  5. Return the result
💡 Using a binary search approach can reduce the time complexity of the solution from O(sqrt(n)) to O(log n)

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