Hasuer's Studio.

32. Test Your Knowledge (Medium)

Grokking Interview Pattern Interview
Word count: 19.8kReading time: 123 min
2024/06/01

Daily Temperatures

Problem Statement

You are given a list of daily temperatures. Your task is to return an answer array such that answer[i] is the number of days you would have to wait until a warmer temperature for each of the days. If there is no future day for which this is possible, put 0 instead.

Examples

    • Input: [45, 50, 40, 60, 55]
    • Expected Output: [1, 2, 1, 0, 0]
    • Justification: The next day after the first day is warmer (50 > 45). Two days after the second day, the temperature is warmer (60 > 50).. The next day after the third day is warmer (60 > 40). There are no warmer days after the fourth and fifth days.
    • Input: [80, 75, 85, 90, 60]
    • Expected Output: [2, 1, 1, 0, 0]
    • Justification: Two days after the first day, the temperature is warmer (85 > 80). The next day after the second day is warmer (85 > 75). The next day after the third day is warmer (90 > 85). There are no warmer days after the fourth and fifth days.
    • Input: [32, 32, 32, 32, 32]
    • Expected Output: [0, 0, 0, 0, 0]
    • Justification: All the temperatures are the same, so there are no warmer days ahead.

Constraints:

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

Solution

  • Understanding the Problem:
    • The problem is to find the number of days until a warmer day for each day in the list.
  • Approach:
    • Use a stack to keep track of the indices of the days.
    • Iterate through the list of temperatures.
      • While the stack is not empty and the current temperature is greater than the temperature at the index at the top of the stack:
        • Pop an index from the stack and calculate the difference between the current day and the popped index.
        • Store this difference at the popped index in the result array.
      • Push the current day’s index onto the stack.
  • Why This Works:
    • The stack keeps track of the days for which a warmer day has not yet been found.
    • When a warmer day is found, the days are popped from the stack and the difference in days is calculated.

Algorithm Walkthrough

Consider the input [45, 50, 40, 60, 55]:

  • Initialize an empty stack and a result array filled with zeros: stack = [], res = [0, 0, 0, 0, 0].
  • Iterate through the list:
    • Day 1 (45): stack = [0].
    • Day 2 (50): Pop 0 from stack, res[0] = 1 - 0 = 1, stack = [1].
    • Day 3 (40): stack = [1, 2].
    • Day 4 (60): Pop 2 from stack, res[2] = 3 - 2 = 1, Pop 1 from stack, res[1] = 3 - 1 = 2, stack = [3].
    • Day 5 (55): stack = [3, 4].
  • End of iteration, res = [1, 2, 1, 0, 0].

Code Development

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def dailyTemperatures(self, temperatures):
        # Initialize an empty stack and a result list filled with zeros
        stack = []
        res = [0] * len(temperatures)
        # Iterate through the list of temperatures
        for i, temp in enumerate(temperatures):
            # Pop indices from the stack while the current temperature is greater than the temperature at the popped index
            while stack and temp > temperatures[stack[-1]]:
                idx = stack.pop()
                res[idx] = i - idx
            # Push the current index onto the stack
            stack.append(i)
        # Return the final result list
        return res

# Testing the algorithm
solution = Solution()
example1 = [45, 50, 40, 60, 55]
example2 = [80, 75, 85, 90, 60]
example3 = [32, 32, 32, 32, 32]
# Output: [1, 2, 1, 0, 0]
print(solution.dailyTemperatures(example1))
# Output: [2, 1, 1, 0, 0]
print(solution.dailyTemperatures(example2))
# Output: [0, 0, 0, 0, 0]
print(solution.dailyTemperatures(example3))

Complexity Analysis

  • Time Complexity: O(n), where n is the number of temperatures. This is because the algorithm iterates through the list of temperatures once, performing constant-time operations for each temperature.
  • Space Complexity: O(n), as it uses a stack to keep track of indices.

Group Anagrams

Problem Statement

Given a list of strings, the task is to group the anagrams together.

An anagram is a word or phrase formed by rearranging the letters of another, such as “cinema”, formed from “iceman”.

Example Generation

Example 1:

  • Input: ["dog", "god", "hello"]
  • Output: [["dog", "god"], ["hello"]]
  • Justification: “dog” and “god” are anagrams, so they are grouped together. “hello” does not have any anagrams in the list, so it is in its own group.

Example 2:

  • Input: ["listen", "silent", "enlist"]
  • Output: [["listen", "silent", "enlist"]]
  • Justification: All three words are anagrams of each other, so they are grouped together.

Example 3:

  • Input: ["abc", "cab", "bca", "xyz", "zxy"]
  • Output: [["abc", "cab", "bca"], ["xyz", "zxy"]]
  • Justification: “abc”, “cab”, and “bca” are anagrams, as are “xyz” and “zxy”.

Constraints:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Solution

  • Sorting Approach:
    • For each word in the input list:
      • Sort the letters of the word.
      • Use the sorted word as a key in a hash map, and add the original word to the list of values for that key.
    • The hash map values will be the groups of anagrams.
  • Why This Will Work:
    • Anagrams will always result in the same sorted word, so they will be grouped together in the hash map.

Algorithm Walkthrough

  • Given the input ["abc", "cab", "bca", "xyz", "zxy"]
  • For “abc”:
    • Sorted word is “abc”.
    • Add “abc” to the hash map with key “abc”.
  • For “cab”:
    • Sorted word is “abc”.
    • Add “cab” to the list in the hash map with key “abc”.
  • Continue this process for all words.
  • The hash map values are the groups of anagrams.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def groupAnagrams(self, strs):
        # Dictionary to hold sorted word as key and list of words as value
        d = {}
        for s in strs:
            sorted_str = ''.join(sorted(s))
            # If the sorted word is not already a key in the dictionary, add it with a new list as its value
            if sorted_str not in d:
                d[sorted_str] = []
            # Add the original word to the list of values for the sorted word key
            d[sorted_str].append(s)
        # Return the values of the dictionary as a list of lists
        return list(d.values())

# Testing the function
sol = Solution()
print(sol.groupAnagrams(["dog", "god", "hello"]))
print(sol.groupAnagrams(["listen", "silent", "enlist"]))
print(sol.groupAnagrams(["abc", "cab", "bca", "xyz", "zxy"]))

Complexity Analysis

  • Time Complexity: O(nklog(k)), where n is the number of strings, and k is the maximum length of a string in strs. This is because each of the n strings is sorted in O(k*log(k)) time.
  • Space Complexity: O(n*k), where n is the number of strings, and k is the maximum length of a string in strs. This space is used for the output data structure and the hash map.

Decode String

Problem Statement

You have a string that represents encodings of substrings, where each encoding is of the form k[encoded_string], where k is a positive integer, and encoded_string is a string that contains letters only.

Your task is to decode this string by repeating the encoded_string k times and return it. It is given that k is always a positive integer.

Examples

    • Input: "3[a3[c]]"
    • Expected Output: "acccacccaccc"
    • Justification: The inner 3[c] is decoded as ccc, and then a is appended to the front, forming acc. This is then repeated 3 times to form acccacccaccc.
    • Input: "2[b3[d]]"
    • Expected Output: "bdddbddd"
    • Justification: The inner 3[d] is decoded as ddd, and then b is appended to the front, forming bddd. This is then repeated 2 times to form bddd bddd.
    • Input: "4[z]"
    • Expected Output: "zzzz"
    • Justification: The 4[z] is decoded as z repeated 4 times, forming zzzz.

Constraints:

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets ‘[]’.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].

Solution

  • Understanding the Problem:
    • The problem involves decoding a string that contains patterns where a number is followed by a string in brackets.
    • The number indicates how many times the string in brackets should be repeated.
  • Approach:
    • Use a stack to keep track of the characters in the string.
    • Iterate through the string character by character.
    • When a number is encountered, calculate the complete number.
    • When an opening bracket [ is encountered, push the calculated number to the stack.
    • When a closing bracket ] is encountered, pop elements from the stack until a number is encountered and form the substring to be repeated.
    • Multiply the substring with the number and push the result back to the stack.
  • Handling Nested Brackets:
    • The stack will naturally handle nested brackets as it will continue popping elements until a number is encountered, forming the substring for the innermost bracket first.

Algorithm Walkthrough

  • Given Input: "3[a3[c]]"
  • Steps:
    • Initialize an empty stack.
    • Iterate through the string:
      • Encounter 3, push 3 to the stack.
      • Encounter [, do nothing.
      • Encounter a, push a to the stack.
      • Encounter 3, push 3 to the stack.
      • Encounter [, do nothing.
      • Encounter c, push c to the stack.
      • Encounter ], pop c and 3, form ccc and push it back to the stack.
      • Encounter ], pop ccc, a, and 3, form acccacccaccc and push it back to the stack.
    • The final stack contains acccacccaccc as the only element, which is the decoded string.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        num = 0
        curr_str = ""
        for c in s:
            if c.isdigit():
                # Calculate the number
                num = num * 10 + int(c)
            elif c == '[':
                # Push the number and current string to the stack
                stack.append(num)
                stack.append(curr_str)
                num = 0
                curr_str = ""
            elif c == ']':
                # Pop elements to form the substring and push the result back
                prev_str = stack.pop()
                repeat = stack.pop()
                curr_str = prev_str + curr_str * repeat
            else:
                # Append the character to the current string
                curr_str += c
        return curr_str

# Testing the function
sol = Solution()
print(sol.decodeString("3[a3[c]]"))  # Output: acccacccaccc
print(sol.decodeString("2[b3[d]]"))  # Output: bdddbddd
print(sol.decodeString("4[z]"))  # Output: zzzz

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string. This is because we are iterating through the string once and processing each character.
  • Space Complexity: O(n), where n is the length of the input string. In the worst case, the stack will store all the characters of the input string.

Valid Sudoku

Problem Statement

Determine if a 9x9 Sudoku board is valid. A valid Sudoku board will hold the following conditions:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. The 9 3x3 sub-boxes of the grid must also contain the digits 1-9 without repetition.

Note:

  1. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
  2. You need to validate only filled cells.

Example 1:

  • Input:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    [["5","3",".",".","7",".",".",".","."]
    ,["6",".",".","1","9","5",".",".","."]
    ,[".","9","8",".",".",".",".","6","."]
    ,["8",".",".",".","6",".",".",".","3"]
    ,["4",".",".","8",".","3",".",".","1"]
    ,["7",".",".",".","2",".",".",".","6"]
    ,[".","6",".",".",".",".","2","8","."]
    ,[".",".",".","4","1","9",".",".","5"]
    ,[".",".",".",".","8",".",".","7","9"]]

  • Expected Output: true

  • Justification: This Sudoku board is valid as it adheres to the rules of no repetition in each row, each column, and each 3x3 sub-box.

Example 2:

  • Input:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    [["8","3",".",".","7",".",".",".","."]
    ,["6",".",".","1","9","5",".",".","."]
    ,[".","9","8",".",".",".",".","6","."]
    ,["8",".",".",".","6",".",".",".","3"]
    ,["4",".",".","8",".","3",".",".","1"]
    ,["7",".",".",".","2",".",".",".","6"]
    ,[".","6",".",".",".",".","2","8","."]
    ,[".",".",".","4","1","9",".",".","5"]
    ,[".",".",".",".","8",".",".","7","9"]]

  • Expected Output: false

  • Justification: The first and fourth rows both contain the number ‘8’, violating the Sudoku rules.

Example 3:

  • Input:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    [[".",".","4",".",".",".","6","3","."]
    ,[".",".",".",".",".",".",".",".","."]
    ,["5",".",".",".",".",".",".","9","."]
    ,[".",".",".","5","6",".",".",".","."]
    ,["4",".","3",".",".",".",".",".","1"]
    ,[".",".",".","7",".",".",".",".","."]
    ,[".",".",".","5",".",".",".",".","."]
    ,[".",".",".",".",".",".",".",".","."]
    ,[".",".",".",".",".",".",".",".","."]]

  • Expected Output: false

  • Justification: The fourth column contains the number ‘5’ two times, violating the Sudoku rules.

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or ‘.’.

Solution

  • Initialization:
    • Create three hash sets for rows, columns, and boxes to keep track of the seen numbers.
  • Iteration:
    • Iterate through each cell in the 9x9 board.
      • If the cell is not empty:
        • Formulate keys for the row, column, and box that include the current number and its position.
        • Check the corresponding sets for these keys.
          • If any key already exists in the sets, return false.
          • Otherwise, add the keys to the respective sets.
  • Final Check:
    • If the iteration completes without finding any repetition, return true.

This approach works because it checks all the necessary conditions for a valid Sudoku by keeping track of the numbers in each row, column, and box using hash sets. The use of hash sets allows for efficient lookups to ensure no numbers are repeated in any row, column, or box.

Algorithm Walkthrough

Consider Example 2 from above:

  • Initialize three empty hash sets for rows, columns, and boxes.
  • Start iterating through each cell in the board.
    • For the first cell, which contains ‘8’:
      • Formulate keys: row0(8), col0(8), and box0(8).
      • Since these keys are not in the sets, add them.
    • Continue this for other cells.
    • Upon reaching the first cell of the fourth row, which also contains ‘8’:
      • Formulate keys: row3(8), col0(8), and box1(8).
      • The key col0(8) already exists in the column set, so return false.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def isValidSudoku(self, board):
        # Initialize sets to keep track of the numbers in each row, column, and box.
        rows = set()
        columns = set()
        boxes = set()

        # Iterate through each cell in the 9x9 board.
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != '.':
                    # Formulate keys for the row, column, and box.
                    row_key = f"row{i}({num})"
                    col_key = f"col{j}({num})"
                    box_key = f"box{i // 3 * 3 + j // 3}({num})"
                    # Check the corresponding sets for these keys.
                    if (row_key in rows or col_key in columns or box_key in boxes):
                        return False
                    rows.add(row_key)
                    columns.add(col_key)
                    boxes.add(box_key)
        return True

# Testing the code
sol = Solution()
board1 = [
    ['5','3','.','.','7','.','.','.','.'],
    ['6','.','.','1','9','5','.','.','.'],
    ['.','9','8','.','.','.','.','6','.'],
    ['8','.','.','.','6','.','.','.','3'],
    ['4','.','.','8','.','3','.','.','1'],
    ['7','.','.','.','2','.','.','.','6'],
    ['.','6','.','.','.','.','2','8','.'],
    ['.','.','.','4','1','9','.','.','5'],
    ['.','.','.','.','8','.','.','7','9']
]
print(sol.isValidSudoku(board1))  # Output: True

Complexity Analysis

  • Time Complexity: O(1) or O(81), as we only iterate through the 9x9 board once.
  • Space Complexity: O(1) or O(81), as the maximum size of our sets is 81.

Product of Array Except Self

Problem Statement

Given an array of integers, return a new array where each element at index i of the new array is the product of all the numbers in the original array except the one at i. You must solve this problem without using division.

Examples

    • Input: [2, 3, 4, 5]
    • Expected Output: [60, 40, 30, 24]
    • Justification: For the first element: 3*4*5 = 60, for the second element: 2*4*5 = 40, for the third element: 2*3*5 = 30, and for the fourth element: 2*3*4 = 24.
    • Input: [1, 1, 1, 1]
    • Expected Output: [1, 1, 1, 1]
    • Justification: Every element is 1, so the product of all other numbers for each index is also 1.
    • Input: [10, 20, 30, 40]
    • Expected Output: [24000, 12000, 8000, 6000]
    • Justification: For the first element: 20*30*40 = 24000, for the second element: 10*30*40 = 12000, for the third element: 10*20*40 = 8000, and for the fourth element: 10*20*30 = 6000.

Constraints:

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution

  • Initialize Two Arrays:
    • Start by initializing two arrays, left and right. The left array will hold the product of all numbers to the left of index i, and the right array will hold the product of all numbers to the right of index i.
  • Populate the Left Array:
    • The first element of the left array will always be 1 because there are no numbers to the left of the first element.
    • For the remaining elements, each value in the left array is the product of its previous value and the corresponding value in the input array.
  • Populate the Right Array:
    • Similarly, the last element of the right array will always be 1 because there are no numbers to the right of the last element.
    • For the remaining elements, each value in the right array is the product of its next value and the corresponding value in the input array.
  • Calculate the Result:
    • For each index i, the value in the result array will be the product of left[i] and right[i].

Algorithm Walkthrough

Using the input [2, 3, 4, 5]:

  1. Initialize left and right arrays with the same length as the input array and fill them with 1.
  2. Populate the left array:
    • left[0] = 1
    • left[1] = left[0] * input[0] = 2
    • left[2] = left[1] * input[1] = 6
    • left[3] = left[2] * input[2] = 24
  3. Populate the right array:
    • right[3] = 1
    • right[2] = right[3] * input[3] = 5
    • right[1] = right[2] * input[2] = 20
    • right[0] = right[1] * input[1] = 60
  4. Calculate the result:
    • result[0] = left[0] * right[0] = 60
    • result[1] = left[1] * right[1] = 40
    • result[2] = left[2] * right[2] = 30
    • result[3] = left[3] * right[3] = 24

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        left, right, result = [1] * n, [1] * n, [1] * n

        # Populate the left array
        for i in range(1, n):
            left[i] = left[i - 1] * nums[i - 1]

        # Populate the right array
        for i in range(n - 2, -1, -1):
            right[i] = right[i + 1] * nums[i + 1]

        # Calculate the result array
        for i in range(n):
            result[i] = left[i] * right[i]

        return result

# Testing the function
sol = Solution()
print(sol.productExceptSelf([2, 3, 4, 5]))
print(sol.productExceptSelf([1, 1, 1, 1]))
print(sol.productExceptSelf([10, 20, 30, 40]))

Complexity Analysis:

  • Time Complexity: O(n). We traverse the input array three times, so the time complexity is linear.
  • Space Complexity: O(n). We use three additional arrays (left, right, and result).

Maximum Product Subarray

Problem Statement

Given an integer array, find the contiguous subarray (at least one number in it) that has the maximum product. Return this maximum product.

Examples

    • Input: [2,3,-2,4]
    • Expected Output: 6
    • Justification: The subarray [2,3] has the maximum product of 6.
    • Input: [-2,0,-1]
    • Expected Output: 0
    • Justification: The subarray [0] has the maximum product of 0.
    • Input: [-2,3,2,-4]
    • Expected Output: 48
    • Justification: The subarray [-2,3,2,-4] has the maximum product of 48.

Constraints:

  • 1 <= nums.length <= 2*104
  • -10 <= nums[i] <= 10
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution

  • Initialization:
    • Start by initializing two variables, maxCurrent and minCurrent, to the first element of the array. These variables will keep track of the current maximum and minimum product, respectively.
    • Also, initialize a variable maxProduct to the first element of the array. This will store the maximum product found so far.
  • Iterate through the array:
    • For each number in the array (starting from the second number), calculate the new maxCurrent by taking the maximum of the current number, the product of maxCurrent and the current number, and the product of minCurrent and the current number.
    • Similarly, calculate the new minCurrent by taking the minimum of the current number, the product of maxCurrent and the current number, and the product of minCurrent and the current number.
    • Update maxProduct by taking the maximum of maxProduct and maxCurrent.
  • Handle negative numbers:
    • Since a negative number can turn a large negative product into a large positive product, we need to keep track of both the maximum and minimum product at each step.
  • Return the result:
    • After iterating through the entire array, maxProduct will have the maximum product of any subarray.

Algorithm Walkthrough

Using the input [2,3,-2,4]:

  • Start with maxCurrent = 2, minCurrent = 2, and maxProduct = 2.
  • For the next number, 3:
    • New maxCurrent = max(3, 2 * 3) = 6
    • New minCurrent = min(3, 2 * 3) = 3
    • Update maxProduct = max(2, 6) = 6
  • For the next number, -2:
    • New maxCurrent = max(-2, 3*(-2)) = -2
    • New minCurrent = min(-2, 6*(-2)) = -12
    • maxProduct remains 6
  • For the last number, 4:
    • New maxCurrent = max(4, -2*4) = 4
    • New minCurrent = min(4, -12*4) = -48
    • maxProduct remains 6
  • The final answer is 6.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def maxProduct(self, nums):
        # Base case: if the list is empty
        if not nums:
            return 0

        # Initialize the current maximum, minimum, and the result
        maxCurrent = minCurrent = maxProduct = nums[0]

        # Iterate through the list starting from the second element
        for i in range(1, len(nums)):
            # If the current number is negative, swap max and min
            if nums[i] < 0:
                maxCurrent, minCurrent = minCurrent, maxCurrent
            
            # Update maxCurrent for the current number
            maxCurrent = max(nums[i], maxCurrent * nums[i])
            
            # Update minCurrent for the current number
            minCurrent = min(nums[i], minCurrent * nums[i])
            
            # Update the result
            maxProduct = max(maxProduct, maxCurrent)

        return maxProduct

sol = Solution()
print(sol.maxProduct([2,3,-2,4]))  # 6
print(sol.maxProduct([-2,0,-1]))  # 0
print(sol.maxProduct([-2,3,2,-4]))  # 48

Complexity Analysis

  • Time Complexity: O(n) - We iterate through the array only once.
  • Space Complexity: O(1) - We use a constant amount of space regardless of the input size.

Container With Most Water

Problem Statement

Given an array of non-negative integers, where each integer represents the height of a vertical line positioned at index i. You need to find the two lines that, when combined with the x-axis, form a container that can hold the most water.

The goal is to find the maximum amount of water (area) that this container can hold.

Note: The water container’s width is the distance between the two lines, and its height is determined by the shorter of the two lines.

Examples

Example 1:

  • Input: [1,3,2,4,5]
  • Expected Output: 9
  • Justification: The lines at index 1 and 4 form the container with the most water. The width is 3 (4-1), and the height is determined by the shorter line, which is 3. Thus, the area is 3 3 = 9.

Example 2:

  • Input: [5,2,4,2,6,3]
  • Expected Output: 20
  • Justification: The lines at index 0 and 4 form the container with the most water. The width is 5 (4-0), and the height is determined by the shorter line, which is 5. Thus, the area is 5 4 = 20.

Example 3:

  • Input: [2,3,4,5,18,17,6]
  • Expected Output: 17
  • Justification: The lines at index 4 and 5 form the container with the most water. The width is 17 (5-4), and the height is determined by the shorter line, which is 17. Thus, the area is 17 1 = 17.

Constraints:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

Solution

The “Container With Most Water” problem can be efficiently solved using a two-pointer approach. The essence of the solution lies in the observation that the container’s capacity is determined by the length of the two lines and the distance between them.

By starting with two pointers at the extreme ends of the array and moving them toward each other, we can explore all possible container sizes. At each step, we calculate the area and update our maximum if the current area is larger. The key insight is to always move the pointer pointing to the shorter line, as this has the potential to increase the container’s height and, thus, its capacity.

  1. Initialization: Begin by initializing two pointers, one at the start (left) and one at the end (right) of the array. Also, initialize a variable maxArea to store the maximum area found.
  2. Pointer Movement: At each step, calculate the area formed by the lines at the left and right pointers. If this area is greater than maxArea, update maxArea. Then, move the pointer pointing to the shorter line towards the other pointer. This is because by moving the taller line, we might miss out on a larger area, but by moving the shorter line, we have a chance of finding a taller line and, thus a larger area.
  3. Termination: Continue moving the pointers until they meet. At this point, we have considered all possible pairs of lines.
  4. Return: Once the pointers meet, return the maxArea.

Algorithm Walkthrough

Using the input [1,3,2,4,5]:

  • Initialize left to 0 and right to 4. maxArea is 0.
  • Calculate area with left and right: min(1,5) * (4-0) = 4. Update maxArea to 4.
  • Move the left pointer to 1 since height at left is shorter.
  • Calculate area with left and right: min(3,5) * (4-1) = 9. Update maxArea to 9.
  • Move the left pointer to 2.
  • Calculate area with left and right: min(2,5) * (4-2) = 4. maxArea remains 9.
  • Move the left pointer to 3.
  • Calculate area with left and right: min(4,5) * (4-3) = 4. maxArea remains 9.
  • Pointers meet. Return maxArea which is 9.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxArea(self, height):
        left, right = 0, len(height) - 1  # Initialize pointers at the start and end
        maxArea = 0  # To store the maximum area found

        while left < right:
            minHeight = min(height[left], height[right])  # Find the shorter of the two lines
            maxArea = max(maxArea, minHeight * (right - left))  # Compute the area and update maxArea if needed

            # Move the pointer pointing to the shorter line
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return maxArea

sol = Solution()
print(sol.maxArea([1,3,2,4,5]))  # Expected output: 9
print(sol.maxArea([5,2,4,2,6,3]))  # Expected output: 20
print(sol.maxArea([2,3,4,5,18,17,6]))  # Expected output: 17

Complexity Analysis:

  • Time Complexity: O(n) - We traverse the array once using two pointers.
  • Space Complexity: O(1) - We use a constant amount of space.

Palindromic Substrings

Problem Statement

Given a string, determine the number of palindromic substrings present in it.

A palindromic substring is a sequence of characters that reads the same forwards and backward. The substring can be of any length, including 1.

Example

    • Input: “racecar”
    • Expected Output: 10
    • Justification: The palindromic substrings are “r”, “a”, “c”, “e”, “c”, “a”, “r”, “cec”, “aceca”, “racecar”.
    • Input: “noon”
    • Expected Output 6
    • Justification: The palindromic substrings are “n”, “o”, “o”, “n”, “oo”, “noon”.
    • Input: “apple”
    • Expected Output: 6
    • Justification: The palindromic substrings are “a”, “p”, “p”, “l”, “e”, “pp”.

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Solution

The core idea behind the algorithm is to consider each character in the string as a potential center of a palindrome and then expand outwards from this center to identify all palindromic substrings.

By doing this for every character in the string, we can efficiently count all such substrings. This approach is based on the observation that every palindromic substring has a center (or two centers for even-length palindromes).

  1. Initialization: Begin by initializing a counter to zero. This counter will be used to keep track of the number of palindromic substrings.
  2. Center Expansion: For each character in the string, treat it as the center of a possible palindrome. There are two scenarios to consider: odd-length palindromes (with a single center) and even-length palindromes (with two centers). For each character, expand outwards and check for both scenarios.
  3. Palindrome Check: As you expand outwards from the center, compare the characters. If they are the same, increment the counter. If they are different or if you’ve reached the boundary of the string, stop expanding.
  4. Result: Once all characters have been treated as centers and all possible expansions have been checked, the counter will hold the total number of palindromic substrings.

Algorithm Walkthrough

Using the input “noon”:

  • Start with the first character “n”:
    • Treat it as the center of an odd-length palindrome. No expansion is possible.
    • Treat it as the left center of an even-length palindrome. The right center would be “o”. Since “n” and “o” are different, no expansion is possible.
  • Move to the second character “o”:
    • Treat it as the center of an odd-length palindrome. No expansion is possible.
    • Treat it as the left center of an even-length palindrome. The right center is also “o”. Increment the counter.
  • Continue this process for each character in the string.
  • The final count is 7.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def countSubstrings(self, s: str) -> int:
        # Helper function to expand from the center
        def expandFromCenter(s, left, right):
            count = 0
            # Check for palindrome while staying within string boundaries
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
            return count

        count = 0
        for i in range(len(s)):
            # Check for odd length palindromes
            count += expandFromCenter(s, i, i)
            # Check for even length palindromes
            count += expandFromCenter(s, i, i + 1)

        return count

# Test the algorithm
sol = Solution()
print(sol.countSubstrings("racecar"))  # 10
print(sol.countSubstrings("noon"))  # 6
print(sol.countSubstrings("apple"))  # 6

Complexity Analysis:

  • Time Complexity: O(n^2). For each character in the string, we might expand outwards up to n times.
  • Space Complexity: O(1). We are not using any additional data structures that scale with the input size.

Remove Nth Node From End of List

Problem Statement

Given a linked list, remove the last nth node from the end of the list and return the head of the modified list.

Example 1:

  • Input: list = 1 -> 2 -> 3 -> 4 -> 5, n = 2
  • Expected Output: 1 -> 2 -> 3 -> 5
  • Justification: The 2nd node from the end is “4”, so after removing it, the list becomes [1,2,3,5].

Example 2:

  • Input: list = 10 -> 20 -> 30 -> 40, n = 4
  • Expected Output: 20 -> 30 -> 40
  • Justification: The 4th node from the end is “10”, so after removing it, the list becomes [20,30,40].

Example 3:

  • Input: list = 7 -> 14 -> 21 -> 28 -> 35, n = 3
  • Expected Output: 7 -> 14 -> 28 -> 35
  • Justification: The 3rd node from the end is “21”, so after removing it, the list becomes [7,14,28,35].

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Solution

  • Two-Pass Approach:
    • Begin by calculating the length of the linked list. This can be done by traversing the list from the head to the end.
    • Once the length is determined, calculate which node to remove by subtracting n from the length.
    • Traverse the list again and remove the node at the calculated position.
  • One-Pass Approach using Two Pointers:
    • Use two pointers, first and second, and place them at the start of the list.
    • Move the first pointer n nodes ahead in the list.
    • Now, move both first and second pointers one step at a time until the first pointer reaches the end of the list. The second pointer will now be n nodes from the end.
    • Remove the node next to the second pointer.
  • Advantage of One-Pass Approach:
    • The one-pass approach is more efficient as it traverses the list only once, whereas the two-pass approach requires two traversals.
  • Edge Cases:
    • If n is equal to the length of the list, remove the head of the list.

Algorithm Walkthrough

Using the input list = [1,2,3,4,5], n = 2:

  1. Initialize two pointers, first and second, at the head of the list.
  2. Move the first pointer 2 nodes ahead. Now, first points to “3” and second points to “1”.
  3. Move both first and second pointers one step at a time. When first reaches “5”, second will be at “3”.
  4. The next node to second is “4”, which is the node to be removed.
  5. Remove “4” by updating the next pointer of “3” to point to “5”.
  6. The modified list is [1,2,3,5].

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# class Node:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNth(head, n):
        # Create a dummy node to simplify edge cases
        dummy = Node(0)
        dummy.next = head
        first = dummy
        second = dummy

        # Move first pointer n nodes ahead
        for _ in range(n + 1):
            first = first.next

        # Move first to the end, maintaining the gap
        while first:
            first = first.next
            second = second.next

        # Remove the nth node from the end
        second.next = second.next.next
        return dummy.next

head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
result = Solution.removeNth(head, 2)
print("Nodes after removing the Nth node from the end:", end=" ")
while result:
    print(result.val, end=" ")
    result = result.next

Complexity Analysis

  • Time Complexity: O(L) - We traverse the list with two pointers. Here, L is the number of nodes in the list.
  • Space Complexity: O(1) - We only used constant extra space.

Find Minimum in Rotated Sorted Array

Problem Statement

You have an array of length n, which was initially sorted in ascending order. This array was then rotated x times. It is given that 1 <= x <= n. For example, if you rotate [1, 2, 3, 4] array 3 times, resultant array is [2, 3, 4, 1].

Your task is to find the minimum element from this array. Note that the array contains unique elements.

You must write an algorithm that runs in O(log n) time.

Example 1:

  • Input: [8, 1, 3, 4, 5]
  • Expected Output: 1
  • Justification: The smallest number in the array is 1.

Example 2:

  • Input: [4, 5, 7, 8, 0, 2, 3]
  • Expected Output: 0
  • Justification: The smallest number in the array is 0.

Example 3:

  • Input: [7, 9, 12, 3, 4, 5]
  • Expected Output: 3
  • Justification: In this rotated array, the smallest number present is 3.

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and n times.

Solution

To determine the minimum element in a rotated sorted array, we’ll leverage the binary search method.

In a standard sorted array, the elements increase (or remain the same) from left to right. But in our rotated sorted array, at some point, there will be a sudden drop, which indicates the start of the original sorted sequence and, hence, the minimum element. This drop will be our guide during the search. With binary search, we’ll repeatedly halve our search range until we pinpoint the location of this sudden drop or the smallest element.

  1. Initialization: Start with two pointers, left and right, set at the beginning and the end of the array, respectively.
  2. Binary Search Process:
    • Calculate the middle index, mid.
    • If the element at mid is greater than the element at right, this indicates that the minimum element is somewhere to the right of mid. Hence, update left to mid + 1.
    • Otherwise, the minimum element is to the left, so update right to mid.
  3. Termination: The loop will eventually lead left to point to the minimum element. This happens when left equals right.
  4. Edge Case Handling: If the array isn’t rotated at all, the smallest element will be the first. Our binary search process accounts for this scenario.

Algorithm Walkthrough

Consider the array [4, 5, 7, 8, 0, 2, 3]:

  • Start with left = 0 and right = 6.
  • Calculate mid = (0 + 6) / 2 = 3. The array element at index 3 is 8.
  • Since 8 > 3 (element at right), update left to mid + 1 = 4.
  • Now, left = 4 and right = 6. Calculate mid = (4 + 6) / 2 = 5.
  • Element at index 5 is 2. Since 2 < 3, update right to mid = 5.
  • Now, left = 4 and right = 5. Calculate mid = (4 + 5) / 2 = 4.
  • Element at index 4 is 0. Since 0 < 2, update right to mid = 4.
  • left is now equal to right, both pointing at index 4, where the minimum element 0 is present.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findMin(self, nums) -> int:
        left, right = 0, len(nums) - 1
        
        # Continue until the search range is exhausted
        while left < right:
            mid = (left + right) // 2  # Finding the middle index
            
            # If mid element is greater than the rightmost element, the minimum is on the right
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid  # Otherwise, the minimum is on the left or at mid
                
        return nums[left]  # Return the smallest element

# Test
sol = Solution()
print(sol.findMin([8, 1, 3, 4, 5]))  # Expected output: 1
print(sol.findMin([4, 5, 7, 8, 0, 2, 3]))  # Expected output: 0
print(sol.findMin([7, 9, 12, 3, 4, 5]))  # Expected output: 3

Complexity Analysis

Time Complexity: O(log n) because we are using a binary search approach, which reduces the problem size by half in each step.

Space Complexity: O(1) as we are using a constant amount of space regardless of the input size.

Pacific Atlantic Water Flow

Problem Statement:

Given a matrix m x n that represents the height of each unit cell in a Island, determine which cells can have water flow to both the Pacific and Atlantic oceans. The Pacific ocean touches the left and top edges of the continent, while the Atlantic ocean touches the right and bottom edges.

From each cell, water can only flow to adjacent cells (top, bottom, left, or right) if the adjacent cell’s height is less than or equal to the current cell’s height.

We need to return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

Example 1:

  • Input: [[1,2,3],[4,5,6],[7,8,9]]
  • Expected Output: [[0,2],[1,2],[2,0],[2,1],[2,2]]
  • Justification: The cells that can flow to both the Pacific and Atlantic oceans are
    • [0,2]:
      • To Pacific Ocean: Directly from [0,2] since it’s on the top border.
      • To Atlantic Ocean: [0,2] -> [1,2] -> [2,2].
    • [1,2]:
      • To Pacific Ocean: [1,2] -> [0,2].
      • To Atlantic Ocean: [1,2] -> [2,2].
    • [2,0]:
      • To Pacific Ocean: Directly from [2,0] since it’s on the left border.
      • To Atlantic Ocean: [2,0] -> [2,1].
    • [2,1]:
      • To Pacific Ocean: [2,1] -> [2,0].
      • To Atlantic Ocean: [2,1] -> [2,2].
    • [2,2]:
      • To Pacific Ocean: [2,2] -> [1,2] -> [0,2].
      • To Atlantic Ocean: Directly from [2,2] since it’s on the bottom-right corner.

Example 2:

  • Input: [[10,10,10],[10,1,10],[10,10,10]]
  • Expected Output: [[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]
  • Justification: The water can flow to both oceans from all cells except from the central cell [1,1].

Example 3:

  • Input: [[5,4,3],[4,3,2],[3,2,1]]
  • Expected Output: [[0,0],[0,1],[0,2],[1,0],[2,0]]
  • Justification: All the leftmost cells can have water flowing to both oceans. Similarly, top cells also satisfy the criteria.

Constraints:

  • m == matrix.length
  • n == matrix[r].length
  • 1 <= m, n <= 200
  • 0 <= matrix[r][c] <= 105

Solution

Overview: The problem is essentially asking for matrix cells from which water can flow to both the Pacific and Atlantic oceans. The matrix is viewed as an elevation map. By starting from the borders of the matrix, which are directly connected to the oceans, we can perform a Depth First Search (DFS) inwards to determine which cells can flow water to each ocean. We can then compare the results for both oceans to identify cells that can flow to both.

Detailed Explanation:

  1. Initialization:
    • Begin by creating two matrices, pacific and atlantic, of the same size as the input matrix. These matrices will be used to mark the cells that can flow water to the respective oceans.
    • The edges of the matrix adjacent to the top and left borders are considered part of the Pacific, while those adjacent to the bottom and right borders are considered part of the Atlantic.
  2. DFS Traversal:
    • Perform a Depth First Search (DFS) starting from each cell on the borders.
    • For the Pacific ocean, initiate DFS from the top and left borders. For the Atlantic ocean, initiate DFS from the bottom and right borders.
    • While traversing using DFS, move from a cell to its neighboring cells only if the neighboring cell’s height is greater than or equal to the current cell. This ensures that water can flow in that direction (from high or equal elevation to higher elevations).
    • Mark cells as visited for each ocean as you traverse to prevent reprocessing.
  3. Result Compilation:
    • After completing the DFS traversal for both oceans, iterate over the matrix to identify cells that were visited in both the pacific and atlantic matrices. These are the cells from which water can flow to both oceans.
    • Collect these cells and return them as the result.

Algorithm Walkthrough

  1. Initialization:
    • We have our input matrix: [[1,2,3],[4,5,6],[7,8,9]]
    • Create two matrices pacific and atlantic with dimensions matching the input matrix, filled with False values. These will keep track of cells water can reach from each ocean.
    • Define the matrix boundaries: top and left for Pacific, and bottom and right for Atlantic.
  2. Starting from Borders:
    • For the Pacific ocean:
      • Start DFS from the top border: [0,0], [0,1], and [0,2].
        • For [0,0] and [0,1], water cannot flow left or upwards as there’s no cell in that direction. Only downwards or to the right is possible. But since the elevation increases in both these directions, water cannot flow.
        • For [0,2] (value 3), water can flow downwards to [1,2] (value 6) as 3 < 6.
      • Start DFS from the left border: [0,0], [1,0], and [2,0].
        • Only [2,0] (value 7) can flow to [2,1] (value 8) as 7 < 8.
    • For the Atlantic ocean:
      • Start DFS from the bottom border: [2,0], [2,1], and [2,2].
        • For [2,0] and [2,1], water cannot flow downwards as there’s no cell in that direction. Only upwards or to the left/right is possible. However, only [2,1] can flow to [2,2] as 8 < 9.
        • For [2,2] (value 9), water can flow upwards to [1,2] (value 6) as 9 > 6.
      • Start DFS from the right border: [0,2] [1,2], and [2,2].
        • For [0,2], water can flow downwards as already discussed.
        • For [1,2], water can flow upwards to [0,2] and downwards to [2,2].
  3. Identifying Common Cells:
    • Iterate through the matrix and find cells where both pacific and atlantic matrices are True.
    • For our example, the cells are: [0,2], [1,2], [2,0], [2,1], and [2,2].

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
    # Define the directions for North, East, South, and West
    DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    def pacificAtlantic(self, matrix):
        # Check if the matrix is empty or has no rows/columns
        if not matrix or not matrix[0]:
            return []

        m, n = len(matrix), len(matrix[0])
        
        # Initialize two matrices to track the visited status for Pacific and Atlantic oceans
        pacific = [[False for _ in range(n)] for _ in range(m)]
        atlantic = [[False for _ in range(n)] for _ in range(m)]

        # Start the DFS traversal for each cell on the borders for both oceans
        for i in range(m):
            self.dfs(matrix, i, 0, pacific, float('-inf'))
            self.dfs(matrix, i, n - 1, atlantic, float('-inf'))
        for j in range(n):
            self.dfs(matrix, 0, j, pacific, float('-inf'))
            self.dfs(matrix, m - 1, j, atlantic, float('-inf'))

        # Gather the result, which are the cells that both oceans can reach
        res = []
        for i in range(m):
            for j in range(n):
                if pacific[i][j] and atlantic[i][j]:
                    res.append([i, j])
        return res

    def dfs(self, matrix, r, c, visited, height):
        # Check boundaries, if the cell was visited before, or if the cell has a value less than the current height
        m, n = len(matrix), len(matrix[0])
        if r < 0 or r >= m or c < 0 or c >= n or visited[r][c] or matrix[r][c] < height:
            return
        
        # Mark the cell as visited
        visited[r][c] = True
        
        # Explore the neighboring cells
        for dir in self.DIRECTIONS:
            self.dfs(matrix, r + dir[0], c + dir[1], visited, matrix[r][c])


sol = Solution()
print(sol.pacificAtlantic([[1,2,3],[4,5,6],[7,8,9]]))  # Expected output: [[0,2],[1,2],[2,0],[2,1],[2,2]]
print(sol.pacificAtlantic([[10,10,10],[10,1,10],[10,10,10]]))  # Expected output: [[0,1],[1,0],[1,2],[2,1]]
print(sol.pacificAtlantic([[5,4,3],[4,3,2],[3,2,1]]))  # Expected output: [[0,2],[1,2],[2,0],[2,1],[2,2]]

Complexity Analysis

Time Complexity: O(m x n) where m is the number of rows and n is the number of columns in the matrix. This is because each cell is visited once for both oceans.

Space Complexity: O(m x n) due to the two additional matrices (for Pacific and Atlantic) to keep track of visited cells.

Validate Binary Search Tree

Problem Statement

Determine if a given binary tree is a binary search tree (BST). In a BST, for each node:

  • All nodes to its left have values less than the node’s value.
  • All nodes to its right have values greater than the node’s value.

Example Generation

Example 1:

  • Input: [5,3,7]
  • Expected Output: true
  • Justification: The left child of the root (3) is less than the root, and the right child of the root (7) is greater than the root. Hence, it’s a BST.

Example 2:

  • Input: [5,7,3]
  • Expected Output: false
  • Justification: The left child of the root (7) is greater than the root, making it invalid.

Example 3:

  • Input: [10,5,15,null,null,12,20]
  • Expected Output: true
  • Justification: Each subtree of the binary tree is a valid binary search tree. So, a whole binary tree is a valid binary search tree.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -2^31 <= Node.val <= 2^31- 1

Solution

In essence, to validate if a given binary tree is a binary search tree (BST), we employ a recursive approach that checks the validity of each node by comparing its value with a permissible range. This range is determined by the node’s ancestors, ensuring every node meets the BST property. Initially, the root node can take any value between negative infinity and positive infinity. As we traverse down the tree, we update this range based on the current node’s value.

Detailed Breakdown:

  1. Recursion:
    • For each node in the binary tree, we validate its value against a permissible range. If the value does not lie within this range, the tree is not a BST.
    • The range for any node is influenced by its ancestors, ensuring that every node, even those deep in the tree, satisfies the BST condition.
  2. Base Case:
    • If the node we are inspecting is null (i.e., we’ve reached a leaf node), we return true since a null subtree is always a BST by definition.
  3. Recursive Step:
    • Compare the node’s value against its permissible range. If it’s not within the range, return false.
    • If it is within range, we recursively check the left and right children, but with updated permissible ranges.
  4. Implementation:
    • Initially, the root node’s range is set to (-Infinity, +Infinity).
    • For every left child, the upper limit of its permissible range is updated to the current node’s value. Similarly, for every right child, the lower limit is updated to the current node’s value.

Algorithm Walkthrough

For the tree [10,5,15,null,null,12,20]:

  • Start with the root, range = (-Infinity, +Infinity)
    • Node 10 is within the range.
  • Move to the left child, range = (-Infinity, 10)
    • Node 5 is within the range.
  • Move to the right child of root, range = (10, +Infinity)
    • Node 15 is within the range.
  • Move to the left child of 15, range = (10, 15)
    • Node 12 is within the range.
  • Move to the right child of 15, range = (15, +Infinity)
    • Node 20 is within the range.
  • return true, as the next left node is null.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # Helper function to recursively check node value against a range
        def helper(node, low=float('-inf'), high=float('inf')):
            if not node:
                return True
            if not low < node.val < high:
                return False
            # Recursively check left (with updated high) and right (with updated low)
            return helper(node.left, low, node.val) and helper(node.right, node.val, high)

        return helper(root)

# Test the solution with the examples
if __name__ == "__main__":
    sol = Solution()

    example1 = TreeNode(5, TreeNode(3), TreeNode(7))
    print(sol.isValidBST(example1))  # true

    example2 = TreeNode(5, TreeNode(7), TreeNode(3))
    print(sol.isValidBST(example2))  # false

    example3 = TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(12), TreeNode(20)))
    print(sol.isValidBST(example3))  # false

Complexity Analysis

  • Time Complexity: O(n) - We traverse each node once.
  • Space Complexity: O(h) - The space is determined by the height of the tree due to recursive calls. In the worst case (skewed tree), it’s O(n), while in the best case (balanced tree), it’s O(log n).

Construct Binary Tree from Preorder and Inorder Traversal

Problem Statement

Given the preorder and inorder traversal sequences of a binary tree, your task is to reconstruct this binary tree. Assume that the tree does not contain duplicate values.

Example Generation

Example 1:

  • Input:
    • Preorder: [1,2,4,5,3,6,7]
    • Inorder: [4,2,5,1,6,3,7]
  • Expected Output:
    • Tree Representation: [1,2,3,4,5,6,7]

  • Justification:
    • The first value in preorder (1) is the root. In the inorder list, everything left of value 1 is the left subtree and everything on the right is the right subtree. Following this pattern recursively helps in reconstructing the binary tree.

Example 2:

  • Input:
    • Preorder: [8,5,9,7,1,12,2,4,11,3]
    • Inorder: [9,5,1,7,2,12,8,4,3,11]
  • Expected Output:
    • Tree Representation: [8,5,4,9,7,11,1,12,2,null,3]

  • Justification:
    • Start with 8 (from preorder) as the root. Splitting at 8 in inorder, we find the left and right subtrees. Following this pattern recursively, we can construct the tree.

Example 3:

  • Input:
    • Preorder: [3,5,6,2,7,4,1,9,8]
    • Inorder: [6,5,7,2,4,3,9,1,8]
  • Expected Output:
    • Tree Representation: [3,5,1,6,2,9,8,null,null,7,4]

  • Justification:
    • Following the same approach, using 3 as root from preorder, we split the inorder sequence into left and right subtrees and continue recursively.

Constraints:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values.
  • Each value of inorder also appears in preorder.
  • preorder is guaranteed to be the preorder traversal of the tree.
  • inorder is guaranteed to be the inorder traversal of the tree.

Solution

Reconstructing a binary tree from its preorder and inorder traversals involves recognizing the structure imposed by these traversal methods. The first element of the preorder traversal always gives us the root of the tree. Once we identify the root, its position in the inorder traversal divides the tree into its left and right subtrees. By harnessing this division recursively for both the left and the right subtrees, we can reconstruct the entire binary tree.

Detailed Steps:

  1. Start with Preorder’s Root: The first element in the preorder list is always the root of the tree.
  2. Find the Root in Inorder: Once we have the root from preorder, we find its position in the inorder sequence. This position divides the tree into its left and right subtrees.
  3. Recursion: Based on the root’s position in inorder, we can split both the preorder and inorder lists into two halves each - one for the left subtree and the other for the right subtree. We then recursively construct the left and right subtrees.
  4. Base Case: If the inorder sequence becomes empty, it indicates there’s no tree to construct, so we return null.

This approach capitalizes on the properties of the preorder and inorder traversals to recursively reconstruct the tree.

Algorithm Walkthrough

Given Preorder: [1,2,4,5,3,6,7] and Inorder: [4,2,5,1,6,3,7]

  1. Take the first value from preorder (1) as the root.
  2. Find the position of 1 in inorder (position 4).
  3. Everything before position 4 in inorder is the left subtree, and everything after is the right subtree.
  4. Using the size of the left subtree (3 nodes), we take the next 3 values from preorder [2,4,5] for the left subtree and recursively repeat the process.
  5. Similarly, for the right subtree, we use the remaining values from preorder [3,6,7] and follow the same recursive approach.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# class TreeNode:
#     def __init__(self, val=0):
#         self.val = val
#         self.left = self.right = None

class Solution:
    def __init__(self):
        self.preIndex = 0
        self.inorderIndexMap = {}

    def buildTree(self, preorder, inorder):
        # Create a dictionary to store the indices of values in the inorder list
        self.inorderIndexMap = {val: idx for idx, val in enumerate(inorder)}
        # Call the helper function to construct the binary tree
        return self._constructTree(preorder, 0, len(inorder) - 1)

    def _constructTree(self, preorder, inStart, inEnd):
        # Base case: If the start index is greater than the end index, return None
        if inStart > inEnd:
            return None

        # Get the value at the current preorder index as the root value
        rootVal = preorder[self.preIndex]
        self.preIndex += 1
        root = TreeNode(rootVal)

        # If the start index is equal to the end index, return the root node
        if inStart == inEnd:
            return root

        # Find the index of the root value in the inorder list
        inIndex = self.inorderIndexMap[rootVal]
        
        # Recursively construct the left and right subtrees
        root.left = self._constructTree(preorder, inStart, inIndex - 1)
        root.right = self._constructTree(preorder, inIndex + 1, inEnd)
        return root

def printTree(root):
    if not root:
        return

    queue = [root]
    while queue:
        levelSize = len(queue)
        isLastLevel = True

        for _ in range(levelSize):
            curr = queue.pop(0)
            if curr:
                print(curr.val, end=' ')
                queue.append(curr.left)
                queue.append(curr.right)
                if curr.left or curr.right:
                    isLastLevel = False
            else:
                print('null', end=' ')

        if isLastLevel:
            break

# Example usage:
sol = Solution()
root = sol.buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
printTree(root)  # Expected output: 3 9 20 null null 15 7

Complexity Analysis

  • Time Complexity: O(n). We are visiting each node once, and the look-up for the inorder index is constant time (due to HashMap or equivalent).
  • Space Complexity: O(n). The space is majorly used for the hashmap and the recursive stack.

Clone Graph

Problem Statement

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

Example 1:

Input:

1
2
3
1--2
|  |
4--3

Expected Output:

1
2
3
1--2
|  |
4--3

Explanation: The graph has four nodes with the following connections:

  • Node 1 is connected to nodes 2 and 4.
  • Node 2 is connected to nodes 1 and 3.
  • Node 3 is connected to nodes 2 and 4.
  • Node 4 is connected to nodes 1 and 3.

Example 2:

Input:

1
2
3
4
5
  1--2
 /    \
5      3
       |
       4

Expected Output:

1
2
3
4
5
  1--2
 /    \
5      3
       |
       4

Explanation: The graph consists of five nodes with these connections:

  • Node 1 is connected to nodes 2 and 5.
  • Node 2 is connected to nodes 1 and 3.
  • Node 3 is connected to nodes 2 and 4.
  • Node 4 is connected to node 3.
  • Node 5 is connected to node 1.

Example 3:

Input:

1
2
3
4
5
  1--2
 /    \
4      3
 \    /
  5--6

Expected Output:

1
2
3
4
5
  1--2
 /    \
4      3
 \    /
  5--6

Explanation: The graph has six nodes with the following connections:

  • Node 1 is connected to nodes 2 and 4.
  • Node 2 is connected to nodes 1 and 3.
  • Node 3 is connected to nodes 2 and 6.
  • Node 4 is connected to nodes 1 and 5.
  • Node 5 is connected to nodes 4 and 6.
  • Node 6 is connected to nodes 3 and 5.

Constraints:

  • The number of nodes in the graph is in the range [0, 100].
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • There are no repeated edges and no self-loops in the graph.
  • The Graph is connected and all nodes can be visited starting from the given node.

Solution

To deep clone a given graph, the primary approach is to traverse the graph using Depth-First Search (DFS) and simultaneously create clones of the visited nodes. A hashmap (or dictionary) is utilized to track and associate original nodes with their respective clones, ensuring no duplications.

  1. Initialization: Create an empty hashmap to match the original nodes to their clones.
  2. DFS Traversal and Cloning: Traverse the graph with DFS. When encountering a node not in the hashmap, create its clone and map them in the hashmap. Recursively apply DFS for each of the node’s neighbors. After cloning a node and all its neighbors, associate the cloned node with the clones of its neighbors.
  3. Termination: Once DFS covers all nodes, return the cloned version of the starting node.

Algorithm Walkthrough (using Example 1):

For the input graph:

1
2
3
1--2
|  |
4--3
  • Start with an empty hashmap visited.
  • Begin DFS with node 1.
    • Node 1 isn’t in visited. Clone it to get 1' and map (1, 1') in the hashmap.
    • For each neighbor of node 1, apply DFS.
      • First with 2.
        • Node 2 isn’t in visited. Clone to get 2' and map (2, 2').
        • Node 2‘s neighbors are 1 and 3. Node 1 is visited, so link 2'to 1'. Move to 3.
          • Node 3 isn’t in visited. Clone to get 3' and map (3, 3').
          • Node 3 has neighbors 2 and 4. Node 2 is visited, so link 3' to 2'. Move to 4.
            • Node 4 isn’t in visited. Clone to get 4' and map (4, 4').
            • Node 4 has neighbors 1 and 3, both visited. Link 4' to 1' and 3'.
  • With DFS complete, return the clone of the starting node, 1'.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from collections import deque

# class GraphNode:
#     def __init__(self, val = 0, neighbors = None):
#         self.val = val
#         self.neighbors = neighbors if neighbors is not None else []

class Solution:
    def __init__(self):
        # Dictionary to keep track of nodes that are already visited
        self.visited = {}

    def cloneGraph(self, node: 'GraphNode') -> 'GraphNode':
        if not node:
            return node

        # If the node is already visited, return its clone
        if node in self.visited:
            return self.visited[node]

        # Otherwise, create a new node with the same value
        clone_node = GraphNode(node.val, [])
        self.visited[node] = clone_node

        # Process all the neighbors for the current node
        for neighbor in node.neighbors:
            clone_node.neighbors.append(self.cloneGraph(neighbor))

        return clone_node

    def printGraph(self, node):
        # Use BFS to print the graph
        printed = set()
        queue = deque([node])
        while queue:
            curr = queue.popleft()
            if curr not in printed:
                print(curr.val, '-->', [n.val for n in curr.neighbors])
                for n in curr.neighbors:
                    queue.append(n)
                printed.add(curr)

    def main(self):
        sol = Solution()

        # Example 1: Create and clone a simple two-node graph
        node1 = GraphNode(1)
        node2 = GraphNode(2)
        node1.neighbors = [node2]
        node2.neighbors = [node1]
        sol.printGraph(sol.cloneGraph(node1))  # Expecting: 1-->2, 2-->1

if __name__ == "__main__":
    Solution().main()

Complexity Analysis

  • Time Complexity: O(N+M) where N is the number of nodes and M is the number of edges. Each node and edge is visited once.
  • Space Complexity: O(N) as we are creating a clone for each node. Additionally, the recursion stack might use O(H) where H is the depth of the graph (in the worst case this would be O(N)).

House Robber II

Problem Statement

You are given an array representing the amount of money each house has. This array models a circle of houses, meaning that the first and last houses are adjacent. You are tasked with figuring out the maximum amount of money you can rob without alerting the neighbors.

The rule is: if you rob one house, you cannot rob its adjacent houses.

Examples

Example 1:

  • Input: [4, 2, 3, 1]
  • Expected Output: 7
  • Justification: Rob the 1st and 3rd house, which gives 4 + 3 = 7.

Example 2:

  • Input: [5, 1, 2, 5]
  • Expected Output: 7
  • Justification: Rob the 1st and 3rd house, which gives 5 + 2 = 7.

Example 3:

  • Input: [1, 2, 3, 4, 5]
  • Expected Output: 8
  • Justification: Rob the 3rd and 5th house, which gives 3 + 5 = 8.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

Solution

The core idea of our algorithm is to split the circular house problem into two simpler linear problems and then solve each linear problem using a dynamic programming approach. Since the first and last houses in the circle are adjacent, we can’t rob them both. Thus, we consider two scenarios: robbing houses excluding the first one and robbing houses excluding the last one. For each scenario, we use a helper function that returns the maximum amount we can rob. This helper function utilizes dynamic programming to keep track of the cumulative robbery amounts, ensuring that no two consecutive houses are robbed. Finally, our solution is the maximum of the two scenarios.

  1. Edge Cases Handling: Begin by checking for edge cases:

    • If the input array is null or has a length of 0, return 0 since there are no houses to rob.
    • If there’s only one house, return its value.
    • If there are two houses, return the maximum value of the two houses.

  2. Two Scenarios Handling: Due to the circular structure, handle two scenarios:

    • Exclude the first house and compute for the rest.
    • Exclude the last house and compute for the others.

    Use a helper function to compute the maximum for each scenario.

  3. Simple Robber Helper Function: This function calculates the maximum robbing amount for a linear set of houses using dynamic programming:

    • Maintain two variables, prevMax and currMax, to keep track of the max amount robbed up to the previous and current house, respectively.
    • Iterate through each house in the given range (based on the scenario). At each house, decide whether to rob it (in which case you can’t rob the previous house) or skip it.
    • For each house, update currMax based on whether robbing the current house results in a larger amount than skipping it.

  4. Return the Maximum: The main function concludes by returning the maximum value from the two scenarios.

Algorithm Walkthrough

Using the input [4, 2, 3, 1]:

  1. Check for edge cases. Since the array has more than two houses, move to the next step.

  2. Calculate the maximum amount that can be robbed for the two scenarios:

    a. For the scenario excluding the last house (consider houses from index 0 to 2):

    • Start with prevMax = 0 and currMax = 0.
    • For the first house (value 4), currMax becomes 4.
    • For the second house (value 2), currMax remains 4 (because 4 > 2 + 0).
    • For the third house (value 3), currMax becomes 7 (because 4 + 3 > 4). So, for this scenario, the maximum is 7.

    b. For the scenario excluding the first house (consider houses from index 1 to 3):

    • Start with prevMax = 0 and currMax = 0.
    • For the second house (value 2), currMax becomes 2.
    • For the third house (value 3), currMax becomes 3 (because 3 > 2).
    • For the fourth house (value 1), currMax remains 3 (because 3 > 1 + 2). So, for this scenario, the maximum is 3.

  3. The main function then returns the maximum of the two scenarios, which is 7 in this case.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def rob(self, nums):
        if not nums: return 0
        if len(nums) == 1: return nums[0]
        if len(nums) == 2: return max(nums[0], nums[1])
        
        # Compare the result excluding the first or the last house.
        return max(self._rob(nums, 0, len(nums) - 2), self._rob(nums, 1, len(nums) - 1))

    # The simple rob function that doesn't consider the circle scenario.
    def _rob(self, nums, start, end):
        prevMax, currMax = 0, 0
        for i in range(start, end + 1):
            temp = currMax
            currMax = max(prevMax + nums[i], currMax)
            prevMax = temp
        return currMax

# Test the solution
solution = Solution()
print(solution.rob([4, 2, 3, 1]))  # Expected 7
print(solution.rob([5, 1, 2, 5]))  # Expected 7
print(solution.rob([1, 2, 3, 4, 5]))  # Expected 8

Complexity Analysis

Time Complexity: We are solving the house robber problem twice (once excluding the first house and once excluding the last house). Each run of the house robber problem has a time complexity of (O(n)), where (n) is the number of houses. Thus, our overall time complexity is (O(n)).

Space Complexity: We use a constant amount of space to store our previous and current max values. Hence, the space complexity is (O(1)).

Decode Ways

Problem Statement

You have given a string that consists only of digits. This string can be decoded into a set of alphabets where ‘1’ can be represented as ‘A’, ‘2’ as ‘B’, … , ‘26’ as ‘Z’. The task is to determine how many ways the given digit string can be decoded into alphabets.

Examples

    • Input: “121”
    • Expected Output: 3
    • Justification: The string “121” can be decoded as “ABA”, “AU”, and “LA”.
    • Input: “27”
    • Expected Output: 1
    • Justification: The string “27” can only be decoded as “BG”.
    • Input: “110”
    • Expected Output: 1
    • Justification: The string “110” can only be decoded as “JA”.

Constraints:

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

Solution

Our approach to solving this problem involves using dynamic programming to iteratively build the solution. Given a string of digits, we want to determine how many ways it can be decoded into alphabets. The key insight is that the number of ways to decode a string of length i is dependent on the number of ways to decode the previous two substrings of length i-1 and i-2. We’ll use two variables, prev and current, to store these values and update them as we loop through the string.

  1. Initialization: Begin by checking if the string is valid for decoding (e.g., it should not start with a ‘0’). If the string is invalid, return 0. Next, initialize two variables, prev and current, both set to 1. prev will store the number of ways to decode the string of length i-2, and current will store the number of ways to decode the string of length i-1.
  2. Iterate Through the String: Loop through the string from the second character to the end. For each character, compute the number of ways it can be decoded when combined with the previous character.
  3. Update Variables: For each character, evaluate the following conditions:
    • If the current character and the previous character form a valid number between 10 and 26, they can be decoded together.
    • If the current character is not ‘0’, it can be decoded individually. Use these conditions to update the prev and current variables accordingly.
  4. Return the Result: Once the iteration completes, the current variable will hold the total number of ways the entire string can be decoded. Return this value.

This dynamic programming approach is efficient because it computes the solution by using previously calculated results, and it avoids redundant calculations. By tracking and updating the number of ways to decode the current and previous substrings, the algorithm effectively builds the solution for the entire string.

Algorithm Walkthrough

Consider the input “121”:

  • Initialize prev = 1 and current = 1.
  • For the second character ‘2’:
    • “12” can be decoded as “AB” or “L”.
    • Update prev and current by swapping their values and setting current += prev.
    • Now, prev = 1 and current = 2.
  • For the third character ‘1’:
    • “21” can be decoded as “BA” or “U”.
    • Again, update prev and current.
    • Now, prev = 2 and current = 3.
  • The final answer is 3, which is the value of current.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def numDecodings(self, s: str) -> int:
        # Return 0 for empty strings or strings starting with '0'
        if not s or s[0] == '0':
            return 0

        # Initialize two variables to store results of sub-problems
        prev, current = 1, 1
        
        for i in range(1, len(s)):
            temp = 0

            # If current character is not '0', it can be decoded on its own
            if s[i] != '0':
                temp = current

            # Check if two characters can be decoded together
            if 10 <= int(s[i-1:i+1]) <= 26:
                temp += prev

            prev, current = current, temp
        
        return current

if __name__ == "__main__":
    sol = Solution()
    print(sol.numDecodings("121"))  # Expected 3
    print(sol.numDecodings("27"))   # Expected 1
    print(sol.numDecodings("110"))  # Expected 1

Complexity Analysis

  • Time Complexity: O(N), where N is the length of the string. We loop through the string once.
  • Space Complexity: O(1), as we only use a constant amount of space regardless of the input size.

Unique Paths

Problem Statement

Given a 2-dimensional grid of size m x n (where m is the number of rows and n is the number of columns), you need to find out the number of unique paths from the top-left corner to the bottom-right corner. The constraints are that you can only move either right or down at any point in time.

Examples

  1. Example 1:

    • Input: 3, 3

    • Expected Output: 6

    • Justification:

 The six possible paths are:

 1. Right, Right, Down, Down
 2. Right, Down, Right, Down
 3. Right, Down, Down, Right
 4. Down, Right, Right, Down
 5. Down, Right, Down, Right
 6. Down, Down, Right, Right

  1. Example 2:

    • Input: 3, 2
    • Expected Output: 3
    • Justification: The three possible paths are:
      • Right, right, down
      • Right, down, right
      • Down, right, right

  2. Example 3:

    • Input: 2, 3
    • Expected Output: 3
    • Justification: The three possible paths are:
      • Down, right, right
      • Right, down, right
      • Right, right, down

Solution

The unique paths problem can be approached using a dynamic programming solution. Essentially, the idea is to think of the grid as a graph where each cell is a node. Given we can only move right or down, the number of ways to reach a cell is the sum of the number of ways to reach the cell above it and the cell to its left. By breaking down the problem in this way, we can iteratively compute the number of paths to reach any cell, starting from the top-left and working our way to the bottom-right of the grid.

  1. Initialization:
    • Create a 2-dimensional array dp of size m x n initialized to zero. This array will store the number of unique paths to reach each cell.
  2. Boundary Cases:
    • All cells in the first row can only be reached by moving right from the top-left corner. So, the number of unique paths for all cells in the first row will be 1.
    • Similarly, all cells in the first column can only be reached by moving downwards from the top-left corner. So, the number of unique paths for all cells in the first column will be 1.
  3. Filling the Table:
    • For each remaining cell, the number of unique paths to that cell is the sum of the number of paths from the cell above it and the cell to the left of it. This is because we can only move right or down.
  4. Result:
    • The bottom-right cell will contain the total number of unique paths from the top-left corner to the bottom-right corner.

Algorithm Walkthrough

Using the input from Example 1 (2, 2):

  • Initialize a 2x2 matrix dp with all zeros.

    1
    2
    0 0
    0 0

  • Fill the first row and first column with 1s.

    1
    2
    1 1
    1 0

  • For cell dp[1][1], add values from cell above (dp[0][1]) and cell to the left (dp[1][0]).

    1
    2
    1 1
    1 2

  • The bottom-right cell (dp[1][1]) contains the number of unique paths: 2.

Constraints:

  • 1 <= m, n <= 100

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Initialize the dp array with 1s
        dp = [[1] * n for _ in range(m)]
        
        # Calculate the number of ways to reach each cell
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        # Return number of ways to reach the bottom-right cell
        return dp[-1][-1]

if __name__ == "__main__":
    sol = Solution()
    print(sol.uniquePaths(2, 2)) # 2
    print(sol.uniquePaths(3, 2)) # 3
    print(sol.uniquePaths(2, 3)) # 3

Complexity Analysis

  • Time Complexity: O(m * n) - We are processing each cell once.
  • Space Complexity: O(m * n) - Due to the 2D dp array.

Word Break

Problem Statement

Given a non-empty string and a dictionary containing a list of non-empty words, determine if the string can be segmented into a space-separated sequence of one or more dictionary words. Each word in the dictionary can be reused multiple times.

Examples

Example 1:

  • Input:
    • String: “ilovecoding”
    • Dictionary: [“i”, “love”, “coding”]
  • Expected Output: True
  • Justification: The string can be segmented as “i love coding”.

Example 2:

  • Input:
    • String: “helloworld”
    • Dictionary: [“hello”, “world”, “hell”, “low”]
  • Expected Output: True
  • Justification: The string can be segmented as “hello world”.

Example 3:

  • Input:
    • String: “enjoylife”
    • Dictionary: [“enj”, “life”, “joy”]
  • Expected Output: False
  • Justification: Despite having the words “enj” and “life” in the dictionary, we can’t segment the string into the space-separated dictionary words.

Constraints:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Solution

Our algorithm’s primary objective is to determine whether the given string can be broken down into a sequence of words present in the dictionary. To achieve this, we use a dynamic programming approach, maintaining an array to keep track of the possibility of forming valid sequences up to every index of the string. The primary idea is to iterate through the string and, at each step, check all possible word endings at the current position. If a valid word is found, and the starting position of that word was marked as achievable, we mark the current position as achievable too.

  1. Initialization:
    • Begin by initializing a boolean array dp of size n+1, where n is the length of the string. This array will record whether the string can be segmented up to a certain index. We set the first element, dp[0], to true since an empty string can always be segmented.
  2. Dynamic Programming:
    • Iterate over the length of the string. For each index i, verify every substring ending at i and see if it exists in the dictionary.
    • If a valid word is found and the starting position (denoted as dp[j]) of the substring is true, set dp[i+1] to true.
    • Proceed in this manner until you reach the end of the string.
  3. Result:
    • Once the iteration is complete, the value of dp[n] will indicate if the entire string can be segmented into dictionary words or not.
  4. Optimization:
    • For faster lookups, convert the word dictionary into a set. This ensures constant time complexity when searching for words in the dictionary.

Algorithm Walkthrough

Given the string “helloworld” and dictionary [“hello”, “world”, “hell”, “low”]:

  • Initialize dp to [true, false, false, ..., false] (length = 11 since “helloworld” has 10 characters).
  • For i = 0, substring = “h”. It’s not in the dictionary, so move to next.
  • For i = 1, substring = “he”, “h”. Neither is in the dictionary.
  • For i = 4, substring = “hello”, which is in the dictionary and dp[0] is true. So, set dp[5] to true.
  • Continuing this, when we get to i = 9, substring = “world” is in the dictionary, and dp[5] is true, so we set dp[10] to true.
  • Finally, dp[10] is true, so “helloworld” can be segmented.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def wordBreak(self, s, wordDict):
        # Convert wordDict into a set for O(1) lookup
        wordSet = set(wordDict)
        
        # Initialize dp list with false values and set the first value to true
        dp = [False] * (len(s) + 1)
        dp[0] = True

        # Iterate over the string
        for i in range(1, len(s) + 1):
            # For each position, check all possible words that end at this position
            for j in range(i):
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True
                    break

        # Return if the entire string can be segmented or not
        return dp[len(s)]

# Test the code
sol = Solution()
print(sol.wordBreak("ilovecoding", ["i", "love", "coding"]))  # true
print(sol.wordBreak("helloworld", ["hello", "world", "hell", "low"]))  # true
print(sol.wordBreak("enjoylife", ["enj", "life", "joy"]))  # false

Complexity Analysis

  • Time Complexity: O(n^2) due to the two nested loops where we check all possible substrings.
  • Space Complexity: O(n) for the DP array and the word set.

Lowest Common Ancestor of a Binary Search Tree

Problem Statement

Given a binary search tree (BST) and two of its nodes, find the node that is the lowest common ancestor (LCA) of the two given nodes. The LCA of two nodes is the node that lies in between the two nodes in terms of value and is the furthest from the root. In other words, it’s the deepest node where the two nodes diverge in the tree. Remember, in a BST, nodes have unique values.

Examples

    • Input:

      • BST: [6,2,8,0,4,7,9,null,null,3,5]
      • Node 1: 2
      • Node 2: 8

    • Expected Output: 6

  • Justification: The nodes 2 and 8 are on the left and right children of node 6. Hence, node 6 is their LCA.

    • Input:

      • BST: [6,2,8,0,4,7,9,null,null,3,5]
      • Node 1: 0
      • Node 2: 3

    • Expected Output: 2

  • Justification: The nodes 0 and 3 are on the left and right children of node 2, which is the closest ancestor to these nodes.

    • Input:

      • BST: [6,2,8,0,4,7,9,null,null,3,5]
      • Node 1: 4
      • Node 2: 5

    • Expected Output: 4

  • Justification: Node 5 is the right child of node 4. Hence, the LCA is node 4 itself.

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -10^9 <=Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

Solution

The binary search tree property helps us find the solution without exploring the entire tree. Each node, starting from the root, provides a range based on its value that can determine where the two nodes are located.

  1. Starting at the Root: Begin at the root of the BST.
  2. Determining Direction: If the values of both nodes are greater than the current root node’s value, then the LCA must be in the right subtree. If the values are both less, then the LCA is in the left subtree.
  3. Divergence Point: If one node’s value is less than the root’s value and the other node’s value is greater (or if one of them matches the root’s value), then the current root is the LCA, since the path to reach both nodes diverges from here.
  4. Iterative Search: Repeat the process iteratively on the selected subtree (either left or right) until you find the LCA.

Algorithm Walkthrough

Using the first example input:

  • BST: [6,2,8,0,4,7,9,null,null,3,5]
  • Node 1: 2
  • Node 2: 8

Steps:

  • Start at root which is 6.
  • Both 2 and 8 are on different sides of 6 (2 on the left and 8 on the right).
  • Therefore, 6 is the lowest common ancestor.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        # Iterate until the LCA is found
        while root:
            if p < root.val and q < root.val:
                root = root.left  # Both nodes are on the left
            elif p > root.val and q > root.val:
                root = root.right  # Both nodes are on the right
            else:
                return root.val  # One node is on the left and the other is on the right, so we found the LCA
        return None  # Just in case, though we should always find an LCA in a valid input

if __name__ == "__main__":
    # Creating the example tree
    root = TreeNode(6, TreeNode(2, TreeNode(0), TreeNode(4, TreeNode(3), TreeNode(5))), TreeNode(8, TreeNode(7), TreeNode(9)))
    solution = Solution()
    # Testing the solution on the provided examples
    print(solution.lowestCommonAncestor(root, 2, 8))  # expected: 6
    print(solution.lowestCommonAncestor(root, 0, 3))  # expected: 2
    print(solution.lowestCommonAncestor(root, 4, 5))  # expected: 4

Complexity Analysis

The algorithm traverses the BST in a single path, either going left or right, but never both. Therefore:

  • Time Complexity: O(h), where h is the height of the BST.
  • pace Complexity: O(1) since we only used a constant amount of space.

Longest Consecutive Sequence

Problem Statement

Given an unsorted array of integers, find the length of the longest consecutive sequence of numbers in it. A consecutive sequence means the numbers in the sequence are contiguous without any gaps. For instance, 1, 2, 3, 4 is a consecutive sequence, but 1, 3, 4, 5 is not.

Examples

    • Input: [10, 11, 14, 12, 13]
    • Output: 5
    • Justification: The entire array forms a consecutive sequence from 10 to 14.
    • Input: [3, 6, 4, 100, 101, 102]
    • Output: 3
    • Justification: There are two consecutive sequences, [3, 4] and [100,101,102]. The latter has a maximum length of 3.
    • Input: [4, 3, 6, 2, 5, 8, 4, 7, 0, 1]
    • Output: 9
    • Justification: The longest consecutive sequences here are [0, 1, 2,, 3, 4, 5, 6, 7, 8].
    • Input: [7, 8, 10, 11, 15]
    • Output: 2
    • Justification: The longest consecutive sequences here are [7,8] and [10,11], both of length 2.

Constraints:

  • 0 <= nums.length <= 105
  • -10^9 <= nums[i] <= 10^9

Solution

To solve this problem, the key observation is that if n is part of a consecutive sequence, then n+1 and n-1 must also be in that sequence.

  1. HashSet: Begin by inserting all elements of the array into a HashSet. The reason for using a HashSet is to ensure O(1) time complexity during look-up operations.
  2. Initial Scan: Iterate through each element of the array. For every number, check if it’s the starting point of a possible sequence. This can be determined by checking if n-1 exists in the HashSet. If not, then it means n is the start of a sequence.
  3. Building Sequences: For each starting number identified in step 2, keep checking if n+1, n+2… exist in the HashSet. For each present number, increase the length of the sequence and move to the next number.
  4. Result: Store the length of each sequence found in step 3. The answer will be the longest of all sequences identified.

Algorithm Walkthrough

Given the input: [3, 6, 4, 100, 101, 102]

  • Initialize an empty HashSet and populate it with all numbers from the input.
  • Start with the first number, 3. Since 2 (which is 3-1) is not in the HashSet, we recognize 3 as the starting of a sequence.
    • Check for 4. It’s there. Move to 5. It’s not there. So, the sequence is [3,4] with a length of 2.
  • Next, take 6. 5 is not there, so 6 might be the start of a new sequence. However, 7 isn’t in the HashSet. So, the sequence is just [6].
  • For 100, 99 isn’t there, so 100 is a starting point.
    • Check for 101. It’s there. Check for 102. It’s there. Check for 103. It’s not there. The sequence is [100,101,102] with a length of 3.
  • The algorithm returns 3, which is the length of the longest sequence.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def longestConsecutive(self, nums):
        # Using a set to store numbers for constant time lookup
        num_set = set(nums)
        longest_sequence = 0

        for num in num_set:
            # Checking if current number is the start of a sequence
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                # Extend the streak for as long as possible
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                # Keep track of the longest streak
                longest_sequence = max(longest_sequence, current_streak)

        return longest_sequence

if __name__ == "__main__":
    sol = Solution()
    print(sol.longestConsecutive([10, 11, 14, 12, 13])) # 5
    print(sol.longestConsecutive([3, 6, 4, 100, 101, 102])) # 3
    print(sol.longestConsecutive([7, 8, 10, 11, 15])) # 2

Complexity Analysis

  • Time Complexity: O(n). Although it seems that the while loop runs for each number, it only runs for the numbers that are the starting points of sequences. So, in total, each number is processed only once.
  • Space Complexity: O(n). The space used by our set.

Meeting Rooms II

Problem Statement

Given a list of time intervals during which meetings are scheduled, determine the minimum number of meeting rooms that are required to ensure that none of the meetings overlap in time.

Examples

  1. Example 1:
    • Input: [[10, 15], [20, 25], [30, 35]]
    • Expected Output: 1
    • Justification: There are no overlapping intervals in the given list. So, only 1 meeting room is enough for all the meetings.
  2. Example 2:
    • Input: [[10, 20], [15, 25], [24, 30]]
    • Expected Output: 2
    • Justification: The first and second intervals overlap, and the second and third intervals overlap as well. So, we need 2 rooms.
  3. Example 3:
    • Input: [[10, 20], [20, 30]]
    • Expected Output: 1
    • Justification: The end time of the first meeting is the same as the start time of the second meeting. So, one meeting can be scheduled right after the other in the same room.

Constraints:

  • 1 <= intervals.length <= 104
  • 0 <= starti < endi <= 106

Solution

To determine the minimum number of rooms required to host the meetings without any time overlap, our approach first involves sorting all meeting intervals based on their start times. This sorting allows us to sequentially evaluate meetings in the order they start. We then utilize a priority queue (min-heap) to keep track of end times of the meetings currently taking place. This queue helps in efficiently determining the earliest ending meeting. By sequentially examining each meeting and comparing its start time to the earliest ending time from the heap, we can decide if a new room is needed or if an existing room can be reused.

  1. Sorting: Begin by sorting all intervals based on their start times. This enables us to sequentially check for overlapping intervals.
  2. Priority Queue: A priority queue (min-heap) is used to monitor end times of meetings that are currently in session. If the start time of the next meeting is less than the smallest end time (i.e., the top of the priority queue), it indicates we require another room.
  3. Reusing Rooms: Once we have checked a meeting and it doesn’t overlap with the smallest end time, this means that the meeting room used by the meeting with the smallest end time can be reassigned. Therefore, we remove the earliest ending meeting from the priority queue.
  4. Counting Rooms: At any given time, the size of the priority queue reflects the number of rooms in use. This can be used to deduce the minimum number of rooms needed up to that point.

Algorithm Walkthrough

Given an input [[10, 20], [15, 30], [25, 40]]:

  • First, sort the intervals: [[10, 20], [15, 30], [25, 40]] (in this case, the intervals are already sorted).
  • Initialize a priority queue. Add the end time of the first meeting to the queue.
  • For the next interval [15, 30], the start time 15 is less than the top of the queue (i.e., 20). Hence, we need another room. Add 30 to the priority queue.
  • For the next interval [25, 40], the start time 25 is greater than the top of the queue (i.e., 20). So, we can use the room which will be free at time 20. Remove 20 from the queue and add 40.
  • The size of the priority queue at the end is 2, indicating 2 rooms are required.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import heapq

class Solution:
    def minMeetingRooms(self, intervals: [[int]]) -> int:
        if not intervals:
            return 0
        
        # Initialize a heap
        free_rooms = []
        
        # Sort the meetings in increasing order of their start time.
        intervals.sort(key=lambda x: x[0])
        
        # Add the first meeting. We have to give a new room to the first meeting.
        heapq.heappush(free_rooms, intervals[0][1])
        
        # For all the remaining meeting rooms
        for i in intervals[1:]:
            # If the room due to free up the earliest is free, assign that room to this meeting.
            if free_rooms[0] <= i[0]:
                heapq.heappop(free_rooms)
            
            # If a new room is to be assigned, then also we add to the heap.
            heapq.heappush(free_rooms, i[1])
        
        # The size of the heap tells us the minimum rooms required for all the meetings.
        return len(free_rooms)

# Test
sol = Solution()
print(sol.minMeetingRooms([[10, 15], [20, 25], [30, 35]])) # 1
print(sol.minMeetingRooms([[10, 20], [15, 25], [24, 30]])) # 2
print(sol.minMeetingRooms([[10, 20], [20, 30]])) # 1

Complexity Analysis

  • Time Complexity: The time complexity of our algorithm is (O(N \log N)), where (N) is the number of intervals. This is because we’re sorting the intervals once and then using priority queues to process them.
  • Space Complexity: The space complexity is (O(N)) as we’re storing all intervals in the worst case.

Encode and Decode Strings

Problem Statement

Given a list of strings, your task is to develop two functions: one that encodes the list of strings into a single string, and another that decodes the resulting single string back into the original list of strings. It is crucial that the decoded list is identical to the original one.

It is given that you can use any encoding technique to encode list of string into the single string.

Examples

  1. Example 1:
    • Input: [“apple”, “banana”]
    • Expected Output: [“apple”, “banana”]
    • Justification: When we encode the input strings [“apple”, “banana”], we get a single encoded string. Decoding this encoded string should give us the original list [“apple”, “banana”].
  2. Example 2:
    • Input: [“sun”, “moon”, “stars”]
    • Expected Output: [“sun”, “moon”, “stars”]
    • Justification: After encoding the input list, decoding it should bring back the original list.
  3. Example 3:
    • Input: [“Hello123”, “&*^%”]
    • Expected Output: [“Hello123”, “&*^%”]
    • Justification: Regardless of the content of the string (special characters, numbers, etc.), decoding the encoded list should reproduce the original list.

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] contains any possible characters out of 256 valid ASCII characters.

Solution

Our approach will utilize a delimiter that doesn’t appear in the input strings. For the sake of simplicity, we can choose a character like #. If # is possible in the input, we can use multiple characters like ## to reduce the chance it appears in the input.

  1. Encoding:
    • For each string in the list, we append it to the encoded string.
    • After appending the string, we add the delimiter ##.
    • Continue this for all the strings in the list.
  2. Decoding:
    • We split the encoded string using our delimiter ##.
    • This will give us a list of strings which is our original list.
  3. Handling Edge Cases:
    • If ## can be part of the input strings, then our approach will fail. To handle such cases, we can prefix each string with its length followed by a special character, like |, before the actual string. This way, during decoding, we can use the length to identify the end of one string and the beginning of the next.

Algorithm Walkthrough

Let’s walk through the algorithm using the input [“apple”, “banana##cherry”]:

  1. During encoding:
    • “apple” becomes “5|apple##”
    • “banana##cherry” becomes “15|banana##cherry##”
    • The final encoded string is “5|apple##15|banana##cherry##”
  2. During decoding:
    • Read the first character, which is 5. It tells us the next 5 characters form the first string “apple”.
    • The next character # is part of our delimiter, so we skip two characters.
    • Next, read the number 15, which tells us the next 15 characters form the string “banana##cherry”.
    • Finally, we reach the end of our encoded string.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    
    def encode(self, strs):
        """Encodes a list of strings to a single string."""
        encoded = ""
        for s in strs:
            # For each string, append its length, a delimiter '|', the string itself, and then "##"
            encoded += str(len(s)) + "|" + s + "##"
        return encoded
    
    def decode(self, s):
        """Decodes a single string to a list of strings."""
        res = []
        i = 0
        while i < len(s):
            # Find the delimiter to extract string's length
            delim = s.find('|', i)
            size = int(s[i:delim])
            
            # Using the extracted size, retrieve the actual string and add to the result list
            res.append(s[delim + 1: delim + 1 + size])
            
            # Move index to start of next encoded string segment
            i = delim + size + 3
        return res

# Test the encode and decode functions
sol = Solution()
example = ["apple", "banana##cherry"]
print(sol.decode(sol.encode(example)))  # Expected Output: ['apple', 'banana##cherry']

Complexity Analysis

  • Time Complexity:
    • For encoding, it is (O(n)), where (n) is the combined length of all the strings in the list because we iterate over each character once.
    • For decoding, it’s also (O(n)) for the same reason.
  • Space Complexity: (O(n)) as we store the encoded version of the string, and its length is proportional to the combined length of all the strings in the list.

Number of Connected Components in an Undirected Graph

Problem Statement

Given an undirected graph represented by ‘n’ nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), determine the number of connected components in the graph. A connected component is a group of nodes that are directly or indirectly linked to each other through the edges.

Examples

  1. Example 1
    • Input: n = 5, edges = [[0,1], [2,3], [3,4]]

  • Expected Output: 2
  • Justification: Two components are: 0-1, and 2-3-4.
  1. Example 2
  • Input: n = 4, edges = [[0,1], [1,2], [2,3]]

  • Expected Output: 1
  • Justification: All the nodes are connected in a single chain: 0-1-2-3.
  1. Example 3
  • Input: n = 3, edges = [[0,1]]

  • Expected Output: 2
  • Justification: Two connected components exist: 0-1 and an isolated node 2.

Constraints:

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai <= bi < n
  • ai != bi
  • There are no repeated edges.

Solution

We will use the Union-Find (also known as Disjoint Set Union, DSU) data structure to solve this problem. This approach is efficient in identifying and merging different sets:

  1. Initialization:
    • Create an array parent of size n where parent[i] = i. This array will keep track of the parent of each node. Initially, each node is its own parent.
    • Count the number of separate components. Initially, the count is n since every node is a separate component.
  2. Union Operation:
    • For each edge (u, v), find the parent of u and the parent of v.
    • If the parents are different, then u and v belong to different components. So, we merge them by assigning one’s parent to the other and reduce the component count by 1.
  3. Find Operation:
    • This operation determines the parent of a node. If a node’s parent is itself, return the node. Otherwise, recursively find the parent of its parent. To optimize the search in future look-ups, we can apply path compression by updating the parent of the current node to its root during the recursion.
  4. Result:
    • After processing all edges, the component count will represent the number of connected components.

Algorithm Walkthrough

Using the input n = 5 and edges = [[0,1], [2,3], [3,4]]:

  1. Initialize parent = [0, 1, 2, 3, 4] and count = 5.
  2. Process edge [0,1]:
    • Parent of 0 is 0.
    • Parent of 1 is 1.
    • They have different parents. Merge them by setting parent of 1 to 0 and reduce count to 4.
  3. Process edge [2,3]:
    • Parent of 2 is 2.
    • Parent of 3 is 3.
    • Merge them by setting parent of 3 to 2. Reduce count to 3.
  4. Process edge [3,4]:
    • Parent of 3 is 2 (from previous merge).
    • Parent of 4 is 4.
    • Merge them by setting parent of 4 to 2. Reduce count to 2.
  5. Final count is 2.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def __init__(self):
        self.parents = []

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])  # Path compression
        return self.parents[x]

    def countComponents(self, n, edges):
        self.parents = [i for i in range(n)]  # Initially, each node is its own parent
        for edge in edges:
            root1 = self.find(edge[0])
            root2 = self.find(edge[1])
            if root1 != root2:
                self.parents[root1] = root2  # Union operation
                n -= 1  # Decrease the component count
        return n

# Test the code
sol = Solution()
print(sol.countComponents(4, [[0,1],[2,3]]))  #Expected 2
print(sol.countComponents(5, [[0,1],[1,2],[2,0]]))  #Expected 3
print(sol.countComponents(3, []))  #Expected 3

Complexity Analysis

  • Time Complexity: The union operation is almost O(1) with path compression. So, for E edges, the time complexity is approximately O(E).
  • Space Complexity: O(N) due to the parent array.

Graph Valid Tree

Problem Statement

Given a number n, which indicates the number of nodes numbered from 0 to n-1, and a list of undirected edges for the graph, determine if the graph is a valid tree.

A graph qualifies as a valid tree if it meets the following criteria:

  1. It has no cycles.
  2. It is fully connected.

Examples

  • Example 1:
    • Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

  • Expected Output: true
  • Justification: There are no cycles in the graph, and all nodes are connected, forming a valid tree.
  • Example 2:
    • Input: n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]]]

  • Expected Output: false
  • Justification: There is a cycle in the graph (0-1-2-3-0), thus it’s not a valid tree.
  • Example 3:
    • Input: n = 5, edges = [[0,1],[1,2],[2,3]]

  • Expected Output: false
  • Justification: TNode 4 is not connected to any other node, making the graph not fully connected.

Constraints:

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai <= bi < n
  • ai != bi
  • There are no self-loops or repeated edges.

Solution

To determine if a given undirected graph forms a valid tree, we must ensure two key conditions are met:

  1. The graph should not have any cycles.
  2. The graph should be fully connected (i.e., all nodes are reachable from any other node).

To verify these conditions, we can adopt the following approach:

  1. Initialization: Construct an adjacency list for the graph. Initialize a set (or an array) to keep track of visited nodes.
  2. DFS for Cycle Check: Use Depth First Search (DFS) to explore the graph. During this traversal, if we ever try to revisit a node we’ve previously visited (excluding the parent node), it indicates the presence of a cycle.
  3. Connectivity Check: After ensuring there are no cycles, we need to ensure that the graph is fully connected. This can be done by verifying that the number of unique nodes visited during our DFS equals the total number of nodes.
  4. Return Result: If both checks pass, then it’s a valid tree and we return true. Otherwise, return false.

Algorithm Walkthrough

Using the input from Example 1:

1
2
n = 5
edges = [[0,1],[0,2],[0,3],[1,4]]

  • Start with the adjacency list:

    1
    2
    3
    4
    5
    0 -> [1, 2, 3]
    1 -> [0, 4]
    2 -> [0]
    3 -> [0]
    4 -> [1]

  • Start DFS from node 0. Mark node 0 as visited.

  • Move to node 1 (from node 0). Mark node 1 as visited.

  • From node 1, visit node 4. Mark node 4 as visited.

  • Backtrack to node 1, and backtrack again to node 0.

  • From node 0, visit node 2. Mark node 2 as visited.

  • From node 0, visit node 3. Mark node 3 as visited.

  • At the end of DFS, we’ve visited all nodes and found no cycles.

  • Since we visited all nodes, the graph is fully connected.

  • Hence, the graph is a valid tree.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from collections import defaultdict

class Solution:
    def __init__(self):
        self.graph = defaultdict(list)
        self.visited = set()

    def validTree(self, n, edges):
        # Building the adjacency list for the graph
        for edge in edges:
            self.graph[edge[0]].append(edge[1])
            self.graph[edge[1]].append(edge[0])

        # Checking for cycle
        if self.hasCycle(-1, 0):
            return False

        # Checking for connectivity
        return len(self.visited) == n

    def hasCycle(self, parent, node):
        self.visited.add(node)
        for neighbor in self.graph[node]:
            if neighbor == parent:
                continue
            if neighbor in self.visited or self.hasCycle(node, neighbor):
                return True
        return False

# Test the algorithm with example inputs
sol = Solution()
print(sol.validTree(5, [[0,1],[0,2],[0,3],[1,4]]))  # true
print(sol.validTree(4, [[0,1],[1,2],[2,3],[3,0]]))  # false
print(sol.validTree(5, [[0,1],[1,2],[2,3]]))       # false

Complexity Analysis

  • Time Complexity: The algorithm visits each node and edge once, so its time complexity is ( O(n + e) ), where ( n ) is the number of nodes and ( e ) is the number of edges.
  • Space Complexity: We are using a graph and visited set, so the space complexity is ( O(n + e) ).

Implement Trie (Prefix Tree)

Problem Statement

Design and implement a Trie (also known as a Prefix Tree). A trie is a tree-like data structure that stores a dynamic set of strings, and is particularly useful for searching for words with a given prefix.

Implement the Solution class:

  • Solution() Initializes the object.
  • void insert(word) Inserts word into the trie, making it available for future searches.
  • bool search(word) Checks if the word exists in the trie.
  • bool startsWith(word) Checks if any word in the trie starts with the given prefix.

Examples

  1. Example 1:
    • Input:
      • Trie operations: ["Trie", "insert", "search", "startsWith"]
      • Arguments: [[], ["apple"], ["apple"], ["app"]]
    • Expected Output: [-1, -1, 1, 1]
    • Justification: After inserting “apple”, “apple” exists in the Trie. There is also a word that starts with “app”, which is “apple”.
  2. Example 2:
    • Input:
      • Trie operations: ["Trie", "insert", "search", "startsWith", "search"]
      • Arguments: [[], ["banana"], ["apple"], ["ban"], ["banana"]]
    • Expected Output: [-1, -1, 0, 1, 1]
    • Justification: After inserting “banana”, “apple” does not exist in the Trie but a word that starts with “ban”, which is “banana”, does exist.
  3. Example 3:
    • Input:
      • Trie operations: ["Trie", "insert", "search", "search", "startsWith"]
      • Arguments: [[], ["grape"], ["grape"], ["grap"], ["gr"]]
    • Expected Output: [-1, -1, 1, 1, 1]
    • Justification: After inserting “grape”, “grape” exists in the Trie. There are words that start with “grap” and “gr”, which is “grape”.

Constraints:

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Solution

The trie is represented as a tree, where each node contains an array of pointers (or references) to its children and a boolean flag indicating if the current node marks the end of a word. When inserting or searching for a word, we start at the root node and navigate through the tree character by character until we either finish the operation or determine the word doesn’t exist in the trie.

Now, let’s break down the operations:

  1. Insert:
    • We begin at the root node.
    • For every character in the word, check if there’s a child node for it.
    • If the child node doesn’t exist, we create it.
    • Navigate to the child node and repeat the process for the next character.
    • Once the end of the word is reached, mark the current node as an endpoint of a word.
  2. Search:
    • Starting at the root, traverse the trie character by character.
    • For every character in the word, check if there’s a child node for it.
    • If at any point there isn’t a child node for the character, the word doesn’t exist in the trie.
    • If we can traverse the entire word and the last node is marked as an endpoint, the word exists in the trie.
  3. StartsWith:
    • The operation is similar to the search, but we don’t need the last node to be an endpoint.
    • If we can traverse the prefix without any missing nodes, there exists a word in the trie that starts with the given prefix.

Algorithm Walkthrough

Using Example 1:

  • ["Trie", "insert", "search", "startsWith"]
  • [[], ["apple"], ["apple"], ["app"]]
  1. Create an empty Trie.
  2. Insert “apple”.
    • Start from the root. For ‘a’, move to the child node or create one if it doesn’t exist.
    • Move to ‘p’, then the next ‘p’, followed by ‘l’ and finally ‘e’. Mark ‘e’ as the end of a word.
  3. Search for “apple”.
    • Start from the root and traverse nodes ‘a’ -> ‘p’ -> ‘p’ -> ‘l’ -> ‘e’. Since ‘e’ is marked as the end of a word, return true.
  4. Check if a word starts with “app”.
    • Traverse nodes for ‘a’ -> ‘p’ -> ‘p’. All nodes exist, so return true.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# class TrieNode:
#     def __init__(self):
#         self.children = {}  # Dictionary to store child nodes.
#         self.isEnd = False  # Flag to represent end of a word.

class Solution:
    def __init__(self):
        self.root = TrieNode()

    # Inserts a word into the trie.
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True

    # Returns if the word is in the trie.
    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.isEnd

    # Returns if there is any word in the trie that starts with the given prefix.
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

if __name__ == "__main__":
    trie = Solution()
    trie.insert("apple")
    print(trie.search("apple"))  # True
    print(trie.search("app"))    # False
    print(trie.startsWith("app"))# True

Complexity Analysis

  • Time Complexity:
    • Insert: (O(m)), where (m) is the key length.
    • Search and StartsWith: (O(m)) in the worst case scenario.
  • Space Complexity: (O(n \times m)), where (n) is the number of inserted keys and (m) is the average key length.

Design Add and Search Words Data Structure

Problem Statement

Design a data structure that supports the addition of new words and the ability to check if a string matches any previously added word.

Implement the Solution class:

  • Solution() Initializes the object.
  • void addWord(word) Inserts word into the data structure, making it available for future searches.
  • bool search(word) Checks if there is any word in the data structure that matches word. The method returns true if such a match exists, otherwise returns false.

Note: In the search query word, the character '.' can represent any single letter, effectively serving as a wildcard character.

Examples

Example 1:

  • Input:

    1
    2
    ["Solution", "addWord", "addWord", "search", "search"]
    [[], ["apple"], ["banana"], ["apple"], ["....."]]

  • Expected Output:

    1
    [-1, -1, -1, 1, 1]

  • Justification: After adding the words “apple” and “banana”, searching for “apple” will return true since “apple” is in the data structure. Searching for “…..” will also return true as both “apple” and “banana” match the pattern.

Example 2:

  • Input:

    1
    2
    ["Solution", "addWord", "addWord", "search", "search"]
    [[], ["cat"], ["dog"], ["c.t"], ["d..g"]]

  • Expected Output:

    1
    [-1, -1, -1, 1, 0]

  • Justification: “c.t” matches “cat” and “d..g” doesn’t matches “dog”.

Example 3:

  • Input:

    1
    2
    ["Solution", "addWord", "search", "search"]
    [[], ["hello"], ["h.llo"], ["h...o"]]

  • Expected Output:

    1
    [-1, -1, 1, 0]

  • Justification: “h.llo” and “h…o” both match “hello”.

Constraints:

  • 1 <= word.length <= 25
  • word in addWord consists of lowercase English letters.
  • word in search consist of ‘.’ or lowercase English letters.
  • There will be at most 2 dots in word for search queries.
  • At most 104 calls will be made to addWord and search.

Solution

The crux of the problem lies in efficiently inserting words and then searching for them, even if the query includes wildcards. To solve this, we utilize the trie (prefix tree) data structure. A trie is a tree-like structure that’s useful for storing a dynamic set of strings, especially when the dataset involves large numbers of queries on prefixes of strings. Each node of the trie can represent a character of a word, and the path from the root node to any node represents the word stored up to that point. The key operation for the wildcard is a recursive search, which allows us to explore multiple paths in the trie when we encounter the wildcard character.

1. Trie Data Structure: Every node of the trie contains multiple child nodes (one for each character of the alphabet). We start with a root node that represents an empty string. Each level of the trie represents the next character of a word.

2. Adding a Word: To insert a word into our trie, we begin at the root and traverse down the trie based on the characters in the word. If a particular character doesn’t have a corresponding child node in the current node, we create a new child node for that character. Once we’ve processed every character of the word, we mark the final node as the end of a valid word.

3. Searching: Searching for a word is similar to inserting, but with an additional consideration for the wildcard character (‘.’). If we encounter a ‘.’, we must consider all child nodes of the current node and recursively continue our search from each of them. If any of the paths result in a match, we return true. If we reach the end of a word without encountering any mismatches or premature ends, we’ve found a valid word in our trie.

This trie-based approach ensures efficient operations for both inserting and searching for words. In cases without wildcards, the search operation can be performed in linear time relative to the word’s length. However, with wildcards, the time complexity might increase, but the trie structure still ensures that we do this efficiently.

Algorithm Walkthrough

Given the word “apple” to insert and then search for “…..”:

  1. Start at the root node.
  2. For inserting “apple”:
    • At ‘a’, move down or create a node if it doesn’t exist.
    • At ‘p’, move down or create.
    • Do the same for the next ‘p’, ‘l’, and ‘e’.
    • Mark the last node (for ‘e’) as the end of a word.
  3. For searching “…..”:
    • At the first ‘.’, check all child nodes and continue.
    • Repeat for each ‘.’.
    • If any path leads to a node that represents the end of a word, return true.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# class TrieNode:
#     def __init__(self):
#         # Initialize children as a dictionary to represent all possible next characters.
#         self.children = {}  
#         # Flag to check if the current node marks the end of any word.
#         self.isEnd = False  

class Solution:

    def __init__(self):
        # Initialize the root node.
        self.root = TrieNode()

    def addWord(self, word: str):
        node = self.root
        for ch in word:
            # If current character isn't already a child of the node, add it.
            if ch not in node.children:
                node.children[ch] = TrieNode()
            # Move on to the next character/node.
            node = node.children[ch]
        # After processing all characters of the word, mark the current node as end of a word.
        node.isEnd = True

    def search(self, word: str) -> bool:
        return self.searchInNode(word, self.root)

    def searchInNode(self, word: str, node: TrieNode) -> bool:
        for i, ch in enumerate(word):
            # Check for wildcard character.
            if ch == '.':
                # Recursively search for all possible characters in place of the wildcard.
                return any(self.searchInNode(word[i+1:], node.children[child]) for child in node.children if child)
            # If character doesn't exist in children, word can't exist in the trie.
            if ch not in node.children:
                return False
            # Move to the next character/node.
            node = node.children[ch]
        # After processing all characters of the word, return if it's a valid word.
        return node.isEnd

# Test the algorithm
obj = Solution()
obj.addWord("apple")
obj.addWord("banana")
print(obj.search("apple"))  # True
print(obj.search("....."))  # True

Complexity Analysis

  • Time Complexity:
    • Insertion (addWord): O(n), where n is the length of the word. This is because each insertion operation runs in linear time with respect to the length of the word.
    • Search: O(n * m) in the worst case, where n is the length of the word and m is the total number of nodes in the Trie. This happens when the search word contains dots (‘.’). However, for words without dots, the search is O(n).
  • Space Complexity: O(m n), where m is the total number of Trie nodes and n is the average number of characters in the words. Each Trie node has up to 26 children (for each letter of the alphabet). In the worst case, when no nodes are shared, the space complexity is O(m n).

Author：Hasuer

Link：https://hasuer.github.io/32-test-your-knowledge-medium/index.html

Publish date：June 1st 2024, 10:28:14 am

Update date：May 28th 2024, 11:32:22 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Daily Temperatures
    1. 1.1. Problem Statement
      1. 1.1.1. Examples
    2. 1.2. Solution
      1. 1.2.1. Algorithm Walkthrough
    3. 1.3. Code Development
    4. 1.4. Complexity Analysis
  2. 2. Group Anagrams
    1. 2.1. Problem Statement
    2. 2.2. Example Generation
    3. 2.3. Solution
      1. 2.3.1. Algorithm Walkthrough
    4. 2.4. Code
    5. 2.5. Complexity Analysis
  3. 3. Decode String
    1. 3.1. Problem Statement
      1. 3.1.1. Examples
    2. 3.2. Solution
      1. 3.2.1. Algorithm Walkthrough
    3. 3.3. Code
    4. 3.4. Complexity Analysis
  4. 4. Valid Sudoku
    1. 4.1. Problem Statement
    2. 4.2. Solution
      1. 4.2.1. Algorithm Walkthrough
    3. 4.3. Code
    4. 4.4. Complexity Analysis
  5. 5. Product of Array Except Self
    1. 5.1. Problem Statement
      1. 5.1.1. Examples
    2. 5.2. Solution
      1. 5.2.1. Algorithm Walkthrough
    3. 5.3. Code
    4. 5.4. Complexity Analysis:
  6. 6. Maximum Product Subarray
    1. 6.1. Problem Statement
      1. 6.1.1. Examples
    2. 6.2. Solution
      1. 6.2.1. Algorithm Walkthrough
    3. 6.3. Code
    4. 6.4. Complexity Analysis
  7. 7. Container With Most Water
    1. 7.1. Problem Statement
      1. 7.1.1. Examples
    2. 7.2. Solution
      1. 7.2.1. Algorithm Walkthrough
    3. 7.3. Code
    4. 7.4. Complexity Analysis:
  8. 8. Palindromic Substrings
    1. 8.1. Problem Statement
      1. 8.1.1. Example
    2. 8.2. Solution
      1. 8.2.1. Algorithm Walkthrough
    3. 8.3. Code
    4. 8.4. Complexity Analysis:
  9. 9. Remove Nth Node From End of List
    1. 9.1. Problem Statement
    2. 9.2. Solution
      1. 9.2.1. Algorithm Walkthrough
    3. 9.3. Code
    4. 9.4. Complexity Analysis
  10. 10. Find Minimum in Rotated Sorted Array
    1. 10.1. Problem Statement
    2. 10.2. Solution
      1. 10.2.1. Algorithm Walkthrough
    3. 10.3. Code
    4. 10.4. Complexity Analysis
  11. 11. Pacific Atlantic Water Flow
    1. 11.1. Problem Statement:
    2. 11.2. Solution
      1. 11.2.1. Algorithm Walkthrough
    3. 11.3. Code
    4. 11.4. Complexity Analysis
  12. 12. Validate Binary Search Tree
    1. 12.1. Problem Statement
      1. 12.1.1. Example Generation
    2. 12.2. Solution
      1. 12.2.1. Algorithm Walkthrough
    3. 12.3. Code
    4. 12.4. Complexity Analysis
  13. 13. Construct Binary Tree from Preorder and Inorder Traversal
    1. 13.1. Problem Statement
      1. 13.1.1. Example Generation
    2. 13.2. Solution
      1. 13.2.1. Algorithm Walkthrough
    3. 13.3. Code
    4. 13.4. Complexity Analysis
  14. 14. Clone Graph
    1. 14.1. Problem Statement
    2. 14.2. Solution
      1. 14.2.1. Algorithm Walkthrough (using Example 1):
    3. 14.3. Code
    4. 14.4. Complexity Analysis
  15. 15. House Robber II
    1. 15.1. Problem Statement
      1. 15.1.1. Examples
    2. 15.2. Solution
      1. 15.2.1. Algorithm Walkthrough
    3. 15.3. Code
    4. 15.4. Complexity Analysis
  16. 16. Decode Ways
    1. 16.1. Problem Statement
      1. 16.1.1. Examples
    2. 16.2. Solution
      1. 16.2.1. Algorithm Walkthrough
    3. 16.3. Code
    4. 16.4. Complexity Analysis
  17. 17. Unique Paths
    1. 17.1. Problem Statement
      1. 17.1.1. Examples
    2. 17.2. Solution
      1. 17.2.1. Algorithm Walkthrough
    3. 17.3. Code
    4. 17.4. Complexity Analysis
  18. 18. Word Break
    1. 18.1. Problem Statement
      1. 18.1.1. Examples
    2. 18.2. Solution
      1. 18.2.1. Algorithm Walkthrough
    3. 18.3. Code
    4. 18.4. Complexity Analysis
  19. 19. Lowest Common Ancestor of a Binary Search Tree
    1. 19.1. Problem Statement
      1. 19.1.1. Examples
    2. 19.2. Solution
      1. 19.2.1. Algorithm Walkthrough
    3. 19.3. Code
    4. 19.4. Complexity Analysis
  20. 20. Longest Consecutive Sequence
    1. 20.1. Problem Statement
      1. 20.1.1. Examples
    2. 20.2. Solution
      1. 20.2.1. Algorithm Walkthrough
    3. 20.3. Code
    4. 20.4. Complexity Analysis
  21. 21. Meeting Rooms II
    1. 21.1. Problem Statement
      1. 21.1.1. Examples
    2. 21.2. Solution
      1. 21.2.1. Algorithm Walkthrough
    3. 21.3. Code
    4. 21.4. Complexity Analysis
  22. 22. Encode and Decode Strings
    1. 22.1. Problem Statement
      1. 22.1.1. Examples
    2. 22.2. Solution
      1. 22.2.1. Algorithm Walkthrough
    3. 22.3. Code
    4. 22.4. Complexity Analysis
  23. 23. Number of Connected Components in an Undirected Graph
    1. 23.1. Problem Statement
      1. 23.1.1. Examples
    2. 23.2. Solution
      1. 23.2.1. Algorithm Walkthrough
    3. 23.3. Code
    4. 23.4. Complexity Analysis
  24. 24. Graph Valid Tree
    1. 24.1. Problem Statement
      1. 24.1.1. Examples
    2. 24.2. Solution
      1. 24.2.1. Algorithm Walkthrough
    3. 24.3. Code
  25. 25. Complexity Analysis
  26. 26. Implement Trie (Prefix Tree)
    1. 26.1. Problem Statement
      1. 26.1.1. Examples
    2. 26.2. Solution
      1. 26.2.1. Algorithm Walkthrough
    3. 26.3. Code
  27. 27. Complexity Analysis
  28. 28. Design Add and Search Words Data Structure
    1. 28.1. Problem Statement
      1. 28.1.1. Examples
    2. 28.2. Solution
      1. 28.2.1. Algorithm Walkthrough
    3. 28.3. Code
    4. 28.4. Complexity Analysis
Total : 41
2024
2022
2021
Interview
技术笔记 Grokking-Interview-Pattern