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
