Leetcode Flashcards
- Minimum Add to Make Parentheses Valid
Medium
2363
138
Add to List
Share
A parentheses string is valid if and only if:
It is the empty string,
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.
You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
For example, if s = “()))”, you can insert an opening parenthesis to be “(()))” or a closing parenthesis to be “())))”.
Return the minimum number of moves required to make s valid.
Example 1:
Input: s = “())”
Output: 1
Example 2:
Input: s = “(((“
Output: 3
Constraints:
1 <= s.length <= 1000
s[i] is either ‘(‘ or ‘)’.
class Solution: def minAddToMakeValid(self, s: str) -\> int: stack = []
for par in s:
if len(stack) == 0:
stack.append(par)
else:
if par == “(“:
stack.append(par)
else:
last = stack.pop()
if last != “(“:
stack.append(last)
stack.append(par)
return len(stack)
Whenever you have a problem where you need to generate all combinations/permutations of some group of letters/numbers, what should you be thinking about?
Backtracking or brute force if the input is very small.
- Dot Product of Two Sparse Vectors
Medium
759
97
Add to List
Share
Given two sparse vectors, compute their dot product.
Implement class SparseVector:
SparseVector(nums) Initializes the object with the vector nums
dotProduct(vec) Compute the dot product between the instance of SparseVector and vec
A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.
Follow up: What if only one of the vectors is sparse?
Example 1:
Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8
Example 2:
Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0
Example 3:
Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6
Constraints:
n == nums1.length == nums2.length
1 <= n <= 10^5
0 <= nums1[i], nums2[i] <= 100
class SparseVector:
def __init__(self, nums: List[int]):
self.nums = nums
self.non_zero = []
for i , num in enumerate(nums):
if num !=0:
self.non_zero.append(i)
# Return the dotProduct of two sparse vectors def dotProduct(self, vec: 'SparseVector') -\> int:
product = 0
indexes = set(vec.non_zero).intersection(self.non_zero)
for i in indexes:
product += vec.nums[i]*self.nums[i]
return product
Your SparseVector object will be instantiated and called as such: # v1 = SparseVector(nums1) # v2 = SparseVector(nums2) # ans = v1.dotProduct(v2)
- Find Peak Element
Medium
5662
3625
Add to List
Share
A peak element is an element that is strictly greater than its neighbors.
Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
Constraints:
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
class Solution(object):
def findPeakElement(self, nums):
l, r = 0, len(nums)-1
while l <= r:
mid = l + (r-l)//2
if (mid-1<0 or nums[mid]>nums[mid-1]) and (mid+1>=len(nums) or nums[mid]>nums[mid+1]):
return mid
elif mid-1>=0 and nums[mid] the right-most element is the peak
2. always decreasing -> the left-most element is the peak
3. first increasing then decreasing -> the pivot point is the peak
4. first decreasing then increasing -> the left-most element is the peak
Therefore, we can find the peak only on its right elements( cut the array to half)
The same idea applies to that an element(not the left-most one) is smaller than its left neighbor.
Conditions:
- array length is 1 -> return the only index
- array length is 2 -> return the bigger number’s index
- array length is bigger than 2 ->
(1) find mid, compare it with its left and right neighbors
(2) return mid if nums[mid] greater than both neighbors
(3) take the right half array if nums[mid] smaller than right neighbor
(4) otherwise, take the left half
Run time: O(logn)
Memory: constant
Test cases:
[1]
[1,2]
[2,1]
[1,2,3]
[3,2,1]
[2,1,3]
def findPeakElement(self, nums): left = 0 right = len(nums)-1
# handle condition 3
while left < right-1:
mid = (left+right)/2
if nums[mid] > nums[mid+1] and nums[mid] > nums[mid-1]:
return mid
if nums[mid] < nums[mid+1]:
left = mid+1
else:
right = mid-1
#handle condition 1 and 2 return left if nums[left] \>= nums[right] else right
Reverse Linked List
Easy
11168
193
Add to List
Share
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000
Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -\> Optional[ListNode]: if not head: return head pointer = head
while pointer.next != None: next1 = pointer.next next2 = pointer.next.next next1.next = head head = next1 pointer.next = next2 # final swap #next1 = pointer.next #next1.next = head #head = next1 #pointer.next = None
return head
- Letter Combinations of a Phone Number
DONE with Bruce force or backtracking
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
Example 2:
Input: digits = “”
Output: []
Example 3:
Input: digits = “2”
Output: [“a”,”b”,”c”]
class Solution: def letterCombinations(self, digits: str) -\> List[str]: # If the input is empty, immediately return an empty answer array if len(digits) == 0: return []
# Map all the digits to their corresponding letters
letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def backtrack(index, path):
# If the path is the same length as digits, we have a complete combination
if len(path) == len(digits):
combinations.append("".join(path))
return # Backtrack
# Get the letters that the current digit maps to, and loop through them
possible_letters = letters[digits[index]]
for letter in possible_letters:
# Add the letter to our current path
path.append(letter)
# Move on to the next digit
backtrack(index + 1, path)
# Backtrack by removing the letter before moving onto the next
path.pop()
# Initiate backtracking with an empty path and starting index of 0
combinations = []
backtrack(0, [])
return combinations
- Longest Consecutive Sequence
Medium
https://leetcode.com/problems/longest-consecutive-sequence/
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
Intuition
It turns out that our initial brute force solution was on the right track, but missing a few optimizations necessary to reach O(n)O(n) time complexity.
Algorithm
This optimized algorithm contains only two changes from the brute force approach: the numbers are stored in a HashSet (or Set, in Python) to allow O(1)O(1) lookups, and we only attempt to build sequences from numbers that are not already part of a longer sequence. This is accomplished by first ensuring that the number that would immediately precede the current number in a sequence is not present, as that number would necessarily be part of a longer sequence.
class Solution: def longestConsecutive(self, nums): longest\_streak = 0 num\_set = set(nums)
for num in num_set:
if num - 1 not in num_set:
current_num = num
current_streak = 1
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak
- Group Shifted Strings
Medium
1263
231
Add to List
Share
We can shift a string by shifting each of its letters to its successive letter.
For example, “abc” can be shifted to be “bcd”.
We can keep shifting the string to form a sequence.
For example, we can keep shifting “abc” to form the sequence: “abc” -> “bcd” -> … -> “xyz”.
Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.
Example 1:
Input: strings = [“abc”,”bcd”,”acef”,”xyz”,”az”,”ba”,”a”,”z”]
Output: [[“acef”],[“a”,”z”],[“abc”,”bcd”,”xyz”],[“az”,”ba”]]
Example 2:
Input: strings = [“a”]
Output: [[“a”]]
Constraints:
1 <= strings.length <= 200
1 <= strings[i].length <= 50
strings[i] consists of lowercase English letters.
class Solution:
def groupStrings(self, strings: List[str]) -\> List[List[str]]:
key\_list = {}
for i,string in enumerate(strings):
key=[]
first = ord(string[0])
for s in string[1:]:
key.append((ord(s) -first)%26)
key = tuple(key)
key_list[key] = key_list.get(key, []) + [string]
return list(key_list.values())
How can you turn an inflow of characters into a cardinal number i.e.
you can do
for c in s:
if c.isdigit():
num = num*10 + int(c)
i.e you multiply by 10 the current number and then add digits
- Lowest Common Ancestor of a Binary Tree
Medium
9218270Add to ListShare
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2 Output: 1
Constraints:
The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the tree.
Recursive
class Solution:
def \_\_init\_\_(self): # Variable to store LCA node. self.ans = None
def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ def recurse\_tree(current\_node):
If reached the end of a branch, return False.
if not current_node:
return False
Left Recursion
left = recurse_tree(current_node.left)
Right Recursion
right = recurse_tree(current_node.right)
If the current node is one of p or q
mid = current_node == p or current_node == q
If any two of the three flags left, right or mid become True.
if mid + left + right >= 2:
self.ans = current_node
Return True if either of the three bool values is True.
return mid or left or right
Traverse the tree
recurse_tree(root)
return self.ans
Iterative
- Simplify Path
Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.
In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.
The canonical path should have the following format:
The path starts with a single slash ‘/’.
Any two directories are separated by a single slash ‘/’.
The path does not end with a trailing ‘/’.
The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period ‘.’ or double period ‘..’)
Return the simplified canonical path.
Example 1:
Input: path = “/home/”
Output: “/home”
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:
Input: path = “/../”
Output: “/”
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:
Input: path = “/home//foo/”
Output: “/home/foo”
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
class Solution:
def simplifyPath(self, path: str) -> str:
split_path = path.split(“/”)
stack= []
string=””
for i,s in enumerate(path):
if s not in [”/”]:
string = string + s
if s == “/” or i == len(path)-1:
if string in [”.”, “”]:
string = “”
elif string ==”..”:
string = “”
if stack:
stack.pop()
else:
stack.append(string)
string = “”
return “/” + “/”.join(stack)
- Custom Sort String
Medium
1921
280
Add to List
Share
You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously.
Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.
Return any permutation of s that satisfies this property.
Example 1:
Input: order = “cba”, s = “abcd”
Output: “cbad”
Explanation:
“a”, “b”, “c” appear in order, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in order, it can be at any position in the returned string. “dcba”, “cdba”, “cbda” are also valid outputs.
Example 2:
Input: order = “cbafg”, s = “abcd”
Output: “cbad”
class Solution:
def customSortString(self, order: str, s: str) -\> str:
freq\_char = {}
for i in s:
freq\_char[i] = freq\_char.get(i,0) + 1
s_return = []
for i in order:
if i in freq_char.keys():
s_return.append(i*freq_char[i])
freq_char[i] = 0
del freq_char[i]
for i in freq_char.keys():
s_return.append(i*freq_char[i])
return ““.join(s_return)
leetcode 325
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.
Example 1:
Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
Example 2:
Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -\> int:
cum\_sum = 0
sum\_index = {0:-1}
max\_lenght = 0
for i, num in enumerate(nums):
cum_sum += num
if cum_sum not in sum_index.keys():
sum_index[cum_sum] = i
if (cum_sum - k) in sum_index.keys():
max_lenght = max(max_lenght, i - sum_index[cum_sum - k])
return max_lenght
- Next Permutation
Medium
9197
3103
Add to List
Share
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]
def nextPermutation(self, nums):
i = j = len(nums)-1
while i > 0 and nums[i-1] >= nums[i]:
i -= 1
if i == 0: # nums are in descending order
nums.reverse()
return
k = i - 1 # find the last “ascending” position
while nums[j] <= nums[k]:
j -= 1
nums[k], nums[j] = nums[j], nums[k]
l, r = k+1, len(nums)-1 # reverse the second part
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l +=1 ; r -= 1
Next Permutation
Medium
9296
3135
Add to List
Share
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]
Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 100
class Solution:
def reverse(self, s): i = 0 j = len(s) -1 while i None:
”””
Do not return anything, modify nums in-place instead.
“””
# To find next permutations, we’ll start from the end
i = j = len(nums)-1
# First we’ll find the first non-increasing element starting from the end
while i > 0 and nums[i-1] >= nums[i]:
i -= 1
print(i)
# After completion of the first loop, there will be two cases
# 1. Our i becomes zero (This will happen if the given array is sorted decreasingly). In this case, we’ll simply reverse the sequence and will return
if i == 0:
nums.reverse()
return
# 2. If it’s not zero then we’ll find the first number grater then nums[i-1] starting from end
while nums[j] <= nums[i-1]:
j -= 1
# Now out pointer is pointing at two different positions
# i. first non-assending number from end
# j. first number greater than nums[i-1]
# We'll swap these two numbers nums[i-1], nums[j] = nums[j], nums[i-1]
# We'll reverse a sequence strating from i to end # nums[i:]= nums[len(nums)-1:i-1:-1] nums[i:] = self.reverse(nums[i:]) # We don't need to return anything as we've modified nums in-place
Intersection of Two Linked Lists
Easy
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge:
The inputs to the judge are given as follows (your program is not given these inputs):
intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
listA - The first linked list.
listB - The second linked list.
skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.
The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at ‘8’
Explanation: The intersected node’s value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2:
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at ‘2’
Explanation: The intersected node’s value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, x): # self.val = x # self.next = None
class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -\> Optional[ListNode]: visited\_a = set() pointer = headA while pointer != None: visited\_a.add(pointer) pointer = pointer.next pointer = headB while pointer != None: if pointer in visited\_a: return pointer pointer = pointer.next
return None
Remove Nth Node From End of List
Medium
9350
441
Add to List
Share
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
Constraints:
The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -\> Optional[ListNode]: right\_pointer = head left\_pointer = head for i in range(n): right\_pointer = right\_pointer.next
if right_pointer == None:
head= left_pointer.next
return head
while right_pointer.next != None:
right_pointer = right_pointer.next
left_pointer = left_pointer.next
destination= left_pointer.next.next
left_pointer.next = destination
return head
- Continuous Subarray Sum
Medium
1688
233
Add to List
Share
Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.
Example 1:
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13
Output: false
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -\> bool:
prefix\_sum = {0 : -1}
current\_sum = 0
for i, num in enumerate(nums):
current_sum = (current_sum+num)%k
if current_sum in prefix_sum :
if i - prefix_sum[current_sum] > 1:
return True
else:
prefix_sum[current_sum] = i
return False
d = dict() # d[0] = -1 # sums = 0
for i in range(len(nums)): # sums+=nums[i] # if(k!=0): # sums = sums%k # if(sums in d): # if(i-d[sums]\>1): # return(True) # else: # d[sums] = i
return(False)
- Daily Temperatures
Medium
6663
155
Add to List
Share
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
class Solution: def dailyTemperatures(self, temperatures: List[int]) -\> List[int]: if len(temperatures) ==1: return [0]
answer = [0] * len(temperatures)
stack = [len(temperatures)-1]
for i in range(len(temperatures)-2,-1,-1):
while len(stack)>0:
current = stack.pop()
if temperatures[i] < temperatures[current]:
answer[i] = current-i
stack.append(current)
break
stack.append(i)
return answer
- Decode String
https: //leetcode.com/problems/decode-string/
Medium
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
Example 1:
Input: s = “3[a]2[bc]” Output: “aaabcbc”
Example 2:
Input: s = “3[a2[c]]” Output: “accaccacc”
Example 3:
Input: s = “2[abc]3[cd]ef” Output: “abcabccdcdcdef”
Constraints:
1 <= s.length <= 30
s consists of lowercase English letters, digits, and square brackets ‘[]’.
s is guaranteed to be a valid input.
All the integers in s are in the range [1, 300].
class Solution(object):
def decodeString(self, s):
stack = []; curNum = 0; curString = ‘’
for c in s:
if c == ‘[’:
stack.append(curString)
stack.append(curNum)
curString = ‘’
curNum = 0
elif c == ‘]’:
num = stack.pop()
prevString = stack.pop()
curString = prevString + num*curString
elif c.isdigit():
curNum = curNum*10 + int(c)
else:
curString += c
return curString
Maximum Size Subarray Sum Equals k
Medium
Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.
Example 1:
Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
Example 2:
Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.
Constraints:
1 <= nums.length <= 2 * 105
- 104 <= nums[i] <= 104
- 109 <= k <= 109
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -\> int:
cum\_sum = 0
sum\_index = {0:-1}
max\_lenght = 0
for i, num in enumerate(nums):
cum_sum += num
if cum_sum not in sum_index.keys():
sum_index[cum_sum] = i
if (cum_sum - k) in sum_index.keys():
max_lenght = max(max_lenght, i - sum_index[cum_sum - k])
return max_lenght
- Range Sum of BST
Easy
3948
329
Add to List
Share
Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
Example 1:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.
Example 2:
Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.
Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
stack = []
sum_tree = 0
stack.append(root)
while len(stack)>0:
current = stack.pop()
val = current.val
if low<=val<=high:
sum_tree += current.val
if current.right is not None and vallow:
stack.append(current.left)
return sum_tree
def add_range_sum(root):
if root is None: # return 0 # sum\_right = add\_range\_sum(root.right) # sum\_left = add\_range\_sum(root.left) # if low\<=root.val\<=high: # return root.val + sum\_right + sum\_left # else: # return sum\_left + sum\_right
return add_range_sum(root)
- Contiguous Array
Medium
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
Example 1:
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
count_hash_map = {0 : -1}
counter = 0
max_lenght = 0
for i, num in enumerate(nums):
if num == 0:
counter -=1
else:
counter += 1
if counter in count_hash_map:
max_lenght = max(max_lenght, i - count_hash_map[counter])
else:
count_hash_map[counter] = i
return max_lenght
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
https://leetcode.com/problems/symmetric-tree/solution/
def isSymmetric(self, root): if not root: return True return self.dfs(root.left, root.right)
def dfs(self, l, r): if l and r: return l.val == r.val and self.dfs(l.left, r.right) and self.dfs(l.right, r.left) return l == r
def isSymmetric(self, root):
if not root:
return True
stack = [(root.left, root.right)]
while stack:
l, r = stack.pop()
if not l and not r:
continue
if not l or not r or (l.val != r.val):
return False
stack.append((l.left, r.right))
stack.append((l.right, r.left))
return True
- Target Sum
Medium
6486
248
Add to List
Share
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols ‘+’ and ‘-‘ before each integer in nums and then concatenate all the integers.
For example, if nums = [2, 1], you can add a ‘+’ before 2 and a ‘-‘ before 1 and concatenate them to build the expression “+2-1”.
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1
Output: 1
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -\> int:
memo = {}
self.counter = 0
def search_target(i, target):
if i==len(nums)-1:
counter = 0
if nums[len(nums)-1] == target:
counter+=1
if nums[len(nums)-1] == -target:
counter+=1
return counter
if (i,target) not in memo:
memo[(i, target)] = search_target(i+1, target-nums[i]) + search_target(i+1, target+nums[i])
return memo[(i, target)]
return search_target(0,target)
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Post-order traversal is to traverse the left subtree first. Then traverse the right subtree. Finally, visit the root.
Here is an animation to help you understand post-order traversal:
https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/992/
def postorderTraversal1(self, root):
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root:
self.dfs(root.left, res)
self.dfs(root.right, res)
res.append(root.val)
iteratively
note that here it is doing something fairly smart basically computing it in the opposite order and then reversing at the end.
it uses modified preorder (right subtree first). Then reverse the result.
def postorderTraversal(self, root):
res, stack = [], [root]
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.left)
stack.append(node.right)
return res[::-1]
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).
Example 1:
Input
[“Solution”,”pickIndex”]
[[[1]],[]]
Output
[null,0]
Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
Example 2:
Input
[“Solution”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.
Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
……
and so on.
class Solution:
def __init__(self, w: List[int]):
“””
:type w: List[int]
“””
self.prefix_sums = []
prefix_sum = 0
for weight in w:
prefix_sum += weight
self.prefix_sums.append(prefix_sum)
self.total_sum = prefix_sum
def pickIndex(self) -> int:
“””
:rtype: int
“””
target = self.total_sum * random.random()
# run a linear search to find the target zone
for i, prefix_sum in enumerate(self.prefix_sums):
if target < prefix_sum:
return i
def pickIndex(self) -\> int: target = self.total\_sum \* random.random() low = 0 high = len(self.prefix\_sums) while low self.prefix\_sums[mid]: low = mid + 1 else: high = mid return low
- Basic Calculator II
Medium
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = “3+2*2”
Output: 7
Example 2:
Input: s = “ 3/2 “
Output: 1
Example 3:
Input: s = “ 3+5 / 2 “
Output: 5
Constraints:
1 <= s.length <= 3 * 105
s consists of integers and operators (‘+’, ‘-‘, ‘*’, ‘/’) separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 231 - 1].
The answer is guaranteed to fit in a 32-bit integer.
22 + 4 + 7*3 - 12 - 3/2
class Solution:
def calculate(self, s: str) -> int:
operator = [”+”,”-“,”*”,”/”]
s = s.replace(“ “,””)
s = s.strip()
stack = []
num = 0
previ_op = “+”
for index, i in enumerate(s):
if i not in operator:
num = num * 10 + int(i)
if i in operator:
if previ_op == “*”:
fac1 = stack.pop()
res = fac1 * num
stack.append(res)
if previ_op == “/”:
fac1 = stack.pop()
res = fac1 / num
stack.append(int(res))
print(res)
if previ_op == “-“:
stack.append(-num)
if previ_op == “+”:
stack.append(num)
previ_op = i
num = 0
if index == len(s)-1:
if previ_op == “*”:
fac1 = stack.pop()
res = fac1 * num
stack.append(res)
if previ_op == “/”:
fac1 = stack.pop()
res = fac1 / num
print(res,int(fac1/num))
if previ_op == “-“:
stack.append(-num)
if previ_op == “+”:
stack.append(num)
return sum(stack)
#-12 #21 #4 #22
- Linked List Cycle
Easy
Share
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, x): # self.val = x # self.next = None
class Solution: def hasCycle(self, head: Optional[ListNode]) -\> bool: if not head: return False slow\_pointer = head fast\_pointer = head
while fast_pointer.next != None and fast_pointer != None:
slow_pointer = slow_pointer.next
fast_pointer = fast_pointer.next.next
if fast_pointer == slow_pointer:
return True
if fast_pointer ==None:
return False
return False
- Group Anagrams
Medium
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Example 2:
Input: strs = [””]
Output: [[””]]
Example 3:
Input: strs = [“a”]
Output: [[“a”]]
Constraints:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.
class Solution:
def create\_hash(self, word : str) -\> Dict:
char\_hash = {}
for i in word:
char\_hash[i] = char\_hash.get(i,0) + 1
return char\_hash
def create\_vector(self, word : str) -\> Dict:
char\_vector = [0]\*26
for i in word:
char\_vector[ord(i)-ord("a")] +=1
return tuple(char\_vector)
# def is\_anagram(self, word1, word2):
# if len(word1) != len(word2):
# return False
else: # hash\_1 = self.create\_hash(word1) # hash\_2 = self.create\_hash(word2) # for key in hash\_1.keys(): # if hash\_1[key] != hash\_2[key]: # return False # return True
def groupAnagrams\_2(self, strs: List[str]) -\> List[List[str]]: # grouped\_anagrams = [] # for i in strs: # hash\_i = self.create\_hash(i)
def groupAnagrams(self, strs: List[str]) -\> List[List[str]]: # if not strs: # return [[""]]
if len(strs)==1: # return [strs]
word\_to\_index = {}
# for i, word in enumerate(strs):
# sort\_word = "".join(sorted(word))
# if sort\_word in word\_to\_index.keys():
# word\_to\_index[sort\_word].append(i)
# else:
# word\_to\_index[sort\_word] = [i]
# return\_grouped = []
# for key in word\_to\_index.keys():
# word\_group = []
# for word\_index in word\_to\_index[key]:
# word\_group.append(strs[word\_index])
return_grouped.append(word_group)
return return_grouped
def groupAnagrams(self, strs: List[str]) -\> List[List[str]]: if not strs: return [[""]]
if len(strs)==1: return [strs]
word_to_index = {}
for i, word in enumerate(strs):
vector_freq = self.create_vector(word)
if vector_freq in word_to_index.keys():
word_to_index[vector_freq].append(i)
else:
word_to_index[vector_freq] = [i]
return_grouped = []
for key in word_to_index.keys():
word_group = []
for word_index in word_to_index[key]:
word_group.append(strs[word_index])
return_grouped.append(word_group)
return return_grouped
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Recursive
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
iterative
from collections import deque
Iterative
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
worklist = deque([root])
num_node_level = 1
levels = 0
while worklist:
node = worklist.popleft()
if node.left:
worklist.append(node.left)
if node.right:
worklist.append(node.right)
num_node_level -= 1
if num_node_level == 0:
levels += 1
num_node_level = len(worklist)
return levels
. Odd Even Linked List
Medium
5105
383
Add to List
Share
Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.
Example 1:
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Example 2:
Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
if head.next == None:
return head
odd\_node = [] # even\_node =[] # pointer = head # i = 1 # while pointer != None: # if i % 2 == 0: # even\_node.append(pointer) # else: # odd\_node.append(pointer) # pointer = pointer.next # i +=1
for i in range(len(odd_node) -1):
odd_node[i].next = odd_node[i+1]
for i in range(len(even_node) -1):
even\_node[i].next = even\_node[i+1] # head = odd\_node[0] # odd\_node[-1].next = even\_node[0] # even\_node[-1].next = None # return head
pointer_odd = head
pointer_even = head.next
while(pointer_even and pointer_odd and pointer_even.next and pointer_odd.next):
while pointer_even.next != None and pointer_even != None:
print(pointer_even.val,pointer_odd.val ,”beg”)
pointer_odd.next = pointer_even.next
pointer_odd = pointer_odd.next
pointer_even.next = pointer_odd.next
pointer_even = pointer_even.next
pointer_odd.next = head.next
return head
- Remove All Adjacent Duplicates In String
Easy
3021
149
Add to List
Share
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
Example 1:
Input: s = “abbaca”
Output: “ca”
Explanation:
For example, in “abbaca” we could remove “bb” since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is “aaca”, of which only “aa” is possible, so the final string is “ca”.
Example 2:
Input: s = “azxxzy”
Output: “ay”
class Solution: def removeDuplicates(self, s: str) -\> str: stack = [s[0]] for i in range(1, len(s)): if len(stack) \> 0:
if s[i] != stack[-1]:
stack. append(s[i])
else:
stack. pop()
else:
stack. append(s[i])
return ““.join(stack)
- Min Cost Climbing Stairs
Easy
5604
978
Add to List
Share
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
Constraints:
2 <= cost.length <= 1000
0 <= cost[i] <= 999
class Solution: def minCostClimbingStairs(self, cost: List[int]) -\> int:
def min\_cost\_to\_reach\_i(i): # if i == 0: # memo[0] = 0 # return 0 # if i == 1: # memo[1] = 0 # return 0 # if i not in memo: # memo[i] = min(min\_cost\_to\_reach\_i(i-1) + cost[i-1], min\_cost\_to\_reach\_i(i-2)+cost[i-2]) # return memo[i]
memo = {}
return min_cost_to_reach_i(len(cost))
cost_to_reach_i = [0]*(len(cost)+1)
for i in range(2,len(cost)+1):
cost_to_reach_i[i] = min(cost_to_reach_i[i-1] + cost[i-1],
cost_to_reach_i[i-2]+cost[i-2])
return cost_to_reach_i[-1]
- Lowest Common Ancestor of a Binary Tree III
Medium
812
24
Add to List
Share
Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).
Each node will have a reference to its parent node. The definition for Node is below:
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
”””
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
“””
import collections
class Solution:
def lowestCommonAncestor(self, p: ‘Node’, q: ‘Node’) -> ‘Node’:
parents_p = []
while p != None:
parents_p.append(p)
p=p.parent
parents_q = []
while q != None:
parents_q.append(q)
q=q.parent
pointer_p = len(parents_p) -1
pointer_q = len(parents_q) -1
ancestor = None
while pointer_q>=0 and pointer_p>=0 and parents_p[pointer_p].val == parents_q[pointer_q].val:
ancestor = parents_q[pointer_q]
pointer_q-=1
pointer_p-=1
return ancestor
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).
class Solution:
def __init__(self, w: List[int]):
“””
:type w: List[int]
“””
self.prefix_sums = []
prefix_sum = 0
for weight in w:
prefix_sum += weight
self.prefix_sums.append(prefix_sum)
self.total_sum = prefix_sum
def pickIndex(self) -> int:
“””
:rtype: int
“””
target = self.total_sum * random.random()
# run a linear search to find the target zone
for i, prefix_sum in enumerate(self.prefix_sums):
if target < prefix_sum:
return i
def pickIndex(self) -\> int: target = self.total\_sum \* random.random() low = 0 high = len(self.prefix\_sums) while low self.prefix\_sums[mid]: low = mid + 1 else: high = mid return low
- Buildings With an Ocean View
Medium
717
97
Add to List
Share
There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.
The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.
Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.
Example 1:
Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.
Example 2:
Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.
Example 3:
Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.
Constraints:
1 <= heights.length <= 105
1 <= heights[i] <= 109
from collections import deque
class Solution: def findBuildings(self, heights: List[int]) -\> List[int]:
with_view = deque()
if len(heights) == 1: return [0]
max_h = -1
for i in range(len(heights) -1 , -1, -1):
if heights[i] > max_h:
with_view.appendleft(i)
max_h = heights[i]
return list(with_view)
for i in range(len(heights)-1): # if heights[i]\>max\_heigth\_right[i+1]: # view.append(i) # view.append(i+1) # return view
How can you truncate an integer division towards zero?
simply use int(a/b)
Longest Consecutive Sequence
Medium
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
class Solution: def longestConsecutive(self, nums: List[int]) -\> int: if not nums: return 0 nums = set(nums)
longest_seq = 1
for i in nums:
if i-1 not in nums:
counter = 1
while i+1 in nums:
i += 1
counter +=1
longest_seq = max(longest_seq, counter)
return longest_seq
- Valid Word Abbreviation
Easy
419
1531
Add to List
Share
A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.
For example, a string such as “substitution” could be abbreviated as (but not limited to):
“s10n” (“s ubstitutio n”)
“sub4u4” (“sub stit u tion”)
“12” (“substitution”)
“su3i1u2on” (“su bst i t u ti on”)
“substitution” (no substrings replaced)
The following are not valid abbreviations:
“s55n” (“s ubsti tutio n”, the replaced substrings are adjacent)
“s010n” (has leading zeros)
“s0ubstitution” (replaces an empty substring)
Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: word = “internationalization”, abbr = “i12iz4n”
Output: true
Explanation: The word “internationalization” can be abbreviated as “i12iz4n” (“i nternational iz atio n”).
Example 2:
Input: word = “apple”, abbr = “a2e”
Output: false
Explanation: The word “apple” cannot be abbreviated as “a2e”.
class Solution: def validWordAbbreviation(self, word: str, abbr: str) -\> bool: if len(abbr) \> len(word): return False digits = ["1","2","3","4","5","6","7","8","9","0"] word\_pointer = 0 abbr\_pointer = 0 # if abbr\_pointer goes out it is not a valid abbreviation while word\_pointer \< len(word): print(word[word\_pointer], abbr[abbr\_pointer]) if abbr[abbr\_pointer] in digits:
if abbr[abbr_pointer] == “0”:
return False
jump = 0 while abbr[abbr\_pointer] in digits: jump = jump \* 10 + int(abbr[abbr\_pointer]) abbr\_pointer += 1 if abbr\_pointer\>=len(abbr): break word\_pointer += jump # print(word[word\_pointer])
elif word[word_pointer] != abbr[abbr_pointer]:
return False
else:
word_pointer +=1
abbr_pointer+=1
if word\_pointer \> len(word): # print(word\_pointer,len(word)) return False return True
- Basic Calculator II
Medium
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = “3+2*2”
Output: 7
Example 2:
Input: s = “ 3/2 “
Output: 1
Example 3:
Input: s = “ 3+5 / 2 “
Output: 5
22 + 4 + 7*3 - 12 - 3/2
class Solution:
def calculate(self, s: str) -> int:
operator = [”+”,”-“,”*”,”/”]
s = s.replace(“ “,””)
s = s.strip()
stack = []
num = 0
previ_op = “+”
for index, i in enumerate(s):
if i not in operator:
num = num * 10 + int(i)
if i in operator:
if previ_op == “*”:
fac1 = stack.pop()
res = fac1 * num
stack.append(res)
if previ_op == “/”:
fac1 = stack.pop()
res = fac1 / num
stack.append(int(res))
print(res)
if previ_op == “-“:
stack.append(-num)
if previ_op == “+”:
stack.append(num)
previ_op = i
num = 0
if index == len(s)-1:
if previ_op == “*”:
fac1 = stack.pop()
res = fac1 * num
stack.append(res)
if previ_op == “/”:
fac1 = stack.pop()
res = fac1 / num
print(res,int(fac1/num))
if previ_op == “-“:
stack.append(-num)
if previ_op == “+”:
stack.append(num)
return sum(stack)
#-12 #21 #4 #22
- Longest Common Subsequence
Medium
6037
66
Add to List
Share
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.
Example 2:
Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.
Example 3:
Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -\> int:
memo = {}
# def longest\_at\_i\_j(i,j):
if i \< 0 or j \< 0: # return 0
if (i,j) not in memo: # if text1[i] == text2[j]: # memo[(i,j)] = 1 + longest\_at\_i\_j(i-1,j-1)
else: # memo[(i,j)] = max(longest\_at\_i\_j(i-1,j), longest\_at\_i\_j(i,j-1))
return memo[(i,j)]
return longest_at_i_j(len(text1)-1,len(text2)-1)
longest_at_i_j = [[0]*len(text2) for i in range(len(text1))]
if text1[0] == text2[0]:
longest_at_i_j [0][0] = 1
else:
longest_at_i_j [0][0] = 0
for i in range(1,len(text1)):
for j in range(1,len(text2)):
if text1[i] == text2[j]:
longest_at_i_j[i][j] = 1 + longest_at_i_j[i-1][j-1]
else:
longest_at_i_j[i][j] = max(longest_at_i_j[i-1][j], longest_at_i_j[i][j-1])
print(longest_at_i_j)
return(longest_at_i_j[len(text1)-1][len(text2)-1])
- Contiguous Array
Medium
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
Example 1:
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
count_hash_map = {0 : -1}
counter = 0
max_lenght = 0
for i, num in enumerate(nums):
if num == 0:
counter -=1
else:
counter += 1
if counter in count_hash_map:
max_lenght = max(max_lenght, i - count_hash_map[counter])
else:
count_hash_map[counter] = i
return max_lenght
- Pow(x, n)
Medium
4161
5172
Add to List
Share Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Constraints:
- 100.0 < x < 100.0
- 231 <= n <= 231-1
- 104 <= xn <= 104
class Solution:
def power(self,x,n):
if n == 1:
return x
double_half = self.power(x, n//2)
if n%2 == 0:
return double_half * double_half
else:
return double_half * double_half * x
def myPow(self, x: float, n: int) -\> float: if n==0: return 1
n_mod = abs(n)
res = self.power(x,n_mod)
if n < 0:
return 1.0/res
else:
return res
- Binary Tree Right Side View
Medium
6164
331
Add to List
Share
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2:
Input: root = [1,null,3]
Output: [1,3]
Example 3:
Input: root = []
Output: []
Definition for a binary tree node. # class TreeNode: # def \_\_init\_\_(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right
from collections import deque class Solution: def rightSideView(self, root: Optional[TreeNode]) -\> List[int]:
if root is None:
return []
queue = deque([root])
right_view = []
while len(queue)>0:
len_q = len(queue)
current_node = queue.popleft()
right_view.append(current_node.val)
if current_node.right is not None:
queue.append(current_node.right)
if current_node.left is not None:
queue.append(current_node.left)
for i in range(len_q-1):
current_node = queue.popleft()
if current_node.right is not None:
queue.append(current_node.right)
if current_node.left is not None:
queue.append(current_node.left)
return right_view
- Diameter of Binary Tree
Easy
7466
465
Add to List
Share
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100
Definition for a binary tree node. # class TreeNode: # def \_\_init\_\_(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -\> int:
self.diameter = 0 def longest\_from\_node(node):
if node.right is None and node.left is None:
return 0
max_from_here = 0
right_sum = 0
left_sum = 0
if node.right is not None:
right_sum = 1 + longest_from_node(node.right)
max_from_here = right_sum + max_from_here
if node.left is not None:
left_sum = 1 + longest_from_node(node.left)
max_from_here = left_sum + max_from_here
self.diameter = max(self.diameter, max_from_here)
return max(right_sum,left_sum)
longest_from_node(root)
return self.diameter
Maximum Depth of Binary Tree
Easy
6598
123
Add to List
Share
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2
Constraints:
The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100
Definition for a binary tree node. # class TreeNode: # def \_\_init\_\_(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxDepth(self, root: Optional[TreeNode]) -\> int: # the max depth rooted in one node is max depth of left and right +1
def helper(node):
if node is None:
return 0
if node.right is None and node.left is None:
return 1
depth = max(helper(node.left), helper(node.right)) + 1
return depth
return helper(root)
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
Preorder means node than its left leaf and then the right one
recursively
def preorderTraversal1(self, root):
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root:
res.append(root.val)
self.dfs(root.left, res)
self.dfs(root.right, res)
iteratively
def preorderTraversal(self, root):
stack, res = [root], []
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.right)
stack.append(node.left)
return res
What are the steps of a sliding window problem?
Basic template of such problems is basically 3 steps.
- Step1: Have a counter or hash-map to count specific array input and keep on increasing the window toward right using outer loop.
- Step2: Have a while loop inside to reduce the window side by sliding toward right. Movement will be based on constraints of problem.
- Step3: Store the current maximum window size or minimum window size or number of windows based on problem requirement.
Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.
You can do it with 2 pointer but it is tricky better use an hash array to memorize the previous time you have seen an elemente
Remember if you have seen it before someone you have already seen it you should just move on
class Solution: def lengthOfLongestSubstring(self, s: str) -\> int: if len(s)==0: return 0
current_string = {}
lenght = 0
beginning = 0
max_len = 0
for i,char in enumerate(s):
if char not in current_string or current_string.get(char,0) < beginning:
current_string[char] = i
lenght +=1
if i == len(s)-1:
max_len = max(lenght, max_len)
else:
max_len = max(lenght, max_len)
beginning = current_string[char]
lenght = i - beginning
current_string[char] = i
return max_len
- Symmetric Tree
Easy
8987
223
Add to List
Share
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
Constraints:
The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
def isSymmetric(self, root): if not root: return True return self.dfs(root.left, root.right)
def dfs(self, l, r): if l and r: return l.val == r.val and self.dfs(l.left, r.right) and self.dfs(l.right, r.left) return l == r
def isSymmetric(self, root):
if not root:
return True
stack = [(root.left, root.right)]
while stack:
l, r = stack.pop()
if not l and not r:
continue
if not l or not r or (l.val != r.val):
return False
stack.append((l.left, r.right))
stack.append((l.right, r.left))
return True
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Example 1:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.
Time complexity: O(NlogN) Sort the list according to the distance to origin. Apparently, we did more than the question asked. We sorted all the distance, the question only ask for top k. To improve time complexity, we need to think about how to get we ask without extra effort. This is where heap data structure comes in. class Solution: def kClosest(self, points: List[List[int]], K: int) -\> List[List[int]]: points.sort(key = lambda P:P[0]\*\*2+P[1]\*\*2) return points[:K] Time complexity: O(nlogn), intuitively use minimum Heap: make a maximum-heap to store distance, (point's distance to original, point) each time call heapq.heappop (distance), it will pop the smallest item in the heap. So heappop K times will be the result. import heapq class Solution: def kClosest(self, points: List[List[int]], K: int) -\> List[List[int]]: distance = [] for i in points: heapq.heappush(distance,(i[0]\*\*2+i[1]\*\*2,i)) K\_points = [] for i in range(K): K\_points.append(heapq.heappop(distance)[1]) return K\_points
- Reverse Linked List
iven the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -\> Optional[ListNode]: if not head: return head pointer = head
while pointer.next != None: next1 = pointer.next next2 = pointer.next.next next1.next = head head = next1 pointer.next = next2 # final swap #next1 = pointer.next #next1.next = head #head = next1 #pointer.next = None
return head
- House Robber
Medium
11637
249
Add to List
Share
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Think and propose both iterative and recursive!!
class Solution: def rob(self, nums: List[int]) -\> int:
bottom up solution
dp = [0] * len(nums)
dp[0] = nums[0]
if len(nums)==1: # return dp[-1]
dp[1] = max(nums[0], nums[1])
if len(nums) == 2: # return dp[-1]
for i in range(2, len(nums)): # dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
top-down
def dp(i):
if i == 0 :
return nums[0]
return
if i ==1:
return max(nums[0], nums[1])
if i not in memo:
memo[i] = max(dp(i-1), dp(i-2) + nums[i])
return memo[i]
memo = {}
return dp(len(nums)-1)
- Group Anagrams
Medium
https://leetcode.com/problems/group-anagrams/
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Example 2:
Input: strs = [””]
Output: [[””]]
Example 3:
Input: strs = [“a”]
Output: [[“a”]]
Basically you have to create
Approach 2: Categorize by Count
Intuition
Two strings are anagrams if and only if their character counts (respective number of occurrences of each character) are the same.
Algorithm
We can transform each string \text{s}s into a character count, \text{count}count, consisting of 26 non-negative integers representing the number of \text{a}a’s, \text{b}b’s, \text{c}c’s, etc. We use these counts as the basis for our hash map.
In Java, the hashable representation of our count will be a string delimited with ‘#’ characters. For example, abbccc will be #1#2#3#0#0#0…#0 where there are 26 entries total. In python, the representation will be a tuple of the counts. For example, abbccc will be (1, 2, 3, 0, 0, …, 0), where again there are 26 entries total.
def groupAnagrams(self, strs: List[str]) -\> List[List[str]]: if not strs: return [[""]]
if len(strs)==1: return [strs]
word_to_index = {}
for i, word in enumerate(strs):
vector_freq = self.create_vector(word)
if vector_freq in word_to_index.keys():
word_to_index[vector_freq].append(i)
else:
word_to_index[vector_freq] = [i]
return_grouped = []
for key in word_to_index.keys():
word_group = []
for word_index in word_to_index[key]:
word_group.append(strs[word_index])
return_grouped.append(word_group)
return return_grouped
- Add Two Numbers
Medium
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0] Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
Constraints:
The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.
https://leetcode.com/problems/add-two-numbers/discuss/1016/Clear-python-code-straight-forward
Definition for singly-linked list. # class ListNode: # def \_\_init\_\_(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -\> Optional[ListNode]:
root_answer = ListNode()
current_node = root_answer
keep = 0
while l1 is not None or l2 is not None:
if l1 is None:
val = l2.val
l2 = l2.next
elif l2 is None:
val = l1.val
l1 = l1.next
else:
val = l1.val + l2.val
l1 = l1.next
l2 = l2.next
current_node.val = (val+keep)%10
keep = int( (val+keep) / 10)
if l1 is not None or l2 is not None:
current_node.next = ListNode()
current_node = current_node.next
elif keep !=0:
current_node.next = ListNode()
current_node = current_node.next
current_node.val = keep
return root_answer
https://leetcode.com/problems/add-two-numbers/discuss/1016/Clear-python-code-straight-forward
- Simplify Path
Share
Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.
In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.
The canonical path should have the following format:
The path starts with a single slash ‘/’.
Any two directories are separated by a single slash ‘/’.
The path does not end with a trailing ‘/’.
The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period ‘.’ or double period ‘..’)
Return the simplified canonical path.
Example 1:
Input: path = “/home/”
Output: “/home”
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:
Input: path = “/../”
Output: “/”
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:
Input: path = “/home//foo/”
Output: “/home/foo”
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
similar to the one where you do say basic calculator or parenthesis but be very careful with dealing with cases
class Solution:
def simplifyPath(self, path: str) -> str:
split_path = path.split(“/”)
stack= []
string=””
for i,s in enumerate(path):
if s not in [”/”]:
string = string + s
if s == “/” or i == len(path)-1:
if string in [”.”, “”]:
string = “”
elif string ==”..”:
string = “”
if stack:
stack.pop()
else:
stack.append(string)
string = “”
return “/” + “/”.join(stack)
https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/
1010
You are given a list of songs where the ith song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
Example 2:
Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Of course you can go brute force.
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -\> int:
count = 0
hash\_map = {}
for i in range(len(time)):
tim = time[i]%60
count += hash\_map.get(60-tim,0)
count += hash\_map.get(0-tim,0)
hash\_map[tim] = hash\_map.get(tim,0) + 1
return countGiven the root of a binary tree, return the inorder traversal of its nodes’ values.
Now is really depth first you go all the way down to the left side hit a leaf and then add node and the right leaf after that.
recursively
def inorderTraversal1(self, root):
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
iteratively
def inorderTraversal(self, root):
res, stack = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return res
node = stack.pop()
res.append(node.val)
root = node.right
- Maximum Swap
Medium
2394
137
Add to List
Share
You are given an integer num. You can swap two digits at most once to get the maximum valued number.
Return the maximum valued number you can get.
Example 1:
Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
Input: num = 9973
Output: 9973
Explanation: No swap.
Constraints:
0 <= num <= 108
class Solution: def maximumSwap(self, num: int) -\> int: num = list(str(num)) len\_n = len(num) max\_from\_left = [-1]\*len\_n max\_n = len\_n - 1 for i in range(len\_n-1,-1,-1):
if int(num[i])>int(num[max_n]):
max_from_left[i] = i
max_n = i
else:
max_from_left[i] = max_n
for i in range(len\_n):
if int(num[i]) \< int(num[max\_from\_left[i]]):
num[i],num[max\_from\_left[i]] = num[max\_from\_left[i]],num[i]
return int("".join(num))
return int("".join(num))
