Skip to content

LeetCode Top 150#

The LeetCode Top 150 is a curated LeetCode list for interview prep. Each problem includes the statement, Python solution(s), and explanations in the same format as DSA Patterns.

Explore overlaps

Compare this sheet with others in the DSA Venn Explorer.

How to use

  1. Try on LeetCode first — attempt the problem before reading solutions.
  2. Check the pattern link (when shown) for additional approaches in DSA Patterns.
  3. Compare your solution with the reference code below.

Arrays & Hashing#

1. Candy (Leetcode:135)#

Problem Statement

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.

  • Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2] Output: 4 Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

  • n == ratings.length

  • 1 <= n <= 2 * 104

  • 0 <= ratings[i] <= 2 * 104

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def candy(self, ratings: List[int]) -> int:
            n = len(ratings)
            # Initialize with one candy becuase each child must have at least one candy.
            candies = [1] * n 

            # Iterate from left to right 
            for i in range(1, n):
                # Check if current rating is greater than left neighbor
                if ratings[i] > ratings[i - 1]:
                    # Rating is higher so deserves more candy than left neighbor
                    candies[i] = candies[i - 1] + 1

            # Iterate from right to left
            for i in range(n - 2, -1, -1):
                # Check if current rating is greater than right neighbor
                if ratings[i] > ratings[i + 1]:
                    # Take max to check if the value is already greater than its right neighbor + 1.
                    candies[i] = max(candies[i], candies[i + 1] + 1)

            return sum(candies)
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

2. Contains Duplicate II (Leetcode:219)#

Problem Statement

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3 Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1 Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2 Output: false

Constraints:

  • 1 <= nums.length <= 105

  • -109 <= nums[i] <= 109

  • 0 <= k <= 105

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
            window = set()
            L = 0

            for R in range(len(nums)):
                if R - L > k:
                    window.remove(nums[L])
                    L += 1
                if nums[R] in window:
                    return True
                window.add(nums[R])
            return False
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

3. Find the Index of the First Occurrence in a String (Leetcode:28)#

Also in DSA Patterns

Find the Index of First Occurrence in a String — 20. String Matching (may include extra approaches and complexity analysis).

Problem Statement

Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad" Output: 0

Example 2:

Input: haystack = "leetcode", needle = "leeto" Output: -1

Constraints:

1 <= haystack.length, needle.length <= 10^4, lowercase English letters.

Code and Explanation 

 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 strStr(self, haystack: str, needle: str) -> int:
        if needle == "":
            return 0
        lps = [0] * len(needle)

        prevLPS, i = 0, 1
        while i < len(needle):
            if needle[i] == needle[prevLPS]:
                lps[i] = prevLPS + 1
                prevLPS += 1
                i += 1
            elif prevLPS == 0:
                lps[i] = 0
                i += 1
            else:
                prevLPS = lps[prevLPS - 1]

        i = 0  # ptr for haystack
        j = 0  # ptr for needle
        while i < len(haystack):
            if haystack[i] == needle[j]:
                i, j = i + 1, j + 1
            else:
                if j == 0:
                    i += 1
                else:
                    j = lps[j - 1]
            if j == len(needle):
                return i - len(needle)
        return -1
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

4. Gas Station (Leetcode:134)#

Also in DSA Patterns

Gas Station — 10. Greedy Algorithm (may include extra approaches and complexity analysis).

Problem Statement

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Output: 3 Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3] Output: -1 Explanation: You can't start at station 0 or 1, as there is not enough gas to travel to the next station. Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 0. Your tank = 4 - 3 + 2 = 3 Travel to station 1. Your tank = 3 - 3 + 3 = 3 You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3. Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

  • n == gas.length == cost.length
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104
  • The input is generated such that the answer is unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        start, end = len(gas) - 1, 0
        total = gas[start] - cost[start]

        while start >= end:
            while total < 0 and start >= end:
                start -= 1
                total += gas[start] - cost[start]
            if start == end:
                return start
            total += gas[end] - cost[end]
            end += 1
        return -1
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

5. Group Anagrams (Leetcode:49)#

Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Constraints:

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

 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 groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}

        # Iterate over strings
        for s in strs: # O(m)
            count = {}

            # Count frequency of each character
            for char in s: # O(n)
                count[char] = count.get(char, 0) + 1

            # Convert count Dict to List, sort it, and then convert to Tuple (we cannot use dicts or lists as keys in a hashmap)
            tup = tuple(sorted(count.items())) # O(1) because there is limited amount of possible keys in the alphabet -> O(26) + O(26*log26) + O(26)

            if tup in groups:
                groups[tup].append(s)
            else:
                groups[tup] = [s] 

        return list(groups.values())

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)

        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord("a")] += 1
            ans[tuple(count)].append(s)
        return list(ans.values())
Explanation:

  1. Key = sorted tuple of chars groups anagrams.
  2. Append word to bucket; return all buckets.
  3. O(n * k log k) for word length k.
  4. Time complexity: O(n × k log k)
  5. Space complexity: O(n × k)

6. H-Index (Leetcode:274)#

Problem Statement

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example 1:

Input: citations = [3,0,6,1,5] Output: 3 Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

Input: citations = [1,3,1] Output: 1

Constraints:

  • n == citations.length

  • 1 <= n <= 5000

  • 0 <= citations[i] <= 1000

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def hIndex(self, citations: List[int]) -> int:
            length = len(citations)
            citations.sort()
            for i in range(length):
                if citations[i] >= length - i:
                    return length - i
            return 0
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

7. Happy Number (Leetcode:202)#

Also in DSA Patterns

Happy Number — 02. Fast and Slow Pointers (may include extra approaches and complexity analysis).

Problem Statement

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2^31 - 1

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def isHappy(self, n: int) -> bool:
        slow, fast = n, self.sumSquareDigits(n)

        while slow != fast:
            fast = self.sumSquareDigits(fast)
            fast = self.sumSquareDigits(fast)
            slow = self.sumSquareDigits(slow)

        return True if fast == 1 else False

    def sumSquareDigits(self, n):
        output = 0
        while n:
            output += (n % 10) ** 2
            n = n // 10
        return output
Explanation:

  1. The slow pointer moves one step at a time.
  2. The fast pointer moves two steps at a time.
  3. Cycle Detection: If a cycle exists, the fast pointer will meet the slow pointer inside the cycle.
  4. Middle Element: The slow pointer will be at the middle when the fast pointer reaches the end.
  5. Pattern Matching: Helps detect patterns like palindromes by dividing the structure into two parts.

8. Integer to Roman (Leetcode:12)#

Problem Statement

Seven different symbols represent Roman numerals with the following values:

Symbol Value

I 1

V 5

X 10

L 50

C 100

D 500

M 1000

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

  • If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.

  • If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).

  • Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.

Given an integer, convert it to a Roman numeral.

Example 1:

Input: num = 3749

Output: "MMMDCCXLIX"

Explanation:

3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M) 700 = DCC as 500 (D) + 100 (C) + 100 (C) 40 = XL as 10 (X) less of 50 (L) 9 = IX as 1 (I) less of 10 (X) Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 58

Output: "LVIII"

Explanation:

50 = L 8 = VIII

Example 3:

Input: num = 1994

Output: "MCMXCIV"

Explanation:

1000 = M 900 = CM 90 = XC 4 = IV

Constraints:

  • 1 <= num <= 3999
Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def intToRoman(self, num: int) -> str:
            symList = [
                ["I", 1],
                ["IV", 4],
                ["V", 5],
                ["IX", 9],
                ["X", 10],
                ["XL", 40],
                ["L", 50],
                ["XC", 90],
                ["C", 100],
                ["CD", 400],
                ["D", 500],
                ["CM", 900],
                ["M", 1000],
            ]
            res = ""
            for sym, val in reversed(symList):
                if num // val:
                    count = num // val
                    res += sym * count
                    num = num % val
            return res
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

9. Isomorphic Strings (Leetcode:205)#

Problem Statement

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"

Output: true

Explanation:

The strings s and t can be made identical by:

  • Mapping 'e' to 'a'.

  • Mapping 'g' to 'd'.

Example 2:

Input: s = "f11", t = "b23"

Output: false

Explanation:

The strings s and t can not be made identical as '1' needs to be mapped to both '2' and '3'.

Example 3:

Input: s = "paper", t = "title"

Output: true

Constraints:

  • 1 <= s.length <= 5 * 104

  • t.length == s.length

  • s and t consist of any valid ascii character.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def isIsomorphic(self, s: str, t: str) -> bool:
            mapST, mapTS = {}, {}

            for c1, c2 in zip(s, t):
                if (c1 in mapST and mapST[c1] != c2) or (c2 in mapTS and mapTS[c2] != c1):
                    return False
                mapST[c1] = c2
                mapTS[c2] = c1

            return True
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

10. Jump Game (Leetcode:55)#

Also in DSA Patterns

Jump Game — 10. Greedy Algorithm (may include extra approaches and complexity analysis).

Problem Statement

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def canJump(self, nums: list[int]) -> bool:
        farthest = 0
        for i, jump in enumerate(nums):
            if i > farthest:
                return False
            farthest = max(farthest, i + jump)
        return True
Explanation:

  1. Track farthest reach: far = max index reachable so far.
  2. Early fail: If i > far, index i is unreachable.
  3. Update reach: far = max(far, i + nums[i]).
  4. Success: Reach last index. O(n) time, O(1) space.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def canJump(self, nums: list[int]) -> bool:
        n = len(nums)
        dp = [False] * n
        dp[0] = True
        for i in range(n):
            if not dp[i]:
                continue
            for step in range(1, nums[i] + 1):
                if i + step >= n:
                    return True
                dp[i + step] = True
        return dp[-1]
Explanation:

  1. State: dp[i] = can we reach index i?
  2. From each reachable i: Mark all i+1 .. i+nums[i] reachable.
  3. **Return dp[n-1].
  4. Correct but slower: O(n²) worst case.
  5. Time complexity: O(n²)
  6. Space complexity: O(n)

11. Jump Game II (Leetcode:45)#

Also in DSA Patterns

Jump Game II — 10. Greedy Algorithm (may include extra approaches and complexity analysis).

Problem Statement

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.

Example 1:

Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4] Output: 2

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def jump(self, nums: List[int]) -> int:
        l, r = 0, 0
        res = 0
        while r < (len(nums) - 1):
            maxJump = 0
            for i in range(l, r + 1):
                maxJump = max(maxJump, i + nums[i])
            l = r + 1
            r = maxJump
            res += 1
        return res
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

12. Length of Last Word (Leetcode:58)#

Problem Statement

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example 1:

Input: s = "Hello World" Output: 5 Explanation: The last word is "World" with length 5.

Example 2:

Input: s = " fly me to the moon " Output: 4 Explanation: The last word is "moon" with length 4.

Example 3:

Input: s = "luffy is still joyboy" Output: 6 Explanation: The last word is "joyboy" with length 6.

Constraints:

  • 1 <= s.length <= 104

  • s consists of only English letters and spaces ' '.

  • There will be at least one word in s.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def lengthOfLastWord(self, s: str) -> int:
            """
        one shortcut
        """
        #   return len(s.split()[-1])
            count = 0
        for i in range(len(s) - 1, -1, -1):
            char = s[i]
            if char == " ":
                if count >= 1:
                    return count
            else:
                count += 1
        return count
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

13. Longest Common Prefix (Leetcode:14)#

Problem Statement

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"] Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

Constraints:

  • 1 <= strs.length <= 200

  • 0 <= strs[i].length <= 200

  • strs[i] consists of only lowercase English letters if it is non-empty.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def longestCommonPrefix(self, strs: List[str]) -> str:
            for i in range(len(strs[0])):
                for s in strs:
                    if i >= len(s) or s[i] != strs[0][i]:
                        return strs[0][:i]
            return strs[0]
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

14. Longest Consecutive Sequence (Leetcode:128)#

Problem Statement

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive sequence is [1, 2, 3, 4].

Constraints:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0

        for n in numSet:
            # check if its the start of a sequence
            if (n - 1) not in numSet:
                length = 1
                while (n + length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest
Explanation:

  1. Insert all numbers into a set.
  2. Only start from sequence beginnings: Skip if num-1 exists.
  3. Extend forward: Count while num+length in set.
  4. Track max length. O(n) average time.
  5. Time complexity: O(n)
  6. Space complexity: O(n)

15. Majority Element (Leetcode:169)#

Problem Statement

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3] Output: 3 Example 2:

Input: nums = [2,2,1,1,1,2,2] Output: 2

Constraints:

  • n == nums.length

  • 1 <= n <= 5 * 104

  • -109 <= nums[i] <= 109

  • The input is generated such that a majority element will exist in the array.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            res, count = 0, 0

            for n in nums:
                if count == 0:
                    res = n
                count += (1 if n == res else -1)

            return res
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

16. Merge Sorted Array (Leetcode:88)#

Problem Statement

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and []. The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

  • nums1.length == m + n

  • nums2.length == n

  • 0 <= m, n <= 200

  • 1 <= m + n <= 200

  • -109 <= nums1[i], nums2[j] <= 109

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """
            while m > 0 and n > 0:
                if nums1[m-1] >= nums2[n-1]:
                    nums1[m+n-1] = nums1[m-1]
                    m -= 1
                else:
                    nums1[m+n-1] = nums2[n-1]
                    n -= 1
            if n > 0:
                nums1[:n] = nums2[:n]
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

17. Product of Array Except Self (Leetcode:238)#

Also in DSA Patterns

Product of Array Except Self — 00. Prefix Sum (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up:

Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def productExceptSelf(self, nums: List[int]) -> List[int]:
                n = len(nums)
                answer = [1] * n

                prefix = 1
                for i in range(n):
                    answer[i] = prefix
                    prefix *= nums[i]

                suffix = 1
                for i in range(n - 1, -1, -1):
                    answer[i] *= suffix
                    suffix *= nums[i]

                return answer
Explanation:

  1. Prefix pass: Fill answer[i] with product of all elements left of i using running prefix.
  2. Suffix pass: Walk right to left, multiplying running suffix into answer[i].
  3. No division: Only multiplication, satisfying the problem constraint.
  4. Time complexity: O(n)
  5. Space complexity: O(1)

18. Ransom Note (Leetcode:383)#

Problem Statement

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input: ransomNote = "a", magazine = "b" Output: false Example 2:

Input: ransomNote = "aa", magazine = "ab" Output: false Example 3:

Input: ransomNote = "aa", magazine = "aab" Output: true

Constraints:

  • 1 <= ransomNote.length, magazine.length <= 105

  • ransomNote and magazine consist of lowercase English letters.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    from collections import Counter

    class Solution:
        def canConstruct(self, ransomNote: str, magazine: str) -> bool:
            r_counter = Counter(ransomNote)
            m_counter = Counter(magazine)
            # magazine contains (>=) ransomNote
            for c in ransomNote:
                if m_counter[c] < r_counter[c]:
                    return False
            return True
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

19. Remove Duplicates from Sorted Array (Leetcode:26)#

Also in DSA Patterns

Remove Duplicates from Sorted Array — 01. Two Pointers (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Return k after placing the final result in the first k slots of nums.

Example 1:

Input: nums = [1,1,2] Output: 2, nums = [1,2,_]

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,,,,,_]

Constraints:

1 <= nums.length <= 3 * 10^4 -10^4 <= nums[i] <= 10^4 nums is sorted in non-decreasing order.

Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        L = 1

        for R in range(1, len(nums)):
            if nums[R] != nums[R - 1]:
                nums[L] = nums[R]
                L += 1
        return L
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

20. Remove Duplicates from Sorted Array II (Leetcode:80)#

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3,_] Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3] Output: 7, nums = [0,0,1,1,2,3,3,,] Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

  • 1 <= nums.length <= 3 * 104

  • -104 <= nums[i] <= 104

  • nums is sorted in non-decreasing order.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def removeDuplicates(self, nums: List[int]) -> int:
            l, r = 0, 0

            while r < len(nums):
                count = 1
                while r + 1 < len(nums) and nums[r] == nums[r + 1]:
                    r += 1
                    count += 1

                for i in range(min(2, count)):
                    nums[l] = nums[r]
                    l += 1
                r += 1
            return l
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

21. Remove Element (Leetcode:27)#

Problem Statement

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.

  • Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array int val = ...; // Value to remove int[] expectedNums = [...]; // The expected answer with correct length. // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length; sort(nums, 0, k); // Sort the first k elements of nums for (int i = 0; i < actualLength; i++) { assert nums[i] == expectedNums[i]; }

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2,,] Explanation: Your function should return k = 2, with the first two elements of nums being 2. It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3,,,_] Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4. Note that the five elements can be returned in any order. It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

  • 0 <= nums.length <= 100

  • 0 <= nums[i] <= 50

  • 0 <= val <= 100

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            k = 0
            for i in range(len(nums)):
                if nums[i] != val:
                    nums[k] = nums[i]
                    k += 1
            return k

    # Optimized solution with the same time and space complexity
    class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            # Avoid unessary copy operations in a previous solution, when k == i and nums[i] != val 
            # by swapping nums[i] and the last element of the array (nums[n])
            n = len(nums)
            i = 0

            while i < n:
                if nums[i] == val:
                    nums[i], nums[n - 1] = nums[n - 1], nums[i]
                    n -= 1  # decrement the length of the array by discarding the last element
                else:
                    i += 1

            return n
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

22. Reverse Words in a String (Leetcode:151)#

Also in DSA Patterns

Reverse Words in a String — 01. Two Pointers (may include extra approaches and complexity analysis).

Problem Statement

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue" Output: "blue is sky the"

Example 2:

Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

1 <= s.length <= 10^4 s contains English letters, digits, and spaces. There is at least one word in s.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def reverseWords(self, s: str) -> str:
                res = []
                left = right = len(s) - 1

                while left >= 0:
                    # Skip trailing spaces
                    while left >= 0 and s[left] == " ":
                        left -= 1
                    if left < 0:
                        break

                    right = left
                    # Move left to the start of the word
                    while left >= 0 and s[left] != " ":
                        left -= 1

                    # Append the word
                    res.append(s[left+1:right+1])

                return " ".join(res)
Explanation:

  1. This technique is ideal for problems like finding unique elements, counting subarrays, or rearranging elements.
  2. One pointer (typically called slow) moves through the array, while the other pointer (called fast) explores further elements.
  3. The slow pointer often keeps track of the current valid position, while the fast pointer scans for new valid elements.
  4. This is especially useful for sliding window problems, where the window expands and shrinks by adjusting the pointers.
  5. It can also be used to remove duplicates in-place in an array.

23. Roman to Integer (Leetcode:13)#

Problem Statement

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.

  • X can be placed before L (50) and C (100) to make 40 and 90.

  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III" Output: 3 Explanation: III = 3.

Example 2:

Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

  • 1 <= s.length <= 15

  • s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').

  • It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def romanToInt(self, s: str) -> int:
            roman = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
            res = 0
            for i in range(len(s)):
                if i + 1 < len(s) and roman[s[i]] < roman[s[i + 1]]:
                    res -= roman[s[i]]
                else:
                    res += roman[s[i]]
            return res
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

24. Rotate Array (Leetcode:189)#

Problem Statement

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
  • 0 <= k <= 10^5

Follow up:

  • Try to come up with as many solutions as you can. There are at least three different approaches. Solve it in-place with O(1) extra space.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        l, r = 0, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l, r = l + 1, r - 1

        l, r = 0, k - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l, r = l + 1, r - 1

        l, r = k, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l, r = l + 1, r - 1
Explanation:

  1. This technique is ideal for problems like finding unique elements, counting subarrays, or rearranging elements.
  2. One pointer (typically called slow) moves through the array, while the other pointer (called fast) explores further elements.
  3. The slow pointer often keeps track of the current valid position, while the fast pointer scans for new valid elements.
  4. This is especially useful for sliding window problems, where the window expands and shrinks by adjusting the pointers.
  5. It can also be used to remove duplicates in-place in an array.

25. Text Justification (Leetcode:68)#

Problem Statement

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

Note:

  • A word is defined as a character sequence consisting of non-space characters only.

  • Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.

  • The input array words contains at least one word.

Example 1:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: [    "This    is    an",    "example  of text",    "justification.  " ]

Example 2:

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16 Output: [   "What   must   be",   "acknowledgment  ",   "shall be        " ] Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word.

Example 3:

Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20 Output: [   "Science  is  what we", "understand      well",   "enough to explain to",   "a  computer.  Art is",   "everything  else  we",   "do                  " ]

Constraints:

  • 1 <= words.length <= 300

  • 1 <= words[i].length <= 20

  • words[i] consists of only English letters and symbols.

  • 1 <= maxWidth <= 100

  • words[i].length <= maxWidth

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
            res = []
            line = []  # Words in current line
            length = 0  # Current line length
            i = 0
            while i < len(words):
                if length + len(line) + len(words[i]) > maxWidth:
                    # Line complete
                    extra_space = maxWidth - length
                    word_cnt = len(line) - 1
                    spaces = extra_space // max(1, word_cnt)
                    remainder = extra_space % max(1, word_cnt)

                    for j in range(max(1, len(line) - 1)):
                        line[j] += " " * spaces
                        if remainder:
                            line[j] += " "
                            remainder -= 1

                    res.append("".join(line))
                    line, length = [], 0  # Reset line and length

                line.append(words[i])
                length += len(words[i])
                i += 1

            # Handling the last line
            last_line = " ".join(line)
            trail_spaces = maxWidth - len(last_line)
            res.append(last_line + (trail_spaces * " "))

            return res
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

26. Two Sum (Leetcode:1)#

Also in DSA Patterns

Two Sum — 01. Two Pointers (may include extra approaches and complexity analysis).

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

2 <= nums.length <= 10^4 -10^9 <= nums[i] <= 10^9 -10^9 <= target <= 10^9 Only one valid answer exists.

Follow Up:

Can you come up with an algorithm that is less than O(n^2) time complexity?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from typing import List

            def two_sum(nums: List[int], target: int) -> List[int]:
                # Step 1: Pair values with original indices
                paired = [(num, i) for i, num in enumerate(nums)]

                # Step 2: Sort by the numbers
                paired.sort(key=lambda x: x[0])

                # Step 3: Use two pointers
                left, right = 0, len(paired) - 1
                while left < right:
                    current_sum = paired[left][0] + paired[right][0]
                    if current_sum == target:
                        # Step 4: Return the original indices
                        return [paired[left][1], paired[right][1]]
                    elif current_sum < target:
                        left += 1
                    else:
                        right -= 1

                # By problem constraints, this line should never be reached
                raise ValueError("No two sum solution found")
Explanation:

  1. Scan the array once: Loop through nums with index i and value num.
  2. Look for the complement: Compute target - num. If that value is already in seen, return [seen[complement], i].
  3. Store what you have seen: Otherwise record seen[num] = i so a later element can pair with it.
  4. Time complexity: O(n)
  5. Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        indexed = sorted(enumerate(nums), key=lambda x: x[1])
        left, right = 0, len(indexed) - 1
        while left < right:
            total = indexed[left][1] + indexed[right][1]
            if total == target:
                return [indexed[left][0], indexed[right][0]]
            if total < target:
                left += 1
            else:
                right -= 1
        return []
Explanation:

  1. Pair values with indices: Build [(num, index), ...] so sorting does not lose original positions.
  2. Sort by value: Sort pairs ascending so two pointers can search for the target sum.
  3. Move pointers inward: If sum is too small, move left right; if too large, move right left; if equal, return stored indices.
  4. Tradeoff: Easy to visualize but sorting costs O(n log n) vs O(n) for the hash map.
  5. Time complexity: O(n log n)
  6. Space complexity: O(n)

27. Valid Anagram (Leetcode:242)#

Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word formed by rearranging the letters of another.

Example 1:

Input: s = "anagram", t = "nagaram" Output: true

Constraints:

  • 1 <= s.length, t.length <= 5 * 10^4
  • s and t consist of lowercase English letters
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        countS, countT = {}, {}

        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        return countS == countT


    # easier solution
    #return True if sorted(s) == sorted(t) else False
Explanation:

  1. Count chars in s, decrement for t.
  2. Anagram iff all counts zero.
  3. O(n) time.
  4. Time complexity: O(n)
  5. Space complexity: O(1)

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

  1. Sort both strings and compare equality.
  2. O(n log n) but very short code.
  3. Time complexity: O(n log n)
  4. Space complexity: O(n)

28. Word Pattern (Leetcode:290)#

Problem Statement

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Specifically:

  • Each letter in pattern maps to exactly one unique word in s.

  • Each unique word in s maps to exactly one letter in pattern.

  • No two letters map to the same word, and no two words map to the same letter.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"

Output: true

Explanation:

The bijection can be established as:

  • 'a' maps to "dog".

  • 'b' maps to "cat".

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"

Output: false

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"

Output: false

Constraints:

  • 1 <= pattern.length <= 300

  • pattern contains only lower-case English letters.

  • 1 <= s.length <= 3000

  • s contains only lowercase English letters and spaces ' '.

  • s does not contain any leading or trailing spaces.

  • All the words in s are separated by a single space.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def wordPattern(self, pattern: str, s: str) -> bool:
            words = s.split(" ")
            if len(pattern) != len(words):
                return False
            charToWord = {}
            wordToChar = {}

            for c, w in zip(pattern, words):
                if c in charToWord and charToWord[c] != w:
                    return False
                if w in wordToChar and wordToChar[w] != c:
                    return False
                charToWord[c] = w
                wordToChar[w] = c
            return True
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

29. Zigzag Conversion (Leetcode:6)#

Problem Statement

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N A P L S I I G Y I R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I

Example 3:

Input: s = "A", numRows = 1 Output: "A"

Constraints:

  • 1 <= s.length <= 1000

  • s consists of English letters (lower-case and upper-case), ',' and '.'.

  • 1 <= numRows <= 1000

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def convert(self, s: str, numRows: int) -> str:
            if numRows == 1 or numRows >= len(s):
                return s

            res = [""] * numRows

            index = 0
            step = 1
            for c in s:
                res[index] += c
                if index == 0:
                    step = 1
                elif index == numRows - 1:
                    step = -1
                index += step

            return "".join(res)
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

Backtracking#

30. Combination Sum (Leetcode:39)#

Also in DSA Patterns

Combination Sum — 12. Backtracking (may include extra approaches and complexity analysis).

Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1 Output: []

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []

        def backtrack(start: int, remaining: int, path: list[int]) -> None:
            if remaining == 0:
                result.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break
                path.append(candidates[i])
                backtrack(i, remaining - candidates[i], path)
                path.pop()

        candidates.sort()
        backtrack(0, target, [])
        return result
Explanation:

  1. Sort candidates: Helps prune and handle duplicates if needed.
  2. Choose / explore / undo: Add a candidate, recurse with reduced target, remove on backtrack.
  3. Accept when target hits zero: Append current combination to results.
  4. Avoid reuse: Recurse from same index i to allow reusing same number.
  5. Time complexity: O(2^target)
  6. Space complexity: O(target)

31. Combinations (Leetcode:77)#

Also in DSA Patterns

Combinations — 12. Backtracking (may include extra approaches and complexity analysis).

Problem Statement

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Explanation: There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

  • 1 <= n <= 20
  • 1 <= k <= n
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def helper(start, comb):
            if len(comb) == k:
                res.append(comb.copy())
                return
            for i in range(start, n+1):
                comb.append(i)
                helper(i+1, comb)
                comb.pop()
        helper(1, [])
        return res
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

32. Generate Parentheses (Leetcode:22)#

Also in DSA Patterns

Generate Parentheses — 12. Backtracking (may include extra approaches and complexity analysis).

Problem Statement

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

  • 1 <= n <= 8
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        stack = []
        res = []

        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append("".join(stack))
                return

            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop()
            if closedN < openN:
                stack.append(")")
                backtrack(openN, closedN + 1)
                stack.pop()

        backtrack(0, 0)
        return res
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

33. Letter Combinations of a Phone Number (Leetcode:17)#

Also in DSA Patterns

Letter Combinations of a Phone Number — 12. Backtracking (may include extra approaches and complexity analysis).

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = "" Output: []

Example 3:

Input: digits = "2" Output: ["a","b","c"]

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].
Code and Explanation 

 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 letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        digit_to_char = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        res: list[str] = []

        def backtrack(index: int, path: str) -> None:
            if index == len(digits):
                res.append(path)
                return
            for char in digit_to_char[digits[index]]:
                backtrack(index + 1, path + char)

        backtrack(0, "")
        return res
Explanation:

  1. Build combinations digit by digit with backtracking.
  2. At each index, append one mapped character and recurse to the next digit.
  3. When the path length equals the input length, push it into the result list.

34. N-Queens II (Leetcode:52)#

Problem Statement

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle**.

Example 1:

Input: n = 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1 Output: 1

Constraints:

  • 1 <= n <= 9
Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def totalNQueens(self, n: int) -> int:
            answer = 0

            cols = set()
            posdiag = set()
            negdiag = set()

            def backtrack(i):
                if i == n:
                    nonlocal answer
                    answer += 1
                    return

                for j in range(n):
                    if j in cols or (i+j) in posdiag or (i-j) in negdiag:
                        continue

                    cols.add(j)
                    posdiag.add(i+j)
                    negdiag.add(i-j)

                    backtrack(i+1)

                    cols.remove(j)
                    posdiag.remove(i+j)
                    negdiag.remove(i-j)

            backtrack(0)
            return answer
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

35. Permutations (Leetcode:46)#

Also in DSA Patterns

Permutations — 12. Backtracking (may include extra approaches and complexity analysis).

Problem Statement

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1] Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1] Output: [[1]]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        res: list[list[int]] = []

        def backtrack(path: list[int], remaining: list[int]) -> None:
            if not remaining:
                res.append(path[:])
                return
            for i, num in enumerate(remaining):
                path.append(num)
                backtrack(path, remaining[:i] + remaining[i + 1 :])
                path.pop()

        backtrack([], nums)
        return res
Explanation:

  1. Use backtracking to build one permutation at a time.
  2. Pick each unused number, recurse on the remaining values, then undo the choice.
  3. When no numbers remain, append a copy of the current path to the answer.

36. Word Search (Leetcode:79)#

Also in DSA Patterns

Word Search — 12. Backtracking (may include extra approaches and complexity analysis).

Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Code and Explanation 

 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
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        path = set()

        def dfs(r, c, i):
            if i == len(word):
                return True
            if (
                min(r, c) < 0
                or r >= ROWS
                or c >= COLS
                or word[i] != board[r][c]
                or (r, c) in path
            ):
                return False
            path.add((r, c))
            res = (
                dfs(r + 1, c, i + 1)
                or dfs(r - 1, c, i + 1)
                or dfs(r, c + 1, i + 1)
                or dfs(r, c - 1, i + 1)
            )
            path.remove((r, c))
            return res

        # To prevent TLE,reverse the word if frequency of the first letter is more than the last letter's
        count = sum(map(Counter, board), Counter())
        if count[word[0]] > count[word[-1]]:
            word = word[::-1]

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

    # O(n * m * 4^n)
Explanation:

  1. Try each cell as start for word[0].
  2. DFS with index: Match next char in 4 directions.
  3. Mark visited temporarily (e.g. '#'), restore on backtrack.
  4. Return true on full match.
  5. Time complexity: O(m × n × 4^L)
  6. Space complexity: O(L)

37. Find First and Last Position of Element in Sorted Array (Leetcode:34)#

Also in DSA Patterns

Find First and Last Position of Element in Sorted Array — 09. Binary Search (may include extra approaches and complexity analysis).

Problem Statement

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Example 3:

Input: nums = [], target = 0 Output: [-1,-1]

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = self.binSearch(nums, target, True)
        right = self.binSearch(nums, target, False)
        return [left, right]

    # leftBias=[True/False], if false, res is rightBiased
    def binSearch(self, nums, target, leftBias):
        l, r = 0, len(nums) - 1
        i = -1
        while l <= r:
            m = (l + r) // 2
            if target > nums[m]:
                l = m + 1
            elif target < nums[m]:
                r = m - 1
            else:
                i = m
                if leftBias:
                    r = m - 1
                else:
                    l = m + 1
        return i
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

38. Find Minimum in Rotated Sorted Array (Leetcode:153)#

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the rotated array nums of distinct integers, return the minimum element.

Example 1:

Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def findMin(self, nums: List[int]) -> int:
        start , end = 0, len(nums) - 1 
        curr_min = float("inf")

        while start  <  end :
            mid = start + (end - start ) // 2
            curr_min = min(curr_min,nums[mid])

            # right has the min 
            if nums[mid] > nums[end]:
                start = mid + 1

            # left has the  min 
            else:
                end = mid - 1 

        return min(curr_min,nums[start])
Explanation:

  1. Binary search on rotated array: Compare nums[mid] with nums[right].
  2. If nums[mid] > nums[right]: Minimum is in (mid, right] → left = mid + 1.
  3. Else: Minimum is in [left, mid] → right = mid.
  4. Stop when left == right: That index is the minimum. O(log n) time.
  5. Time complexity: O(log n)
  6. Space complexity: O(1)

39. Find Peak Element (Leetcode:162)#

Also in DSA Patterns

Find Peak Element — 09. Binary Search (may include extra approaches and complexity analysis).

Problem Statement

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

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

Example 1:

Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4] Output: 5 Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • nums[i] != nums[i + 1] for all valid i.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (r + l) // 2
            if mid < len(nums) - 1 and nums[mid] < nums[mid+1]:
                l = mid + 1
            elif mid > 0 and nums[mid] < nums[mid-1]:
                r = mid - 1
            else:
                break
        return mid
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

40. Median of Two Sorted Arrays (Leetcode:4)#

Problem Statement

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106
Code and Explanation 

 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
# Time: log(min(n, m))


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2

        if len(B) < len(A):
            A, B = B, A

        l, r = 0, len(A) - 1
        while True:
            i = (l + r) // 2  # A
            j = half - i - 2  # B

            Aleft = A[i] if i >= 0 else float("-infinity")
            Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
            Bleft = B[j] if j >= 0 else float("-infinity")
            Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")

            # partition is correct
            if Aleft <= Bright and Bleft <= Aright:
                # odd
                if total % 2:
                    return min(Aright, Bright)
                # even
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
            elif Aleft > Bright:
                r = i - 1
            else:
                l = i + 1
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

41. Search a 2D Matrix (Leetcode:74)#

Also in DSA Patterns

Search a 2D Matrix — 09. Binary Search (may include extra approaches and complexity analysis).

Problem Statement

You are given an m x n integer matrix matrix with the following two properties:

  • Each row is sorted in non-decreasing order.
  • The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104
Code and Explanation 

 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 searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])

        top, bot = 0, ROWS - 1
        while top <= bot:
            row = (top + bot) // 2
            if target > matrix[row][-1]:
                top = row + 1
            elif target < matrix[row][0]:
                bot = row - 1
            else:
                break

        if not (top <= bot):
            return False
        row = (top + bot) // 2
        l, r = 0, COLS - 1
        while l <= r:
            m = (l + r) // 2
            if target > matrix[row][m]:
                l = m + 1
            elif target < matrix[row][m]:
                r = m - 1
            else:
                return True
        return False
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

42. Search in Rotated Sorted Array (Leetcode:33)#

Also in DSA Patterns

Search in Rotated Sorted Array — 09. Binary Search (may include extra approaches and complexity analysis).

Problem Statement

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Example 3:

Input: nums = [1], target = 0 Output: -1

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -104 <= target <= 104
Code and Explanation 

 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 search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            mid = (l + r) // 2
            if target == nums[mid]:
                return mid

            # left sorted portion
            if nums[l] <= nums[mid]:
                if target > nums[mid] or target < nums[l]:
                    l = mid + 1
                else:
                    r = mid - 1
            # right sorted portion
            else:
                if target < nums[mid] or target > nums[r]:
                    r = mid - 1
                else:
                    l = mid + 1
        return -1
Explanation:

  1. Binary search frame: Keep left and right on the rotated sorted array.
  2. Find sorted half: Compare nums[left] with nums[mid].
  3. Locate target: Check if target lies in the sorted half's value range; shrink search there.
  4. Return index or -1: O(log n) time, O(1) space.
  5. Time complexity: O(log n)
  6. Space complexity: O(1)

43. Search Insert Position (Leetcode:35)#

Also in DSA Patterns

Search Insert Position — 09. Binary Search (may include extra approaches and complexity analysis).

Problem Statement

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5 Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2 Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7 Output: 4

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums contains distinct values sorted in ascending order.
  • -104 <= target <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # O(log n) and O(1)


        low, high = 0, len(nums)
        while low<high:
            mid = low +(high - low) // 2
            if target > nums[mid]:
                low = mid + 1
            else:
                high = mid
        return low
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

Bit Manipulation#

44. Add Binary (Leetcode:67)#

Problem Statement

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1" Output: "100" Example 2:

Input: a = "1010", b = "1011" Output: "10101"

Constraints:

  • 1 <= a.length, b.length <= 104

  • a and b consist only of '0' or '1' characters.

  • Each string does not contain leading zeros except for the zero itself.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def addBinary(self, a: str, b: str) -> str:
            res = ""
            carry = 0

            a, b = a[::-1], b[::-1]
            for i in range(max(len(a), len(b))):
                bitA = ord(a[i]) - ord('0') if i < len(a) else 0
                bitB = ord(b[i]) - ord('0') if i < len(b) else 0

                total = bitA + bitB + carry
                char = str(total % 2)
                res = char + res
                carry = total // 2

            if carry:
                res = "1" + res

            return res
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

45. Bitwise AND of Numbers Range (Leetcode:201)#

Also in DSA Patterns

Bitwise AND of Numbers Range — 06. Bit Manipulation (may include extra approaches and complexity analysis).

Problem Statement

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

0 <= left <= right <= 2^31 - 1

Code and Explanation 

 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
# check difference at each bit (cannot be more than left - right)
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        res = 0

        for i in range(32):
            bit = (left >> i) & 1
            if not bit:
                continue

            remain = left % (1 << (i + 1))
            diff = (1 << (i + 1)) - remain
            if right - left < diff:
                res = res | (1 << i)
        return res

# find the longest matching prefix of set bits between left and right
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        i = 0
        while left != right:
            left = left >> 1
            right = right >> 1
            i += 1
        return left << i
Explanation:

  1. AND (&): Sets a bit to 1 if both corresponding bits are 1.

  • Example: 1101 & 1011 = 1001 (binary) 2. OR (|): Sets a bit to 1 if at least one of the corresponding bits is 1.

  • Example: 1101 | 1011 = 1111 3. XOR (^): Sets a bit to 1 if the corresponding bits are different.

  • Example: 1101 ^ 1011 = 0110 4. NOT (~): Flips all bits (inverts 0s to 1s and 1s to 0s).

  • Example: ~1101 = 0010 (assuming 4-bit representation) 5. Left Shift (<<): Shifts bits to the left, equivalent to multiplying the number by 2.

  • Example: 1010 << 1 = 10100 (multiplies by 2)

46. Number of 1 Bits (Leetcode:191)#

Also in DSA Patterns

Number of 1 Bits — 06. Bit Manipulation (may include extra approaches and complexity analysis).

Problem Statement

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Example 1:

Input: n = 11 Output: 3 Explanation: The input binary string 1011 has a total of three set bits.

Constraints:

  • 2^31 <= n < 2^31
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count
Explanation:

  1. Check least significant bit: n & 1 tells if the last bit is set.
  2. Shift right: n >>= 1 processes the next bit.
  3. Count set bits: Increment counter each time LSB is 1.
  4. Time complexity: O(1)
  5. Space complexity: O(1)

1
2
3
4
5
6
7
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count
Explanation:

  1. Clear lowest set bit: n &= n - 1 drops the rightmost 1-bit.
  2. Count iterations: Each loop removes one set bit.
  3. Stop at zero: Number of iterations equals Hamming weight.
  4. Faster when sparse: O(# of set bits) instead of O(32).
  5. Time complexity: O(k)
  6. Space complexity: O(1)

47. Reverse Bits (Leetcode:190)#

Also in DSA Patterns

Reverse Bits — 06. Bit Manipulation (may include extra approaches and complexity analysis).

Problem Statement

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: n = 43261596 Output: 964176192 Explanation: The binary representation is reversed.

Constraints:

  • The input must be a binary string of length 32
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for _ in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result
Explanation:

  1. Extract LSB: n & 1 appends to result.
  2. Shift result left, n right: Repeat 32 times for 32-bit input.
  3. Build reversed bits: Result accumulates from LSB to MSB of original.
  4. Time complexity: O(1)
  5. Space complexity: O(1)

48. Single Number (Leetcode:136)#

Also in DSA Patterns

Single Number — 06. Bit Manipulation (may include extra approaches and complexity analysis).

Problem Statement

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
Each element appears twice except for one element which appears only once.

Code and Explanation 

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for n in nums:
            res = n ^ res
        return res
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

49. Single Number II (Leetcode:137)#

Problem Statement

Given an integer array nums where every element appears three times except for one, which appears exactly once, find the single element.

Example 1:

Input: nums = [2,2,3,2] Output: 3

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        ones = twos = 0
        for num in nums:
            ones = (ones ^ num) & ~twos
            twos = (twos ^ num) & ~ones
        return ones
Explanation:

  1. Use two bitmasks to count each bit modulo 3.
  2. ones tracks bits seen once; twos tracks bits seen twice.
  3. After processing, ones holds the bits of the unique number.

Design#

50. Find Median from Data Stream (Leetcode:295)#

Also in DSA Patterns

Find Median from Data Stream — 15. Heaps (may include extra approaches and complexity analysis).

Problem Statement

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

  • For example, for arr = [2,3,4], the median is 3.
  • For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

  • MedianFinder() initializes the MedianFinder object.
  • void addNum(int num) adds the integer num from the data stream to the data structure.
  • double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0]

Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0

Constraints:

  • -105 <= num <= 105
  • There will be at least one element in the data structure before calling findMedian.
  • At most 5 * 104 calls will be made to addNum and findMedian.

Follow up:

  • If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
  • If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
Code and Explanation 

 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 MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        # two heaps, large, small, minheap, maxheap
        # heaps should be equal size
        self.small, self.large = [], []  # maxHeap, minHeap (python default)

    def addNum(self, num: int) -> None:
        if self.large and num > self.large[0]:
            heapq.heappush(self.large, num)
        else:
            heapq.heappush(self.small, -1 * num)

        if len(self.small) > len(self.large) + 1:
            val = -1 * heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        if len(self.large) > len(self.small) + 1:
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -1 * val)

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -1 * self.small[0]
        elif len(self.large) > len(self.small):
            return self.large[0]
        return (-1 * self.small[0] + self.large[0]) / 2.0
Explanation:

  1. Max-heap small holds lower half; min-heap large holds upper half.
  2. After each insert, rebalance so sizes differ by at most 1.
  3. Median is top of small (odd count) or average of both tops (even).
  4. Time complexity: O(log n) per add
  5. Space complexity: O(n)

51. Insert Delete GetRandom O(1) (Leetcode:380)#

Also in DSA Patterns

Insert Delete GetRandom O(1) — 22. Challenge Yourself (may include extra approaches and complexity analysis).

Problem Statement

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set. Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

Input: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output: [null, true, false, true, 2, true, false, 2]

Constraints:

  • -231 <= val <= 231 - 1
  • At most 2 * 105 calls will be made to insert, remove, and getRandom.
  • There will be at least one element in the structure when getRandom is called.

Patterns: Hash Map · Array

Code and Explanation 

 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
from random import choice


class RandomizedSet:

    def __init__(self):
        self.dict = {}
        self.list = []

    def insert(self, val: int) -> bool:
        if val in self.dict:
            return False

        self.dict[val] = len(self.list)
        self.list.append(val)

        return True

    def remove(self, val: int) -> bool:
        if val not in self.dict:
            return False

        idx, last_element = self.dict[val], self.list[-1]
        self.list[idx], self.dict[last_element] = last_element, idx
        self.list.pop()
        del self.dict[val]

        return True

    def getRandom(self) -> int:
        return choice(self.list)
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

52. LRU Cache (Leetcode:146)#

Also in DSA Patterns

LRU Cache — 22. Challenge Yourself (may include extra approaches and complexity analysis).

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 104
  • 0 <= value <= 105
  • At most 2 * 105 calls will be made to get and put.

Patterns: Hash Map · Linked List

Code and Explanation 

 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 Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # map key to node

        self.left, self.right = Node(0, 0), Node(0, 0)
        self.left.next, self.right.prev = self.right, self.left

    # remove node from list
    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev

    # insert node at right
    def insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.next = nxt.prev = node
        node.next, node.prev = nxt, prev

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])

        if len(self.cache) > self.cap:
            # remove from the list and delete the LRU from hashmap
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

53. Min Stack (Leetcode:155)#

Also in DSA Patterns

Min Stack — 08. Stack (may include extra approaches and complexity analysis).

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints:

  • -231 <= val <= 231 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        val = min(val, self.minStack[-1] if self.minStack else val)
        self.minStack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStack[-1]
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

Divide & Conquer#

54. Construct Quad Tree (Leetcode:427)#

Problem Statement

Given an n x n matrix grid where n is a power of 2, construct a quad tree representing the grid.

Example 1:

Input: grid = [[0,1],[1,0]] Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]

Constraints:

  • n == grid.length == grid[i].length
  • n == 2^x where 0 <= x <= 6
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def construct(self, grid: list[list[int]]) -> 'Node | None':
        def is_uniform(x: int, y: int, size: int) -> bool:
            val = grid[x][y]
            for i in range(x, x + size):
                for j in range(y, y + size):
                    if grid[i][j] != val:
                        return False
            return True

        def build(x: int, y: int, size: int) -> 'Node':
            if is_uniform(x, y, size):
                return Node(grid[x][y] == 1, True)
            half = size // 2
            return Node(
                True,
                False,
                build(x, y, half),
                build(x, y + half, half),
                build(x + half, y, half),
                build(x + half, y + half, half),
            )
        return build(0, 0, len(grid))
Explanation:

  1. If a subgrid is uniform, create a leaf node with that value.
  2. Otherwise split the region into four equal quadrants recursively.
  3. Return an internal node with isLeaf=False and four children.

55. Convert Sorted Array to Binary Search Tree (Leetcode:108)#

Also in DSA Patterns

Convert Sorted Array to Binary Search Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation:
[0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation:
[1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

  • 1 4
  • -104 4
  • nums is sorted in a strictly increasing order.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = len(nums)//2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

56. Sort List (Leetcode:148)#

Problem Statement

Given the head of a linked list, return the list after sorting it in ascending order**.

Example 1:

Input: head = [4,2,1,3] Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]

Example 3:

Input: head = [] Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 5 * 104].

  • -105 <= Node.val <= 105

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
            if not head or not head.next:
                return head

            mid = self.get_mid(head)
            left, right = self.sortList(head), self.sortList(mid)

            return self.merge_two_sorted(left, right)


        def merge_two_sorted(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
            if not list1:
                return list2

            if not list2:
                return list1

            sentinel = ListNode()
            prev = sentinel
            while list1 and list2:
                if list1.val < list2.val:
                    prev.next = list1
                    list1 = list1.next
                else:
                    prev.next = list2
                    list2 = list2.next
                prev = prev.next

            if list1:
                prev.next = list1
            else:
                prev.next = list2

            return sentinel.next


        def get_mid(self, head: Optional[ListNode]) -> Optional[ListNode]:
            mid_prev = None
            while head and head.next:
                mid_prev = mid_prev.next if mid_prev else head
                head = head.next.next

            mid = mid_prev.next
            mid_prev.next = None

            return mid
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

Dynamic Programming#

57. Best Time to Buy and Sell Stock (Leetcode:121)#

Also in DSA Patterns

Best Time to Buy and Sell Stock — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize profit by choosing a single day to buy and a different day in the future to sell. Return the maximum profit. If no profit is possible, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.

Constraints:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
        return max_profit
Explanation:

  1. Track cheapest buy price: min_price stores the lowest price seen while scanning left to right.
  2. Profit if selling today: At each day, price - min_price is the best profit ending on that day.
  3. Keep global maximum: Update max_profit whenever today's profit beats the record.
  4. Why one pass works: The best sell day for any buy must come after that buy. O(n) time, O(1) space.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

58. Best Time to Buy and Sell Stock II (Leetcode:122)#

Also in DSA Patterns

Best Time to Buy and Sell Stock II — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given prices, you may complete as many transactions as you like (buy one and sell one share multiple times). You may not hold more than one share at a time. Return the maximum profit.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: (1,5)+(3,6) = 4+3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4

Constraints:

  • 1 <= prices.length <= 3 × 10⁴
  • 0 <= prices[i] <= 10⁴
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                max_profit += prices[i] - prices[i-1]
        return max_profit
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

59. Best Time to Buy and Sell Stock III (Leetcode:123)#

Also in DSA Patterns

Best Time to Buy and Sell Stock III — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve with at most two transactions.

Example 1:

Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0), sell on day 6 (price = 3), buy on day 7 (price = 1), sell on day 8 (price = 4).

Constraints:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^5
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        buy1 = buy2 = float('inf')
        sell1 = sell2 = 0
        for price in prices:
            buy1 = min(buy1, price)
            sell1 = max(sell1, price - buy1)
            buy2 = min(buy2, price - sell1)
            sell2 = max(sell2, price - buy2)
        return sell2
Explanation:

  1. Track the best cost for the first buy and profit after the first sell.
  2. Extend to a second transaction using profit from the first sell.
  3. sell2 holds the maximum profit achievable with at most two transactions.

60. Best Time to Buy and Sell Stock IV (Leetcode:188)#

Also in DSA Patterns

Best Time to Buy and Sell Stock IV — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve with at most k transactions.

Example 1:

Input: k = 2, prices = [2,4,1] Output: 2 Explanation: Buy on day 3 (price = 1) and sell on day 2 (price = 4), profit = 3 - 1 = 2.

Constraints:

  • 1 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        if not prices or k == 0:
            return 0
        n = len(prices)
        if k >= n // 2:
            profit = 0
            for i in range(1, n):
                if prices[i] > prices[i - 1]:
                    profit += prices[i] - prices[i - 1]
            return profit
        buy = [float('inf')] * (k + 1)
        sell = [0] * (k + 1)
        for price in prices:
            for j in range(1, k + 1):
                sell[j] = max(sell[j], buy[j] + price)
                buy[j] = min(buy[j], sell[j - 1] - price)
        return sell[k]
Explanation:

  1. If k is large enough, unlimited-transaction greedy applies.
  2. Otherwise use DP arrays buy[j] and sell[j] for j transactions.
  3. Update sell before buy for each price to avoid same-day reuse.

61. Climbing Stairs (Leetcode:70)#

Also in DSA Patterns

Climbing Stairs — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 3 Output: 3 Explanation: 1+1+1, 1+2, or 2+1.

Constraints:

  • 1 <= n <= 45
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 3:
            return n
        n1, n2 = 2, 3

        for i in range(4, n + 1):
            temp = n1 + n2
            n1 = n2
            n2 = temp
        return n2
Explanation:

  1. Base cases: 1 way to reach step 1; 2 ways to reach step 2.
  2. Fibonacci recurrence: Ways to step i = ways(i-1) + ways(i-2).
  3. Rolling variables: Only keep last two states in a and b.
  4. Time complexity: O(n)
  5. Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}

        def dp(i: int) -> int:
            if i <= 2:
                return i
            if i not in memo:
                memo[i] = dp(i - 1) + dp(i - 2)
            return memo[i]

        return dp(n)
Explanation:

  1. Recursive definition: dp(i) = ways to reach step i.
  2. Base: dp(1)=1, dp(2)=2.
  3. Memoize: Store computed dp(i) to avoid recomputation.
  4. Tradeoff: Same logic as bottom-up; uses O(n) recursion stack.
  5. Time complexity: O(n)
  6. Space complexity: O(n)

62. Coin Change (Leetcode:322)#

Also in DSA Patterns

Coin Change II – Minimum Number of Coins — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins needed to make up that amount. If impossible, return -1.

Example 1:

Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1.

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0

        for a in range(1, amount + 1):
            for c in coins:
                if a - c >= 0:
                    dp[a] = min(dp[a], 1 + dp[a - c])
        return dp[amount] if dp[amount] != amount + 1 else -1
Explanation:

  1. State: dp[a] = minimum coins to make amount a.
  2. Initialize: dp[0]=0, others to infinity.
  3. Transition: For each amount, try every coin: dp[a] = min(dp[a], 1 + dp[a-coin]).
  4. Answer: dp[amount] or -1 if unreachable. O(amount * coins) time.
  5. Time complexity: O(amount × coins)
  6. Space complexity: O(amount)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        memo = {}

        def dp(remaining: int) -> int:
            if remaining == 0:
                return 0
            if remaining < 0:
                return float('inf')
            if remaining in memo:
                return memo[remaining]
            memo[remaining] = min(1 + dp(remaining - c) for c in coins)
            return memo[remaining]

        result = dp(amount)
        return result if result != float('inf') else -1
Explanation:

  1. Recursive function: dp(remaining) = min coins for that amount.
  2. Try each coin: Return 1 + min(dp(remaining - coin)).
  3. Memo table: Cache results by remaining amount.
  4. Same complexity as bottom-up but top-down is often easier to write first.
  5. Time complexity: O(amount × coins)
  6. Space complexity: O(amount)

63. Edit Distance (Leetcode:72)#

Also in DSA Patterns

Edit Distance — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given two strings word1 and word2, return the minimum number of operations to convert word1 to word2. Allowed operations: insert, delete, or replace a character.

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[float("inf")] * (len(word2) + 1) for i in range(len(word1) + 1)]

        for j in range(len(word2) + 1):
            dp[len(word1)][j] = len(word2) - j
        for i in range(len(word1) + 1):
            dp[i][len(word2)] = len(word1) - i

        for i in range(len(word1) - 1, -1, -1):
            for j in range(len(word2) - 1, -1, -1):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i + 1][j + 1]
                else:
                    dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1])
        return dp[0][0]
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

64. House Robber (Leetcode:198)#

Also in DSA Patterns

House Robber I — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stored. Adjacent houses have security systems connected — you cannot rob two adjacent houses. Return the maximum amount you can rob without alerting the police.

Example 1:

Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and house 3 (money = 3), total = 4.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0

        for n in nums:
            temp = max(n + rob1, rob2)
            rob1 = rob2
            rob2 = temp
        return rob2
Explanation:

  1. State: dp[i] = max money from houses 0..i.
  2. Choice at house i: Rob it (dp[i-2]+nums[i]) or skip (dp[i-1]).
  3. Rolling variables: Only need previous two DP values.
  4. O(n) time, O(1) space.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

65. Interleaving String (Leetcode:97)#

Problem Statement

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

  • s = s_1_ + s_2_ + ... + s_n_

  • t = t_1_ + t_2_ + ... + t_m_

  • |n - m| <= 1

  • The interleaving is s_1_ + t_1_ + s_2_ + t_2_ + s_3_ + t_3_ + ... or t_1_ + s_1_ + t_2_ + s_2_ + t_3_ + s_3_ + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Explanation: One way to obtain s3 is: Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a". Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac". Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = "", s2 = "", s3 = "" Output: true

Constraints:

  • 0 <= s1.length, s2.length <= 100

  • 0 <= s3.length <= 200

  • s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
            if len(s1) + len(s2) != len(s3):
                return False

            dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
            dp[len(s1)][len(s2)] = True

            for i in range(len(s1), -1, -1):
                for j in range(len(s2), -1, -1):
                    if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
                        dp[i][j] = True
                    if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
                        dp[i][j] = True
            return dp[0][0]
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

66. Longest Increasing Subsequence (Leetcode:300)#

Also in DSA Patterns

Longest Increasing Subsequence — 09. Binary Search (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence**.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3] Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7] Output: 1

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        piles = []
        for num in nums:
            left, right = 0, len(piles)
            while left < right:
                mid = (left + right) // 2
                if piles[mid] < num:
                    left = mid + 1
                else:
                    right = mid
            if left == len(piles):
                piles.append(num)
            else:
                piles[left] = num
        return len(piles)
Explanation:

  1. Tail array: tails[i] = smallest tail of an increasing subsequence of length i+1.
  2. Process each number: Binary search where num fits in tails; extend or replace.
  3. Length of tails: Final LIS length equals len(tails).
  4. Optimal for LIS: O(n log n) time, O(n) space.
  5. Time complexity: O(n log n)
  6. Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        if not nums:
            return 0
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
Explanation:

  1. State: dp[i] = LIS length ending at index i.
  2. Transition: For each j < i with nums[j] < nums[i], set dp[i] = max(dp[i], dp[j]+1).
  3. Answer: max(dp).
  4. Easier to code: O(n²) time — good for interviews before optimizing.
  5. Time complexity: O(n²)
  6. Space complexity: O(n)

67. Longest Palindromic Substring (Leetcode:5)#

Also in DSA Patterns

Longest Palindromic Substring — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.

Constraints:

  • 1 <= s.length <= 1000
  • s consists of only digits and English letters
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def longestPalindrome(self, s: str) -> str:
        self.res = ""
        self.lenres = 0
        for i in range(len(s)):
            s1 = self.helper(s, i, i)
            s2 = self.helper(s, i, i + 1)
        return s2

    def helper(self, s, left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if (right - left + 1) > self.lenres:
                    self.res = s[left:right+1]
                    self.lenres = right - left + 1
                left -= 1
                right += 1
            return self.res
Explanation:

  1. Each index (and between indices) is a center.
  2. Expand while chars match.
  3. Track longest palindrome found.
  4. O(n²) time, O(1) space.
  5. Time complexity: O(n²)
  6. Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        dp = [[False] * n for _ in range(n)]
        start = end = 0
        for length in range(1, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if length == 1:
                    dp[i][j] = True
                elif length == 2:
                    dp[i][j] = s[i] == s[j]
                else:
                    dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
                if dp[i][j] and length > end - start + 1:
                    start, end = i, j
        return s[start:end + 1]
Explanation:

  1. dp[i][j] true if s[i:j+1] palindrome.
  2. Fill by increasing length using inner substrings.
  3. Track best start/end.
  4. O(n²) time and space.
  5. Time complexity: O(n²)
  6. Space complexity: O(n²)

68. Maximal Square (Leetcode:221)#

Also in DSA Patterns

Maximal Square — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given an m × n binary matrix matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        cache = {}  # map each (r, c) -> maxLength of square

        def helper(r, c):
            if r >= ROWS or c >= COLS:
                return 0

            if (r, c) not in cache:
                down = helper(r + 1, c)
                right = helper(r, c + 1)
                diag = helper(r + 1, c + 1)

                cache[(r, c)] = 0
                if matrix[r][c] == "1":
                    cache[(r, c)] = 1 + min(down, right, diag)
            return cache[(r, c)]

        helper(0, 0)
        return max(cache.values()) ** 2
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

69. Maximum Subarray (Leetcode:53)#

Also in DSA Patterns

Maximum Subarray — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[0]

        total = 0
        for n in nums:
            total += n
            res = max(res, total)
            if total < 0:
                total = 0
        return res
Explanation:

  1. Track two values: current = best sum ending here; best = best sum anywhere.
  2. Extend or restart: Add current number to current, or restart from current number.
  3. Update global best: best = max(best, current) each step.
  4. Intuition: Negative running sums should not carry forward. O(n) time, O(1) space.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

 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 maxSubArray(self, nums: list[int]) -> int:
        def divide(lo: int, hi: int) -> int:
            if lo == hi:
                return nums[lo]
            mid = (lo + hi) // 2
            left = divide(lo, mid)
            right = divide(mid + 1, hi)
            cross = self._max_crossing(nums, lo, mid, hi)
            return max(left, right, cross)

        return divide(0, len(nums) - 1)

    def _max_crossing(self, nums: list[int], lo: int, mid: int, hi: int) -> int:
        left_sum = float('-inf')
        total = 0
        for i in range(mid, lo - 1, -1):
            total += nums[i]
            left_sum = max(left_sum, total)
        right_sum = float('-inf')
        total = 0
        for i in range(mid + 1, hi + 1):
            total += nums[i]
            right_sum = max(right_sum, total)
        return left_sum + right_sum
Explanation:

  1. Split in half: Recursively solve left, right, and crossing subarray through mid.
  2. Crossing sum: Expand from mid outward for best sum using both halves.
  3. Combine: Answer is max(left, right, crossing).
  4. Tradeoff: Correct but O(n log n); Kadane's is preferred.
  5. Time complexity: O(n log n)
  6. Space complexity: O(log n)

70. Maximum Sum Circular Subarray (Leetcode:918)#

Problem Statement

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Example 1:

Input: nums = [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3.

Example 2:

Input: nums = [5,-3,5] Output: 10 Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3:

Input: nums = [-3,-2,-3] Output: -2 Explanation: Subarray [-2] has maximum sum -2.

Constraints:

  • n == nums.length

  • 1 <= n <= 3 * 104

  • -3 * 104 <= nums[i] <= 3 * 104

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def maxSubarraySumCircular(self, nums: List[int]) -> int:
            globMax, globMin = nums[0], nums[0]
            curMax, curMin = 0, 0
            total = 0

            for i, n in enumerate(nums):
                curMax = max(curMax + n, n)
                curMin = min(curMin + n, n)
                total += n
                globMax = max(curMax, globMax)
                globMin = min(curMin, globMin)

            return max(globMax, total - globMin) if globMax > 0 else globMax
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

71. Minimum Path Sum (Leetcode:64)#

Also in DSA Patterns

Minimum Path Sum in Grid — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given an m × n grid filled with non-negative numbers, find a path from top-left to bottom-right which minimizes the sum of all numbers along its path. You may only move down or right.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Path 1→3→1→1→1 sums to 7.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        prev = [float("inf")] * n
        prev[-1] = 0

        for row in range(m - 1, -1, -1):
            dp = [float("inf")] * n
            for col in range(n - 1, -1, -1):
                if col < n - 1:
                    dp[col] = min(dp[col], dp[col + 1])
                dp[col] = min(dp[col], prev[col]) + grid[row][col]
            prev = dp

        return prev[0]
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

72. Triangle (Leetcode:120)#

Also in DSA Patterns

Triangle — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given a triangle array triangle, return the minimum path sum from top to bottom. Each step you may move to an adjacent number on the row below. Adjacent for index j on row i means indices j or j+1 on row i+1.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: 2 + 3 + 5 + 1 = 11.

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • −10⁴ <= triangle[i][j] <= 10⁴
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = triangle[-1]

        for row in range(len(triangle) - 2, -1, -1):
            for col in range(0, row + 1):
                dp[col] = triangle[row][col] + min(dp[col], dp[col + 1])

        return dp[0]
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

73. Unique Paths II (Leetcode:63)#

Problem Statement

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]] Output: 1

Constraints:

  • m == obstacleGrid.length

  • n == obstacleGrid[i].length

  • 1 <= m, n <= 100

  • obstacleGrid[i][j] is 0 or 1.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
            M, N = len(grid), len(grid[0])
            dp = [0] * N
            dp[N-1] = 1

            # Time: O(N*M), Space: O(N)
            for r in reversed(range(M)):
                for c in reversed(range(N)):
                    if grid[r][c]:
                        dp[c] = 0
                    elif c + 1 < N:
                        dp[c] = dp[c] + dp[c + 1]
            return dp[0]


            # Time: O(N*M), Space: O(N*M)
            M, N = len(grid), len(grid[0])
            dp = {(M - 1, N - 1): 1}

            def dfs(r, c):
                if r == M or c == N or grid[r][c]:
                    return 0
                if (r, c) in dp:
                    return dp[(r, c)]
                dp[(r, c)] = dfs(r + 1, c) + dfs(r, c + 1)
                return dp[(r, c)]
            return dfs(0, 0)
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

74. Word Break (Leetcode:139)#

Problem Statement

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false

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.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        dp = [False] * (len(s) + 1)
        dp[len(s)] = True

        for i in range(len(s) - 1, -1, -1):
            for w in wordDict:
                if (i + len(w)) <= len(s) and s[i : i + len(w)] == w:
                    dp[i] = dp[i + len(w)]
                if dp[i]:
                    break

        return dp[0]
Explanation:

  1. State: dp[i] = True if s[:i] can be segmented.
  2. Base: dp[0] = True (empty prefix).
  3. Transition: For each start j, if dp[j] and s[j:i] in dictionary, set dp[i]=True.
  4. Answer: dp[len(s)]. O(n² * dict lookup).
  5. Time complexity: O(n² × m)
  6. Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
from collections import deque


class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)
        queue = deque([0])
        visited = set()
        while queue:
            start = queue.popleft()
            if start == len(s):
                return True
            if start in visited:
                continue
            visited.add(start)
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in word_set:
                    queue.append(end)
        return False
Explanation:

  1. Graph view: Edge from index i to j if s[i:j] is a valid word.
  2. BFS from 0: Reach len(s) means string is breakable.
  3. Visited set: Skip reprocessing same start index.
  4. Same logical problem, different traversal style.
  5. Time complexity: O(n² × m)
  6. Space complexity: O(n)

Graphs#

75. Clone Graph (Leetcode:133)#

Problem Statement

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

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]]

Constraints:

  • The number of nodes is in the range [0, 100]
  • Node.val is unique for each node
  • Node.val is generated as a small integer
  • No repeated edges and no self-loops
  • The graph is connected and all nodes can be visited from the given node
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        clones = {}

        def dfs(original: 'Node') -> 'Node':
            if original in clones:
                return clones[original]
            copy = Node(original.val)
            clones[original] = copy
            for neighbor in original.neighbors:
                copy.neighbors.append(dfs(neighbor))
            return copy

        return dfs(node)
Explanation:

  1. Clone map: clones[original] stores the copied node for each original.
  2. DFS from start: If already cloned, return existing copy.
  3. Create copy and wire neighbors: Clone node, then DFS each neighbor and append clone to neighbor list.
  4. O(V+E) time and space.
  5. Time complexity: O(V + E)
  6. Space complexity: O(V)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
from collections import deque


class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        clones = {node: Node(node.val)}
        queue = deque([node])
        while queue:
            curr = queue.popleft()
            for neighbor in curr.neighbors:
                if neighbor not in clones:
                    clones[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)
                clones[curr].neighbors.append(clones[neighbor])
        return clones[node]
Explanation:

  1. Queue traversal: Process nodes level by level while cloning.
  2. Clone on first visit: Add to map and queue when neighbor first seen.
  3. Wire neighbors: Append cloned neighbor pointers from map.
  4. Same complexity as DFS, iterative style.
  5. Time complexity: O(V + E)
  6. Space complexity: O(V)

76. Course Schedule (Leetcode:207)#

Problem Statement

There are a total of numCourses courses labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates you must take course bi before ai. Return true if you can finish all courses, or false if there is a cycle.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: Take course 0 then course 1.

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All pairs are unique
Code and Explanation 

 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
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # dfs
        preMap = {i: [] for i in range(numCourses)}

        # map each course to : prereq list
        for crs, pre in prerequisites:
            preMap[crs].append(pre)

        visiting = set()

        def dfs(crs):
            if crs in visiting:
                return False
            if preMap[crs] == []:
                return True

            visiting.add(crs)
            for pre in preMap[crs]:
                if not dfs(pre):
                    return False
            visiting.remove(crs)
            preMap[crs] = []
            return True

        for c in range(numCourses):
            if not dfs(c):
                return False
        return True
Explanation:

  1. Build graph and indegree: Edge prereq -> course.
  2. Start with indegree 0 courses in a queue.
  3. Pop course, reduce indegree of neighbors: If indegree hits 0, enqueue.
  4. No cycle iff all courses processed. O(V+E).
  5. Time complexity: O(V + E)
  6. Space complexity: O(V + E)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[course].append(prereq)
        state = [0] * numCourses  # 0=unvisited, 1=visiting, 2=done

        def has_cycle(course: int) -> bool:
            if state[course] == 1:
                return True
            if state[course] == 2:
                return False
            state[course] = 1
            for prereq in graph[course]:
                if has_cycle(prereq):
                    return True
            state[course] = 2
            return False

        return not any(has_cycle(c) for c in range(numCourses) if state[c] == 0)
Explanation:

  1. Adjacency list: Store prerequisites per course.
  2. Three states: unvisited, visiting, done.
  3. Back edge = cycle: Revisit a visiting node.
  4. All nodes finish without cycle → true.
  5. Time complexity: O(V + E)
  6. Space complexity: O(V + E)

77. Course Schedule II (Leetcode:210)#

Problem Statement

An n x n matrix isConnected represents cities. isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] → Output: 2

Constraints: 1 <= n <= 200

Code and Explanation 

 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 findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        prereq = {c: [] for c in range(numCourses)}
        for crs, pre in prerequisites:
            prereq[crs].append(pre)

        output = []
        visit, cycle = set(), set()

        def dfs(crs):
            if crs in cycle:
                return False
            if crs in visit:
                return True

            cycle.add(crs)
            for pre in prereq[crs]:
                if dfs(pre) == False:
                    return False
            cycle.remove(crs)
            visit.add(crs)
            output.append(crs)
            return True

        for c in range(numCourses):
            if dfs(c) == False:
                return []
        return output
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

78. Evaluate Division (Leetcode:399)#

Problem Statement

You are given equations, values, and queries representing division relations. Return the answers to all queries. If an answer cannot be determined, return -1.0.

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] Output: [6.0,0.5,-1.0,1.0,-1.0]

Constraints:

  • 1 <= equations.length <= 20
Code and Explanation 

 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 calcEquation(self, equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:
        graph: dict[str, dict[str, float]] = {}
        for (a, b), val in zip(equations, values):
            graph.setdefault(a, {})[b] = val
            graph.setdefault(b, {})[a] = 1.0 / val

        def dfs(src: str, dst: str, visited: set[str]) -> float:
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0
            visited.add(src)
            for nei, weight in graph[src].items():
                if nei in visited:
                    continue
                result = dfs(nei, dst, visited)
                if result != -1.0:
                    return weight * result
            return -1.0

        answers: list[float] = []
        for a, b in queries:
            answers.append(dfs(a, b, set()))
        return answers
Explanation:

  1. Build a weighted directed graph for each division relation.
  2. For each query, DFS from numerator to denominator multiplying edge weights.
  3. Return -1.0 when either variable is unknown or no path exists.

79. Minimum Genetic Mutation (Leetcode:433)#

Problem Statement

A gene string can be transformed by changing one letter at a time. Given startGene, endGene, and bank, return the minimum number of mutations needed to change startGene into endGene. Return -1 if it is impossible.

Example 1:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"] Output: 1

Constraints:

  • 1 <= bank.length <= 10
  • All gene strings have length 8.
Code and Explanation 

 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 minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
        bank_set = set(bank)
        if endGene not in bank_set:
            return -1
        genes = 'ACGT'
        queue = [(startGene, 0)]
        visited = {startGene}
        while queue:
            gene, steps = queue.pop(0)
            if gene == endGene:
                return steps
            chars = list(gene)
            for i in range(8):
                original = chars[i]
                for g in genes:
                    if g == original:
                        continue
                    chars[i] = g
                    nxt = ''.join(chars)
                    if nxt in bank_set and nxt not in visited:
                        visited.add(nxt)
                        queue.append((nxt, steps + 1))
                chars[i] = original
        return -1
Explanation:

  1. Treat valid bank genes as nodes in an unweighted graph.
  2. BFS from startGene, generating one-letter neighbors at each step.
  3. Return the first time endGene is reached, or -1 if unreachable.

80. Number of Islands (Leetcode:200)#

Problem Statement

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1

Example 2:

Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.
Code and Explanation 

 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        islands = 0
        visit = set()
        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if (
                r not in range(rows)
                or c not in range(cols)
                or grid[r][c] == "0"
                or (r, c) in visit
            ):
                return

            visit.add((r, c))
            directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            for dr, dc in directions:
                dfs(r + dr, c + dc)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visit:
                    islands += 1
                    dfs(r, c)
        return islands

# DFS O(1) Space and much less code
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        def dfs(r, c):
            if not 0 <= r < len(grid) or not 0 <= c < len(grid[0]) or grid[r][c] == '0':
                return 0
            grid[r][c] = '0'
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
            return 1
        count = 0
        for r in range(rows):
            for c in range(cols):
                count += dfs(r, c)
        return count

# BFS Version From Video
class SolutionBFS:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        visited = set()
        islands = 0

         def bfs(r, c):
             q = deque()
             visited.add((r, c))
             q.append((r, c))

             while q:
                 row, col = q.popleft()
                 directions = [[1, 0],[-1, 0],[0, 1],[0, -1]]

                 for dr, dc in directions:
                     r, c = row + dr, col + dc
                     if (r) in range(rows) and (c) in range(cols) and grid[r][c] == '1' and (r, c) not in visited:

                         q.append((r, c ))
                         visited.add((r, c ))

         for r in range(rows):
             for c in range(cols):

                 if grid[r][c] == "1" and (r, c) not in visited:
                     bfs(r, c)
                     islands += 1 

         return islands
Explanation:

  1. Scan grid: Each unvisited '1' starts a new island.
  2. DFS flood fill: Mark visited by flipping to '0'.
  3. Explore 4 directions recursively.
  4. Count DFS launches. O(mn) time.
  5. Time complexity: O(m × n)
  6. Space complexity: O(m × n)

 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
from collections import deque


class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0

        def bfs(r: int, c: int) -> None:
            queue = deque([(r, c)])
            grid[r][c] = '0'
            while queue:
                row, col = queue.popleft()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    bfs(r, c)
        return count
Explanation:

  1. Same outer scan as DFS for new land cells.
  2. Queue flood fill: Process cells layer by layer.
  3. Mark visited on enqueue to avoid duplicates.
  4. Equivalent result, iterative traversal.
  5. Time complexity: O(m × n)
  6. Space complexity: O(m × n)

81. Snakes and Ladders (Leetcode:909)#

Problem Statement

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

  • Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].

  • This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.

  • If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.

  • The game ends when you reach the square n2.

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 are not the starting points of any snake or ladder.

Note that you only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

  • For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of dice rolls required to reach the square n2. If it is not possible to reach the square, return -1.

Example 1:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Output: 4 Explanation: In the beginning, you start at square 1 (at row 5, column 0). You decide to move to square 2 and must take the ladder to square 15. You then decide to move to square 17 and must take the snake to square 13. You then decide to move to square 14 and must take the ladder to square 35. You then decide to move to square 36, ending the game. This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]] Output: 1

Constraints:

  • n == board.length == board[i].length

  • 2 <= n <= 20

  • board[i][j] is either -1 or in the range [1, n2].

  • The squares labeled 1 and n2 are not the starting points of any snake or ladder.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def snakesAndLadders(self, board: List[List[int]]) -> int:
            length = len(board)
            board.reverse()

            def intToPos(square):
                r = (square - 1) // length
                c = (square - 1) % length
                if r % 2:
                    c = length - 1 - c
                return [r, c]

            q = deque()
            q.append([1, 0])  # [square, moves]
            visit = set()
            while q:
                square, moves = q.popleft()
                for i in range(1, 7):
                    nextSquare = square + i
                    r, c = intToPos(nextSquare)
                    if board[r][c] != -1:
                        nextSquare = board[r][c]
                    if nextSquare == length * length:
                        return moves + 1
                    if nextSquare not in visit:
                        visit.add(nextSquare)
                        q.append([nextSquare, moves + 1])
            return -1
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

82. Surrounded Regions (Leetcode:130)#

Problem Statement

An n x n matrix isConnected represents cities. isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] → Output: 2

Constraints: 1 <= n <= 200

Code and Explanation 

 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
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        rows, cols = len(board), len(board[0])
        flag = set()

        def dfs(r, c):
            if not(r in range(rows) and c in range(cols)) or board[r][c] != 'O' or (r, c) in flag:
                return
            flag.add((r, c))
            return (dfs(r + 1, c), dfs(r - 1, c), dfs(r, c + 1), dfs(r, c - 1))

        # traverse through the board
        for r in range(rows):
            for c in range(cols):
                if( (r == 0 or c == 0 or r == rows - 1 or c == cols - 1) and board[r][c] == 'O'):
                    dfs(r, c)

        # set all of the 'X's to 'O's
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O' and (r, c) not in flag:
                    board[r][c] = 'X'

    '''
    def solve(self, board: List[List[str]]) -> None:
        ROWS, COLS = len(board), len(board[0])

        def capture(r, c):
            if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":
                return
            board[r][c] = "T"
            capture(r + 1, c)
            capture(r - 1, c)
            capture(r, c + 1)
            capture(r, c - 1)

        # 1. (DFS) Capture unsurrounded regions (O -> T)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
                    capture(r, c)

        # 2. Capture surrounded regions (O -> X)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"

        # 3. Uncapture unsurrounded regions (T -> O)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "T":
                    board[r][c] = "O"
    '''
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

83. Word Ladder (Leetcode:127)#

Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints:

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.
Code and Explanation 

 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 ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        nei = collections.defaultdict(list)
        wordList.append(beginWord)
        for word in wordList:
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j + 1 :]
                nei[pattern].append(word)

        visit = set([beginWord])
        q = deque([beginWord])
        res = 1
        while q:
            for i in range(len(q)):
                word = q.popleft()
                if word == endWord:
                    return res
                for j in range(len(word)):
                    pattern = word[:j] + "*" + word[j + 1 :]
                    for neiWord in nei[pattern]:
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            res += 1
        return 0
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

Heap / Priority Queue#

84. Find K Pairs with Smallest Sums (Leetcode:373)#

Also in DSA Patterns

Find K Pairs with Smallest Sums — 14. K-way Merge (may include extra approaches and complexity analysis).

Problem Statement

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Output: [[1,2],[1,4],[1,6]] Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Output: [[1,1],[1,1]] Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Constraints:

  • 1 <= nums1.length, nums2.length <= 105
  • -109 <= nums1[i], nums2[i] <= 109
  • nums1 and nums2 both are sorted in non-decreasing order.
  • 1 <= k <= 104
  • k <= nums1.length * nums2.length
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def kSmallestPairs(self, nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:
        import heapq
        if not nums1 or not nums2:
            return []
        heap: list[tuple[int, int, int]] = []
        for i in range(min(len(nums1), k)):
            heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))
        result: list[list[int]] = []
        while heap and len(result) < k:
            _, i, j = heapq.heappop(heap)
            result.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
        return result
Explanation:

  1. Seed a min-heap with pairs (nums1[i], nums2[0]) for the first k indices.
  2. Pop the smallest sum and push the next pair from the same nums1 row.
  3. Stop after collecting k pairs.

85. IPO (Leetcode:502)#

Also in DSA Patterns

IPO — 10. Greedy Algorithm (may include extra approaches and complexity analysis).

Problem Statement

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] Output: 4 Explanation: Since your initial capital is 0, you can only start the project indexed 0. After finishing it you will obtain profit 1 and your capital becomes 1. With capital 1, you can either start the project indexed 1 or the project indexed 2. Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital. Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Example 2:

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2] Output: 6

Constraints:

  • 1 <= k <= 105
  • 0 <= w <= 109
  • n == profits.length
  • n == capital.length
  • 1 <= n <= 105
  • 0 <= profits[i] <= 104
  • 0 <= capital[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        # O(nlogn)
        maxProfit = [] # only projects we can afford
        minCapital = [(c, p) for c, p in zip(capital, profits)]
        heapq.heapify(minCapital)

        for i in range(k):

            while minCapital and minCapital[0][0] <= w:
                c, p = heapq.heappop(minCapital)
                heapq.heappush(maxProfit, -1 * p)
            if not maxProfit:
                break
            w += -1 * heapq.heappop(maxProfit)
        return w
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

86. Kth Largest Element in an Array (Leetcode:215)#

Also in DSA Patterns

Kth Largest Element in an Array — 15. Heaps (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2 Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4

Constraints:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104
Code and Explanation 

 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
# Solution: Sorting
# Time Complexity:
#   - Best Case: O(n*log(k))
#   - Average Case: O(n*log(k))
#   - Worst Case:O(n*log(k))
# Extra Space Complexity: O(k)
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapify(nums)
        while len(nums) > k:
            heappop(nums)
        return nums[0]

# Solution: Sorting
# Time Complexity:
#   - Best Case: O(n)
#   - Average Case: O(n*log(n))
#   - Worst Case:O(n*log(n))
# Extra Space Complexity: O(n)
class Solution1:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[len(nums) - k]


# Solution: QuickSelect
# Time Complexity: O(n)
# Extra Space Complexity: O(n)
class Solution2:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        pivot = random.choice(nums)
        left = [num for num in nums if num > pivot]
        mid = [num for num in nums if num == pivot]
        right = [num for num in nums if num < pivot]

        length_left = len(left)
        length_right = len(right)
        length_mid = len(mid)
        if k <= length_left:
            return self.findKthLargest(left, k)
        elif k > length_left + length_mid:
            return self.findKthLargest(right, k - length_mid - length_left)
        else:
            return mid[0]
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

87. Merge k Sorted Lists (Leetcode:23)#

Also in DSA Patterns

Merge k Sorted Lists — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted linked list: 1->1->2->3->4->4->5->6

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
Code and Explanation 

 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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists or len(lists) == 0:
            return None

        while len(lists) > 1:
            mergedLists = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                mergedLists.append(self.mergeList(l1, l2))
            lists = mergedLists
        return lists[0]

    def mergeList(self, l1, l2):
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        if l1:
            tail.next = l1
        if l2:
            tail.next = l2
        return dummy.next
Explanation:

  1. Push head of each list onto min-heap.
  2. Pop smallest, append to result, push that node's next.
  3. O(N log k) for total N nodes across k lists.
  4. Time complexity: O(N log k)
  5. Space complexity: O(k)

 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 mergeKLists(self, lists: list[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None

        def merge_two(a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
            dummy = ListNode(0)
            tail = dummy
            while a and b:
                if a.val <= b.val:
                    tail.next = a
                    a = a.next
                else:
                    tail.next = b
                    b = b.next
                tail = tail.next
            tail.next = a or b
            return dummy.next

        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                merged.append(merge_two(lists[i], lists[i + 1] if i + 1 < len(lists) else None))
            lists = merged
        return lists[0]
Explanation:

  1. Repeatedly merge pairs of lists until one remains.
  2. merge_two standard sorted merge.
  3. O(N log k) without heap.
  4. Time complexity: O(N log k)
  5. Space complexity: O(1)

Intervals#

88. Insert Interval (Leetcode:57)#

Also in DSA Patterns

Problem 2. Insert Interval — 04. Overlapping Intervals (may include extra approaches and complexity analysis).

Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti.
You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 10^5

Code and Explanation 

 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 insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
                    answer = []
                    i, n = 0, len(intervals)

                    while i < n and newInterval[0] > intervals[i][0]:
                        answer.append(intervals[i])
                        i += 1

                    if not answer or answer[-1][1]<newInterval[0]:
                        answer.append(newInterval)
                    else:
                        answer[-1][1] = max(answer[-1][1], newInterval[1])

                    while i<n:
                        if answer[-1][1] < intervals[i][0]:
                            answer.append(intervals[i])
                        else:
                            answer[-1][1] = max(answer[-1][1], intervals[i][1])

                        i+=1
                    return answer
Explanation:

  1. Three cases: New interval before, after, or overlapping existing ones.
  2. Build result list: Insert merged interval when overlap region ends.
  3. Single pass through intervals.
  4. O(n) time if intervals already sorted.
  5. Time complexity: O(n)
  6. Space complexity: O(n)

89. Merge Intervals (Leetcode:56)#

Also in DSA Patterns

Problem 1. Merge Intervals — 04. Overlapping Intervals (may include extra approaches and complexity analysis).

Problem Statement

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

1 <= intervals.length <= 10^4 intervals[i].length == 2 0 <= starti <= endi <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda pair: pair[0])
        output = [intervals[0]]

        for start, end in intervals:
            lastEnd = output[-1][1]

            if start <= lastEnd:
                # merge
                output[-1][1] = max(lastEnd, end)
            else:
                output.append([start, end])
        return output
Explanation:

  1. Sort by start time.
  2. Merge if overlap: If current start <= last end, extend last interval.
  3. Else push new interval.
  4. O(n log n) from sort.
  5. Time complexity: O(n log n)
  6. Space complexity: O(n)

90. Minimum Number of Arrows to Burst Balloons (Leetcode:452)#

Also in DSA Patterns

Minimum Number of Arrows to Burst Balloons — 00. Prefix Sum (may include extra approaches and complexity analysis).

Problem Statement

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]] Output: 2 Explanation: The balloons can be burst by 2 arrows: - Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6]. - Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]] Output: 4 Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]] Output: 2 Explanation: The balloons can be burst by 2 arrows: - Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3]. - Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

  • 1 <= points.length <= 105
  • points[i].length == 2
  • -231 <= xstart < xend <= 231 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()

        res = len(points)
        prev = points[0]
        for i in range(1, len(points)):
            curr = points[i]
            if curr[0] <= prev[1]:
                res -= 1
                prev = [curr[0], min(curr[1], prev[1])]
            else:
                prev = curr

        return res
Explanation:

  1. Non-overlapping (Separate):

  • Condition: \(a_2 < b_1\) or \(b_2 < a_1\) 2. Description: The intervals do not overlap and are entirely separate. No merging is needed. 3. Partial Overlap (b ends after a):

  • Condition: \(a_1 \leq b_1 \leq a_2 \leq b_2\) 4. Description: The interval \(b\) partially overlaps \(a\), extending beyond it. In this case, \(b\)'s end is after \(a\)'s end. 5. Complete Overlap (a contains b):

  • Condition: \(a_1 \leq b_1 \leq b_2 \leq a_2\)

91. Summary Ranges (Leetcode:228)#

Problem Statement

You are given a sorted unique integer array nums. Return the smallest sorted list of ranges that cover all numbers in the array exactly.

Example 1:

Input: nums = [0,1,2,4,5,7] Output: ["0->2","4->5","7"]

Constraints:

  • 0 <= nums.length <= 20
  • -2^31 <= nums[i] <= 2^31 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def summaryRanges(self, nums: list[int]) -> list[str]:
        ranges: list[str] = []
        i = 0
        while i < len(nums):
            start = nums[i]
            while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1:
                i += 1
            if start == nums[i]:
                ranges.append(str(start))
            else:
                ranges.append(f"{start}->{nums[i]}")
            i += 1
        return ranges
Explanation:

  1. Scan the sorted array and mark the start of each range.
  2. Extend the range while the next number is consecutive.
  3. Format single values or start->end pairs and move on.

Linked List#

92. Add Two Numbers (Leetcode:2)#

Also in DSA Patterns

Add Two Numbers — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0] Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.
Code and Explanation 

 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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        cur = dummy

        carry = 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0

            # new digit
            val = v1 + v2 + carry
            carry = val // 10
            val = val % 10
            cur.next = ListNode(val)

            # update ptrs
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

93. Copy List with Random Pointer (Leetcode:138)#

Also in DSA Patterns

Copy List with Random Pointer — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]

Constraints:

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random is null or is pointing to some node in the linked list.
Code and Explanation 

 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
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        oldToCopy = {None: None}

        cur = head
        while cur:
            copy = Node(cur.val)
            oldToCopy[cur] = copy
            cur = cur.next
        cur = head
        while cur:
            copy = oldToCopy[cur]
            copy.next = oldToCopy[cur.next]
            copy.random = oldToCopy[cur.random]
            cur = cur.next
        return oldToCopy[head]
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

94. Linked List Cycle (Leetcode:141)#

Also in DSA Patterns

Linked List Cycle — 02. Fast and Slow Pointers (may include extra approaches and complexity analysis).

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
Explanation:

  1. Slow moves 1 step, fast moves 2.
  2. If they meet, cycle exists.
  3. If fast reaches null, no cycle.
  4. O(n) time, O(1) space — optimal.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

1
2
3
4
5
6
7
8
9
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False
Explanation:

  1. Track visited nodes in a set.
  2. Cycle if node seen again.
  3. Simple but O(n) extra space.
  4. Time complexity: O(n)
  5. Space complexity: O(n)

95. Merge Two Sorted Lists (Leetcode:21)#

Also in DSA Patterns

Merge Two Sorted Lists (Recursive) — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:


Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.
Code and Explanation 

 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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

# Iterative
class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = node = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                node.next = list1
                list1 = list1.next
            else:
                node.next = list2
                list2 = list2.next
            node = node.next

        node.next = list1 or list2

        return dummy.next

# Recursive
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        lil, big = (list1, list2) if list1.val < list2.val else (list2, list1)
        lil.next = self.mergeTwoLists(lil.next, big)
        return lil
Explanation:

  1. Dummy head simplifies tail insertion.
  2. Attach smaller head node, advance that list.
  3. Append remainder when one list ends.
  4. Time complexity: O(n + m)
  5. Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2
Explanation:

  1. Compare heads, attach smaller, recurse on rest.
  2. Base cases for empty lists.
  3. Same O(n) time, uses call stack.
  4. Time complexity: O(n + m)
  5. Space complexity: O(n + m)

96. Partition List (Leetcode:86)#

Also in DSA Patterns

Partition List — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2 Output: [1,2]

Constraints:

  • The number of nodes in the list is in the range [0, 200].
  • -100 <= Node.val <= 100
  • -200 <= x <= 200
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        less_head, bigger_head = ListNode(-1), ListNode(-1)
        less_prev, bigger_prev = less_head, bigger_head
        while head:
            if head.val < x:
                less_prev.next = head
                less_prev = less_prev.next
            else:
                bigger_prev.next = head
                bigger_prev = bigger_prev.next

            head = head.next

        less_prev.next = bigger_prev.next = None
        less_prev.next = bigger_head.next

        return less_head.next
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

97. Remove Duplicates from Sorted List II (Leetcode:82)#

Problem Statement

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3] Output: [2,3]

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        while head:
            if head.next and head.val == head.next.val:
                while head.next and head.val == head.next.val:
                    head = head.next
            else:
                prev.next = head
                prev = prev.next
            head = head.next
        prev.next = None
        return dummy.next
Explanation:

  1. Dummy node handles duplicate runs at the head cleanly.
  2. Skip duplicate runs by advancing head while values match.
  3. Link distinct nodes through prev when no duplicate run starts.
  4. Time complexity: O(n)
  5. Space complexity: O(1)

98. Remove Nth Node From End of List (Leetcode:19)#

Also in DSA Patterns

Remove Nth Node From End of List — 02. Fast and Slow Pointers (may include extra approaches and complexity analysis).

Problem Statement

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

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

The number of nodes in the list is sz.1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz`

**Follow up: ** Could you do this in one pass?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        left = dummy
        right = head

        while n > 0:
            right = right.next
            n -= 1

        while right:
            left = left.next
            right = right.next

        # delete
        left.next = left.next.next
        return dummy.next
Explanation:

  1. Dummy node handles deleting head edge case.
  2. Fast pointer is n+1 ahead of slow when fast hits end.
  3. Skip node after slow.
  4. One pass.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

99. Reverse Linked List II (Leetcode:92)#

Also in DSA Patterns

Reverse Linked List II — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1 Output: [5]

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Follow up: Could you do it in one pass?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], left: int, right: int
    ) -> Optional[ListNode]:
        dummy = ListNode(0, head)

        # 1) reach node at position "left"
        leftPrev, cur = dummy, head
        for i in range(left - 1):
            leftPrev, cur = cur, cur.next

        # Now cur="left", leftPrev="node before left"
        # 2) reverse from left to right
        prev = None
        for i in range(right - left + 1):
            tmpNext = cur.next
            cur.next = prev
            prev, cur = cur, tmpNext

        # 3) Update pointers
        leftPrev.next.next = cur  # cur is node after "right"
        leftPrev.next = prev  # prev is "right"
        return dummy.next
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

100. Reverse Nodes in k-Group (Leetcode:25)#

Also in DSA Patterns

Reverse Nodes in k-Group — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]

Constraints:

  • The number of nodes in the list is n.
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Code and Explanation 

 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
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0, head)
        groupPrev = dummy

        while True:
            kth = self.getKth(groupPrev, k)
            if not kth:
                break
            groupNext = kth.next

            # reverse group
            prev, curr = kth.next, groupPrev.next
            while curr != groupNext:
                tmp = curr.next
                curr.next = prev
                prev = curr
                curr = tmp

            tmp = groupPrev.next
            groupPrev.next = kth
            groupPrev = tmp
        return dummy.next

    def getKth(self, curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1
        return curr
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

101. Rotate List (Leetcode:61)#

Also in DSA Patterns

Rotate List — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

Given the head of a linked list, rotate the list to the right by k places.

Example 1:


Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:


Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

  • The number of nodes in the list is in the range [0, 500].
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109
Code and Explanation 

 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 rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next or k == 0:
            return head

        old_head = head

        curr, size = head, 0
        while curr:
            curr, size = curr.next, size + 1

        if k % size == 0:
            return head

        k %= size
        slow = fast = head
        while fast and fast.next:
            if k <= 0:
                slow = slow.next
            fast = fast.next
            k -= 1

        new_tail, new_head, old_tail = slow, slow.next, fast
        new_tail.next, old_tail.next = None, old_head

        return new_head
Explanation:

  1. The slow pointer moves one step at a time.
  2. The fast pointer moves two steps at a time.
  3. Cycle Detection: If a cycle exists, the fast pointer will meet the slow pointer inside the cycle.
  4. Middle Element: The slow pointer will be at the middle when the fast pointer reaches the end.
  5. Pattern Matching: Helps detect patterns like palindromes by dividing the structure into two parts.

Math & Geometry#

102. Factorial Trailing Zeroes (Leetcode:172)#

Problem Statement

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

Input: n = 3 Output: 0

Example 2:

Input: n = 5 Output: 1

Constraints:

  • 0 <= n <= 10^4
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n:
            n //= 5
            count += n
        return count
Explanation:

  1. Trailing zeros come from factors of 10, i.e. pairs of 2 and 5.
  2. There are always more factors of 2 than 5 in n!.
  3. Count how many multiples of 5, 25, 125, ... appear up to n.

103. Max Points on a Line (Leetcode:149)#

Also in DSA Patterns

Max Points on a Line — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

Given an array of points where points[i] = [xᵢ, yᵢ] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

1 <= points.length <= 300
points[i].length == 2
-10^4 <= xᵢ, yᵢ <= 10^4
All the points are unique.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        # 1. For each pt determine if it lies on the longest line
        # 2. Count all pts with same slope
        # 3. Update result with max

        res = 1
        for i in range(len(points)):
            p1 = points[i]
            count = collections.defaultdict(int)
            for j in range(i + 1, len(points)):
                p2 = points[j]
                if p2[0] == p1[0]:
                    slope = float("inf")
                else:
                    slope = (p2[1] - p1[1]) / (p2[0] - p1[0])
                count[slope] += 1
                res = max(res, count[slope] + 1)
        return res
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

104. Palindrome Number (Leetcode:9)#

Problem Statement

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121 Output: true Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

  • -231 <= x <= 231 - 1

Follow up: Could you solve it without converting the integer to a string?

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def isPalindrome(self, x: int) -> bool:
            if x < 0: return False

            div = 1
            while x >= 10 * div:
                div *= 10

            while x:
                right = x % 10
                left = x // div

                if left != right: return False

                x = (x % div) // 10
                div = div / 100
            return True
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

105. Plus One (Leetcode:66)#

Problem Statement

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Incrementing by one gives 123 + 1 = 124. Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321. Incrementing by one gives 4321 + 1 = 4322. Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9] Output: [1,0] Explanation: The array represents the integer 9. Incrementing by one gives 9 + 1 = 10. Thus, the result should be [1,0].

Constraints:

  • 1 <= digits.length <= 100

  • 0 <= digits[i] <= 9

  • digits does not contain any leading 0's.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def plusOne(self, digits: List[int]) -> List[int]:
            one = 1
            i = 0
            digits = digits[::-1]

            while one:
                if i < len(digits):
                    if digits[i] == 9:
                        digits[i] = 0
                    else:
                        digits[i] += 1
                        one = 0
                else:
                    digits.append(one)
                    one = 0
                i += 1
            return digits[::-1]
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

106. Pow(x n) (Leetcode:50)#

Also in DSA Patterns

Pow(x, n) — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2⁻² = 1/2² = 1/4 = 0.25

Constraints:

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1
n is an integer.
Either x is not zero or n > 0.
-10^4 <= x^n <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def helper(x, n):
            if x == 0:
                return 0
            if n == 0:
                return 1

            res = helper(x * x, n // 2)
            return x * res if n % 2 else res

        res = helper(x, abs(n))
        return res if n >= 0 else 1 / res
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

107. Sqrt(x) (Leetcode:69)#

Also in DSA Patterns

Sqrt(x) — 09. Binary Search (may include extra approaches and complexity analysis).

Problem Statement

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

  • 0 <= x <= 231 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x
        while l <= r:
            mid = (l + r) // 2
            if mid * mid == x:
                return mid
            if mid * mid < x:
                l = mid + 1
            else:
                r = mid - 1
        return r
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

Matrix#

108. Game of Life (Leetcode:289)#

Problem Statement

According to the rules of Conway's Game of Life, simultaneously apply the next state to every cell in an m x n board of 0 (dead) and 1 (live) cells.

Example 1:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]] Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 25
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                live = 0
                for di in (-1, 0, 1):
                    for dj in (-1, 0, 1):
                        if di == 0 and dj == 0:
                            continue
                        ni, nj = i + di, j + dj
                        if 0 <= ni < m and 0 <= nj < n:
                            live += board[ni][nj] & 1
                if board[i][j] & 1:
                    if live < 2 or live > 3:
                        board[i][j] = 0b10
                elif live == 3:
                    board[i][j] = 0b11
        for i in range(m):
            for j in range(n):
                board[i][j] >>= 1
Explanation:

  1. Encode next state in bit 1 and keep current state in bit 0.
  2. Count live neighbors using only the lowest bit of each cell.
  3. Shift every cell right once to finalize the next generation.

109. Rotate Image (Leetcode:48)#

Also in DSA Patterns

Rotate Image — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise in place.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000
Code and Explanation 

 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 rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        l, r = 0, len(matrix) - 1
        while l < r:
            for i in range(r - l):
                top, bottom = l, r

                # save the topleft
                topLeft = matrix[top][l + i]

                # move bottom left into top left
                matrix[top][l + i] = matrix[bottom - i][l]

                # move bottom right into bottom left
                matrix[bottom - i][l] = matrix[bottom][r - i]

                # move top right into bottom right
                matrix[bottom][r - i] = matrix[top + i][r]

                # move top left into top right
                matrix[top + i][r] = topLeft
            r -= 1
            l += 1
Explanation:

  1. Transpose across diagonal swaps [i][j] with [j][i].
  2. Reverse each row for 90° clockwise rotation.
  3. In-place O(n²).
  4. Time complexity: O(n²)
  5. Space complexity: O(1)

110. Set Matrix Zeroes (Leetcode:73)#

Also in DSA Patterns

Set Matrix Zeroes — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1
Code and Explanation 

 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 setZeroes(self, matrix: List[List[int]]) -> None:
        # O(1)
        ROWS, COLS = len(matrix), len(matrix[0])
        rowZero = False

        # determine which rows/cols need to be zero
        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == 0:
                    matrix[0][c] = 0
                    if r > 0:
                        matrix[r][0] = 0
                    else:
                        rowZero = True

        for r in range(1, ROWS):
            for c in range(1, COLS):
                if matrix[0][c] == 0 or matrix[r][0] == 0:
                    matrix[r][c] = 0

        if matrix[0][0] == 0:
            for r in range(ROWS):
                matrix[r][0] = 0

        if rowZero:
            for c in range(COLS):
                matrix[0][c] = 0
Explanation:

  1. Use first row/col as flags for zero rows/columns.
  2. Remember if first row/col themselves had zeros.
  3. Mark from inner cells, apply marks, fix first row/col last.
  4. O(mn) time, O(1) space.
  5. Time complexity: O(m × n)
  6. Space complexity: O(1)

111. Spiral Matrix (Leetcode:54)#

Also in DSA Patterns

Spiral Matrix — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100
Code and Explanation 

 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 spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        left, right = 0, len(matrix[0])
        top, bottom = 0, len(matrix)

        while left < right and top < bottom:
            # get every i in the top row
            for i in range(left, right):
                res.append(matrix[top][i])
            top += 1
            # get every i in the right col
            for i in range(top, bottom):
                res.append(matrix[i][right - 1])
            right -= 1
            if not (left < right and top < bottom):
                break
            # get every i in the bottom row
            for i in range(right - 1, left - 1, -1):
                res.append(matrix[bottom - 1][i])
            bottom -= 1
            # get every i in the left col
            for i in range(bottom - 1, top - 1, -1):
                res.append(matrix[i][left])
            left += 1

        return res
Explanation:

  1. Four boundaries: top, bottom, left, right.
  2. Traverse right, down, left, up; shrink bounds.
  3. Stop when bounds cross.
  4. Time complexity: O(m × n)
  5. Space complexity: O(1)

112. Valid Sudoku (Leetcode:36)#

Problem Statement

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  • Each row must contain the digits 1-9 without repetition.

  • Each column must contain the digits 1-9 without repetition.

  • Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.

  • Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = [["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"]] Output: true

Example 2:

Input: board = [["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"]] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

  • board.length == 9

  • board[i].length == 9

  • board[i][j] is a digit 1-9 or '.'.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def isValidSudoku(self, board: List[List[str]]) -> bool:
            cols = collections.defaultdict(set)
            rows = collections.defaultdict(set)
            squares = collections.defaultdict(set)  # key = (r /3, c /3)

            for r in range(9):
                for c in range(9):
                    if board[r][c] == ".":
                        continue
                    if (
                        board[r][c] in rows[r]
                        or board[r][c] in cols[c]
                        or board[r][c] in squares[(r // 3, c // 3)]
                    ):
                        return False
                    cols[c].add(board[r][c])
                    rows[r].add(board[r][c])
                    squares[(r // 3, c // 3)].add(board[r][c])

            return True
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

Sliding Window#

113. Longest Substring Without Repeating Characters (Leetcode:3)#

Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with length 3.

Constraints:

  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols and spaces
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = best = 0
        for right, ch in enumerate(s):
            if ch in last_seen and last_seen[ch] >= left:
                left = last_seen[ch] + 1
            last_seen[ch] = right
            best = max(best, right - left + 1)
        return best
Explanation:

  1. Expand right, track last index of each char in map.
  2. If duplicate inside window, move left past previous occurrence.
  3. Update max window length each step.
  4. O(n) time.
  5. Time complexity: O(n)
  6. Space complexity: O(min(n, charset))

114. Minimum Size Subarray Sum (Leetcode:209)#

Problem Statement

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4] Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0

Constraints:

  • 1 <= target <= 109

  • 1 <= nums.length <= 105

  • 1 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def minSubArrayLen(self, target: int, nums: List[int]) -> int:
            res = float('inf')
            l, total = 0, 0

            for r in range(len(nums)):
                total += nums[r]
                while total >= target:
                    res = min(res, r - l + 1)
                    total -= nums[l]
                    l += 1
            return res if res != float('inf') else 0
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

115. Minimum Window Substring (Leetcode:76)#

Also in DSA Patterns

Minimum Window Substring — 03. Sliding Window (may include extra approaches and complexity analysis).

Problem Statement

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window.

Example 3:

nput: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length n == t.length 1 <= m, n <= 105 s and t consist of uppercase and lowercase English letters.

Follow up:

Could you find an algorithm that runs in O(m + n) time?

Code and Explanation 

 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 Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t):
            return ""

        need: dict[str, int] = {}
        for ch in t:
            need[ch] = need.get(ch, 0) + 1

        have = 0
        required = len(need)
        window: dict[str, int] = {}
        res = (-1, -1)
        res_len = float("inf")
        left = 0

        for right, ch in enumerate(s):
            window[ch] = window.get(ch, 0) + 1
            if ch in need and window[ch] == need[ch]:
                have += 1

            while have == required:
                if (right - left + 1) < res_len:
                    res = (left, right)
                    res_len = right - left + 1
                window[s[left]] -= 1
                if s[left] in need and window[s[left]] < need[s[left]]:
                    have -= 1
                left += 1

        left, right = res
        return s[left : right + 1] if res_len != float("inf") else
Explanation:

  1. The window size remains constant throughout the process.
  2. The window moves from the beginning of the sequence to the end, sliding one element at a time.
  3. At each step, the next element is added, and the element that is no longer within the window is removed.
  4. The window expands or contracts depending on certain conditions.
  5. The size of the window is not fixed and can change during traversal.

116. Substring with Concatenation of All Words (Leetcode:30)#

Also in DSA Patterns

Substring with Concatenation of All Words — 03. Sliding Window (may include extra approaches and complexity analysis).

Problem Statement

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

  • For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: [] Explanation: There is no concatenated substring.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] Output: [6,9,12] Explanation: The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"]. The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"]. The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].

Constraints:

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • s and words[i] consist of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:

        max_sum = curr_sum = sum(nums[:k])

        for i in range(k,len(nums)):

            curr_sum+= nums[i] - nums[i-k]
            max_sum = max(max_sum, curr_sum)

        return max_sum/k
Explanation:

  1. The window size remains constant throughout the process.
  2. The window moves from the beginning of the sequence to the end, sliding one element at a time.
  3. At each step, the next element is added, and the element that is no longer within the window is removed.
  4. The window expands or contracts depending on certain conditions.
  5. The size of the window is not fixed and can change during traversal.

Stack#

117. Basic Calculator (Leetcode:224)#

Also in DSA Patterns

Basic Calculator — 08. Stack (may include extra approaches and complexity analysis).

Problem Statement

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "1 + 1" Output: 2

Example 2:

Input: s = " 2-1 + 2 " Output: 3

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.
  • '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
  • '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.
Code and Explanation 

 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 calculate(self, s: str) -> int:
        stack: list[int] = []
        result = number = sign = 0
        for ch in s:
            if ch.isdigit():
                number = number * 10 + int(ch)
            elif ch in '+-':
                result += sign * number
                number = 0
                sign = 1 if ch == '+' else -1
            elif ch == '(':
                stack.append(result)
                stack.append(sign)
                result = number = 0
                sign = 1
            elif ch == ')':
                result += sign * number
                number = 0
                result *= stack.pop()
                result += stack.pop()
        return result + sign * number
Explanation:

  1. Scan digits to build the current number and apply the current sign.
  2. On '(', push accumulated result and sign onto a stack.
  3. On ')', finalize the inner expression and combine with saved context.

118. Evaluate Reverse Polish Notation (Leetcode:150)#

Also in DSA Patterns

Evaluate Reverse Polish Notation — 08. Stack (may include extra approaches and complexity analysis).

Problem Statement

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

  • The valid operators are '+', '-', '*', and '/'.
  • Each operand may be an integer or another expression.
  • The division between two integers always truncates toward zero.
  • There will not be any division by zero.
  • The input represents a valid arithmetic expression in a reverse polish notation.
  • The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

Constraints:

  • 1 <= tokens.length <= 104
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for c in tokens:
            if c == "+":
                stack.append(stack.pop() + stack.pop())
            elif c == "-":
                a, b = stack.pop(), stack.pop()
                stack.append(b - a)
            elif c == "*":
                stack.append(stack.pop() * stack.pop())
            elif c == "/":
                a, b = stack.pop(), stack.pop()
                stack.append(int(float(b) / a))
            else:
                stack.append(int(c))
        return stack[0]
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

119. Simplify Path (Leetcode:71)#

Problem Statement

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.

The rules of a Unix-style file system are as follows:

  • A single period '.' represents the current directory.

  • A double period '..' represents the previous/parent directory.

  • Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.

  • Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...'and '....' are valid directory or file names.

The simplified canonical path should follow these rules:

  • The path must start with a single slash '/'.

  • Directories within the path must be separated by exactly one slash '/'.

  • The path must not end with a slash '/', unless it is the root directory.

  • The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.

Return the simplified canonical path.

Example 1:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

Example 2:

Input: path = "/home//foo/"

Output: "/home/foo"

Explanation:

Multiple consecutive slashes are replaced by a single one.

Example 3:

Input: path = "/home/user/Documents/../Pictures"

Output: "/home/user/Pictures"

Explanation:

A double period ".." refers to the directory up a level (the parent directory).

Example 4:

Input: path = "/../"

Output: "/"

Explanation:

Going one level up from the root directory is not possible.

Example 5:

Input: path = "/.../a/../b/c/../d/./"

Output: "/.../b/d"

Explanation:

"..." is a valid name for a directory in this problem.

Constraints:

  • 1 <= path.length <= 3000

  • path consists of English letters, digits, period '.', slash '/' or '_'.

  • path is a valid absolute Unix path.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def simplifyPath(self, path: str) -> str:

            stack = []

            for i in path.split("/"):
                #  if i == "/" or i == '//', it becomes '' (empty string)

                if i == "..":
                    if stack:
                        stack.pop()
                elif i == "." or i == '':
                    # skip "." or an empty string
                    continue
                else:
                    stack.append(i)

            res = "/" + "/".join(stack)
            return res
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

120. Valid Parentheses (Leetcode:20)#

Also in DSA Patterns

Valid Parentheses — 08. Stack (may include extra approaches and complexity analysis).

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()" Output: true

Example 2:

Input: s = "()[]{}" Output: true

Example 3:

Input: s = "(]" Output: false

Example 4:

Input: s = "([])" Output: true

Example 5:

Input: s = "([)]" Output: false

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isValid(self, s: str) -> bool:
        bracketMap = {")": "(", "]": "[", "}": "{"}
        stack = []

        for c in s:
            if c not in bracketMap:
                stack.append(c)
                continue
            if not stack or stack[-1] != bracketMap[c]:
                return False
            stack.pop()

        return not stack
Explanation:

  1. Push opening brackets.
  2. On closing, stack must match top.
  3. Valid iff stack empty at end.
  4. Time complexity: O(n)
  5. Space complexity: O(n)

Trees#

121. Average of Levels in Binary Tree (Leetcode:637)#

Problem Statement

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [3.0,14.5,11.0]

Constraints:

  • The number of nodes in the tree is in the range [1, 10^4].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def averageOfLevels(self, root: TreeNode | None) -> list[float]:
        from collections import deque
        if not root:
            return []
        queue: deque[TreeNode] = deque([root])
        averages: list[float] = []
        while queue:
            level_size = len(queue)
            total = 0
            for _ in range(level_size):
                node = queue.popleft()
                total += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            averages.append(total / level_size)
        return averages
Explanation:

  1. Use BFS with level-size snapshots.
  2. Sum node values at each level before moving deeper.
  3. Append total divided by level size to the answer.

122. Binary Search Tree Iterator (Leetcode:173)#

Also in DSA Patterns

Binary Search Tree Iterator — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree.

Example 1:

Input: ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"], [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []] Output: [null, 3, 7, true, 9, true, 15, true, 20, false]

Constraints:

  • The number of nodes in the tree is in the range [1, 10^5].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class BSTIterator:
    def __init__(self, root: TreeNode | None):
        self.stack: list[TreeNode] = []
        self._push_left(root)

    def _push_left(self, node: TreeNode | None) -> None:
        while node:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

    def hasNext(self) -> bool:
        return bool(self.stack)
Explanation:

  1. Use a stack to simulate iterative in-order traversal.
  2. Initialize by pushing all left nodes from the root.
  3. On next(), pop the smallest node and push left chain of its right child.

123. Binary Tree Level Order Traversal (Leetcode:102)#

Also in DSA Patterns

Binary Tree Level Order Traversal — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

Example 3:

Input: root = [] Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
Code and Explanation 

 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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        q = collections.deque()
        if root:
            q.append(root)

        while q:
            val = []

            for i in range(len(q)):
                node = q.popleft()
                val.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(val)
        return res
Explanation:

  1. Queue starts with root.
  2. Snapshot queue size each iteration = current level width.
  3. Collect values, enqueue children.
  4. Time complexity: O(n)
  5. Space complexity: O(n)

124. Binary Tree Maximum Path Sum (Leetcode:124)#

Also in DSA Patterns

Maximum Path Sum in Binary Tree — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can only appear at most once. The path sum is the sum of the node values. Given the root, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3] Output: 6 Explanation: Optimal path is 2 -> 1 -> 3 with sum 6.

Constraints:

  • The number of nodes is in the range [1, 3 * 10^4]
  • -1000 <= Node.val <= 1000
Code and Explanation 

 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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        res = [root.val]

        # return max path sum without split
        def dfs(root):
            if not root:
                return 0

            leftMax = dfs(root.left)
            rightMax = dfs(root.right)
            leftMax = max(leftMax, 0)
            rightMax = max(rightMax, 0)

            # compute max path sum WITH split
            res[0] = max(res[0], root.val + leftMax + rightMax)
            return root.val + max(leftMax, rightMax)

        dfs(root)
        return res[0]
Explanation:

  1. At each node, best path through node = left_gain + val + right_gain.
  2. Return to parent only one-sided gain: val + max(left, right).
  3. Global best tracks maximum anywhere in tree.
  4. Time complexity: O(n)
  5. Space complexity: O(h)

125. Binary Tree Right Side View (Leetcode:199)#

Also in DSA Patterns

Binary Tree Right Side View — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Example 2:

Example 3:

Example 4:

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        res = []
        q = collections.deque([root])

        while q:
            rightSide = None
            qLen = len(q)

            for i in range(qLen):
                node = q.popleft()
                if node:
                    rightSide = node
                    q.append(node.left)
                    q.append(node.right)
            if rightSide:
                res.append(rightSide.val)
        return res
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

126. Binary Tree Zigzag Level Order Traversal (Leetcode:103)#

Also in DSA Patterns

Binary Tree Zigzag Level Order Traversal — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

Example 3:

Input: root = [] Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return
        result, zigzagDirection = [], 1
        q = [root]
        while q:
            level, queueLength = [], len(q)
            for i in range(queueLength):
                node = q.pop(0)
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            result.append(level[::zigzagDirection])
            zigzagDirection *= -1
        return result
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

127. Construct Binary Tree from Inorder and Postorder Traversal (Leetcode:106)#

Also in DSA Patterns

Construct Binary Tree from Inorder and Postorder Traversal — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

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

 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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def buildTreeHelper(left, right):
            if left > right:
                return None

            rootVal = postorder.pop()
            rootNode = TreeNode(rootVal)

            idx = inorderIndexMap[rootVal]
            rootNode.right = buildTreeHelper(idx + 1, right)
            rootNode.left = buildTreeHelper(left, idx - 1)
            return rootNode

        inorderIndexMap = {}
        for (i, val) in enumerate(inorder):
            inorderIndexMap[val] = i

        return buildTreeHelper(0, len(postorder) - 1)
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

128. Construct Binary Tree from Preorder and Inorder Traversal (Leetcode:105)#

Also in DSA Patterns

Construct Binary Tree from Preorder and Inorder Traversal — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

Constraints:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values
  • Each value appears once in both arrays
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        in_index = {val: i for i, val in enumerate(inorder)}
        pre_idx = 0

        def helper(left: int, right: int) -> Optional[TreeNode]:
            nonlocal pre_idx
            if left > right:
                return None
            root_val = preorder[pre_idx]
            pre_idx += 1
            root = TreeNode(root_val)
            mid = in_index[root_val]
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

        return helper(0, len(inorder) - 1)
Explanation:

  1. Precompute inorder positions: Build in_index = {value: index} from inorder. When we pick a root from preorder, this map instantly tells us where that value splits the inorder array into left and right parts.
  2. Shared preorder pointer: pre_idx reads roots in preorder order (root → left subtree → right subtree). Each recursive call consumes exactly one preorder value — that value is always the root of the subtree being built.
  3. Recurse on index ranges, not slices: helper(left, right) builds the tree for the inorder segment [left..right]. If left > right, the segment is empty → return None.
  4. Split using the root's inorder index: After creating root from preorder[pre_idx], look up mid = in_index[root_val]. Left subtree covers inorder indices [left, mid-1]; right covers [mid+1, right]. No list copying.
  5. Why this is optimal: Each node is visited once with O(1) hash lookups — no repeated slicing or .index() calls.
  6. Time complexity: O(n)
  7. Space complexity: O(n)

1
2
3
4
5
6
7
8
9
class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
        return root
Explanation:

  1. Root is always preorder[0]. Find it in inorder at index mid.
  2. Left subtree: preorder[1:mid+1] pairs with inorder[:mid].
  3. Right subtree: preorder[mid+1:] pairs with inorder[mid+1:].
  4. Easy to understand but O(n²) from slicing and .index() at every level.
  5. Time complexity: O(n²)
  6. Space complexity: O(n²)

129. Count Complete Tree Nodes (Leetcode:222)#

Also in DSA Patterns

Count Nodes in Complete Binary Tree — 11. Divide and Conquer (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:


Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [0, 5 * 10^4].
  • 0 <= Node.val <= 5 * 10^4
  • The tree is guaranteed to be complete.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def countNodes(self, root: TreeNode | None) -> int:
        if not root:
            return 0
        left = right = 0
        node = root
        while node.left:
            left += 1
            node = node.left
        node = root
        while node.right:
            right += 1
            node = node.right
        if left == right:
            return (1 << (left + 1)) - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
Explanation:

  1. Measure left height and right height from the root.
  2. If equal, the tree is a perfect tree with 2^(h+1) - 1 nodes.
  3. Otherwise recurse on left and right subtrees and add 1 for the root.

130. Flatten Binary Tree to Linked List (Leetcode:114)#

Also in DSA Patterns

Flatten Binary Tree to Linked List — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, flatten the tree into a "linked list" in-place using the same TreeNode class where the right child pointer points to the next node and the left child pointer is always null.

Example 1:

Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]

Constraints:

  • The number of nodes in the tree is in the range [0, 200].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def flatten(self, root: TreeNode | None) -> None:
        if not root:
            return
        self.flatten(root.left)
        self.flatten(root.right)
        right = root.right
        root.right = root.left
        root.left = None
        node = root
        while node.right:
            node = node.right
        node.right = right
Explanation:

  1. Recursively flatten left and right subtrees first.
  2. Save the original right subtree, then attach the flattened left subtree to the right.
  3. Walk to the end of the new right chain and reconnect the saved right subtree.

131. Invert Binary Tree (Leetcode:226)#

Also in DSA Patterns

Invert Binary Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Explanation:

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        # swap the children
        root.left, root.right = root.right, root.left

        # make 2 recursive calls
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
Explanation:

  1. Swap left and right at each node recursively.
  2. Post-order: invert children then assign.
  3. Time complexity: O(n)
  4. Space complexity: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from collections import deque


class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        queue = deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root
Explanation:

  1. Queue nodes; swap children when dequeuing.
  2. Enqueue swapped children for later processing.
  3. Time complexity: O(n)
  4. Space complexity: O(n)

132. Kth Smallest Element in a BST (Leetcode:230)#

Also in DSA Patterns

Kth Smallest Element in a BST — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1 Output: 1

Constraints:

  • The number of nodes is n where 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        curr = root

        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
            curr = curr.right
Explanation:

  1. Push left spine onto stack.
  2. Pop, visit, go right.
  3. Stop at kth pop.
  4. Time complexity: O(h + k)
  5. Space complexity: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.count = 0
        self.result = 0

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left)
            self.count += 1
            if self.count == k:
                self.result = node.val
                return
            inorder(node.right)

        inorder(root)
        return self.result
Explanation:

  1. Inorder visits BST in sorted order.
  2. Increment count on visit; return at k.
  3. Time complexity: O(h + k)
  4. Space complexity: O(h)

133. Lowest Common Ancestor of a Binary Tree (Leetcode:236)#

Also in DSA Patterns

Lowest Common Ancestor in a Binary Tree — 11. Divide and Conquer (may include extra approaches and complexity analysis).

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q in the tree. The LCA is defined as the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Constraints:

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

 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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return
        if root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root

        if left:
            return left
        if right:
            return right

        return None
Explanation:

  1. If node is p or q, return it.
  2. Search left and right subtrees.
  3. If both return non-null, current node is LCA; else propagate non-null side.
  4. Time complexity: O(n)
  5. Space complexity: O(h)

134. Maximum Depth of Binary Tree (Leetcode:104)#

Also in DSA Patterns

Maximum Depth of Binary Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root down to the farthest leaf.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: 3

Constraints:

  • The number of nodes is in the range [0, 10^4]
  • -100 <= Node.val <= 100
Code and Explanation 

 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
# RECURSIVE DFS
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))


# ITERATIVE DFS
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        stack = [[root, 1]]
        res = 0

        while stack:
            node, depth = stack.pop()

            if node:
                res = max(res, depth)
                stack.append([node.left, depth + 1])
                stack.append([node.right, depth + 1])
        return res


# BFS
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        q = deque()
        if root:
            q.append(root)

        level = 0

        while q:

            for i in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return level
Explanation:

  1. Base case: Empty node → depth 0.
  2. Recurse on children; return 1 + max(left, right).
  3. Simple post-order height computation.
  4. Time complexity: O(n)
  5. Space complexity: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from collections import deque


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        depth = 0
        queue = deque([root])
        while queue:
            depth += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return depth
Explanation:

  1. Queue level-order traversal.
  2. Increment depth after processing each level's nodes.
  3. Avoids recursion depth limits.
  4. Time complexity: O(n)
  5. Space complexity: O(n)

135. Minimum Absolute Difference in BST (Leetcode:530)#

Also in DSA Patterns

Minimum Absolute Difference in BST — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]
Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 10⁴].
  • 0 <= Node.val <= 10⁵
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def getMinimumDifference(self, root: TreeNode | None) -> int:
        prev = None
        best = float('inf')
        def inorder(node: TreeNode | None) -> None:
            nonlocal prev, best
            if not node:
                return
            inorder(node.left)
            if prev is not None:
                best = min(best, node.val - prev)
            prev = node.val
            inorder(node.right)
        inorder(root)
        return best
Explanation:

  1. In-order traversal visits BST values in sorted order.
  2. Compare each node with its in-order predecessor.
  3. Track the smallest positive difference.

136. Path Sum (Leetcode:112)#

Also in DSA Patterns

Path Sum — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation:
The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation:
There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation:
Since the tree is empty, there are no root-to-leaf paths.

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
Code and Explanation 

 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
# Recursive Solution
class Solution:
    def hasPathSum(self, root, sum):
        if not root:
            return False
        sum -= root.val
        if not root.left and not root.right:
            return sum == 0
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

# Iterative Solution
class Solution:
    def hasPathSum(self, root, sum):
        de = [
            (root, sum - root.val),
        ]
        while de:
            node, curr_sum = de.pop()
            if not node.left and not node.right and curr_sum == 0:
                return True
            if node.right:
                de.append((node.right, curr_sum - node.right.val))
            if node.left:
                de.append((node.left, curr_sum - node.left.val))
        return False
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

137. Populating Next Right Pointers in Each Node II (Leetcode:117)#

Also in DSA Patterns

Populating Next Right Pointers in Each Node II — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given a binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Each node has an additional next pointer.

Example 1:

Input: root = [1,2,3,4,5,null,7] Output: Nodes are connected level by level.

Constraints:

  • The number of nodes in the tree is in the range [0, 6000].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def connect(self, root: 'Node | None') -> 'Node | None':
        head = root
        while head:
            dummy = Node(0)
            tail = dummy
            node = head
            while node:
                if node.left:
                    tail.next = node.left
                    tail = tail.next
                if node.right:
                    tail.next = node.right
                    tail = tail.next
                node = node.next
            head = dummy.next
        return root
Explanation:

  1. Process the tree level by level using existing next pointers.
  2. Build the next level's linked list with a dummy head and tail.
  3. Advance head to the start of the next level and repeat.

138. Same Tree (Leetcode:100)#

Also in DSA Patterns

Same Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two trees are the same if they are structurally identical and nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3] Output: true

Constraints:

  • The number of nodes is in the range [0, 100]
  • -10^4 <= Node.val <= 10^4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if p and q and p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False
Explanation:

  1. Both null → true; one null → false.
  2. Values must match; recurse on both children.
  3. Time complexity: O(n)
  4. Space complexity: O(h)

139. Sum Root to Leaf Numbers (Leetcode:129)#

Also in DSA Patterns

Sum Root to Leaf Numbers — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

You are given the root of a binary tree containing digits from 0 to 9 only. Each root-to-leaf path represents a number. Return the total sum of all root-to-leaf numbers.

Example 1:

Input: root = [1,2,3] Output: 25 Explanation: Paths 12 and 13 give 12 + 13 = 25.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def sumNumbers(self, root: TreeNode | None) -> int:
        def dfs(node: TreeNode | None, current: int) -> int:
            if not node:
                return 0
            current = current * 10 + node.val
            if not node.left and not node.right:
                return current
            return dfs(node.left, current) + dfs(node.right, current)
        return dfs(root, 0)
Explanation:

  1. DFS while building the number along the current path.
  2. At a leaf, return the completed number.
  3. Sum results from left and right subtrees.

140. Symmetric Tree (Leetcode:101)#

Also in DSA Patterns

Symmetric Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100
Code and Explanation 

 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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root.left and not root.right:
            return True
        queueLeft = deque()
        queueRight = deque()

        queueLeft.appendleft(root.left)
        queueRight.appendleft(root.right)

        while queueLeft and queueRight:
            nodeLeft, nodeRight = queueLeft.pop(), queueRight.pop()
            if not nodeLeft and not nodeRight:
                continue
            # both node must exist
            # if exists thet must have the same value
            if not nodeLeft or not nodeRight or nodeLeft.val != nodeRight.val:
                return False

            queueLeft.appendleft(nodeLeft.left)
            queueLeft.appendleft(nodeLeft.right)

            queueRight.appendleft(nodeRight.right)
            queueRight.appendleft(nodeRight.left)
        return not (queueLeft or queueRight)
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

141. Validate Binary Search Tree (Leetcode:98)#

Also in DSA Patterns

Validate Binary Search Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree only nodes with keys greater than the node's key.

Example 1:

Input: root = [2,1,3] Output: true

Constraints:

  • The number of nodes is in the range [1, 10^4]
  • -2^31 <= Node.val <= 2^31 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def valid(node, left, right):
            if not node:
                return True
            if not (left < node.val < right):
                return False

            return valid(node.left, left, node.val) and valid(
                node.right, node.val, right
            )

        return valid(root, float("-inf"), float("inf"))
Explanation:

  1. Pass valid (min, max) range down recursion.
  2. Node must satisfy min < val < max.
  3. Left child max becomes current val; right child min becomes current val.
  4. Time complexity: O(n)
  5. Space complexity: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = float('-inf')

        def inorder(node: Optional[TreeNode]) -> bool:
            nonlocal prev
            if not node:
                return True
            if not inorder(node.left):
                return False
            if node.val <= prev:
                return False
            prev = node.val
            return inorder(node.right)

        return inorder(root)
Explanation:

  1. BST inorder is strictly increasing.
  2. Track previous visited value.
  3. Invalid if current <= prev.
  4. Time complexity: O(n)
  5. Space complexity: O(h)

Tries#

142. Design Add and Search Words Data Structure (Leetcode:211)#

Also in DSA Patterns

Add and Search Word — 19. Tries (may include extra approaches and complexity analysis).

Problem Statement

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true] Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True

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.
Code and Explanation 

 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
class TrieNode:
    def __init__(self):
        self.children = {}  # a : TrieNode
        self.word = False


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

    def addWord(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.word = True

    def search(self, word: str) -> bool:
        def dfs(j, root):
            cur = root

            for i in range(j, len(word)):
                c = word[i]
                if c == ".":
                    for child in cur.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if c not in cur.children:
                        return False
                    cur = cur.children[c]
            return cur.word

        return dfs(0, self.root)
Explanation:

  1. Insert words into trie normally.
  2. Search: on '.', try all children recursively.
  3. Match succeeds at end-of-word flag.
  4. Time complexity: O(26^L) worst
  5. Space complexity: O(total chars)

143. Implement Trie (Prefix Tree) (Leetcode:208)#

Also in DSA Patterns

Implement Trie (Prefix Tree) — 19. Tries (may include extra approaches and complexity analysis).

Problem Statement

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true]

Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

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.
Code and Explanation 

 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):
        self.children = [None] * 26
        self.end = False


class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        curr = self.root
        for c in word:
            i = ord(c) - ord("a")
            if curr.children[i] is None:
                curr.children[i] = TrieNode()
            curr = curr.children[i]
        curr.end = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        curr = self.root
        for c in word:
            i = ord(c) - ord("a")
            if curr.children[i] is None:
                return False
            curr = curr.children[i]
        return curr.end

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        curr = self.root
        for c in prefix:
            i = ord(c) - ord("a")
            if curr.children[i] is None:
                return False
            curr = curr.children[i]
        return True
Explanation:

  1. Each node has char → child map and end flag.
  2. insert walks/creates path; search requires end flag; startsWith only needs path.
  3. Time complexity: O(L) per op
  4. Space complexity: O(total chars)

144. Word Search II (Leetcode:212)#

Also in DSA Patterns

Word Search II — 19. Tries (may include extra approaches and complexity analysis).

Problem Statement

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.
Code and Explanation 

 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
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
        self.refs = 0

    def addWord(self, word):
        cur = self
        cur.refs += 1
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
            cur.refs += 1
        cur.isWord = True

    def removeWord(self, word):
        cur = self
        cur.refs -= 1
        for c in word:
            if c in cur.children:
                cur = cur.children[c]
                cur.refs -= 1


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for w in words:
            root.addWord(w)

        ROWS, COLS = len(board), len(board[0])
        res, visit = set(), set()

        def dfs(r, c, node, word):
            if (
                r not in range(ROWS) 
                or c not in range(COLS)
                or board[r][c] not in node.children
                or node.children[board[r][c]].refs < 1
                or (r, c) in visit
            ):
                return

            visit.add((r, c))
            node = node.children[board[r][c]]
            word += board[r][c]
            if node.isWord:
                node.isWord = False
                res.add(word)
                root.removeWord(word)

            dfs(r + 1, c, node, word)
            dfs(r - 1, c, node, word)
            dfs(r, c + 1, node, word)
            dfs(r, c - 1, node, word)
            visit.remove((r, c))

        for r in range(ROWS):
            for c in range(COLS):
                dfs(r, c, root, "")

        return list(res)
Explanation:

  1. Build trie of all words.
  2. DFS board while walking trie; prune when prefix missing.
  3. Collect word at trie node; mark found to dedupe.
  4. Time complexity: O(m × n × 4^L)
  5. Space complexity: O(total chars)

Two Pointers#

145. 3Sum (Leetcode:15)#

Also in DSA Patterns

3Sum — 01. Two Pointers (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: The distinct triplets are [-1,0,1] and [-1,-1,2].

Example 2:

Input: nums = [0,1,1] Output: []

Example 3:

Input: nums = [0,0,0] Output: [[0,0,0]]

Constraints:

3 <= nums.length <= 3000 -10^5 <= nums[i] <= 10^5

Code and Explanation 

 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
def threeSum(nums):
                nums.sort()
                res = []

                for i in range(len(nums) - 2):
                    # Skip duplicates for i
                    if i > 0 and nums[i] == nums[i - 1]:
                        continue

                    left = i + 1
                    right = len(nums) - 1

                    while left < right:
                        curr_sum = nums[i] + nums[left] + nums[right]

                        if curr_sum == 0:
                            res.append([nums[i], nums[left], nums[right]])
                            # Skip duplicates for left and right
                            while left < right and nums[left] == nums[left + 1]:
                                left += 1
                            while left < right and nums[right] == nums[right - 1]:
                                right -= 1

                            left += 1
                            right -= 1

                        elif curr_sum < 0:
                            left += 1
                        else:
                            right -= 1

                return res
Explanation:

  1. Sort first: Enables two-pointer search and duplicate skipping.
  2. Fix one number at i: Set left = i+1, right = n-1, find pairs summing to -nums[i].
  3. Skip duplicates: After finding a triplet or advancing i, skip equal values.
  4. Time complexity: O(n²)
  5. Space complexity: O(1)

146. Container With Most Water (Leetcode:11)#

Also in DSA Patterns

Container With Most Water — 01. Two Pointers (may include extra approaches and complexity analysis).

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The max area of water the container can contain is 49.

Example 2:

Input: height = [1,1] Output: 1

Constraints:

n == height.length 2 <= n <= 10^5 0 <= height[i] <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0

        while left < right:
            h = min(height[left], height[right])
            w = right - left
            max_area = max(max_area, h * w)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area
Explanation:

  1. Start wide: left = 0, right = n-1.
  2. Area formula: Height = min(height[left], height[right]); width = right - left.
  3. Move shorter side: Advance the pointer at the shorter wall to seek more area.
  4. Why: Keeping the shorter side fixes the height cap. O(n) time.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

147. Is Subsequence (Leetcode:392)#

Problem Statement

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "abc", t = "ahbgdc" Output: true Example 2:

Input: s = "axc", t = "ahbgdc" Output: false

Constraints:

  • 0 <= s.length <= 100

  • 0 <= t.length <= 104

  • s and t consist only of lowercase English letters.

Follow up: Suppose there are lots of incoming s, say s_1_, s_2_, ..., s_k_ where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def isSubsequence(self, s: str, t: str) -> bool:
            i, j = 0, 0
            while i < len(s) and j < len(t):
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == len(s)
    ```
    **Explanation:**

    1. Official-style Python solution adapted for Brewing Intelligence sheets.
    2. Compare your approach with the reference implementation below.

148. Trapping Rain Water (Leetcode:42)#

Also in DSA Patterns

Trapping Rain Water — 08. Stack (may include extra approaches and complexity analysis).

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        l, r = 0, len(height) - 1
        leftMax, rightMax = height[l], height[r]
        res = 0
        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
        return res
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

149. Two Sum II - Input Array Is Sorted (Leetcode:167)#

Problem Statement

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers index1 and index2, each incremented by one, as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1

        while l < r:
            curSum = numbers[l] + numbers[r]

            if curSum > target:
                r -= 1
            elif curSum < target:
                l += 1
            else:
                return [l + 1, r + 1]
Explanation:

  1. Official-style Python solution adapted for Brewing Intelligence sheets.
  2. Compare your approach with the reference implementation below.

150. Valid Palindrome (Leetcode:125)#

Also in DSA Patterns

Valid Palindrome — 01. Two Pointers (may include extra approaches and complexity analysis).

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True
Explanation:

  1. Move inward skipping non-alphanumeric.
  2. Compare lowercased chars.
  3. O(n) time, O(1) space.
  4. Time complexity: O(n)
  5. Space complexity: O(1)