Grind 75#

The Grind 75 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

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

Arrays & Hashing#

1. Array Partition (Leetcode:561)#

Problem Statement

Given an integer array nums of 2n integers, group these into n pairs so that the sum of the minima of each pair is maximized.

Example 1:

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

Constraints:

1 <= n <= 10^4

nums.length == 2 * n

Code and Explanation

Optimal

class Solution:
    def arrayPairSum(self, nums: list[int]) -> int:
        nums.sort()
        return sum(nums[i] for i in range(0, len(nums), 2))

Explanation:

Sort the array so adjacent values form close pairs.
In each sorted pair, the smaller value is always taken.
Sum every even index after sorting.

2. Contains Duplicate (Leetcode:217)#

Problem Statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

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

Constraints:

1 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9

Code and Explanation

Hash Set (Optimal)Sort + Adjacent Scan

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashset = set()

        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False

Explanation:

Walk the array: For each num, check whether it is already in seen.
Duplicate found: If yes, return True immediately.
Otherwise insert: Add num to the set and continue.
Result: Return False after the loop. O(n) time, O(n) space.
Time complexity: O(n)
Space complexity: O(n)

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

Explanation:

Sort the array: Bring equal values next to each other.
Compare neighbors: If any nums[i] == nums[i-1], a duplicate exists.
No extra structure: Uses only the sorted array.
Tradeoff: O(n log n) time, O(1) extra space if sorting in place.
Time complexity: O(n log n)
Space complexity: O(1)

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

4. Detect Capital (Leetcode:520)#

Problem Statement

Given a word word, return true if the usage of capitals in it is correct.

Example 1:

Input: word = "USA" Output: true

Example 2:

Input: word = "FlaG" Output: false

Constraints:

1 <= word.length <= 100

word consists of lowercase and uppercase English letters.

Code and Explanation

Optimal

class Solution:
    def detectCapitalUse(self, word: str) -> bool:
        return word.isupper() or word.islower() or word.istitle()

Explanation:

Valid patterns are all uppercase, all lowercase, or title case.
Python string methods check each pattern directly.
Return true if any valid capitalization pattern matches.

5. Distribute Candies (Leetcode:575)#

Problem Statement

Alice has n candies, where the ith candy is of type candyType[i]. Bob has a rule that he can eat at most half of the candies. Return the maximum number of different types of candies Alice can eat.

Example 1:

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

Constraints:

n == candyType.length

2 <= n <= 10^4

Code and Explanation

Optimal

class Solution:
    def distributeCandies(self, candyType: list[int]) -> int:
        return min(len(set(candyType)), len(candyType) // 2)

Explanation:

Count distinct candy types with a set.
Alice may eat at most half of all candies.
Return the smaller of those two limits.

6. Find All Numbers Disappeared in an Array (Leetcode:448)#

Also in DSA Patterns

Find All Numbers Disappeared in an Array — 05. Cyclic Sort (may include extra approaches and complexity analysis).

Problem Statement

Given nums of length n with values in [1, n], return all integers in [1, n] that do not appear.

Example 1:

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

Code and Explanation

Optimal

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for n in nums:
            i = abs(n) - 1
            nums[i] = -1 * abs(nums[i])

        res = []
        for i, n in enumerate(nums):
            if n > 0:
                res.append(i + 1)
        return res

Explanation:

Walk through the approach in the code above.

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

Optimal

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:

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

8. First Unique Character in a String (Leetcode:387)#

Problem Statement

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = "leetcode" Output: 0

Example 2:

Input: s = "loveleetcode" Output: 2

Constraints:

1 <= s.length <= 10^5

s consists of only lowercase English letters.

Code and Explanation

Optimal

class Solution:
    def firstUniqChar(self, s: str) -> int:
        counts: dict[str, int] = {}
        for ch in s:
            counts[ch] = counts.get(ch, 0) + 1
        for i, ch in enumerate(s):
            if counts[ch] == 1:
                return i
        return -1

Explanation:

Count the frequency of each character in one pass.
Scan the string again in order to find the first count of 1.
Return -1 if every character repeats.

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

Optimal

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:

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

10. Intersection of Two Arrays (Leetcode:349)#

Problem Statement

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Explanation: [4,9] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 1000

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
            seen = set(nums1)

            res = []
            for n in nums2:
                if n in seen:
                    res.append(n)
                    seen.remove(n)
            return res
    ```
    **Explanation:**

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

11. Intersection of Two Arrays II (Leetcode:350)#

Problem Statement

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 1000

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

What if nums1's size is small compared to nums2's size? Which algorithm is better?

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
            counter1 = Counter(nums1)
            counter2 = Counter(nums2)

            # Using defaultdict to handle missing keys more efficiently
            counter1 = defaultdict(int, counter1)
            counter2 = defaultdict(int, counter2)

            intersection = []

            for num, freq in counter1.items():
                min_freq = min(freq, counter2[num])
                if min_freq > 0:
                    intersection.extend([num] * min_freq)

            return intersection
    ```
    **Explanation:**

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

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

13. Keyboard Row (Leetcode:500)#

Problem Statement

Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of an American keyboard.

Example 1:

Input: words = ["Hello","Alaska","Dad","Peace"] Output: ["Alaska","Dad"]

Constraints:

1 <= words.length <= 20

1 <= words[i].length <= 100

Code and Explanation

Optimal

class Solution:
    def findWords(self, words: list[str]) -> list[str]:
        rows = [
            set('qwertyuiop'),
            set('asdfghjkl'),
            set('zxcvbnm'),
        ]
        result: list[str] = []
        for word in words:
            letters = {ch.lower() for ch in word}
            if any(letters <= row for row in rows):
                result.append(word)
        return result

Explanation:

Map each keyboard row to a set of lowercase letters.
For each word, collect its unique letters in lowercase.
Include the word if all letters fit within one row.

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

15. License Key Formatting (Leetcode:482)#

Problem Statement

You are given a license key consisting of alphanumeric characters and dashes. Reformat the string so that each group contains k characters, except possibly the first group, and convert all letters to uppercase.

Example 1:

Input: s = "5F3Z-2e-9-w", k = 4 Output: "5F3Z-2E9W"

Constraints:

1 <= s.length <= 10^5

2 <= k <= 10^4

Code and Explanation

Optimal

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        chars = [ch.upper() for ch in s if ch != '-']
        n = len(chars)
        if n == 0:
            return ""
        first_len = n % k or k
        parts = [''.join(chars[:first_len])]
        for i in range(first_len, n, k):
            parts.append(''.join(chars[i:i + k]))
        return '-'.join(parts)

Explanation:

Remove dashes and uppercase all characters.
The first group may be shorter when length is not divisible by k.
Join remaining groups of size k with dashes.

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

17. Longest Harmonious Subsequence (Leetcode:594)#

Problem Statement

A harmonious array has a difference of exactly 1 between its maximum and minimum values. Given an integer array nums, return the length of its longest harmonious subsequence.

Example 1:

Input: nums = [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Constraints:

1 <= nums.length <= 2 * 10^4

Code and Explanation

Optimal

class Solution:
    def findLHS(self, nums: list[int]) -> int:
        counts: dict[int, int] = {}
        for num in nums:
            counts[num] = counts.get(num, 0) + 1
        best = 0
        for num, count in counts.items():
            if num + 1 in counts:
                best = max(best, count + counts[num + 1])
        return best

Explanation:

Count frequency of each value.
For each value x, check whether x + 1 also appears.
A harmonious subsequence uses all copies of both consecutive values.

18. Longest Palindrome (Leetcode:409)#

Problem Statement

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Example 1:

Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome is "dccaccd" with length 7.

Constraints:

1 <= s.length <= 2000

s consists of lowercase and/or uppercase English letters only.

Code and Explanation

Optimal

class Solution:
    def longestPalindrome(self, s: str) -> int:
        counts: dict[str, int] = {}
        for ch in s:
            counts[ch] = counts.get(ch, 0) + 1
        length = 0
        odd = False
        for count in counts.values():
            length += count // 2 * 2
            odd = odd or count % 2 == 1
        return length + (1 if odd else 0)

Explanation:

Count character frequencies.
Each character pair contributes 2 to the palindrome length.
At most one odd-count character can sit in the center.

19. Longest Uncommon Subsequence I (Leetcode:521)#

Problem Statement

Given two strings a and b, return the length of the longest uncommon subsequence between them. If no uncommon subsequence exists, return -1.

Example 1:

Input: a = "aba", b = "cdc" Output: 3

Constraints:

1 <= a.length, b.length <= 50

Code and Explanation

Optimal

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        if a == b:
            return -1
        return max(len(a), len(b))

Explanation:

If the strings are equal, every subsequence of one appears in the other.
If they differ, the longer entire string cannot be a subsequence of the other.
Return the length of the longer string, or -1 when equal.

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

21. Max Consecutive Ones (Leetcode:485)#

Problem Statement

Given a binary array nums, return the maximum number of consecutive 1s in the array.

Example 1:

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

Constraints:

1 <= nums.length <= 10^5

nums[i] is either 0 or 1.

Code and Explanation

Optimal

class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        best = current = 0
        for num in nums:
            if num == 1:
                current += 1
                best = max(best, current)
            else:
                current = 0
        return best

Explanation:

Track the current streak of consecutive ones.
Reset the streak when a zero appears.
Keep the maximum streak seen.

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

23. Minimum Index Sum of Two Lists (Leetcode:599)#

Problem Statement

Given two lists of strings list1 and list2, return the common strings with the least index sum.

Example 1:

Input: list1 = ["Shogun","Tapioca Bubble","Ninja","Frog"], list2 = ["Frog","Shogun","Tapioca Bubble"] Output: ["Shogun","Tapioca Bubble"]

Constraints:

1 <= list1.length, list2.length <= 1000

Code and Explanation

Optimal

class Solution:
    def findRestaurant(self, list1: list[str], list2: list[str]) -> list[str]:
        index1 = {name: i for i, name in enumerate(list1)}
        best = float('inf')
        result: list[str] = []
        for j, name in enumerate(list2):
            if name in index1:
                total = index1[name] + j
                if total < best:
                    best = total
                    result = [name]
                elif total == best:
                    result.append(name)
        return result

Explanation:

Map each restaurant in list1 to its index.
Scan list2 and compute index sums for common names.
Keep only names achieving the minimum index sum.

24. Move Zeroes (Leetcode:283)#

Problem Statement

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

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

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

Constraints:

1 <= nums.length <= 104

-231 <= nums[i] <= 231 - 1

Follow up: Could you minimize the total number of operations done?

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def moveZeroes(self, nums: List[int]) -> None:
            """
            Do not return anything, modify nums in-place instead.
            """
            slow = 0
            for fast in range(len(nums)):

                if nums[fast] != 0 and nums[slow] == 0:
                    nums[slow], nums[fast] = nums[fast], nums[slow]

                if nums[slow] != 0:
                    slow += 1
    ```
    **Explanation:**

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

25. Number of Segments in a String (Leetcode:434)#

Problem Statement

Given a string s, return the number of segments in the string.

A segment is defined as a contiguous sequence of non-space characters.

Example 1:

Input: s = "Hello, my name is John" Output: 5

Constraints:

0 <= s.length <= 300

s consists of printable ASCII characters.

Code and Explanation

Optimal

class Solution:
    def countSegments(self, s: str) -> int:
        return len(s.split())

Explanation:

Split the string on whitespace.
Each non-empty token is one segment.
Return the number of tokens.

26. Pascal's Triangle (Leetcode:118)#

Problem Statement

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] Example 2:

Input: numRows = 1 Output: [[1]]

Constraints:

1 <= numRows <= 30

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def generate(self, rowIndex) -> List[List[int]]:
            if rowIndex == 0:
                return [[1]]
            else:
                return self.getAllRow(rowIndex - 1)

        def getAllRow(self, rowIndex):
            if rowIndex == 0:
                return [[1]]
            ListPrec = self.getAllRow(rowIndex - 1)
            Len = len(ListPrec[-1])
            ListPrec.append([1])
            for i in range(0, Len - 1):
                ListPrec[-1].append(ListPrec[-2][i] + ListPrec[-2][i + 1])
            ListPrec[-1].append(1)
            return ListPrec
    ```
    **Explanation:**

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

27. Pascal's Triangle II (Leetcode:119)#

Problem Statement

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: rowIndex = 3 Output: [1,3,3,1] Example 2:

Input: rowIndex = 0 Output: [1] Example 3:

Input: rowIndex = 1 Output: [1,1]

Constraints:

0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        Memo = {}

        def getRow(self, rowIndex: int) -> List[int]:
            if rowIndex in self.Memo:
                return self.Memo[rowIndex]
            if rowIndex == 0:
                return [1]
            ListPrec = self.getRow(rowIndex - 1)
            Result = [1]
            for i in range(0, len(ListPrec) - 1):
                Result.append(ListPrec[i] + ListPrec[i + 1])
            Result.append(1)
            self.Memo[rowIndex] = Result
            return Result
    ```
    **Explanation:**

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

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

Prefix & Suffix Product

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:

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

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

30. Relative Ranks (Leetcode:506)#

Problem Statement

You are given an integer array score of size n, where score[i] is the score of the ith athlete. Return a string array answer where answer[i] is the rank of the ith athlete.

Example 1:

Input: score = [5,4,3,2,1] Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]

Constraints:

n == score.length

1 <= n <= 10^4

Code and Explanation

Optimal

class Solution:
    def findRelativeRanks(self, score: list[int]) -> list[str]:
        indexed = sorted((s, i) for i, s in enumerate(score), reverse=True)
        answer = [''] * len(score)
        medals = {0: 'Gold Medal', 1: 'Silver Medal', 2: 'Bronze Medal'}
        for rank, (_, i) in enumerate(indexed):
            answer[i] = medals.get(rank, str(rank + 1))
        return answer

Explanation:

Sort scores with original indices in descending order.
Assign medal labels to ranks 0, 1, and 2.
Place numeric ranks for all remaining positions.

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

Optimal

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:

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

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

33. Repeated Substring Pattern (Leetcode:459)#

Problem Statement

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Example 1:

Input: s = "abab" Output: true Explanation: It is the substring "ab" twice.

Example 2:

Input: s = "aba" Output: false

Example 3:

Input: s = "abcabcabcabc" Output: true Explanation: It is the substring "abc" four times or the substring "abcabc" twice.

Constraints:

1 <= s.length <= 104

s consists of lowercase English letters.

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def repeatedSubstringPattern(self, s: str) -> bool:
            return s in (s + s)[1:-1]
    ```
    **Explanation:**

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

34. Reverse String II (Leetcode:541)#

Problem Statement

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

Example 1:

Input: s = "abcdefg", k = 2 Output: "bacdfeg"

Constraints:

1 <= s.length <= 10^4

s consists of lowercase English letters.

Code and Explanation

Optimal

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        chars = list(s)
        for i in range(0, len(chars), 2 * k):
            chars[i:i + k] = reversed(chars[i:i + k])
        return ''.join(chars)

Explanation:

Process the string in blocks of size 2k.
Reverse only the first k characters of each block.
Join characters back into a string.

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

36. Set Mismatch (Leetcode:645)#

Also in DSA Patterns

Set Mismatch — 05. Cyclic Sort (may include extra approaches and complexity analysis).

Problem Statement

One number from 1..n was duplicated and another is missing. Return [duplicate, missing].

Example 1:

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

Code and Explanation

Optimal

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

Explanation:

Walk through the approach in the code above.

37. Sort Colors (Leetcode:75)#

Also in DSA Patterns

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

Problem Statement

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.

Example 1:

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

Example 2:

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

Constraints:

n == nums.length 1 <= n <= 300 nums[i] is either 0, 1, or 2.

Follow Up: Could you come up with a one-pass algorithm using only constant extra space?

Code and Explanation

Optimal

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low, mid, high = 0, 0, len(nums) - 1

        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

Explanation:

Dutch National Flag: three pointers partition 0, 1, and 2 in one pass.
0: swap to the low region and advance both low and mid.
1: already in the middle region — advance mid.
2: swap to the high region and shrink high.
Time complexity: O(n)
Space complexity: O(1)

38. String to Integer (atoi) (Leetcode:8)#

Problem Statement

Implement myAtoi(string s) which converts a string to a 32-bit signed integer (similar to C's atoi).

The algorithm for myAtoi(string s) is as follows: 1. Read in and ignore any leading whitespace. 2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. 3. Read in next the characters until the next non-digit character or the end of the input is reached. Interpret these digits as an integer. 4. Clamp the integer if it is less than -2^31 or greater than 2^31 - 1.

Example 1:

Input: s = "42" Output: 42

Constraints:

0 <= s.length <= 200

s consists of English letters, digits, '+', '-', and ' '.

Code and Explanation

Optimal

class Solution:
    def myAtoi(self, s: str) -> int:
        i, n = 0, len(s)
        while i < n and s[i] == ' ':
            i += 1
        sign = 1
        if i < n and s[i] in '+-':
            sign = -1 if s[i] == '-' else 1
            i += 1
        result = 0
        while i < n and s[i].isdigit():
            result = result * 10 + int(s[i])
            i += 1
        result *= sign
        return max(-2**31, min(2**31 - 1, result))

Explanation:

Skip leading whitespace, then read an optional sign.
Accumulate digits until a non-digit is seen.
Apply sign and clamp to 32-bit signed integer range.

39. Student Attendance Record I (Leetcode:551)#

Problem Statement

You are given a string s representing an attendance record where 'A' means absent, 'L' means late, and 'P' means present. Return true if the record is acceptable.

Example 1:

Input: s = "PPALLP" Output: true

Constraints:

1 <= s.length <= 1000

s[i] is 'A', 'L', or 'P'.

Code and Explanation

Optimal

class Solution:
    def checkRecord(self, s: str) -> bool:
        return s.count('A') < 2 and 'LLL' not in s

Explanation:

A record is invalid if there are two or more absences.
It is also invalid if three consecutive lates appear.
Check both conditions directly on the string.

40. Third Maximum Number (Leetcode:414)#

Problem Statement

Given an integer array nums, return the third distinct maximum number in the array. If it does not exist, return the maximum number.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 10^4

Code and Explanation

Optimal

class Solution:
    def thirdMax(self, nums: list[int]) -> int:
        first = second = third = float('-inf')
        for num in nums:
            if num in (first, second, third):
                continue
            if num > first:
                third, second, first = second, first, num
            elif num > second:
                third, second = second, num
            elif num > third:
                third = num
        return int(third) if third != float('-inf') else int(first)

Explanation:

Track the three largest distinct values while scanning.
Skip duplicates without updating the top three.
If fewer than three distinct values exist, return the maximum.

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

Hash Map (Optimal)Two Pointers (Sorted)

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:

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

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:

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

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

Character Counter (Optimal)Sort + Compare

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:

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

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

Explanation:

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

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

Backtracking#

44. Binary Watch (Leetcode:401)#

Problem Statement

A binary watch has 4 LEDs for hours (0-11) and 6 LEDs for minutes (0-59). Given an integer turnedOn representing the number of LEDs that are on, return all possible times the watch could represent.

Example 1:

Input: turnedOn = 1 Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Constraints:

0 <= turnedOn <= 10

Code and Explanation

Optimal

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> list[str]:
        def count_bits(x: int) -> int:
            return bin(x).count('1')

        result: list[str] = []
        for h in range(12):
            for m in range(60):
                if count_bits(h) + count_bits(m) == turnedOn:
                    result.append(f"{h}:{m:02d}")
        return result

Explanation:

Try every valid hour (0-11) and minute (0-59) combination.
Count set bits in hour and minute; keep pairs whose sum equals turnedOn.
Format minutes with two digits.

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

Backtracking

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:

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

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

Optimal

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:

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

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

Optimal

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:

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

48. Subsets (Leetcode:78)#

Also in DSA Patterns

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

Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 10

-10 <= nums[i] <= 10

All the numbers of nums are unique.

Code and Explanation

Optimal

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        subset = []

        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return
            # decision to include nums[i]
            subset.append(nums[i])
            dfs(i + 1)
            # decision NOT to include nums[i]
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res

Explanation:

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

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

Backtracking DFS

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:

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

Binary Search#

50. Arranging Coins (Leetcode:441)#

Problem Statement

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

Example 1:

Input: n = 5 Output: 2 Explanation: Because the 3rd row is incomplete, we return 2.

Example 2:

Input: n = 8 Output: 3 Explanation: Because the 4th row is incomplete, we return 3.

Constraints:

1 <= n <= 231 - 1

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def arrangeCoins(self, n: int) -> int:
            l, r = 1, n
            res = 0
            while l <=r:
                mid = (l+r)//2
                coins = (mid /2) * (mid+1)
                if coins > n:
                    r = mid - 1
                else:
                    l = mid + 1
                    res = max(mid, res)
            return res
    ```
    **Explanation:**

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

51. Binary Search (Leetcode:704)#

Also in DSA Patterns

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

Problem Statement

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

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

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 104

-104 < nums[i], target < 104

All the integers in nums are unique.

nums is sorted in ascending order.

Code and Explanation

Optimal

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            m = l + ((r - l) // 2)  # (l + r) // 2 can lead to overflow
            if nums[m] > target:
                r = m - 1
            elif nums[m] < target:
                l = m + 1
            else:
                return m
        return -1

Explanation:

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

52. First Bad Version (Leetcode:278)#

Also in DSA Patterns

First Bad Version — 09. Binary Search (may include extra approaches and complexity analysis).

Problem Statement

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4 Output: 4 Explanation: call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1 Output: 1

Constraints:

1 <= bad <= n <= 231 - 1

Code and Explanation

Optimal

class Solution:
    def firstBadVersion(self, n: int) -> int:
        l, r = 1, n
        while l < r:
            v = (l + r) // 2
            if isBadVersion(v):
                r = v
            else:
                l = v + 1
        return l

Explanation:

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

53. Guess Number Higher or Lower (Leetcode:374)#

Problem Statement

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked (the number I picked stays the same throughout the game).

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

-1: Your guess is higher than the number I picked (i.e. num > pick).

1: Your guess is lower than the number I picked (i.e. num < pick).

0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.

Example 1:

Input: n = 10, pick = 6 Output: 6

Example 2:

Input: n = 1, pick = 1 Output: 1

Example 3:

Input: n = 2, pick = 1 Output: 1

Constraints:

1 <= n <= 231 - 1

1 <= pick <= n

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def guessNumber(self, n: int) -> int:
            # return a num btw 1,..,n

            low = 1
            high = n

            while True:
                mid = low + (high - low) // 2
                myGuess = guess(mid)
                if myGuess == 1:
                    low = mid + 1
                elif myGuess == -1:
                    high = mid - 1
                else:
                    return mid
    ```
    **Explanation:**

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

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

Optimal

# 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:

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

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

Binary Search

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:

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

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

Optimal

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:

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

57. Valid Perfect Square (Leetcode:367)#

Also in DSA Patterns

Valid Perfect Square — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Follow up: Do not use any built-in library function such as sqrt.

Example 1:

Input: num = 16
Output: true

Example 2:

Input: num = 14
Output: false

Constraints:

1 <= num <= 2^31 - 1

Code and Explanation

Optimal

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        for i in range(1, num+1):
            if i * i == num:
                return True
            if i* i > num:
                return False



    def isPerfectSquare_2(self, num: int) -> bool:
        l ,r = 1, num
        while l <= r:
            mid = (l +r) // 2
            if mid * mid > num:
                r = mid - 1
            elif mid * mid < num:
                l = mid + 1
            else:
                return True
        return False

Explanation:

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

Bit Manipulation#

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

59. Counting Bits (Leetcode:338)#

Also in DSA Patterns

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

Problem Statement

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1s in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]

Constraints:

0 <= n <= 10^5

Code and Explanation

Dynamic Programming (Bits)

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        offset = 1

        for i in range(1, n + 1):
            if offset * 2 == i:
                offset = i
            dp[i] = 1 + dp[i - offset]
        return dp

# Another dp solution
class Solution2:
    def countBits(self, n: int) -> List[int]:
        res = [0] * (n + 1)
        for i in range(1, n + 1):
            if i % 2 == 1:
                res[i] = res[i - 1] + 1
            else:
                res[i] = res[i // 2]
        return res
# This solution is based on the division of odd and even numbers. 
# I think it's easier to understand.
# This is my full solution, covering the details: https://leetcode.com/problems/counting-bits/solutions/4411054/odd-and-even-numbers-a-easier-to-understanding-way-of-dp/

Explanation:

Base case: dp[0] = 0.
Even i: dp[i] = dp[i >> 1] — same bit count as i/2.
Odd i: dp[i] = dp[i >> 1] + 1 — one extra bit vs i/2.
Build table 0..n: O(n) time, O(n) space.
Time complexity: O(n)
Space complexity: O(n)

60. Missing Number (Leetcode:268)#

Also in DSA Patterns

Missing Number — 05. Cyclic Sort (may include extra approaches and complexity analysis).

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

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

Constraints:

n == nums.length, 1 <= n <= 10^4, 0 <= nums[i] <= n, all unique.

Code and Explanation

Gauss Sum FormulaXOR (Optimal)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums)

        for i in range(len(nums)):
            res += i - nums[i]
        return res

Explanation:

Expected sum: Numbers 0..n sum to n*(n+1)/2.
Actual sum: Add all elements in nums.
Missing value: Difference between expected and actual.
Time complexity: O(n)
Space complexity: O(1)

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        result = len(nums)
        for i, num in enumerate(nums):
            result ^= i ^ num
        return result

Explanation:

XOR all indices 0..n with all array values.
Pairs cancel: Duplicate index/value pairs XOR to 0.
Remaining value: The missing number.
Time complexity: O(n)
Space complexity: O(1)

61. Number Complement (Leetcode:476)#

Problem Statement

The complement of an integer is the integer you get when you flip all the 0s to 1s and all the 1s to 0s in its binary representation.

Example 1:

Input: num = 5 Output: 2 Explanation: 5 is "101" in binary; its complement is "010" = 2.

Constraints:

1 <= num < 2^31

Code and Explanation

Optimal

class Solution:
    def findComplement(self, num: int) -> int:
        mask = (1 << num.bit_length()) - 1
        return num ^ mask

Explanation:

Build a mask with the same bit width as num.
XOR num with the mask to flip every bit.
bit_length() handles the width without leading zeros.

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

Bit ShiftingBrian Kernighan's Algorithm (Optimal)

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count

Explanation:

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

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count

Explanation:

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

63. Power of Two (Leetcode:231)#

Also in DSA Patterns

Power of Two — 06. Bit Manipulation (may include extra approaches and complexity analysis).

Problem Statement

Given an integer n, return true if it is a power of two. Otherwise, return false.

Example 1:

Input: n = 1
Output: true

Example 2:

Input: n = 16
Output: true

Example 3:

Input: n = 3
Output: false

Constraints:

-2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

Code and Explanation

Optimal

# iterative
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        x = 1
        while x < n:
            x *= 2
        return x == n        

# Bit manipulation
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0

# Bit manipulation
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and ((1 << 30) % n) == 0

Explanation:

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

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

Bit Reversal

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for _ in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result

Explanation:

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

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

Optimal

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for n in nums:
            res = n ^ res
        return res

Explanation:

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

Design#

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

Two Heaps

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:

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

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

Optimal

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:

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

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

Optimal

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:

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

69. Serialize and Deserialize Binary Tree (Leetcode:297)#

Also in DSA Patterns

Serialize and Deserialize Binary Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example 1:

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

Constraints:

The number of nodes is in the range [0, 10^4]

-1000 <= Node.val <= 1000

Code and Explanation

Preorder Serialization

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Codec:
    def serialize(self, root):
        res = []

        def dfs(node):
            if not node:
                res.append("N")
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(res)

    def deserialize(self, data):
        vals = data.split(",")

        def dfs():
            val = vals.pop(0)
            if val == "N":
                return None
            node = TreeNode(val=int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()

Explanation:

Preorder with 'N' for null encodes structure + values.
Deserialize reads tokens in same order recursively.
Iterator ensures correct node sequence.
Time complexity: O(n)
Space complexity: O(n)

70. Time Based Key-Value Store (Leetcode:981)#

Also in DSA Patterns

Time Based Key-Value Store — 22. Challenge Yourself (may include extra approaches and complexity analysis).

Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Example 1:

Input: ["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output: [null, null, "bar", "bar", null, "bar2", "bar2"]

Constraints:

1 <= key.length, value.length <= 100

key and value consist of lowercase English letters and digits.

1 <= timestamp <= 107

All timestamps of set are strictly increasing.

At most 2 * 105 calls will be made to set and get.

Patterns: Hash Map · Binary Search

Code and Explanation

Optimal

class TimeMap:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.keyStore = {}  # key : list of [val, timestamp]

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.keyStore:
            self.keyStore[key] = []
        self.keyStore[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        res, values = "", self.keyStore.get(key, [])
        l, r = 0, len(values) - 1
        while l <= r:
            m = (l + r) // 2
            if values[m][1] <= timestamp:
                res = values[m][0]
                l = m + 1
            else:
                r = m - 1
        return res

Explanation:

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

Divide & Conquer#

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

Optimal

# 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:

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

Dynamic Programming#

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

One Pass

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:

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

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

Space-Optimized DP (Optimal)Top-Down Memoization

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:

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

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:

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

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

Bottom-Up DP (Optimal)Top-Down Memoization

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:

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

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:

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

75. Fibonacci Number (Leetcode:509)#

Also in DSA Patterns

Fibonacci Number with Memoization — 11. Divide and Conquer (may include extra approaches and complexity analysis).

Problem Statement

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

0 <= n <= 30

Code and Explanation

Optimal

class Solution:
    Memo = {}

    def fib(self, n: int):
        if n in self.Memo:
            return self.Memo[n]
        if n == 0:
            return 0
        if n == 1:
            return 1
        self.Memo[n] = self.fib(n - 1) + self.fib(n - 2)
        return self.Memo[n]

Explanation:

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

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

Expand Around Center (Optimal)2D Dynamic Programming

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:

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

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:

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

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

Kadane's Algorithm (Optimal)Divide and Conquer

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:

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

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:

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

78. Partition Equal Subset Sum (Leetcode:416)#

Also in DSA Patterns

Partition Equal Subset Sum — 12. Backtracking (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

1 <= nums.length <= 200

1 <= nums[i] <= 100

Code and Explanation

Optimal

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2:
            return False

        dp = set()
        dp.add(0)
        target = sum(nums) // 2

        for i in range(len(nums) - 1, -1, -1):
            nextDP = set()
            for t in dp:
                if (t + nums[i]) == target:
                    return True
                nextDP.add(t + nums[i])
                nextDP.add(t)
            dp = nextDP
        return False

Explanation:

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

79. Unique Paths (Leetcode:62)#

Also in DSA Patterns

Unique Paths in Grid — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

There is a robot on an m x n grid. The robot is initially at the top-left corner and tries to move to the bottom-right corner. The robot can only move down or right. How many unique paths are there?

Example 1:

Input: m = 3, n = 7 Output: 28

Constraints:

1 <= m, n <= 100

Code and Explanation

Combinatorics DP

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n

        for i in range(m - 1):
            newRow = [1] * n
            for j in range(n - 2, -1, -1):
                newRow[j] = newRow[j + 1] + row[j]
            row = newRow
        return row[0]

        # O(n * m) O(n)

Explanation:

Grid DP: dp[r][c] = paths to cell (r,c).
Only from top or left: dp[r][c] = dp[r-1][c] + dp[r][c-1].
First row/column: Only one way along edges.
Math alternative: C((m-1)+(n-1), m-1) also works.
Time complexity: O(m × n)
Space complexity: O(n)

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

Dynamic Programming (Optimal)BFS

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:

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

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:

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

Graphs#

81. 01 Matrix (Leetcode:542)#

Problem Statement

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]]

Constraints:

m == mat.length

n == mat[i].length

1 <= m, n <= 10^4

Code and Explanation

Optimal

class Solution:
    def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
        from collections import deque
        m, n = len(mat), len(mat[0])
        dist = [[10**9] * n for _ in range(m)]
        queue: deque[tuple[int, int]] = deque()
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dist[i][j] = 0
                    queue.append((i, j))
        while queue:
            i, j = queue.popleft()
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    queue.append((ni, nj))
        return dist

Explanation:

Multi-source BFS starting from every cell that is already 0.
Propagate distances layer by layer to all four neighbors.
Each cell stores its shortest Manhattan distance to a zero.

82. Accounts Merge (Leetcode:721)#

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

Optimal

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [1] * n

    def find(self, x):
        while x != self.par[x]:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x

    def union(self, x1, x2):
        p1, p2 = self.find(x1), self.find(x2)
        if p1 == p2:
            return False
        if self.rank[p1] > self.rank[p2]:
            self.par[p2] = p1
            self.rank[p1] += self.rank[p2]
        else:
            self.par[p1] = p2
            self.rank[p2] += self.rank[p1]
        return True

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        uf = UnionFind(len(accounts))
        emailToAcc = {} # email -> index of acc

        for i, a in enumerate(accounts):
            for e in a[1:]:
                if e in emailToAcc:
                    uf.union(i, emailToAcc[e])
                else:
                    emailToAcc[e] = i

        emailGroup = defaultdict(list) # index of acc -> list of emails
        for e, i in emailToAcc.items():
            leader = uf.find(i)
            emailGroup[leader].append(e)

        res = []
        for i, emails in emailGroup.items():
            name = accounts[i][0]
            res.append([name] + sorted(emailGroup[i])) # array concat
        return res

Explanation:

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

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

DFS + Hash Map (Optimal)BFS

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:

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

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:

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

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

Kahn's Algorithm (BFS) (Optimal)DFS Cycle Detection

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:

Build graph and indegree: Edge prereq -> course.
Start with indegree 0 courses in a queue.
Pop course, reduce indegree of neighbors: If indegree hits 0, enqueue.
No cycle iff all courses processed. O(V+E).
Time complexity: O(V + E)
Space complexity: O(V + E)

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:

Adjacency list: Store prerequisites per course.
Three states: unvisited, visiting, done.
Back edge = cycle: Revisit a visiting node.
All nodes finish without cycle → true.
Time complexity: O(V + E)
Space complexity: O(V + E)

85. Flood Fill (Leetcode:733)#

Problem Statement

You are given an image represented by an m x n grid of integers and three integers sr, sc, and color. Perform a flood fill starting from (sr, sc).

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Output: [[2,2,2],[2,2,0],[2,0,1]]

Constraints:

m == image.length

n == image[i].length

1 <= m, n <= 50

Code and Explanation

Optimal

class Solution:
    def floodFill(self, image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
        original = image[sr][sc]
        if original == color:
            return image
        stack = [(sr, sc)]
        while stack:
            r, c = stack.pop()
            if image[r][c] != original:
                continue
            image[r][c] = color
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < len(image) and 0 <= nc < len(image[0]) and image[nr][nc] == original:
                    stack.append((nr, nc))
        return image

Explanation:

If the starting color already equals the new color, return early.
DFS or stack-based fill all connected cells with the original color.
Recolor each visited cell and push valid same-color neighbors.

86. Island Perimeter (Leetcode:463)#

Problem Statement

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16 Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:

Input: grid = [[1]] Output: 4

Example 3:

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

Constraints:

row == grid.length

col == grid[i].length

1 <= row, col <= 100

grid[i][j] is 0 or 1.

There is exactly one island in grid.

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def islandPerimeter(self, grid: List[List[int]]) -> int:
            visit = set()

            def dfs(i, j):
                if i >= len(grid) or j >= len(grid[0]) or i < 0 or j < 0 or grid[i][j] == 0:
                    return 1
                if (i, j) in visit:
                    return 0

                visit.add((i, j))
                perim = dfs(i, j + 1)
                perim += dfs(i + 1, j)
                perim += dfs(i, j - 1)
                perim += dfs(i - 1, j)
                return perim

            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j]:
                        return dfs(i, j)
    ```
    **Explanation:**

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

87. Minimum Height Trees (Leetcode:310)#

Problem Statement

A tree is an undirected graph with n nodes labeled from 0 to n - 1. Given n and a list of edges, return all root labels that yield minimum height trees (MHTs).

Example 1:

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] Output: [3,4]

Constraints:

1 <= n <= 2 * 10^4

Code and Explanation

Optimal

class Solution:
    def findMinHeightTrees(self, n: int, edges: list[list[int]]) -> list[int]:
        if n <= 2:
            return list(range(n))
        degree = [0] * n
        graph: list[list[int]] = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
            degree[u] += 1
            degree[v] += 1
        leaves = [i for i in range(n) if degree[i] == 1]
        remaining = n
        while remaining > 2:
            remaining -= len(leaves)
            new_leaves: list[int] = []
            for leaf in leaves:
                for nei in graph[leaf]:
                    degree[nei] -= 1
                    if degree[nei] == 1:
                        new_leaves.append(nei)
            leaves = new_leaves
        return leaves

Explanation:

Build adjacency lists and track node degrees.
Repeatedly remove all current leaves like peeling layers off the tree.
The last one or two nodes remaining are valid MHT roots.

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

Depth-First Search (Optimal)Breadth-First Search

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:

Scan grid: Each unvisited '1' starts a new island.
DFS flood fill: Mark visited by flipping to '0'.
Explore 4 directions recursively.
Count DFS launches. O(mn) time.
Time complexity: O(m × n)
Space complexity: O(m × n)

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:

Same outer scan as DFS for new land cells.
Queue flood fill: Process cells layer by layer.
Mark visited on enqueue to avoid duplicates.
Equivalent result, iterative traversal.
Time complexity: O(m × n)
Space complexity: O(m × n)

89. Rotting Oranges (Leetcode:994)#

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

Optimal

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        q = collections.deque()
        fresh = 0
        time = 0

        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    fresh += 1
                if grid[r][c] == 2:
                    q.append((r, c))

        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        while fresh > 0 and q:
            length = len(q)
            for i in range(length):
                r, c = q.popleft()

                for dr, dc in directions:
                    row, col = r + dr, c + dc
                    # if in bounds and nonrotten, make rotten
                    # and add to q
                    if (
                        row in range(len(grid))
                        and col in range(len(grid[0]))
                        and grid[row][col] == 1
                    ):
                        grid[row][col] = 2
                        q.append((row, col))
                        fresh -= 1
            time += 1
        return time if fresh == 0 else -1

Explanation:

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

Greedy#

90. Assign Cookies (Leetcode:455)#

Also in DSA Patterns

Assign Cookies — 10. Greedy Algorithm (may include extra approaches and complexity analysis).

Problem Statement

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:

Input: g = [1,2,3], s = [1,1] Output: 1 Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1.

Example 2:

Input: g = [1,2], s = [1,2,3] Output: 2 Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. You have 3 cookies and their sizes are big enough to gratify all of the children, You need to output 2.

Constraints:

1 <= g.length <= 3 * 104

0 <= s.length <= 3 * 104

1 <= g[i], s[j] <= 231 - 1 Note: This question is the same as 2410: Maximum Matching of Players With Trainers.

Code and Explanation

Optimal

class Solution:
    def findContentChildren(self, g: list[int], s: list[int]) -> int:
        g.sort()
        s.sort()
        child = cookie = 0
        while child < len(g) and cookie < len(s):
            if s[cookie] >= g[child]:
                child += 1
            cookie += 1
        return child

Explanation:

Sort both greed factors and cookie sizes.
Try to satisfy the least greedy child with the smallest sufficient cookie.
Advance the cookie pointer always; advance the child pointer only on success.

91. Can Place Flowers (Leetcode:605)#

Problem Statement

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1 Output: true Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2 Output: false

Constraints:

1 <= flowerbed.length <= 2 * 104

flowerbed[i] is 0 or 1.

There are no two adjacent flowers in flowerbed.

0 <= n <= flowerbed.length

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
            # Solution with O(1) space complexity
            empty = 0 if flowerbed[0] else 1

            for f in flowerbed:
               if f:
                   n -= int((empty - 1) / 2)  # int division, round toward zero
                   empty = 0
               else:
                   empty += 1

            n -= (empty) // 2
            return n <= 0

    class Solution2:
        def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
           # Another solution with O(1) space complexity
           for i in range(len(flowerbed)):
                if n == 0:
                    return True
                if ((i == 0 or flowerbed[i - 1] == 0)   # If at the first element or the previous element equals to 0
                    and (flowerbed[i] == 0)             # If current element equals to 0
                    and (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0)): # If at the last element or the next element equals to 0
                    # Place flower at the current position
                    flowerbed[i] = 1
                    n -= 1

           return n == 0

    class Solution3:
        def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
           # Solution with O(n) space complexity
           f = [0] + flowerbed + [0]

           for i in range(1, len(f) - 1):  # skip first & last
               if f[i - 1] == 0 and f[i] == 0 and f[i + 1] == 0:
                   f[i] = 1
                   n -= 1
           return n <= 0
    ```
    **Explanation:**

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

Heap / Priority Queue#

92. K Closest Points to Origin (Leetcode:973)#

Also in DSA Patterns

K Closest Points to Origin — 15. Heaps (may include extra approaches and complexity analysis).

Problem Statement

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:

Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Constraints:

1 <= k <= points.length <= 104

-104 <= xi, yi <= 104

Code and Explanation

Optimal

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        minHeap = []
        for x, y in points:
            dist = (x ** 2) + (y ** 2)
            minHeap.append((dist, x, y))

        heapq.heapify(minHeap)
        res = []
        for _ in range(k):
            _, x, y = heapq.heappop(minHeap)
            res.append((x, y))
        return res

Explanation:

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

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

Min Heap (Optimal)Divide and Conquer

# 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:

Push head of each list onto min-heap.
Pop smallest, append to result, push that node's next.
O(N log k) for total N nodes across k lists.
Time complexity: O(N log k)
Space complexity: O(k)

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:

Repeatedly merge pairs of lists until one remains.
merge_two standard sorted merge.
O(N log k) without heap.
Time complexity: O(N log k)
Space complexity: O(1)

94. Task Scheduler (Leetcode:621)#

Also in DSA Patterns

Task Scheduler — 10. Greedy Algorithm (may include extra approaches and complexity analysis).

Problem Statement

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B. After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1 Output: 6 Explanation: A possible sequence is: A -> B -> C -> D -> A -> B. With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = ["A","A","A", "B","B","B"], n = 3 Output: 10 Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B. There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

1 <= tasks.length <= 104

tasks[i] is an uppercase English letter.

0 <= n <= 100

Code and Explanation

Optimal

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        maxHeap = [-cnt for cnt in count.values()]
        heapq.heapify(maxHeap)

        time = 0
        q = deque()  # pairs of [-cnt, idleTime]
        while maxHeap or q:
            time += 1

            if not maxHeap:
                time = q[0][1]
            else:
                cnt = 1 + heapq.heappop(maxHeap)
                if cnt:
                    q.append([cnt, time + n])
            if q and q[0][1] == time:
                heapq.heappush(maxHeap, q.popleft()[0])
        return time


# Greedy algorithm
class Solution(object):
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counter = collections.Counter(tasks)
        max_count = max(counter.values())
        min_time = (max_count - 1) * (n + 1) + \
                    sum(map(lambda count: count == max_count, counter.values()))

        return max(min_time, len(tasks))

Explanation:

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

Intervals#

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

Linear Merge

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:

Three cases: New interval before, after, or overlapping existing ones.
Build result list: Insert merged interval when overlap region ends.
Single pass through intervals.
O(n) time if intervals already sorted.
Time complexity: O(n)
Space complexity: O(n)

96. Meeting Rooms (Leetcode:252)#

Also in DSA Patterns

Meeting Rooms — 10. Greedy Algorithm (may include extra approaches and complexity analysis).

Problem Statement

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]] Output: false

Constraints:

0 <= intervals.length <= 10^4

intervals[i].length == 2

0 <= starti < endi <= 10^6

Code and Explanation

Sort + Scan

class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: if a person could attend all meetings
    """

    def canAttendMeetings(self, intervals):
        intervals.sort(key=lambda i: i[0])

        for i in range(1, len(intervals)):
            i1 = intervals[i - 1]
            i2 = intervals[i]

            if i1[1] > i2[0]:
                return False
        return True

Explanation:

Sort by meeting start.
Compare adjacent: Overlap if next start < previous end.
Return false on first overlap.
Time complexity: O(n log n)
Space complexity: O(1)

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

Sort + Merge

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:

Sort by start time.
Merge if overlap: If current start <= last end, extend last interval.
Else push new interval.
O(n log n) from sort.
Time complexity: O(n log n)
Space complexity: O(n)

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

Optimal

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:

Scan the sorted array and mark the start of each range.
Extend the range while the next number is consecutive.
Format single values or start->end pairs and move on.

Linked List#

99. Intersection of Two Linked Lists (Leetcode:160)#

Problem Statement

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.

listA - The first linked list.

listB - The second linked list.

skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.

skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 Output: Intersected at '8' Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B. - Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Output: Intersected at '2' Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Output: No intersection Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so return null.

Constraints:

The number of nodes of listA is in the m.

The number of nodes of listB is in the n.

1 <= m, n <= 3 * 104

1 <= Node.val <= 105

0 <= skipA <= m

0 <= skipB <= n

intersectVal is 0 if listA and listB do not intersect.

intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None


    class Solution:
        def getIntersectionNode(
            self, headA: ListNode, headB: ListNode
        ) -> Optional[ListNode]:
            l1, l2 = headA, headB
            while l1 != l2:
                l1 = l1.next if l1 else headB
                l2 = l2.next if l2 else headA
            return l1
    ```
    **Explanation:**

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

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

Floyd's Cycle Detection (Optimal)Hash Set

# 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:

Slow moves 1 step, fast moves 2.
If they meet, cycle exists.
If fast reaches null, no cycle.
O(n) time, O(1) space — optimal.
Time complexity: O(n)
Space complexity: O(1)

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:

Track visited nodes in a set.
Cycle if node seen again.
Simple but O(n) extra space.
Time complexity: O(n)
Space complexity: O(n)

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

Iterative Merge (Optimal)Recursive Merge

# 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:

Dummy head simplifies tail insertion.
Attach smaller head node, advance that list.
Append remainder when one list ends.
Time complexity: O(n + m)
Space complexity: O(1)

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:

Compare heads, attach smaller, recurse on rest.
Base cases for empty lists.
Same O(n) time, uses call stack.
Time complexity: O(n + m)
Space complexity: O(n + m)

102. Middle of the Linked List (Leetcode:876)#

Also in DSA Patterns

Middle of the Linked List — 02. Fast and Slow Pointers (may include extra approaches and complexity analysis).

Problem Statement

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

The number of nodes in the list is in the range [1, 100].
1 <= Node.val <= 100

Code and Explanation

Optimal

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next

        return slow

Explanation:

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

103. Palindrome Linked List (Leetcode:234)#

Also in DSA Patterns

Palindrome Linked List — 02. Fast and Slow Pointers (may include extra approaches and complexity analysis).

Problem Statement

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 9

Code and Explanation

Optimal

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        fast = head
        slow = head

        # find the middle (slow)
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # reverse second half
        prev = None
        while slow:
            tmp = slow.next
            slow.next = prev
            prev = slow
            slow = tmp

        # check palindrome
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

Explanation:

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

104. Remove Duplicates from Sorted List (Leetcode:83)#

Problem Statement

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:

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

Example 2:

Input: head = [1,1,2,3,3] Output: [1,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

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
            cur = head
            while cur:
                while cur.next and cur.next.val == cur.val:
                    cur.next = cur.next.next
                cur = cur.next
            return head
    ```
    **Explanation:**

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

105. Remove Linked List Elements (Leetcode:203)#

Also in DSA Patterns

Remove Linked List Elements — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

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

Example 2:

Input: head = [], val = 1 Output: []

Example 3:

Input: head = [7,7,7,7], val = 7 Output: []

Constraints:

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

1 <= Node.val <= 50

0 <= val <= 50

Code and Explanation

Optimal

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(next=head)
        prev, curr = dummy, head

        while curr:
            nxt = curr.next

            if curr.val == val:
                prev.next = nxt
            else:
                prev = curr

            curr = nxt
        return dummy.next

Explanation:

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

106. Reverse Linked List (Leetcode:206)#

Also in DSA Patterns

Reverse Linked List — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

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

Example 2:

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

Example 3:

Input: head = [] Output: []

Constraints:

The number of nodes in the list is the range [0, 5000].

-5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Code and Explanation

Iterative Reversal (Optimal)Recursive Reversal

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head

        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

Explanation:

Three pointers: prev, curr, next.
Reverse link: Point curr.next to prev, shift all forward.
Return prev as new head.
O(n) time, O(1) space.
Time complexity: O(n)
Space complexity: O(1)

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

Explanation:

Base: Empty or single node returns itself.
Recurse on tail, then point tail back to current.
Clear current.next.
O(n) time, O(n) stack space.
Time complexity: O(n)
Space complexity: O(n)

Math & Geometry#

107. Add Strings (Leetcode:415)#

Problem Statement

Given two non-negative integers num1 and num2 represented as strings, return the sum of num1 and num2 as a string.

Example 1:

Input: num1 = "11", num2 = "123" Output: "134"

Constraints:

1 <= num1.length, num2.length <= 10^4

num1 and num2 consist of only digits.

Code and Explanation

Optimal

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i, j = len(num1) - 1, len(num2) - 1
        carry = 0
        digits: list[str] = []
        while i >= 0 or j >= 0 or carry:
            d1 = int(num1[i]) if i >= 0 else 0
            d2 = int(num2[j]) if j >= 0 else 0
            total = d1 + d2 + carry
            digits.append(str(total % 10))
            carry = total // 10
            i -= 1
            j -= 1
        return ''.join(reversed(digits))

Explanation:

Add digits from right to left like grade-school addition.
Track carry and append each result digit.
Reverse the collected digits to form the final string.

108. Base 7 (Leetcode:504)#

Problem Statement

Given an integer num, return a string representing its base 7 representation.

Example 1:

Input: num = 100 Output: "202"

Constraints:

-10^7 <= num <= 10^7

Code and Explanation

Optimal

class Solution:
    def convertToBase7(self, num: int) -> str:
        if num == 0:
            return "0"
        if num < 0:
            return '-' + self.convertToBase7(-num)
        digits: list[str] = []
        while num:
            digits.append(str(num % 7))
            num //= 7
        return ''.join(reversed(digits))

Explanation:

Handle zero and negative numbers separately.
Repeatedly take remainder modulo 7 and divide by 7.
Reverse collected digits to form the base-7 string.

109. Construct the Rectangle (Leetcode:492)#

Problem Statement

A web developer needs to construct a rectangle with area area. Return an array [L, W] such that L * W = area, L >= W, and the difference L - W is minimized.

Example 1:

Input: area = 4 Output: [2,2]

Constraints:

1 <= area <= 10^7

Code and Explanation

Optimal

class Solution:
    def constructRectangle(self, area: int) -> list[int]:
        w = int(area ** 0.5)
        while area % w:
            w -= 1
        return [area // w, w]

Explanation:

Start width at the integer square root of area.
Decrease width until it divides area evenly.
Length is area divided by width, giving the closest pair.

110. Excel Sheet Column Number (Leetcode:171)#

Problem Statement

Given a string columnTitle that represents the column title in an Excel sheet, return its corresponding column number.

Example 1:

Input: columnTitle = "AB" Output: 28

Constraints:

1 <= columnTitle.length <= 7

columnTitle consists only of uppercase English letters.

Code and Explanation

Optimal

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        result = 0
        for ch in columnTitle:
            result = result * 26 + (ord(ch) - ord('A') + 1)
        return result

Explanation:

Excel columns use base-26 with digits 1 through 26.
For each character, shift the accumulated value left by one letter position.
Add the current letter's 1-based index to the running total.

111. Excel Sheet Column Title (Leetcode:168)#

Problem Statement

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...

Example 1:

Input: columnNumber = 1 Output: "A"

Example 2:

Input: columnNumber = 28 Output: "AB"

Example 3:

Input: columnNumber = 701 Output: "ZY"

Constraints:

1 <= columnNumber <= 231 - 1

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def convertToTitle(self, columnNumber: int) -> str:
            # Time: O(logn) - Log base 26 of n
            res = ""
            while columnNumber > 0:
                remainder = (columnNumber - 1) % 26
                res += chr(ord('A') + remainder)
                columnNumber = (columnNumber - 1) // 26

            return res[::-1] # reverse output
    ```
    **Explanation:**

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

112. Fizz Buzz (Leetcode:412)#

Problem Statement

Given an integer n, return a string array answer where answer[i] == "FizzBuzz" if i is divisible by 3 and 5, "Fizz" if divisible by 3, "Buzz" if divisible by 5, or str(i) otherwise.

Example 1:

Input: n = 3 Output: ["1","2","Fizz"]

Constraints:

1 <= n <= 10^4

Code and Explanation

Optimal

class Solution:
    def fizzBuzz(self, n: int) -> list[str]:
        result: list[str] = []
        for i in range(1, n + 1):
            if i % 15 == 0:
                result.append("FizzBuzz")
            elif i % 3 == 0:
                result.append("Fizz")
            elif i % 5 == 0:
                result.append("Buzz")
            else:
                result.append(str(i))
        return result

Explanation:

Loop from 1 through n inclusive.
Check divisibility by 15 first, then 3, then 5.
Append the matching label or the number as a string.

113. Maximum Product of Three Numbers (Leetcode:628)#

Problem Statement

Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

Example 1:

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

Example 2:

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

Constraints:

3 <= nums.length <= 10^4

Code and Explanation

Optimal

class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        nums.sort()
        return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])

Explanation:

Sort the array to inspect extreme values easily.
The maximum product is either the three largest numbers.
Or the two smallest (possibly negative) times the largest.

114. Perfect Number (Leetcode:507)#

Problem Statement

A perfect number is a positive integer equal to the sum of its positive divisors excluding itself. Given an integer n, return true if n is a perfect number, otherwise return false.

Example 1:

Input: num = 28 Output: true Explanation: 28 = 1 + 2 + 4 + 7 + 14

Constraints:

1 <= num <= 10^8

Code and Explanation

Optimal

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False
        total = 1
        i = 2
        while i * i <= num:
            if num % i == 0:
                total += i
                if i * i != num:
                    total += num // i
            i += 1
        return total == num

Explanation:

Sum proper divisors up to sqrt(num).
When i divides num, add both i and num // i.
Compare the divisor sum to num.

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

116. Power of Three (Leetcode:326)#

Problem Statement

Given an integer n, return true if it is a power of three. Otherwise, return false.

Example 1:

Input: n = 27 Output: true

Example 2:

Input: n = 0 Output: false

Constraints:

-2^31 <= n <= 2^31 - 1

Code and Explanation

Optimal

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0

Explanation:

3^19 = 1162261467 is the largest power of three within 32-bit signed range.
If n divides this number evenly, n is a power of three.
Also require n > 0 to reject zero and negatives.

117. Range Addition II (Leetcode:598)#

Problem Statement

You are given an m x n matrix initialized with zeros and a list of operations. Each operation [ai, bi] increments all elements in the top-left ai x bi submatrix by 1. Return the number of maximum integers after all operations.

Example 1:

Input: m = 3, n = 3, ops = [[2,2],[3,3]] Output: 4

Constraints:

1 <= m, n <= 4 * 10^4

0 <= ops.length <= 10^4

Code and Explanation

Optimal

class Solution:
    def maxCount(self, m: int, n: int, ops: list[list[int]]) -> int:
        if not ops:
            return m * n
        min_a = min(op[0] for op in ops)
        min_b = min(op[1] for op in ops)
        return min_a * min_b

Explanation:

Every operation adds 1 to the same overlapping top-left region.
The final maximum region is limited by the smallest ai and smallest bi.
Return the area of that intersection, or m * n if there are no ops.

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

Optimal

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:

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

Matrix#

119. Reshape the Matrix (Leetcode:566)#

Problem Statement

Given an m x n matrix mat and two integers r and c, reshape the matrix into an r x c matrix. If reshape is impossible, return the original matrix.

Example 1:

Input: mat = [[1,2],[3,4]], r = 1, c = 4 Output: [[1,2,3,4]]

Constraints:

m == mat.length

n == mat[0].length

1 <= m, n <= 100

Code and Explanation

Optimal

class Solution:
    def matrixReshape(self, mat: list[list[int]], r: int, c: int) -> list[list[int]]:
        m, n = len(mat), len(mat[0])
        if m * n != r * c:
            return mat
        flat = [mat[i][j] for i in range(m) for j in range(n)]
        return [flat[i * c:(i + 1) * c] for i in range(r)]

Explanation:

Return the original matrix if element counts do not match.
Flatten the matrix in row-major order.
Rebuild rows of length c until r rows are formed.

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

Boundary Traversal

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:

Four boundaries: top, bottom, left, right.
Traverse right, down, left, up; shrink bounds.
Stop when bounds cross.
Time complexity: O(m × n)
Space complexity: O(1)

Sliding Window#

121. Find All Anagrams in a String (Leetcode:438)#

Also in DSA Patterns

Find All Anagrams in a String — 03. Sliding Window (may include extra approaches and complexity analysis).

Problem Statement

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2: Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

1 <= s.length, p.length <= 3 * 104

s and p consist of lowercase English letters.

Code and Explanation

Optimal

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:

        startIndex = 0
        pMap, sMap = {}, {}
        res = []

        for char in p:
            pMap[char] = 1 + pMap.get(char, 0)

        for i in range(len(s)):
            sMap[s[i]] = 1 + sMap.get(s[i], 0)

            if i >= len(p) - 1:
                if sMap == pMap:
                    res.append(startIndex)

                # If current character is in sMap, remove it and re-update the map.
                if s[startIndex] in sMap:
                    sMap[s[startIndex]] -= 1
                    if sMap[s[startIndex]] == 0:
                        del sMap[s[startIndex]]
                startIndex += 1

        return res

Explanation:

The window size remains constant throughout the process.
The window moves from the beginning of the sequence to the end, sliding one element at a time.
At each step, the next element is added, and the element that is no longer within the window is removed.
The window expands or contracts depending on certain conditions.
The size of the window is not fixed and can change during traversal.

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

Sliding Window

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:

Expand right, track last index of each char in map.
If duplicate inside window, move left past previous occurrence.
Update max window length each step.
O(n) time.
Time complexity: O(n)
Space complexity: O(min(n, charset))

123. Maximum Average Subarray I (Leetcode:643)#

Also in DSA Patterns

Maximum Average Subarray I — 03. Sliding Window (may include extra approaches and complexity analysis).

Problem Statement

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

n == nums.length
1 <= k <= n <= 10^5
-10^4 <= nums[i] <= 10^4

Code and Explanation

Optimal

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:

The window size remains constant throughout the process.
The window moves from the beginning of the sequence to the end, sliding one element at a time.
At each step, the next element is added, and the element that is no longer within the window is removed.
The window expands or contracts depending on certain conditions.
The size of the window is not fixed and can change during traversal.

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

Optimal

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:

The window size remains constant throughout the process.
The window moves from the beginning of the sequence to the end, sliding one element at a time.
At each step, the next element is added, and the element that is no longer within the window is removed.
The window expands or contracts depending on certain conditions.
The size of the window is not fixed and can change during traversal.

Stack#

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

Optimal

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:

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

126. Implement Queue using Stacks (Leetcode:232)#

Problem Statement

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.

int pop() Removes the element from the front of the queue and returns it.

int peek() Returns the element at the front of the queue.

boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Example 1:

Input ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 1, 1, false]

Explanation MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

Constraints:

1 <= x <= 9

At most 100 calls will be made to push, pop, peek, and empty.

All the calls to pop and peek are valid.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class MyQueue:

        def __init__(self):
            self.append_stack = []
            self.inverted_stack = []

        def push(self, x: int) -> None:
            self.append_stack.append(x)

        def pop(self) -> int:
            if not self.inverted_stack:
                while self.append_stack:
                    self.inverted_stack.append(self.append_stack.pop())
            return self.inverted_stack.pop()

        def peek(self) -> int:
            if not self.inverted_stack:
                while self.append_stack:
                    self.inverted_stack.append(self.append_stack.pop())
            return self.inverted_stack[-1]

        def empty(self) -> bool:
            return not (self.append_stack or self.inverted_stack)
    ```
    **Explanation:**

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

127. Implement Stack using Queues (Leetcode:225)#

Also in DSA Patterns

Implement Stack using Queues — 08. Stack (may include extra approaches and complexity analysis).

Problem Statement

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input: ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] Output: [null, null, null, 2, 2, false] Explanation: MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // return 2 myStack.pop(); // return 2 myStack.empty(); // return False

Constraints:

1 <= x <= 9

At most 100 calls will be made to push, pop, top, and empty.

All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

Code and Explanation

Optimal

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)

        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0

Explanation:

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

128. Largest Rectangle in Histogram (Leetcode:84)#

Also in DSA Patterns

Largest Rectangle in Histogram — 08. Stack (may include extra approaches and complexity analysis).

Problem Statement

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4] Output: 4

Constraints:

1 <= heights.length <= 105

0 <= heights[i] <= 104

Code and Explanation

Optimal

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = []  # pair: (index, height)

        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index
            stack.append((start, h))

        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))
        return maxArea

Explanation:

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

129. Next Greater Element I (Leetcode:496)#

Problem Statement

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: The next greater element for each value of nums1 is as follows: - 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1. - 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3. - 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4] Output: [3,-1] Explanation: The next greater element for each value of nums1 is as follows: - 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3. - 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Constraints:

1 <= nums1.length <= nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 104

All integers in nums1 and nums2 are unique.

All the integers of nums1 also appear in nums2.

Follow up: Could you find an O(nums1.length + nums2.length) solution?

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:

            # O (n + m)
            nums1Idx = { n:i for i, n in enumerate(nums1) }
            res = [-1] * len(nums1)

            stack = []
            for i in range(len(nums2)):
                cur = nums2[i]

                # while stack exists and current is greater than the top of the stack
                while stack and cur > stack[-1]:
                    val = stack.pop() # take top val
                    idx = nums1Idx[val]
                    res[idx] = cur

                if cur in nums1Idx:
                    stack.append(cur)

            return res


            # O (n * m)
            nums1Idx = { n:i for i, n in enumerate(nums1) }
            res = [-1] * len(nums1)

            for i in range(len(nums2)):
                if nums2[i] not in nums1Idx:
                    continue
                for j in range(i + 1, len(nums2)):
                    if nums2[j] > nums2[i]:
                        idx = nums1Idx[nums2[i]]
                        res[idx] = nums2[j]
                        break

            return res
    ```
    **Explanation:**

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

130. 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:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
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

Stack

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:

Push opening brackets.
On closing, stack must match top.
Valid iff stack empty at end.
Time complexity: O(n)
Space complexity: O(n)

Trees#

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

Optimal

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:

Use BFS with level-size snapshots.
Sum node values at each level before moving deeper.
Append total divided by level size to the answer.

132. Balanced Binary Tree (Leetcode:110)#

Also in DSA Patterns

Balanced Binary Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than one.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: The left subtree of node 1 has a depth of 3, while the right subtree has a depth of 1.

Example 3:

Input: root = []
Output: true

Constraints:

The number of nodes in the tree is in the range [0, 5000].

-10⁴ <= Node.val <= 10⁴

Code and Explanation

Optimal

# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            if not root:
                return [True, 0]

            left, right = dfs(root.left), dfs(root.right)
            balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
            return [balanced, 1 + max(left[1], right[1])]

        return dfs(root)[0]

Explanation:

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

133. Binary Tree Inorder Traversal (Leetcode:94)#

Also in DSA Patterns

Binary Tree Inorder Traversal — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3] Output: [1,3,2] Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,2,6,5,7,1,3,9,8] Explanation:

Example 3:

Input: root = [] Output: []

Example 4:

Input: root = [1] Output: [1]

Constraints:

The number of nodes in the tree is in the range [0, 100].

-100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Code and Explanation

Optimal

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # Iterative
        res, stack = [], []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
        return res

        # Recursive
        res = []

        def helper(root):
            if not root:
                return
            helper(root.left)
            res.append(root.val)
            helper(root.right)

        helper(root)
        return res

Explanation:

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

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

BFS (Level Order)

# 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:

Queue starts with root.
Snapshot queue size each iteration = current level width.
Collect values, enqueue children.
Time complexity: O(n)
Space complexity: O(n)

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

Post-Order DFS

# 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:

At each node, best path through node = left_gain + val + right_gain.
Return to parent only one-sided gain: val + max(left, right).
Global best tracks maximum anywhere in tree.
Time complexity: O(n)
Space complexity: O(h)

136. Binary Tree Paths (Leetcode:257)#

Also in DSA Patterns

Binary Tree Paths — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return all root-to-leaf paths in any order**.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Example 2:

Input: root = [1]
Output: ["1"]

Constraints:

The number of nodes in the tree is in the range [1, 100].

-100 <= Node.val <= 100

Code and Explanation

Optimal

class Solution:
    def binaryTreePaths(self, root: TreeNode | None) -> list[str]:
        paths: list[str] = []
        def dfs(node: TreeNode | None, path: list[str]) -> None:
            if not node:
                return
            path.append(str(node.val))
            if not node.left and not node.right:
                paths.append('->'.join(path))
            else:
                dfs(node.left, path)
                dfs(node.right, path)
            path.pop()
        dfs(root, [])
        return paths

Explanation:

DFS from root while building the current path as a list of values.
At each leaf, join the path with '->' and store it.
Backtrack by removing the last node after exploring children.

137. Binary Tree Postorder Traversal (Leetcode:145)#

Also in DSA Patterns

Binary Tree Postorder Traversal — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3] Output: [3,2,1] Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,6,7,5,2,9,8,3,1] Explanation:

Example 3:

Input: root = [] Output: []

Example 4:

Input: root = [1] Output: [1]

Constraints:

The number of the nodes in the tree is in the range [0, 100].

-100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Code and Explanation

Optimal

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = [root]
        visit = [False]
        res = []

        while stack:
            cur, v = stack.pop(), visit.pop()
            if cur:
                if v:
                    res.append(cur.val)
                else:
                    stack.append(cur)
                    visit.append(True)
                    stack.append(cur.right)
                    visit.append(False)
                    stack.append(cur.left)
                    visit.append(False)
        return res

Explanation:

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

138. Binary Tree Preorder Traversal (Leetcode:144)#

Also in DSA Patterns

Binary Tree Preorder Traversal — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3] Output: [1,2,3] Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [1,2,4,5,6,7,3,8,9] Explanation:

Example 3:

Input: root = [] Output: []

Example 4:

Input: root = [1] Output: [1]

Constraints:

The number of nodes in the tree is in the range [0, 100].

-100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Code and Explanation

Optimal

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        cur, stack = root, []
        res = []
        while cur or stack:
            if cur:
                res.append(cur.val)
                stack.append(cur.right)
                cur = cur.left
            else:
                cur = stack.pop()
        return res

Explanation:

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

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

Optimal

# 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:

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

140. Binary Tree Tilt (Leetcode:563)#

Also in DSA Patterns

Binary Tree Tilt — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return the sum of all tilts of its nodes.

The tilt of a node is the absolute difference between the sum of all left subtree node values and all right subtree node values.

Example 1:

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

Constraints:

The number of nodes in the tree is in the range [0, 10^4].

Code and Explanation

Optimal

class Solution:
    def findTilt(self, root: TreeNode | None) -> int:
        total_tilt = 0
        def sum_tree(node: TreeNode | None) -> int:
            nonlocal total_tilt
            if not node:
                return 0
            left = sum_tree(node.left)
            right = sum_tree(node.right)
            total_tilt += abs(left - right)
            return left + right + node.val
        sum_tree(root)
        return total_tilt

Explanation:

Post-order DFS returns each subtree's total sum.
At each node, add abs(left_sum - right_sum) to the global tilt.
Return node value plus subtree sums for parent calculations.

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

Hash Map + Index Bounds (Optimal)Recursive Slicing

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:

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.
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.
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.
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.
Why this is optimal: Each node is visited once with O(1) hash lookups — no repeated slicing or .index() calls.
Time complexity: O(n)
Space complexity: O(n)

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:

Root is always preorder[0]. Find it in inorder at index mid.
Left subtree: preorder[1:mid+1] pairs with inorder[:mid].
Right subtree: preorder[mid+1:] pairs with inorder[mid+1:].
Easy to understand but O(n²) from slicing and .index() at every level.
Time complexity: O(n²)
Space complexity: O(n²)

142. Construct String from Binary Tree (Leetcode:606)#

Problem Statement

Given the root node of a binary tree, your task is to create a string representation of the tree following a specific set of formatting rules. The representation should be based on a preorder traversal of the binary tree and must adhere to the following guidelines:

Node Representation: Each node in the tree should be represented by its integer value.

Parentheses for Children: If a node has at least one child (either left or right), its children should be represented inside parentheses. Specifically:

If a node has a left child, the value of the left child should be enclosed in parentheses immediately following the node's value.

If a node has a right child, the value of the right child should also be enclosed in parentheses. The parentheses for the right child should follow those of the left child.

Omitting Empty Parentheses: Any empty parentheses pairs (i.e., ()) should be omitted from the final string representation of the tree, with one specific exception: when a node has a right child but no left child. In such cases, you must include an empty pair of parentheses to indicate the absence of the left child. This ensures that the one-to-one mapping between the string representation and the original binary tree structure is maintained.

In summary, empty parentheses pairs should be omitted when a node has only a left child or no children. However, when a node has a right child but no left child, an empty pair of parentheses must precede the representation of the right child to reflect the tree's structure accurately.

Example 1:

Input: root = [1,2,3,4] Output: "1(2(4))(3)" Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

Example 2:

Input: root = [1,2,3,null,4] Output: "1(2()(4))(3)" Explanation: Almost the same as the first example, except the () after 2 is necessary to indicate the absence of a left child for 2 and the presence of a right child.

Constraints:

The number of nodes in the tree is in the range [1, 104].

-1000 <= Node.val <= 1000

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def tree2str(self, root: Optional[TreeNode]) -> str:
            # Solution with O(n) time and space complexity
            res = []
            self.dfs(root, res)
            return "".join(res)

        def dfs(self, t: TreeNode, res: list):
            # If the current node is None, do nothing and return
            if t is None:
                return
            res.append(str(t.val))

            # If both left and right children are None, return as there are no more branches to explore
            if t.left is None and t.right is None:
                return
            res.append('(')

            # Recursively call the DFS function for the left child
            self.dfs(t.left, res)
            res.append(')')

            # If the right child exists, process it
            if t.right is not None:
                res.append('(')

                # Recursively call the DFS function for the right child
                self.dfs(t.right, res)
                res.append(')')
    ```
    **Explanation:**

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

143. Diameter of Binary Tree (Leetcode:543)#

Also in DSA Patterns

Diameter of Binary Tree — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return the length of the diameter — the longest path between any two nodes (path may or may not pass through root).

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: Path 4→2→1→3 or 5→2→1→3.

Example 2:

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

Constraints:

1 <= number of nodes <= 10⁴

−100 <= Node.val <= 100

Code and Explanation

Optimal

# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 0

        def dfs(root):
            nonlocal res

            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            res = max(res, left + right)

            return 1 + max(left, right)

        dfs(root)
        return res

Explanation:

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

144. Find Mode in Binary Search Tree (Leetcode:501)#

Problem Statement

Given the root of a binary search tree with duplicates, return all values with the highest frequency in any order.

Example 1:

Input: root = [1,null,2,2] Output: [2]

Constraints:

The number of nodes in the tree is in the range [1, 10^4].

Code and Explanation

Optimal

class Solution:
    def findMode(self, root: TreeNode | None) -> list[int]:
        counts: dict[int, int] = {}
        best = 0
        def inorder(node: TreeNode | None) -> None:
            nonlocal best
            if not node:
                return
            inorder(node.left)
            counts[node.val] = counts.get(node.val, 0) + 1
            best = max(best, counts[node.val])
            inorder(node.right)
        inorder(root)
        return [val for val, count in counts.items() if count == best]

Explanation:

In-order traversal of a BST visits values in sorted order.
Count frequency of each value while tracking the maximum count.
Return every value whose count equals the maximum.

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

Recursive DFS (Optimal)Iterative BFS

# 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:

Swap left and right at each node recursively.
Post-order: invert children then assign.
Time complexity: O(n)
Space complexity: O(h)

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:

Queue nodes; swap children when dequeuing.
Enqueue swapped children for later processing.
Time complexity: O(n)
Space complexity: O(n)

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

Iterative Inorder (Optimal)Recursive Inorder

# 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:

Push left spine onto stack.
Pop, visit, go right.
Stop at kth pop.
Time complexity: O(h + k)
Space complexity: O(h)

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:

Inorder visits BST in sorted order.
Increment count on visit; return at k.
Time complexity: O(h + k)
Space complexity: O(h)

147. Lowest Common Ancestor of a Binary Search Tree (Leetcode:235)#

Also in DSA Patterns

Lowest Common Ancestor of a Binary Search Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes p and q in the BST. The LCA is defined as the lowest node that has both p and q as descendants.

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: LCA of nodes 2 and 8 is 6.

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 BST

Code and Explanation

BST Iterative Walk (Optimal)Recursive DFS

# 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":
        while True:
            if root.val < p.val and root.val < q.val:
                root = root.right
            elif root.val > p.val and root.val > q.val:
                root = root.left
            else:
                return root

Explanation:

Both targets smaller → go left; both larger → go right.
Otherwise current node is LCA.
Uses BST ordering — no full tree search.
Time complexity: O(h)
Space complexity: O(1)

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root

Explanation:

Same BST logic recursively.
Recurse left or right based on values vs root.
Return node where paths diverge.
Time complexity: O(h)
Space complexity: O(h)

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

Post-Order DFS

# 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:

If node is p or q, return it.
Search left and right subtrees.
If both return non-null, current node is LCA; else propagate non-null side.
Time complexity: O(n)
Space complexity: O(h)

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

Recursive DFS (Optimal)Iterative BFS

# 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:

Base case: Empty node → depth 0.
Recurse on children; return 1 + max(left, right).
Simple post-order height computation.
Time complexity: O(n)
Space complexity: O(h)

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:

Queue level-order traversal.
Increment depth after processing each level's nodes.
Avoids recursion depth limits.
Time complexity: O(n)
Space complexity: O(n)

150. Merge Two Binary Trees (Leetcode:617)#

Also in DSA Patterns

Merge Two Binary Trees — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the non-null node will be used as the node of the new tree.

Return the merged tree.

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

Constraints:

The number of nodes in both trees is in the range [0, 2000].

-10⁴ <= Node.val <= 10⁴

Code and Explanation

Optimal

# 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 mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1 and not t2:
            return None

        v1 = t1.val if t1 else 0
        v2 = t2.val if t2 else 0
        root = TreeNode(v1 + v2)

        root.left = self.mergeTrees(t1.left if t1 else None, t2.left if t2 else None)
        root.right = self.mergeTrees(t1.right if t1 else None, t2.right if t2 else None)
        return root

Explanation:

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\)

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

Optimal

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:

In-order traversal visits BST values in sorted order.
Compare each node with its in-order predecessor.
Track the smallest positive difference.

152. Minimum Depth of Binary Tree (Leetcode:111)#

Also in DSA Patterns

Minimum Depth of Binary Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: 2

Constraints:

The number of nodes in the tree is in the range [0, 10^5].

Code and Explanation

Optimal

class Solution:
    def minDepth(self, root: TreeNode | None) -> int:
        if not root:
            return 0
        if not root.left:
            return 1 + self.minDepth(root.right)
        if not root.right:
            return 1 + self.minDepth(root.left)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

Explanation:

Base case: empty tree has depth 0.
If one child is missing, the shortest path must go through the other child.
Otherwise return 1 plus the minimum depth of left and right subtrees.

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

Optimal

# 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:

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

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

Recursive DFS

# 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:

Both null → true; one null → false.
Values must match; recurse on both children.
Time complexity: O(n)
Space complexity: O(h)

155. Subtree of Another Tree (Leetcode:572)#

Problem Statement

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot, and false otherwise.

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true

Constraints:

The number of nodes in the root tree is in the range [1, 2000]

The number of nodes in the subRoot tree is in the range [1, 1000]

-10^4 <= Node.val <= 10^4

Code and Explanation

DFS + Same-Tree Check

# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True
        if not root:
            return False

        if self.isSameTree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    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:

At each node in root, test if subtree matches subRoot.
same() compares structure and values.
DFS left/right if no match here.
Time complexity: O(m × n)
Space complexity: O(h)

156. Sum of Left Leaves (Leetcode:404)#

Problem Statement

Given the root of a binary tree, return the sum of all left leaves.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: 24 Explanation: Left leaves are 9 and 15; 9 + 15 = 24.

Constraints:

The number of nodes in the tree is in the range [1, 1000].

Code and Explanation

Optimal

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode | None) -> int:
        def dfs(node: TreeNode | None, is_left: bool) -> int:
            if not node:
                return 0
            if is_left and not node.left and not node.right:
                return node.val
            return dfs(node.left, True) + dfs(node.right, False)
        return dfs(root, False)

Explanation:

DFS while tracking whether the current node is a left child.
Add the value when a left child is also a leaf.
Recurse on both subtrees with updated left/right flags.

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

Optimal

# 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:

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

158. Two Sum IV - Input is a BST (Leetcode:653)#

Also in DSA Patterns

Two Sum IV - Input is a BST — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a BST and an integer k, return true if there exist two elements in the BST such that their sum equals k.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9 Output: true

Constraints:

The number of nodes in the tree is in the range [1, 10^4].

Code and Explanation

Optimal

class Solution:
    def findTarget(self, root: TreeNode | None, k: int) -> bool:
        seen: set[int] = set()
        def dfs(node: TreeNode | None) -> bool:
            if not node:
                return False
            if k - node.val in seen:
                return True
            seen.add(node.val)
            return dfs(node.left) or dfs(node.right)
        return dfs(root)

Explanation:

DFS the tree while storing visited values in a set.
For each node, check whether its complement k - val was seen.
Return true immediately when a valid pair is found.

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

Min/Max Bounds (Optimal)Inorder Traversal

# 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:

Pass valid (min, max) range down recursion.
Node must satisfy min < val < max.
Left child max becomes current val; right child min becomes current val.
Time complexity: O(n)
Space complexity: O(h)

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:

BST inorder is strictly increasing.
Track previous visited value.
Invalid if current <= prev.
Time complexity: O(n)
Space complexity: O(h)

Tries#

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

Trie

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:

Each node has char → child map and end flag.
insert walks/creates path; search requires end flag; startsWith only needs path.
Time complexity: O(L) per op
Space complexity: O(total chars)

Two Pointers#

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

Sort + Two Pointers

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:

Sort first: Enables two-pointer search and duplicate skipping.
Fix one number at i: Set left = i+1, right = n-1, find pairs summing to -nums[i].
Skip duplicates: After finding a triplet or advancing i, skip equal values.
Time complexity: O(n²)
Space complexity: O(1)

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

Two Pointers

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:

Start wide: left = 0, right = n-1.
Area formula: Height = min(height[left], height[right]); width = right - left.
Move shorter side: Advance the pointer at the shorter wall to seek more area.
Why: Keeping the shorter side fixes the height cap. O(n) time.
Time complexity: O(n)
Space complexity: O(1)

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

164. Reverse String (Leetcode:344)#

Problem Statement

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Example 2:

Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]

Constraints:

1 <= s.length <= 105

s[i] is a printable ascii character.

Code and Explanation

=== "Optimal"
    ```python linenums="1"
    class Solution:
        def reverseString(self, s: List[str]) -> None:
            """
            Do not return anything, modify s in-place instead.
            """
            l = 0
            r = len(s) - 1
            while l < r:
                s[l],s[r] = s[r],s[l]
                l += 1
                r -= 1
    ```
    **Explanation:**

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

165. Reverse Vowels of a String (Leetcode:345)#

Problem Statement

Given a string s, reverse only the vowels in the string and return the resulting string.

Example 1:

Input: s = "hello" Output: "holle"

Constraints:

1 <= s.length <= 3 * 10^5

s consists of printable ASCII characters.

Code and Explanation

Optimal

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        chars = list(s)
        left, right = 0, len(chars) - 1
        while left < right:
            while left < right and chars[left] not in vowels:
                left += 1
            while left < right and chars[right] not in vowels:
                right -= 1
            chars[left], chars[right] = chars[right], chars[left]
            left += 1
            right -= 1
        return ''.join(chars)

Explanation:

Use two pointers from both ends of the string.
Advance each pointer until it points at a vowel.
Swap vowels and continue until the pointers meet.

166. Reverse Words in a String III (Leetcode:557)#

Problem Statement

Given a string s, reverse the order of characters in each word while preserving whitespace and initial word order.

Example 1:

Input: s = "Let's take LeetCode contest" Output: "s'teL ekat edoCteeL tsetnoc"

Constraints:

1 <= s.length <= 5 * 10^4

s contains printable ASCII characters and spaces.

Code and Explanation

Optimal

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split(' ')
        return ' '.join(word[::-1] for word in words)

Explanation:

Split the string on spaces while keeping empty tokens from repeated spaces.
Reverse each word individually with slicing.
Rejoin words with single spaces.

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

Optimal

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:

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

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

Two Pointers

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:

Move inward skipping non-alphanumeric.
Compare lowercased chars.
O(n) time, O(1) space.
Time complexity: O(n)
Space complexity: O(1)