Buckets:
Table of Contents
-
Contains Duplicate
Valid Anagram
Two Sum
Group Anagrams
Set Matrix Zeroes
Top K Frequent Elements
Products of Array Except itself
Longest Consecutive Sequence
-
Valid Palindrome
Two Sum II
3 Sum
Container with most Water
Trapping Rain Water
-
Best time to buy and sell stock
Longest Substring without repeating Characters
Longest repeating character replacements
Permutation in string
-
Valid parentheses
Minimum stack
Evaluate Reverse Polish Notation
Binary Search
Linked List
Trees
Heap/Priority Queue
Backtracking
Tries
Graph
Advanced Graph
2D Dynamic Programming
Greedy
Intervals
Math Geometry
Bit Manipulation
Foreword
Here are some tricks to remember when solving a problem.
- If a given problem can be solved in
O(n)time and its mentioned that input is sorted array, Binary Search can be used.
Arrays and Hashing
Contains Duplicate (LeetCode, NeetCode) ==EASY==
Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.
Input: nums = [1, 2, 3, 3]
Output: true
Input: nums = [1, 2, 3, 4]
Output: false
Time and Space Complexity
You should aim for a solution with
O(n)time andO(n)space, wherenis the size of the input array.
Solution:
Use a set/dictionary to store the elements of the array. If an element is present already, return True. At the end of loop return False.
Code:
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
res = set()
for num in nums:
if num in res:
return True
else:
res.add(num)
return False
Valid Anagram (LeetCode, NeetCode) ==EASY==
Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.
An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.
Input: s = "racecar", t = "carrace"
Output: true
Time and Space Complexity
You should aim for a solution with
O(n + m)time andO(1)space, wherenis the length of the stringsandmis the length of the stringt.
Solution:
Brute force
class Solution: def isAnagram(self, s: str, t: str) -> bool: s, t = sorted(s), sorted(t) return s == tSimply sorting the characters of both the strings and comparing them for equality. It is of a
O(nlogn + mlogm)time complexity.Optimal
class Solution: def isAnagram(self, s: str, t: str) -> bool: s_len = len(s) t_len = len(t) if s_len != t_len: return False s_map, t_map = {}, {} for i in range(s_len): s_map[s[i]] = s_map.get(s[i], 0) + 1 t_map[t[i]] = t_map.get(t[i], 0) + 1 return s_map == t_mapKeep track of the count of character in the strings in s dictionary and return whether they are equal or not.
Two Sum (LeetCode) ==EASY==
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Input: nums = [3,2,4], target = 6
Output: [1,2]
Input: nums = [3,3], target = 6
Output: [0,1]
Time and Space Complexity
You should aim for a solution with
O(n)time andO(n)space, where n is the size of the input array
Solution:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
pairs = {}
for i in range(len(nums)):
if nums[i] in pairs:
return [pairs[nums[i]], i]
pairs[target - nums[i]] = i
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = dict()
result = None
for i, num in enumerate(nums):
if res is not None and num in res:
result = [res[num], i]
else:
res.update({target - num: i})
return result
Keep a dictionary to store the target - num and index as key and value pairs. If a number from the list of numbers exist in the dictionary, return it’s index and the index corresponding to that number as key in the dictionary.
Group Anagrams (LeetCode) ==MEDIUM==
Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order. An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.
Input: strs = ["act","pots","tops","cat","stop","hat"]
Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]
Input: strs = ["x"]
Output: [["x"]]
Time and Space Complexity
You should aim for a solution with
O(m * n)time andO(m)space, wheremis the number of strings andnis the length of the longest string.
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups: dict[List[str]] = {}
for word in strs:
ref = "".join(sorted(word))
if ref not in groups:
groups.update({ref: [word]})
else:
groups[ref].append(word)
return list(groups.values())
Set Matrix Zeros (LeetCode) ==MEDIUM==
Given an m x n matrix of integers matrix, if an element is 0, set its entire row and column to 0's. You must update the matrix in-place. Follow up: Could you solve it using O(1) space?
Input: matrix = [
[0,1],
[1,1]
]
Output: [
[0,0],
[0,1]
]
Solution:
Brute Force Solution -
**O(m*n*(m+n))+O(m*n)**time complexityLoop over each cell in the matrix.
If a cell contains 0, loop over the row and column for that cell, i.e. if you are in cell 1, 2, loop over all columns in row 1 and all rows in column 2.
Set all non-zero elements to -1 in the traversing row and column.
Once the traverse is complete, traverse the matrix again and replace all -1 with 0.
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: row_len, col_len = len(matrix), len(matrix[0]) for row in range(row_len): for col in range(col_len): if matrix[row][col] == 0: for _col in range(col_len): if matrix[row][_col] != 0: matrix[row][_col] = -1 for _row in range(row_len): if matrix[_row][col] != 0: matrix[_row][col] = -1 for row in range(row_len): for col in range(col_len): if matrix[row][col] == -1: matrix[row][col] = 0Optimized Solution -
**O(m*n)+O(m*n)**time complexity,**O(m+n)**space complexityCreate two 1-D arrays, one of the length of row and one of the length of column.
Loop over each cell in the matrix.
If a cell contains 0, mark the index in row array with -1 at the row index from the matrix, and same with column array. E.g. if there is a 0 in cell 1,2, mark -1 in 1 index of row array and 2 index of column array
Repeat step 3 for all elements in the matrix.
Once the traverse is complete, traverse the matrix again and replace the cells with 0 if the row index of that cell has -1 in the particular index in row array or column index has -1 in the particular index in column array.
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: row_, col_ = [0] * len(matrix), [0] * len(matrix[0]) row_len, col_len = len(matrix), len(matrix[0]) for row in range(row_len): for col in range(col_len): if matrix[row][col] == 0: row_[row], col_[col] = -1, -1 for row in range(row_len): for col in range(col_len): if row_[row] == -1 or col_[col] == -1: matrix[row][col] = 0
Best Approach -
**O(m*n)**time complexity,**O(1)**space complexityclass Solution: def setZeroes(self, matrix: List[List[int]]) -> None: ROWS, COLS = len(matrix), len(matrix[0]) rowZero = False for r in range(ROWS): for c in range(COLS): if matrix[r][c] == 0: matrix[0][c] = 0 if r > 0: matrix[r][0] = 0 else: rowZero = True for r in range(1, ROWS): for c in range(1, COLS): if matrix[0][c] == 0 or matrix[r][0] == 0: matrix[r][c] = 0 if matrix[0][0] == 0: for r in range(ROWS): matrix[r][0] = 0 if rowZero: for c in range(COLS): matrix[0][c] = 0
Top K Frequent Elements (Leetcode) ==MEDIUM==
Given an integer array nums and an integer k, return the k most frequent elements within the array. The test cases are generated such that the answer is always unique. You may return the output in any order.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Input: nums = [1], k = 1
Output: [1]
Time and Space Complexity
You should aim for a solution with
O(n)time andO(n)space, wherenis the size of the input arrayBrute Force
Keep a dictionary to store count of each element in the array
Sort the dictionary based on the values/counts from the dictionary, and return the k top counts from the list.
class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: res = {} for num in nums: res[num] = res.get(num, 0) + 1 return [key for key, val in sorted(res.items(), key=lambda x: x[1], reverse=True)][:k]Optimized
First, keep a counter for items of the list. This will have all the item and their counts in the list.
Then create an empty list of list, with index being the counts from
0ton + 1. This will group the items from the list based on their counts. E.g.: if list is[1,2,4,4,3,3,3]the empty list should finally be[[],[1,2],[4],[3],[]...[]].Finally, we need to loop the dictionary from behind and over each list in the dictionary. Append each item into the res list until the size of res list is equal to k.
class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: counts = [[] for _ in range(len(nums) + 1)] itemCounts = collections.Counter(nums) for item, count in itemCounts.items(): counts[count].append(item) res = [] for i in range(len(counts) - 1, 0, -1): for item in counts[i]: res.append(item) if len(res) == k: return res## Using min-heap import heapq class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: frequency_map = {} for num in nums: frequency_map[num] = frequency_map.get(num, 0) + 1 min_heap = [] for num, frequency in frequency_map.items(): heapq.heappush(min_heap, (frequency, num)) if len(min_heap) > k: heapq.heappop(min_heap) return [num for frequency, num in min_heap]
Products of Array Except Self ==[MEDIUM]==
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Time and Space complexity
Time =
O(n); Space =O(n)By Division
We start by calculating the product of all elements in the array. While calculating product of elements, zeroes are excluded and the zeroes count is stored in a variable.
Next, the zeroes count is checked. If the zero count is more than ‘one’, the result will be a list of zeroes. A list of length of size of the input array is returned.
If the above case passes, then an array of size of the input array is created, and filled with zeroes.
Loop over the elements of the input array. If the item at current index is non-zero, add the
product // numif zero count is< 1else put0to the result array at that index. If the item is zero: put product at the index.Finally return the result.
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: prod = 1 zero_count = 0 for num in nums: if num != 0: prod *= num else: zero_count += 1 if zero_count > 1: return [0] * len(nums) res = [0] * len(nums) for idx, num in enumerate(nums): if num: res[idx] = prod // num if zero_count < 1 else 0 else: res[idx] = prod return resPrefix and Post-fix
To solve this problem, we can first calculate the product of all elements to the left of each index and store it in a list. Then, we calculate the product of all elements to the right of each index and update the result list accordingly by multiplying it with the previously calculated left product. In this way, each element in the result list will contain the product of all elements except the one at that index.
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) result = [1] * n # Calculate the left product of each element left_product = 1 for i in range(n): result[i] *= left_product left_product *= nums[i] # Calculate the right product of each element and update the result list right_product = 1 for i in range(n - 1, -1, -1): result[i] *= right_product right_product *= nums[i] return result
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
Example 3:
Input: nums = [1,0,1,2]
Output: 3
Solution:
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
num_set = set(nums)
max_length = 0
for num in num_set:
if num - 1 not in num_set:
current_num = num
current_length = 1
while current_num + 1 in num_set:
current_num += 1
current_length += 1
max_length = max(max_length, current_length)
return max_length
Two-pointer
Valid Palindrome ==EASY==
Given a string s, return true if it is a palindrome, otherwise return false. A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.
Input: s = "Was it a car or a cat I saw?"
Output: true
Explanation: After considering only alphanumerical characters we have
"wasitacaroracatisaw", which is a palindrome.
Input: s = "tab a cat"
Output: false
Explanation: "tabacat" is not a palindrome.
Solution
class Solution: def isPalindrome(self, s: str) -> bool: l, r = 0, len(s) - 1 while l < r: if not s[l].isalnum(): l += 1 elif not s[r].isalnum(): r -= 1 else: if s[l].lower() != s[r].lower(): return False l += 1 r -= 1 return TrueTo determine if a given string is a valid palindrome, we can use two pointers approach. We initialize two pointers, one at the beginning of the string (left) and the other at the end of the string (right). We then compare characters at these two pointers. If they are both alphanumeric characters and equal in value (ignoring case), we move both pointers towards the centre of the string. If they are not equal, we know the string is not a palindrome. We continue this process until the two pointers meet or cross each other.
Start with two pointers, one at the start other at the end of string, and start moving both towards each other.
if any of the characters at
lorris not alphanumeric, the pointer is moved forward or backward.If the character at
landrare not same when they are lowercase,Falseis returned, else the pointers are moved forward and backward.At the end,
Trueis returned, indicating the string is palindrome.
Two Sum II ==MEDIUM==
Given an array of integers numbers that is sorted in non-decreasing order. Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.
There will always be exactly one valid solution. Your solution must use O(1)O(1) additional space.
Input: numbers = [1,2,3,4], target = 3
Output: [1,2]
Explanation:
The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, index1 = 1,
index2 = 2. We return [1, 2].
Time & Space Complexity
You should aim for a solution with
O(n)time andO(1)space, wherenis the size of the input array.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers) - 1
while l < r:
two_sum = numbers[l] + numbers[r]
if two_sum < target:
l += 1
elif two_sum > target:
r -= 1
else:
return [l + 1, r + 1]
Start with two pointers,
landr, one in the starting of string and other at the end.Calculate the sum of the numbers that are in the
landrpointers. If the sum is lesser than target, movelforward and if sum is greater than target, moverbackward.If both cases fail, we have our answer, which is
[l+1, r+1]. Return it.
3 Sum ==MEDIUM==
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct. The output should not contain any duplicate triplets. You may return the output and the triplets in any order.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Solution
To find all unique triplets that sum to zero, we can use a three-pointer approach. First, we sort the input array
numsin non-decreasing order. Then, we iterate through the array with a fixed first element (i). For each fixed first element, we use two pointers (left and right) to find the other two elements that sum to the negation of the fixed first element. As the array is sorted, we can move these two pointers towards each other to efficiently find all possible triplets.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
size = len(nums)
nums.sort()
for i in range(size - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, size - 1
while l < r:
three_sum = nums[i] + nums[l] + nums[r]
if three_sum < 0:
l += 1
elif three_sum > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
return res
Time and Space complexity
You should aim for a solution with
O(n)time andO(1)space, wherenis the size of the input array.
Container with most water ==MEDIUM==
You are given an integer array **heights** where **heights[i]** represents the height of the ithith bar.
You may choose any two bars to form a container. Return the maximum amount of water a container can store.
![[image.png]]
Example 1:
Input: height = [1,7,2,5,4,7,3,6]
Output: 36
Solution
To find the maximum area of water that can be held between two vertical lines, we can use a two-pointer approach. We initialize two pointers, one at the beginning of the input array (left) and the other at the end of the array (right). The area between the two vertical lines is calculated as the minimum of the heights at the two pointers multiplied by the distance between them. We then update the maximum area found so far and move the pointer with the smaller height towards the other pointer. We continue this process until the two pointers meet or cross each other.
class Solution: def maxArea(self, heights: List[int]) -> int: size = len(heights) l, r = 0, size - 1 max_vol = 0 while l < r: height = min(heights[l], heights[r]) max_vol = max(max_vol, height * (r - l)) if heights[l] <= heights[r]: l += 1 else: r -= 1 return max_volTime and Space complexity
You should aim for a solution with
O(n)time andO(1)space, wherenis the size of the input array.
Trapping Rain Water ==HARD==
You are given an array non-negative integers **height** which represent an elevation map. Each value **height[i]** represents the height of a bar, which has a width of **1**.
Return the maximum area of water that can be trapped between the bars.
Example 1:
![[image 1.png]]
Input: height = [0,2,0,3,1,0,1,3,2,1]
Output: 9
Solution
To find the amount of trapped rainwater in the given elevation histogram represented by the input array 'height', we can use a two-pointer approach. We initialize two pointers, one at the beginning of the array (left) and the other at the end of the array (right). We also initialize two variables to keep track of the maximum left height and maximum right height seen so far. While the left pointer is less than the right pointer, we compare the height at the left and right pointers. If the height at the left pointer is less than or equal to the height at the right pointer, it means we can trap water between the left pointer and the maximum left height. Otherwise, we can trap water between the right pointer and the maximum right height. At each step, we update the trapped water amount and move the pointers and update the maximum heights accordingly.
Time and Space Complexity
You should aim for a solution as good or better than
O(n)time andO(n)space, wherenis the size of the input array.
class Solution: def trap(self, height: List[int]) -> int: left, right = 0, len(height) - 1 max_left, max_right = 0, 0 trapped_water = 0 while left < right: if height[left] <= height[right]: if height[left] >= max_left: max_left = height[left] else: trapped_water += max_left - height[left] left += 1 else: if height[right] >= max_right: max_right = height[right] else: trapped_water += max_right - height[right] right -= 1 return trapped_water
Sliding Window
Best Time to Buy and Sell Stock ==EASY==
You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day. You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it. Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.
Input: prices = [10,1,5,6,7,1]
Output: 6
Input: prices = [10,8,7,5,2]
Output: 0
Time and Space Complexity
You should aim for a solution with
O(n)time andO(1)space, wherenis the size of the input array.Solution
To find the maximum profit from a single buy and sell transaction in the input array
prices, we can use a simple one-pass approach. We initialize two variables,min_priceto keep track of the minimum price seen so far, andmax_profitto store the maximum profit. We iterate through thepricesarray, and for each price, we update themin_priceif we find a smaller price. We also calculate the potential profit if we sell at the current price and updatemax_profitif the current profit is greater than the previous maximum profit.class Solution: def maxProfit(self, prices: List[int]) -> int: buy = 0 profit = 0 for sell in range(1, len(prices)): if prices[sell] < prices[buy]: buy = sell profit = max(profit, prices[sell] - prices[buy]) return profit if profit > 0 else 0
Longest Substring Without Repeating Characters ==MEDIUM==
Given a string **s**, find the length of the longest substring without duplicate characters.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "zxyzxyz"
Output: 3
Explanation:
The string "xyz" is the longest without duplicate characters.
Example 2:
Input: s = "xxxx"
Output: 1
Time and Space Complexity
You should aim for a solution with
O(n)time andO(m)space, wherenis the length of the string andmis the number of unique characters in the string.Solution
To find the length of the longest substring without repeating characters in the input string 's', we can use the sliding window approach. We use two pointers, 'left' and 'right', to represent the current window. As we move the 'right' pointer to the right, we expand the window and add characters to a set to keep track of unique characters in the window. If we encounter a repeating character, we move the 'left' pointer to the right to shrink the window until the repeating character is no longer in the window. At each step, we update the maximum length of the window (i.e., the length of the longest substring without repeating characters).
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: unique_chars = {} max_len = 0 start = 0 size = len(s) for end in range(size): if s[end] in unique_chars: start = max(unique_chars[s[end]] + 1, start) unique_chars[s[end]] = end max_len = max(max_len, end - start + 1) return max_len
Longest Repeating Character Replacement ==MEDIUM==
You are given a string **s** consisting of only uppercase English characters and an integer **k**. You can choose up to **k** characters of the string and replace them with any other uppercase English character.
After performing at most **k** replacements, return the length of the longest substring which contains only one distinct character.
Example 1:
Input: s = "XYYX", k = 2
Output: 4
Explanation: Either replace the 'X's with 'Y's, or replace the 'Y's with 'X's.
Example 2:
Input: s = "AAABABB", k = 1
Output: 5
Solution
To find the maximum length of a substring with at most
kdistinct characters in the input strings, we can use the sliding window approach. We use two pointers,leftandright, to represent the current window. As we move therightpointer to the right, we expand the window and add characters to a dictionary to keep track of their frequencies. If the number of distinct characters in the window exceedsk, we move theleftpointer to the right to shrink the window until the number of distinct characters iskagain. At each step, we update the maximum length of the window.class Solution: def characterReplacement(self, s: str, k: int) -> int: chars = {} l = 0 max_len = 0 max_count = 0 for r in range(len(s)): chars[s[r]] = chars.get(s[r], 0) + 1 max_count = max(max_count, chars[s[r]]) while (r - l + 1) - max_count > k: chars[s[l]] -= 1 l += 1 max_len = max(r - l + 1, max_len) return max_lenTime and Space Complexity
You should aim for a solution with
**O(n)**time and**O(m)**space, where**n**is the length of the given string and**m**is the number of unique characters in the string.
Permutation in String ==MEDIUM==
You are given two strings s1 and s2. Return true if s2 contains a permutation of s1, or false otherwise. That means if a permutation of s1 exists as a substring of s2, then return true. Both strings only contain lowercase letters.
Example 1:
Input: s1 = "abc", s2 = "lecabee"
Output: true
Explanation: The substring "cab" is a permutation of "abc" and is present in "lecabee".
Example 2:
Input: s1 = "abc", s2 = "lecaabee"
Output: false
Time and Space Complexity
You should aim for a solution with
O(n)time andO(1)space, wherenis the maximum of the lengths of the two strings.Solution
To check whether a string
s2contains a permutation of another strings1, we can use a sliding window approach. First, we create a frequency dictionary for characters ins1. Then, we initialize two pointers,leftandright, to represent the current window ins2. As we move therightpointer to the right, we add the character to a temporary frequency dictionary and check if it becomes equal to the frequency dictionary ofs1. If it does, it means we found a permutation ofs1ins2, and we return True. If the window size exceeds the length ofs1, we remove the character at theleftpointer from the temporary dictionary and move theleftpointer to the right to shrink the window. We continue this process until we find a permutation or reach the end ofs2.class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: if len(s1) > len(s2): return False char_freq_s1 = {} for char in s1: char_freq_s1[char] = char_freq_s1.get(char, 0) + 1 left, right = 0, 0 char_freq_temp = {} while right < len(s2): char_freq_temp[s2[right]] = char_freq_temp.get(s2[right], 0) + 1 if right - left + 1 == len(s1): if char_freq_temp == char_freq_s1: return True char_freq_temp[s2[left]] -= 1 if char_freq_temp[s2[left]] == 0: del char_freq_temp[s2[left]] left += 1 right += 1 return False
Stack
Valid Parentheses ==EASY==
You are given a string **s** consisting of the following characters: **'('**, **')'**, **'{'**, **'}'**, **'['** and **']'**.
The input string **s** is valid if and only if:
Every open bracket is closed by the same type of close bracket. Open brackets are closed in the correct order. Every close bracket has a corresponding open bracket of the same type.
Every open bracket is closed by the same type of close bracket.
Open brackets are closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Return **true** if **s** is a valid string, and **false** otherwise.
Example 1:
Input: s = "[]"
Output: true
Example 2:
Input: s = "([{}])"
Output: true
Example 3:
Input: s = "[(])"
Output: false
Explanation: The brackets are not closed in the correct order.
Time and Space Complexity
You should aim for a solution with
O(n)time andO(n)space, wherenis the length of the given string.Solution
To determine if a given string of parentheses
sis valid, we can use a stack data structure. We iterate through each character ins, and if the character is an opening parenthesis ((,{,[), we push it onto the stack. If the character is a closing parenthesis (),},]), we check if the stack is empty or if the top element of the stack does not match the current closing parenthesis. If either of these conditions is met, we know the string is not valid. Otherwise, we pop the top element from the stack. At the end, if the stack is empty, the string is valid.class Solution: def isValid(self, s: str) -> bool: stack = [] char_map = { ")": "(", "]": "[", "}": "{" } for char in s: if char in char_map: if stack and stack[-1] == char_map[char]: stack.pop() else: return False else: stack.append(char) return len(stack) == 0
Minimum Stack ==MEDIUM==
Design a stack class that supports the push, pop, top, and getMin operations.
MinStack() initialises the stack object.void push(int val) pushes the element val onto the stack.void pop() removes the element on the top of the stack.int top() gets the top element of the stack.int getMin() retrieves the minimum element in the stack.
MinStack()initialises the stack object.void push(int val)pushes the elementvalonto the stack.void pop()removes the element on the top of the stack.int top()gets the top element of the stack.int getMin()retrieves the minimum element in the stack.
Each function should run in O(1)O(1) time.
Example 1:
Input: ["MinStack", "push", 1, "push", 2, "push", 0, "getMin", "pop", "top", "getMin"]
Output: [null,null,null,null,0,null,2,1]
Explanation:
MinStack minStack = new MinStack();
minStack.push(1);
minStack.push(2);
minStack.push(0);
minStack.getMin(); # return 0
minStack.pop();
minStack.top(); # return 2
minStack.getMin(); # return 1
Time and Space Complexity
You should aim for a solution with
O(1)time for each function call andO(n)space, wherenis the maximum number of elements present in the stack.
Evaluate Reverse Polish Notation
You are given an array of strings **tokens** that represents a valid arithmetic expression in Reverse Polish Notation. Return the integer that represents the evaluation of the expression. The operands may be integers or the results of other operations.The operators include **'+'**, **'-'**, **'*'**, and **'/'**.Assume that division between integers always truncates toward zero.
The operands may be integers or the results of other operations.
The operators include
'+','-','*', and'/'.Assume that division between integers always truncates toward zero.
Example 1:
Input: tokens = ["1","2","+","3","*","4","-"]
Output: 5
Explanation: ((1 + 2) * 3) - 4 = 5
Time and Space Complexity
You should aim for a solution with
O(n)time andO(n)space, wherenis the size of the input array.Solution
To evaluate a given reverse Polish notation expression, we can use a stack data structure. We iterate through the tokens in the expression, and for each token, if it is a number, we push it onto the stack. If it is an operator (
+,-,*,/), we pop the top two elements from the stack, apply the operator to them, and push the result back onto the stack. At the end, the top element of the stack will be the final result of the expression.class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] for token in tokens: if token == "+": stack.append(stack.pop() + stack.pop()) elif token == "-": a, b = stack.pop(), stack.pop() stack.append(b - a) elif token == "*": stack.append(stack.pop() * stack.pop()) elif token == "/": a, b = stack.pop(), stack.pop() stack.append(int(float(b) / a)) else: stack.append(int(token)) return stack[-1]
Daily Temperatures
You are given an array of integers temperatures where temperatures[i] represents the daily temperatures on the ith day. Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the ith day, set result[i] to 0 instead.
Example 1:
Input: temperatures = [30,38,30,36,35,40,28]
Output: [1,4,1,2,1,0,0]
Example 2:
Input: temperatures = [22,21,20]
Output: [0,0,0]
Time and Space Complexity
You should aim for a solution as good or better than
O(n)time andO(n)space, wherenis the size of the input array.Solution
Create an empty list of size of the
temperaturelist filled with zeros and an empty stack. Start iterating thetemperatureslist. Pop out all the elements from the stack, if available and it’s temperature is lower than current temperature, and store the difference between the current temperature index and the popped temperature index, in the res at that popped temperature index. And finally append the index and temperature to stack, as usual.class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: stack = [] res = [0] * len(temperatures) for idx, temp in enumerate(temperatures): while stack and temp > stack[-1][1]: _idx, _temp = stack.pop() res[_idx] = idx - _idx stack.append((idx, temp)) return res
Car Fleet ==MEDIUM==
There are n cars traveling to the same destination on a one-lane highway. You are given two arrays of integers position and speed, both of length n.
position[i] is the position of the ith car (in miles)speed[i] is the speed of the ith car (in miles per hour)
position[i]is the position of theith car(in miles)speed[i]is the speed of theithcar (in miles per hour)
The destination is at position target miles.
A car can not pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it.
A car fleet is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet.
If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet.
Return the number of different car fleets that will arrive at the destination.
Example 1:
Input: target = 10, position = [1,4], speed = [3,2]
Output: 1
Explanation: The cars starting at 1 (speed 3) and 4 (speed 2) become a fleet,
meeting each other at 10, the destination.
Example 2:
Input: target = 10, position = [4,1,0,7], speed = [2,2,1,1]
Output: 3
Explanation: The cars starting at 4 and 7 become a fleet at position 10.
The cars starting at 1 and 0 never catch up to the car ahead of them.
Thus, there are 3 car fleets that will arrive at the destination.
Time and Space Complexity
You should aim for a solution with
O(nlogn)time andO(n)space, wherenis the size of the input array.Solution
Start by sorting joint
positionandspeedbasis of position. Create a stack and start appending the cars’ time taken to reach destination. The stack must keep the time taken to reach destination for that car which takes time either more or equal to current time. E.g.: If Current car will take 3 hr to reach and previous car took 4 hr to reach, these two cars create a fleet, so 4 will remain in the stack top.class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: sorted_speed_position = sorted([(p, s) for p, s in zip(position, speed)], key=lambda x : x[0], reverse=True) res = [] for i in range(len(sorted_speed_position)): travel_distance = target - sorted_speed_position[i][0] curr_speed = sorted_speed_position[i][1] time_taken = travel_distance / curr_speed if res and res[-1] >= time_taken: res.append(max(time_taken, res.pop())) else: res.append(time_taken) return len(res)
1-D Dynamic Programming
Climbing Stairs ==EASY==
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Time and Space Complexity
You should aim for a solution as good or better than
O(n)time andO(n)space, wherenis the number of steps.Brute Force
Brute force solution is to solve for all possible steps starting from 0, jump 1 or 2 steps.
Base case is reaching the step outside the range
n. When we reach a step beyond or onn, return 1 if we are atnor 0 if we are beyondn. If we are beyondnreturning 0 indicates that we have reached outside the destination and that that step is invalid.
class Solution: def climbStairs(self, n: int) -> int: def helper(i): if i >= n: return int(i == n) return helper(i + 1) + helper(i + 2) return helper(0)TIME and SPACE: $O(2^n)$ $O(2^n)$$O(n)$
Memoization
Same as brute force, but adding a cache to store the repeating cases
Add a cache dictionary to store the distinct ways for each step, and use it when the case is revisited.
class Solution: def climbStairs(self, n: int) -> int: cache = {} def helper(i): if i >= n: return int(i == n) if i in cache: return cache[i] cache[i] = helper(i + 1) + helper(i + 2) return cache[i] return helper(0)TIME and SPACE: $O(n)$ $O(2^n)$$O(n)$
Min Cost Climbing Stairs ==EASY==
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.
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.
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.
Time and Space Complexity
You should aim for a solution as good or better than
O(n)time andO(n)space, wherenis the number of steps on the staircase.Brute Force
Using a recursion approach, we can visit all possible steps to check for best minimum cost.
We start from 0 and move bottom to reach the final destination. Base case would be when we reach beyond the stairs. In that case, 0 will be returned, indicating that path is not possible.
For all other cases, current + 1 and current + 2 steps will be visited and only the minimum of those two will be considered. With that the cost for current step will be added.
When the recursion has finished for 0, for 1 the same will be done and the minimum of both will be returned.
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: size = len(cost) def helper(i): if i >= size: return 0 return min(helper(i + 1), helper(i + 2)) + cost[i] return min(helper(0), helper(1))TIME and SPACE: $O(2^n)$ $O(2^n)$$O(n)$
Memoization
- Same as above, using recursion to cover all possible steps, but caching the visited steps for reference.
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: cache = {} n = len(cost) def helper(i): if i >= n: return 0 if i in cache: return cache[i] cache[i] = min(helper(i + 1), helper(i + 2)) + cost[i] return cache[i] return min(helper(0), helper(1))TIME and SPACE: $O(n)$ $O(2^n)$$O(n)$
House Robber [Leetcode] ==MEDIUM==
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.
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.
Brute Force
Start from the 0th house, move to
i+2th house ori+3th house, chose the max amongst them and add the cost forith house.Base case would be when we have reached the end of list or have reached beyond the list.
class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) def helper(i): if i >= n: return 0 return max(helper(i + 2), helper(i + 3)) + nums[i] return max(helper(0), helper(1))Optimized (Memoization)
- Add a cache dictionary to store visited cases and use them when they are visited again.
class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) cache = {} def helper(i): if i >= n: return 0 if i in cache: return cache[i] cache[i] = max(helper(i + 2), helper(i + 3)) + nums[i] return cache[i] return max(helper(0), helper(1))
House Robber II (Leetcode) ==MEDIUM==
You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbours. You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into. Return the maximum amount of money you can rob without alerting the police.
Input: nums = [3,4,3]
Output: 4
Input: nums = [2,9,8,3,6]
Output: 15
# Explanation: You cannot rob nums[0] + nums[2] + nums[4] = 16 because nums[0] and nums[4] are adjacent houses. The maximum you can rob is nums[1] + nums[4] = 15.
Time and Space Complexity
You should aim for a solution as good or better than
O(n)time andO(n)space, wherenis the number of houses.Brute Force (Recursion)
Optimized (Memoization)
class Solution: def rob(self, nums: List[int]) -> int: size = len(nums) if size == 1: return nums[size - 1] cache = {} def helper(i: int, flag: bool): if i >= size or (flag and i == size - 1): return 0 if (i, flag) in cache: return cache[(i, flag)] cache[(i, flag)] = max( helper(i + 1, flag), helper(i + 2, flag or i == 0) + nums[i], ) return cache[(i, flag)] return max(helper(0, True), helper(1, False))
Xet Storage Details
- Size:
- 55.6 kB
- Xet hash:
- cfa7857dc338864a67e13a394dd5040acaa04decc678cd06f7a47e84900a8d0d
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.