DenCT/test-storage / Notion /Data Structures and Algorithms.md
DenCT's picture
|
download
raw
55.6 kB

Table of Contents

  • Arrays and Hashing

    • Contains Duplicate

    • Valid Anagram

    • Two Sum

    • Group Anagrams

    • Set Matrix Zeroes

    • Top K Frequent Elements

    • Products of Array Except itself

    • Longest Consecutive Sequence

  • Two Pointers

    • Valid Palindrome

    • Two Sum II

    • 3 Sum

    • Container with most Water

    • Trapping Rain Water

  • Sliding Window

    • Best time to buy and sell stock

    • Longest Substring without repeating Characters

    • Longest repeating character replacements

    • Permutation in string

  • Stack

    • Valid parentheses

    • Minimum stack

    • Evaluate Reverse Polish Notation

  • Binary Search

  • Linked List

  • Trees

  • Heap/Priority Queue

  • Backtracking

  • Tries

  • Graph

  • Advanced Graph

  • 1D Dynamic Programming

  • 2D Dynamic Programming

  • Greedy

  • Intervals

  • Math Geometry

  • Bit Manipulation

Foreword

Here are some tricks to remember when solving a problem.

  1. 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 and O(n) space, where n is 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 and O(1) space, where n is the length of the string s and m is the length of the string t.

Solution:

  • Brute force

    class Solution:
        def isAnagram(self, s: str, t: str) -> bool:
            s, t = sorted(s), sorted(t)
            return s == t
    

    Simply 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_map
    

    Keep 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 and O(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 and O(m) space, where m is the number of strings and n is 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 complexity

    1. Loop over each cell in the matrix.

    2. 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.

    3. Set all non-zero elements to -1 in the traversing row and column.

    4. 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] = 0
    
  • Optimized Solution - **O(m*n)+O(m*n)** time complexity, **O(m+n)** space complexity

    1. Create two 1-D arrays, one of the length of row and one of the length of column.

    2. Loop over each cell in the matrix.

    3. 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

    4. Repeat step 3 for all elements in the matrix.

    5. 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 complexity

    class 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 and O(n) space, where n is the size of the input array

  • Brute Force

    1. Keep a dictionary to store count of each element in the array

    2. 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

    1. First, keep a counter for items of the list. This will have all the item and their counts in the list.

    2. Then create an empty list of list, with index being the counts from 0 to n + 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],[]...[]] .

    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

    1. 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.

    2. 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.

    3. If the above case passes, then an array of size of the input array is created, and filled with zeroes.

    4. Loop over the elements of the input array. If the item at current index is non-zero, add the product // num if zero count is < 1 else put 0 to the result array at that index. If the item is zero: put product at the index.

    5. 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 res
    
  • Prefix 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 True
    

    To 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.

    1. Start with two pointers, one at the start other at the end of string, and start moving both towards each other.

    2. if any of the characters at l or r is not alphanumeric, the pointer is moved forward or backward.

    3. If the character at l and r are not same when they are lowercase, False is returned, else the pointers are moved forward and backward.

    4. At the end, True is 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 and O(1) space, where n is 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]
  1. Start with two pointers, l and r , one in the starting of string and other at the end.

  2. Calculate the sum of the numbers that are in the l and r pointers. If the sum is lesser than target, move l forward and if sum is greater than target, move r backward.

  3. 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 nums in 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 and O(1) space, where n is 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_vol
    
    • Time and Space complexity

      You should aim for a solution with O(n) time and O(1) space, where n is 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 and O(n) space, where n is 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 and O(1) space, where n is 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_price to keep track of the minimum price seen so far, and max_profit to store the maximum profit. We iterate through the prices array, and for each price, we update the min_price if we find a smaller price. We also calculate the potential profit if we sell at the current price and update max_profit if 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 and O(m) space, where n is the length of the string and m is 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 k distinct 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 dictionary to keep track of their frequencies. If the number of distinct characters in the window exceeds k, we move the left pointer to the right to shrink the window until the number of distinct characters is k again. 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_len
    
    • Time 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 and O(1) space, where n is the maximum of the lengths of the two strings.

  • Solution

    To check whether a string s2 contains a permutation of another string s1, we can use a sliding window approach. First, we create a frequency dictionary for characters in s1. Then, we initialize two pointers, left and right, to represent the current window in s2. As we move the right pointer to the right, we add the character to a temporary frequency dictionary and check if it becomes equal to the frequency dictionary of s1. If it does, it means we found a permutation of s1 in s2, and we return True. If the window size exceeds the length of s1, we remove the character at the left pointer from the temporary dictionary and move the left pointer to the right to shrink the window. We continue this process until we find a permutation or reach the end of s2.

    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 and O(n) space, where n is the length of the given string.

  • Solution

    To determine if a given string of parentheses s is valid, we can use a stack data structure. We iterate through each character in s, 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 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.

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 and O(n) space, where n is 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 and O(n) space, where n is 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 and O(n) space, where n is the size of the input array.

  • Solution

    Create an empty list of size of the temperature list filled with zeros and an empty stack. Start iterating the temperatures list. 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 the ith car (in miles)

  • speed[i] is the speed of the ith car (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 and O(n) space, where n is the size of the input array.

  • Solution

    Start by sorting joint position and speed basis 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 and O(n) space, where n is the number of steps.

  • Brute Force

    1. Brute force solution is to solve for all possible steps starting from 0, jump 1 or 2 steps.

    2. Base case is reaching the step outside the range n . When we reach a step beyond or on n , return 1 if we are at n or 0 if we are beyond n . If we are beyond n returning 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

    1. Same as brute force, but adding a cache to store the repeating cases

    2. 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 and O(n) space, where n is the number of steps on the staircase.

  • Brute Force

    1. Using a recursion approach, we can visit all possible steps to check for best minimum cost.

    2. 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.

    3. 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.

    4. 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

    1. 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

    1. Start from the 0th house, move to i+2 th house or i+3 th house, chose the max amongst them and add the cost for i th house.

    2. 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)

    1. 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 and O(n) space, where n is 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.