Here is the Python implementation of the above approach:
### Complexity Analysis
Time complexity: O(log x)
- This is due to the binary search algorithm, which cuts the search space in half with each iteration.
Space complexity: O(1)
- We are using a constant amount of space regardless of the input size. Only a few integer variables are used.
This solution efficiently finds the square root of a non-negative integer x rounded down to the nearest integer using binary search.
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
left, right = 2, x // 2
ans = 0
while left <= right:
mid = (left + right) // 2
num = mid * mid
if num > x:
right = mid - 1
else:
ans = mid
left = mid + 1
return ans
### Complexity Analysis
Time complexity: O(log x)
- This is due to the binary search algorithm, which cuts the search space in half with each iteration.
Space complexity: O(1)
- We are using a constant amount of space regardless of the input size. Only a few integer variables are used.
This solution efficiently finds the square root of a non-negative integer x rounded down to the nearest integer using binary search.
👍4
In python, What does the join () method do ?
Anonymous Quiz
0%
Splits a string into a list of substrings based on a delimiter
59%
Concatenates strings from an iterable, with a specified separator between each element
9%
Returns the index of the first occurrence of a substring in a string
31%
Concatenates lists into python dictionary
👍2🔥1🤯1
Which topic should we cover next?
Anonymous Poll
32%
sliding window
50%
two pointer
9%
prefix sum
9%
another topic??
153. Find Minimum in Rotated Sorted Array
#leet_code_Q10 #Medium #binary_search #Q_153
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
#leet_code_Q10 #Medium #binary_search #Q_153
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
Leetcode with dani
153. Find Minimum in Rotated Sorted Array #leet_code_Q10 #Medium #binary_search #Q_153 Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become: [4,5,6,7,0,1,2] if…
class Solution:
def findMin(self, nums: List[int]) -> int:
left = 0
right = len(nums)-1
while(left<=right):
mid = (left+right)//2
if nums[mid] <= nums[mid-1]:
return nums[mid]
elif nums[mid] >= nums[left] and nums[left] >nums[left-1]:
left = mid + 1
else:
right = mid -1
👍3
If a coin rolls around a circular path whose circumference is twice the circumference of the coin, how many full rotations does the coin complete by the time it returns to its starting point?
Anonymous Quiz
20%
1
37%
2
20%
3
22%
4
👍4⚡2🤯2
Leetcode with dani
If a coin rolls around a circular path whose circumference is twice the circumference of the coin, how many full rotations does the coin complete by the time it returns to its starting point?
Don't try to answer at first glance. it's more challenging than it seems
Leetcode with dani
Which topic should we cover next?
based on this poll we will start doing two pointer and sliding window respectively
344. Reverse String
#Topics #twopointers #strings
Write a function that reverses a string. The input string is given as an array of characters s
You must do this by modifying the input array in-place with O(1) extra memory
Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
link
#Topics #twopointers #strings
Write a function that reverses a string. The input string is given as an array of characters s
You must do this by modifying the input array in-place with O(1) extra memory
Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
link
LeetCode
Reverse String - LeetCode
Can you solve this real interview question? Reverse String - Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place [https://en.wikipedia.org/wiki/In-place_algorithm]…
You must do this by modifying the input array in-place [https://en.wikipedia.org/wiki/In-place_algorithm]…
👍3
#leet_code_Q_12 #easy #two_pointer #Q_202 202.Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Example 2:
Input: n = 2
Output: false
Constraints:
1 <= n <= 231 - 1
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Example 2:
Input: n = 2
Output: false
Constraints:
1 <= n <= 231 - 1
Leetcode with dani
344. Reverse String #Topics #twopointers #strings Write a function that reverses a string. The input string is given as an array of characters s You must do this by modifying the input array in-place with O(1) extra memory Example 1: Input:…
class Solution:
def reverseString(self, s: List[str]) -> None:
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
How do you convert a tuple into a list in Python?
a) tuple.toList()
b) list(tuple)
c) tuple.list()
a) tuple.toList()
b) list(tuple)
c) tuple.list()
What will be the output of the following code?
print('Hello' * 3)
print('Hello' * 3)
Anonymous Quiz
69%
a) HelloHelloHello
8%
b) HelloHelloHelloHello
9%
c) Hello, Hello, Hello
14%
D) Error
Leetcode with dani
https://youtu.be/jM2dhDPYMQM?si=WG3yrnoQvRyEvnkm
i recommend this video for those who want to learn sliding window algorithm , we will be working on this algorithm in the coming days
#leet_code_Q_13 #easy #Sliding_window #Q_219 219. Contains Duplicate II
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
👍2❤🔥1
out of topic I just watched an amazing video that dives into the theory of relativity and how time works. ⏳
It’s fascinating how scientists always talk about light, and I used to think they had a beef with speed of light 😂 But now I understand why speed of light is so special and its profound connection to time. https://youtu.be/5BBHEZFearI?si=dGWI303LG9XXgQYh
It’s fascinating how scientists always talk about light, and I used to think they had a beef with speed of light 😂 But now I understand why speed of light is so special and its profound connection to time. https://youtu.be/5BBHEZFearI?si=dGWI303LG9XXgQYh
YouTube
Einstein’s Special Relativity Theory | Does Time really Slow down
What is Time dilation? How speed of light affects space time? Let’s understand Time dilation with Einstein’s Special relativity theory.
@Klonusk
To support on patreon (video noscript with high-res explainer art works) : https://patreon.com/Klonusk975…
@Klonusk
To support on patreon (video noscript with high-res explainer art works) : https://patreon.com/Klonusk975…
👍5👀1