Skip to content

NeetCode 150#

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

Explore overlaps

Compare this sheet with others in the DSA Venn Explorer.

How to use

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

Arrays & Hashing#

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

1
2
3
4
5
6
7
8
9
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:

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

1
2
3
4
5
6
7
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:

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

2. Encode and Decode Strings (Leetcode:271)#

Problem Statement

Design an algorithm to encode a list of strings to a single string and decode it back to the original list. The encoded string should be able to decode back to the original list of strings.

Example 1:

Input: ["neet","code","love","you"] Output: ["neet","code","love","you"]

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def encode(self, strs):
        res = []
        for s in strs:
            res.append(str(len(s)))
            res.append("#")
            res.append(s)
        return "".join(res)

    def decode(self, s):
        res = []
        i = 0

        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            length = int(s[i:j])
            i = j + 1
            j = i + length
            res.append(s[i:j])
            i = j

        return res
Explanation:

  1. Encode each string as len#content.
  2. Decode reads length until '#', then slices that many chars.
  3. Handles any character including delimiters.
  4. Time complexity: O(n)
  5. Space complexity: O(1)

3. Find the Duplicate Number (Leetcode:287)#

Also in DSA Patterns

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

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem in linear runtime complexity?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow2 = 0
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                return slow
Explanation:

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

4. Gas Station (Leetcode:134)#

Also in DSA Patterns

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

Problem Statement

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

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

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

Example 1:

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

Example 2:

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

Constraints:

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

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

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

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

5. Group Anagrams (Leetcode:49)#

Problem Statement

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

Example 1:

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

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}

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

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

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

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

        return list(groups.values())

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

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

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

6. Happy Number (Leetcode:202)#

Also in DSA Patterns

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

Problem Statement

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

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

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

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

Example 1:

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

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2^31 - 1

Code and Explanation 

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

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

        return True if fast == 1 else False

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

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

7. Jump Game (Leetcode:55)#

Also in DSA Patterns

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

Problem Statement

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

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

Example 1:

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

Example 2:

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

Constraints:

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

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

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

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

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

8. Jump Game II (Leetcode:45)#

Also in DSA Patterns

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

Problem Statement

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

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

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

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

Example 1:

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

Example 2:

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

Constraints:

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

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

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

9. Longest Consecutive Sequence (Leetcode:128)#

Problem Statement

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

Example 1:

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

Constraints:

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

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

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

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

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

Also in DSA Patterns

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

Problem Statement

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

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

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

Example 1:

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

Example 2:

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

Constraints:

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

Follow up:

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

Code and Explanation 

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

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

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

                return answer
Explanation:

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

11. Top K Frequent Elements (Leetcode:347)#

Also in DSA Patterns

Top K Frequent Elements — 15. Heaps (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]

        for n in nums:
            count[n] = 1 + count.get(n, 0)
        for n, c in count.items():
            freq[c].append(n)

        res = []
        for i in range(len(freq) - 1, 0, -1):
            res += freq[i]
            if len(res) == k:
                return res


        # O(n)
Explanation:

  1. Count frequencies with Counter.
  2. heapq.nlargest(k, keys, key=counts.get) returns top k.
  3. Simple and effective.
  4. Time complexity: O(n log k)
  5. Space complexity: O(n)

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


class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in counts.items():
            buckets[freq].append(num)
        result = []
        for freq in range(len(buckets) - 1, 0, -1):
            for num in buckets[freq]:
                result.append(num)
                if len(result) == k:
                    return result
        return result
Explanation:

  1. Bucket index = frequency.
  2. Scan buckets high to low until k elements collected.
  3. O(n) when frequency range bounded by n.
  4. Time complexity: O(n)
  5. Space complexity: O(n)

12. Two Sum (Leetcode:1)#

Also in DSA Patterns

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

Problem Statement

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

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

You can return the answer in any order.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Follow Up:

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

Code and Explanation 

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

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

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

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

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

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

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

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

13. Valid Anagram (Leetcode:242)#

Problem Statement

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

Example 1:

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

Constraints:

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

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

        countS, countT = {}, {}

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


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

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

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

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

Backtracking#

14. Combination Sum (Leetcode:39)#

Also in DSA Patterns

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

Problem Statement

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

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

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

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

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

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

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

15. Combination Sum II (Leetcode:40)#

Also in DSA Patterns

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

Problem Statement

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

Example 2:

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

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()

        res = []

        def backtrack(cur, pos, target):
            if target == 0:
                res.append(cur.copy())
                return
            if target <= 0:
                return

            prev = -1
            for i in range(pos, len(candidates)):
                if candidates[i] == prev:
                    continue
                cur.append(candidates[i])
                backtrack(cur, i + 1, target - candidates[i])
                cur.pop()
                prev = candidates[i]

        backtrack([], 0, target)
        return res
Explanation:

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

16. Generate Parentheses (Leetcode:22)#

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= n <= 8
Code and Explanation 

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

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

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

        backtrack(0, 0)
        return res
Explanation:

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

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

Also in DSA Patterns

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

Problem Statement

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

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

Example 1:

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

Example 2:

Input: digits = "" Output: []

Example 3:

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

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

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

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

        backtrack(0, "")
        return res
Explanation:

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

18. N-Queens (Leetcode:51)#

Also in DSA Patterns

N-Queens — 12. Backtracking (may include extra approaches and complexity analysis).

Problem Statement

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

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order**.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1 Output: [["Q"]]

Constraints:

  • 1 <= n <= 9
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set()  # (r + c)
        negDiag = set()  # (r - c)

        res = []
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            if r == n:
                copy = ["".join(row) for row in board]
                res.append(copy)
                return

            for c in range(n):
                if c in col or (r + c) in posDiag or (r - c) in negDiag:
                    continue

                col.add(c)
                posDiag.add(r + c)
                negDiag.add(r - c)
                board[r][c] = "Q"

                backtrack(r + 1)

                col.remove(c)
                posDiag.remove(r + c)
                negDiag.remove(r - c)
                board[r][c] = "."

        backtrack(0)
        return res
Explanation:

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

19. Palindrome Partitioning (Leetcode:131)#

Also in DSA Patterns

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

Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example 1:

Input: s = "aab" Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a" Output: [["a"]]

Constraints:

  • 1 <= s.length <= 16
  • s contains only lowercase English letters.
Code and Explanation 

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

        def dfs(i):
            if i >= len(s):
                res.append(part.copy())
                return
            for j in range(i, len(s)):
                if self.isPali(s, i, j):
                    part.append(s[i : j + 1])
                    dfs(j + 1)
                    part.pop()

        dfs(0)
        return res

    def isPali(self, s, l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l, r = l + 1, r - 1
        return True
Explanation:

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

20. Permutations (Leetcode:46)#

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

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

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

        backtrack([], nums)
        return res
Explanation:

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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:

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

22. Subsets II (Leetcode:90)#

Also in DSA Patterns

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

Problem Statement

Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Example 1:

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

Example 2:

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

Constraints:

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

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

        def backtrack(i, subset):
            if i == len(nums):
                res.append(subset[::])
                return

            # All subsets that include nums[i]
            subset.append(nums[i])
            backtrack(i + 1, subset)
            subset.pop()
            # All subsets that don't include nums[i]
            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                i += 1
            backtrack(i + 1, subset)

        backtrack(0, [])
        return res
Explanation:

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

23. Word Search (Leetcode:79)#

Also in DSA Patterns

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

Problem Statement

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

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

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

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        path = set()

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

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

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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:

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

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

Problem Statement

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

Example 1:

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

Constraints:

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

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

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

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

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

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

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

26. Koko Eating Bananas (Leetcode:875)#

Also in DSA Patterns

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

Problem Statement

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8 Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5 Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6 Output: 23

Constraints:

  • 1 <= piles.length <= 104
  • piles.length <= h <= 109
  • 1 <= piles[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        res = r

        while l <= r:
            k = (l + r) // 2

            totalTime = 0
            for p in piles:
                totalTime += math.ceil(float(p) / k)
            if totalTime <= h:
                res = k
                r = k - 1
            else:
                l = k + 1
        return res
Explanation:

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

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

Problem Statement

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

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

Example 1:

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

Example 2:

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

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Time: log(min(n, m))


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

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

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

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

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

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

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

Also in DSA Patterns

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

Problem Statement

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

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

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

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

Example 1:

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

Example 2:

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

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])

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

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

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

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

Also in DSA Patterns

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

Problem Statement

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

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

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

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

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

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

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

Bit Manipulation#

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def 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:

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

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

1
2
3
4
5
6
7
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:

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

1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        result = len(nums)
        for i, num in enumerate(nums):
            result ^= i ^ num
        return result
Explanation:

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

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

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Constraints:

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

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

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

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

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

33. Reverse Bits (Leetcode:190)#

Also in DSA Patterns

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

Problem Statement

Reverse bits of a given 32 bits unsigned integer.

Example 1:

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

Constraints:

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

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

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

34. Single Number (Leetcode:136)#

Also in DSA Patterns

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

Problem Statement

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

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

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

Constraints:

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

Code and Explanation 

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

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

35. Sum of Two Integers (Leetcode:371)#

Also in DSA Patterns

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

Problem Statement

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Constraints:

-1000 <= a, b <= 1000

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def getSum(self, a: int, b: int) -> int:
        def add(a, b):
            if not a or not b:
                return a or b
            return add(a ^ b, (a & b) << 1)

        if a * b < 0:  # assume a < 0, b > 0
            if a > 0:
                return self.getSum(b, a)
            if add(~a, 1) == b:  # -a == b
                return 0
            if add(~a, 1) < b:  # -a < b
                return add(~add(add(~a, 1), add(~b, 1)), 1)  # -add(-a, -b)

        return add(a, b)  # a*b >= 0 or (-a) > b > 0
Explanation:

  1. XOR gives sum without carry: a ^ b adds bits ignoring carry.
  2. AND + shift finds carry: (a & b) << 1 is carry shifted left.
  3. Repeat until carry is zero: Mask to 32-bit unsigned to simulate fixed-width arithmetic.
  4. Convert back to signed: Handle Python's unbounded integers. O(1) bit width.
  5. Time complexity: O(1)
  6. Space complexity: O(1)

Design#

36. Design Twitter (Leetcode:355)#

Also in DSA Patterns

Design Twitter — 22. Challenge Yourself (may include extra approaches and complexity analysis).

Problem Statement

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and see the 10 most recent tweet ids in the user's news feed.

Implement the Twitter class:

  • Twitter() Initializes your twitter object.
  • void postTweet(int userId, int tweetId) Creates a new tweet with ID tweetId by the user userId. Each call will be made with a unique tweetId.
  • List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's feed. Each item must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
  • void follow(int followerId, int followeeId) The user with ID followerId follows the user with ID followeeId.
  • void unfollow(int followerId, int followeeId) The user with ID followerId unfollowed the user with ID followeeId.

Example 1:

Input: ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
Output: [null, null, [5], null, null, [6, 5], null, [5]]

Constraints:

  • 1 <= userId, followerId, followeeId <= 500
  • 0 <= tweetId <= 104
  • All tweets have unique IDs.
  • At most 3 * 104 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

Patterns: Hash Map · Heap · K-way Merge

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Twitter:
    def __init__(self):
        self.count = 0
        self.tweetMap = defaultdict(list)  # userId -> list of [count, tweetIds]
        self.followMap = defaultdict(set)  # userId -> set of followeeId

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweetMap[userId].append([self.count, tweetId])
        self.count -= 1

    def getNewsFeed(self, userId: int) -> List[int]:
        res = []
        minHeap = []

        self.followMap[userId].add(userId)
        for followeeId in self.followMap[userId]:
            if followeeId in self.tweetMap:
                index = len(self.tweetMap[followeeId]) - 1
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

        while minHeap and len(res) < 10:
            count, tweetId, followeeId, index = heapq.heappop(minHeap)
            res.append(tweetId)
            if index >= 0:
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])
        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        self.followMap[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.followMap[followerId]:
            self.followMap[followerId].remove(followeeId)
Explanation:

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

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

Also in DSA Patterns

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

Problem Statement

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

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

Implement the MedianFinder class:

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

Example 1:

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

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

Constraints:

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

Follow up:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        # two heaps, large, small, minheap, maxheap
        # heaps should be equal size
        self.small, self.large = [], []  # maxHeap, minHeap (python default)

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

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

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

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

38. LRU Cache (Leetcode:146)#

Also in DSA Patterns

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

Problem Statement

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

Implement the LRUCache class:

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

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

Example 1:

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

Constraints:

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

Patterns: Hash Map · Linked List

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None


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

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

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

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

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

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

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

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

39. Min Stack (Leetcode:155)#

Also in DSA Patterns

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

Problem Statement

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

Implement the MinStack class:

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

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

Example 1:

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

Constraints:

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

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

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

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

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for 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:

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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:

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

Dynamic Programming#

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

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Constraints:

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

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

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

43. Best Time to Buy and Sell Stock with Cooldown (Leetcode:309)#

Also in DSA Patterns

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

Problem Statement

Given prices, maximize profit with unlimited transactions, but after you sell your stock, you cannot buy on the next day (one-day cooldown). You may not hold more than one share.

Example 1:

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: buy 1 sell 2, cooldown, buy 0 sell 2.

Example 2:

Input: prices = [1]
Output: 0

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # State: Buying or Selling?
        # If Buy -> i + 1
        # If Sell -> i + 2

        dp = {}  # key=(i, buying) val=max_profit

        def dfs(i, buying):
            if i >= len(prices):
                return 0
            if (i, buying) in dp:
                return dp[(i, buying)]

            cooldown = dfs(i + 1, buying)
            if buying:
                buy = dfs(i + 1, not buying) - prices[i]
                dp[(i, buying)] = max(buy, cooldown)
            else:
                sell = dfs(i + 2, not buying) + prices[i]
                dp[(i, buying)] = max(sell, cooldown)
            return dp[(i, buying)]

        return dfs(0, True)
Explanation:

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

44. Burst Balloons (Leetcode:312)#

Also in DSA Patterns

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

Problem Statement

Given n balloons with integers nums, bursting balloon i adds nums[i-1] * nums[i] * nums[i+1] coins (out-of-bounds treated as 1). Return maximum coins obtainable.

Example 1:

Input: nums = [3,1,5,8]
Output: 167

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        cache = {}
        nums = [1] + nums + [1]

        for offset in range(2, len(nums)):
            for left in range(len(nums) - offset):
                right = left + offset
                for pivot in range(left + 1, right):
                    coins = nums[left] * nums[pivot] * nums[right]
                    coins += cache.get((left, pivot), 0) + cache.get((pivot, right), 0)
                    cache[(left, right)] = max(coins, cache.get((left, right), 0))
        return cache.get((0, len(nums) - 1), 0)
Explanation:

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

45. Climbing Stairs (Leetcode:70)#

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Constraints:

  • 1 <= n <= 45
Code and Explanation 

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

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

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

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

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

        return dp(n)
Explanation:

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

46. Coin Change (Leetcode:322)#

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Constraints:

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

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

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

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

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

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

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

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

47. Coin Change II (Leetcode:518)#

Also in DSA Patterns

Coin Change I – Maximum Number of Ways — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array coins of distinct denominations and an integer amount, return the number of combinations that make up that amount. Each coin may be used an unlimited number of times. The answer fits in a 32-bit integer.

Example 1:

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

Example 2:

Input: amount = 3, coins = [2]
Output: 0

Constraints:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • 0 <= amount <= 5000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # MEMOIZATION
        # Time: O(n*m)
        # Memory: O(n*m)
        cache = {}

        def dfs(i, a):
            if a == amount:
                return 1
            if a > amount:
                return 0
            if i == len(coins):
                return 0
            if (i, a) in cache:
                return cache[(i, a)]

            cache[(i, a)] = dfs(i, a + coins[i]) + dfs(i + 1, a)
            return cache[(i, a)]

        return dfs(0, 0)

        # DYNAMIC PROGRAMMING
        # Time: O(n*m)
        # Memory: O(n*m)
        dp = [[0] * (len(coins) + 1) for i in range(amount + 1)]
        dp[0] = [1] * (len(coins) + 1)
        for a in range(1, amount + 1):
            for i in range(len(coins) - 1, -1, -1):
                dp[a][i] = dp[a][i + 1]
                if a - coins[i] >= 0:
                    dp[a][i] += dp[a - coins[i]][i]
        return dp[amount][0]

        # DYNAMIC PROGRAMMING
        # Time: O(n*m)
        # Memory: O(n) where n = amount
        dp = [0] * (amount + 1)
        dp[0] = 1
        for i in range(len(coins) - 1, -1, -1):
            nextDP = [0] * (amount + 1)
            nextDP[0] = 1

            for a in range(1, amount + 1):
                nextDP[a] = dp[a]
                if a - coins[i] >= 0:
                    nextDP[a] += nextDP[a - coins[i]]
            dp = nextDP
        return dp[amount]
Explanation:

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

48. Decode Ways (Leetcode:91)#

Also in DSA Patterns

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

Problem Statement

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

  • "AAJF" with the grouping (1, 1, 10, 6)
  • "KJF" with the grouping (11, 10, 6)
  • The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226" Output: 3 Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06" Output: 0 Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def numDecodings(self, s: str) -> int:
        # Memoization
        dp = {len(s): 1}

        def dfs(i):
            if i in dp:
                return dp[i]
            if s[i] == "0":
                return 0

            res = dfs(i + 1)
            if i + 1 < len(s) and (
                s[i] == "1" or s[i] == "2" and s[i + 1] in "0123456"
            ):
                res += dfs(i + 2)
            dp[i] = res
            return res

        return dfs(0)

        # Dynamic Programming
        dp = {len(s): 1}
        for i in range(len(s) - 1, -1, -1):
            if s[i] == "0":
                dp[i] = 0
            else:
                dp[i] = dp[i + 1]

            if i + 1 < len(s) and (
                s[i] == "1" or s[i] == "2" and s[i + 1] in "0123456"
            ):
                dp[i] += dp[i + 2]
        return dp[0]
Explanation:

  1. State: dp[i] = ways to decode prefix of length i.
  2. Single digit: Valid if s[i-1] is not '0'.
  3. Two digits: Valid if substring s[i-2:i] is 10-26.
  4. Sum transitions: dp[i] = dp[i-1] + dp[i-2] (when valid).
  5. Time complexity: O(n)
  6. Space complexity: O(n)

49. Distinct Subsequences (Leetcode:115)#

Problem Statement

Given two strings s and t, return the number of distinct subsequences of s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

Example 1:

Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from s. **rabb**b**it** **ra**b**bbit** **rab**b**bit**

Example 2:

Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown below, there are 5 ways you can generate "bag" from s. **ba**b**g**bag **ba**bgba**g** **b**abgb**ag** ba**b**gb**ag** babg**bag**

Constraints:

  • 1 <= s.length, t.length <= 1000

  • s and t consist of English letters.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def numDistinct(self, s: str, t: str) -> int:
            cache = {}

            for i in range(len(s) + 1):
                cache[(i, len(t))] = 1
            for j in range(len(t)):
                cache[(len(s), j)] = 0

            for i in range(len(s) - 1, -1, -1):
                for j in range(len(t) - 1, -1, -1):
                    if s[i] == t[j]:
                        cache[(i, j)] = cache[(i + 1, j + 1)] + cache[(i + 1, j)]
                    else:
                        cache[(i, j)] = cache[(i + 1, j)]
            return cache[(0, 0)]
    ```
    **Explanation:**

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

50. Edit Distance (Leetcode:72)#

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Example 2:

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

Constraints:

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

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

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

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

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

51. House Robber (Leetcode:198)#

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Constraints:

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

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

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

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

52. House Robber II (Leetcode:213)#

Also in DSA Patterns

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

Problem Statement

You are a professional robber planning to rob houses arranged in a circle, meaning the first and last houses are adjacent. Return the maximum amount you can rob without robbing two adjacent houses.

Example 1:

Input: nums = [2,3,2] Output: 3 Explanation: Rob house 2 (money = 3); cannot rob both 1 and 3.

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def rob(self, nums: list[int]) -> int:
        def rob_linear(houses: list[int]) -> int:
            prev2 = prev1 = 0
            for num in houses:
                prev2, prev1 = prev1, max(prev1, prev2 + num)
            return prev1

        if len(nums) == 1:
            return nums[0]
        return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
Explanation:

  1. Two linear runs: Rob houses 0..n-2 and 1..n-1 separately.
  2. Why: First and last houses cannot both be robbed.
  3. Reuse house robber I logic on each segment.
  4. Answer: Max of the two runs.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

53. Interleaving String (Leetcode:97)#

Problem Statement

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

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

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

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

  • |n - m| <= 1

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

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

  • 0 <= s3.length <= 200

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

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

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

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

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

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

54. Longest Common Subsequence (Leetcode:1143)#

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The LCS is "ace".

Constraints:

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of only lowercase English characters
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]

        for i in range(len(text1) - 1, -1, -1):
            for j in range(len(text2) - 1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + dp[i + 1][j + 1]
                else:
                    dp[i][j] = max(dp[i][j + 1], dp[i + 1][j])

        return dp[0][0]
Explanation:

  1. Table: dp[i][j] = LCS length of text1[:i] and text2[:j].
  2. Match: If chars equal, dp[i][j] = dp[i-1][j-1] + 1.
  3. Mismatch: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  4. Answer: dp[m][n]. O(mn) time and space.
  5. Time complexity: O(m × n)
  6. Space complexity: O(m × n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        prev = [0] * (len(text2) + 1)
        for i in range(1, len(text1) + 1):
            curr = [0] * (len(text2) + 1)
            for j in range(1, len(text2) + 1):
                if text1[i - 1] == text2[j - 1]:
                    curr[j] = prev[j - 1] + 1
                else:
                    curr[j] = max(prev[j], curr[j - 1])
            prev = curr
        return prev[-1]
Explanation:

  1. Only need previous row: Keep prev and curr arrays of size len(text2)+1.
  2. Same transitions as 2D DP but roll rows.
  3. Return last cell of final row.
  4. Space: O(min(m,n)) instead of O(mn).
  5. Time complexity: O(m × n)
  6. Space complexity: O(min(m, n))

55. Longest Increasing Path in a Matrix (Leetcode:329)#

Problem Statement

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]] Output: 4 Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]] Output: 1

Constraints:

  • m == matrix.length

  • n == matrix[i].length

  • 1 <= m, n <= 200

  • 0 <= matrix[i][j] <= 231 - 1

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
            ROWS, COLS = len(matrix), len(matrix[0])
            dp = {}  # (r, c) -> LIP

            def dfs(r, c, prevVal):
                if r < 0 or r == ROWS or c < 0 or c == COLS or matrix[r][c] <= prevVal:
                    return 0
                if (r, c) in dp:
                    return dp[(r, c)]

                res = 1
                res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
                res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
                res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
                res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
                dp[(r, c)] = res
                return res

            for r in range(ROWS):
                for c in range(COLS):
                    dfs(r, c, -1)
            return max(dp.values())
    ```
    **Explanation:**

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

56. Longest Increasing Subsequence (Leetcode:300)#

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

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

Code and Explanation 

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

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

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

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

57. Longest Palindromic Substring (Leetcode:5)#

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Constraints:

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

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

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

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

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

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

58. Maximum Product Subarray (Leetcode:152)#

Also in DSA Patterns

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

Problem Statement

Given an integer array nums, find a subarray that has the largest product, and return the product.

Example 1:

Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.

Constraints:

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • The product of any subarray fits in a 32-bit integer
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # O(n)/O(1) : Time/Memory
        res = nums[0]
        curMin, curMax = 1, 1

        for n in nums:

            tmp = curMax * n
            curMax = max(n * curMax, n * curMin, n)
            curMin = min(tmp, n * curMin, n)
            res = max(res, curMax)
        return res
Explanation:

  1. Track max and min product ending here: Negatives can flip a small product into a large one.
  2. Update at each index: Compute new max/min from num, num*max_here, and num*min_here.
  3. Record global best: result = max(result, max_here).
  4. Why: Zeros reset; negatives swap max/min roles. O(n) time, O(1) space.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

59. Maximum Subarray (Leetcode:53)#

Also in DSA Patterns

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

Problem Statement

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

Example 1:

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

Constraints:

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        def divide(lo: int, hi: int) -> int:
            if lo == hi:
                return nums[lo]
            mid = (lo + hi) // 2
            left = divide(lo, mid)
            right = divide(mid + 1, hi)
            cross = self._max_crossing(nums, lo, mid, hi)
            return max(left, right, cross)

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

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

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

60. Min Cost Climbing Stairs (Leetcode:746)#

Problem Statement

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20] Output: 15 Explanation: You will start at index 1. - Pay 15 and climb two steps to reach the top. The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6 Explanation: You will start at index 0. - Pay 1 and climb two steps to reach index 2. - Pay 1 and climb two steps to reach index 4. - Pay 1 and climb two steps to reach index 6. - Pay 1 and climb one step to reach index 7. - Pay 1 and climb two steps to reach index 9. - Pay 1 and climb one step to reach the top. The total cost is 6.

Constraints:

  • 2 <= cost.length <= 1000

  • 0 <= cost[i] <= 999

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def minCostClimbingStairs(self, cost: List[int]) -> int:
            for i in range(len(cost) - 3, -1, -1):
                cost[i] += min(cost[i + 1], cost[i + 2])

            return min(cost[0], cost[1])
    ```
    **Explanation:**

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

61. Palindromic Substrings (Leetcode:647)#

Also in DSA Patterns

Count of Palindromic Substrings — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward.

Example 1:

Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0

        def expand(left: int, right: int) -> None:
            nonlocal count
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1

        for i in range(len(s)):
            expand(i, i)
            expand(i, i + 1)
        return count
Explanation:

  1. Expand from each center; count valid palindromes.
  2. Odd and even centers handled separately.
  3. Time complexity: O(n²)
  4. Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        count = 0
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    count += 1
        return count
Explanation:

  1. dp[i][j] palindrome flag; count true entries.
  2. Fill i backwards so inner substrings ready.
  3. Time complexity: O(n²)
  4. Space complexity: O(n²)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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:

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

63. Regular Expression Matching (Leetcode:10)#

Also in DSA Patterns

Regular Expression Matching — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*':

  • '.' Matches any single character.
  • '*' Matches zero or more of the preceding element.

The matching should cover the entire input string. Return true if s matches p.

Example 1:

Input: s = "aa", p = "a"
Output: false

Example 2:

Input: s = "aa", p = "a*"
Output: true

Example 3:

Input: s = "ab", p = ".*"
Output: true

Constraints:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed that for each occurrence of '*', there is a valid preceding character.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# BOTTOM-UP Dynamic Programming
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        cache = [[False] * (len(p) + 1) for i in range(len(s) + 1)]
        cache[len(s)][len(p)] = True

        for i in range(len(s), -1, -1):
            for j in range(len(p) - 1, -1, -1):
                match = i < len(s) and (s[i] == p[j] or p[j] == ".")

                if (j + 1) < len(p) and p[j + 1] == "*":
                    cache[i][j] = cache[i][j + 2]
                    if match:
                        cache[i][j] = cache[i + 1][j] or cache[i][j]
                elif match:
                    cache[i][j] = cache[i + 1][j + 1]

        return cache[0][0]


# TOP DOWN MEMOIZATION
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        cache = {}

        def dfs(i, j):
            if (i, j) in cache:
                return cache[(i, j)]
            if i >= len(s) and j >= len(p):
                return True
            if j >= len(p):
                return False

            match = i < len(s) and (s[i] == p[j] or p[j] == ".")
            if (j + 1) < len(p) and p[j + 1] == "*":
                cache[(i, j)] = dfs(i, j + 2) or (  # dont use *
                    match and dfs(i + 1, j)
                )  # use *
                return cache[(i, j)]
            if match:
                cache[(i, j)] = dfs(i + 1, j + 1)
                return cache[(i, j)]
            cache[(i, j)] = False
            return False

        return dfs(0, 0)
Explanation:

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

64. Target Sum (Leetcode:494)#

Also in DSA Patterns

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

Problem Statement

Given an integer array nums and an integer target, assign each element a + or − sign so that the resulting expression equals target. Return the number of ways.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • −1000 <= target <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {}  # (index, total) -> # of ways

        def backtrack(i, total):
            if i == len(nums):
                return 1 if total == target else 0
            if (i, total) in dp:
                return dp[(i, total)]

            dp[(i, total)] = backtrack(i + 1, total + nums[i]) + backtrack(
                i + 1, total - nums[i]
            )
            return dp[(i, total)]

        return backtrack(0, 0)
Explanation:

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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:

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

66. Word Break (Leetcode:139)#

Problem Statement

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

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

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

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

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

        return dp[0]
Explanation:

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

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


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

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

Graphs#

67. Alien Dictionary (Leetcode:269)#

Problem Statement

There is a new alien language that uses the English alphabet. However, the order among letters is unknown. You are given a list of strings words from the alien language's dictionary, where the strings are sorted lexicographically. Derive the order of letters in this language. If the order is invalid, return an empty string.

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of only lowercase English letters
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adj = {char: set() for word in words for char in word}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            minLen = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
                return ""
            for j in range(minLen):
                if w1[j] != w2[j]:
                    print(w1[j], w2[j])
                    adj[w1[j]].add(w2[j])
                    break

        visited = {}  # {char: bool} False visited, True current path
        res = []

        def dfs(char):
            if char in visited:
                return visited[char]

            visited[char] = True

            for neighChar in adj[char]:
                if dfs(neighChar):
                    return True

            visited[char] = False
            res.append(char)

        for char in adj:
            if dfs(char):
                return ""

        res.reverse()
        return "".join(res)
Explanation:

  1. Compare adjacent words to extract character order edges.
  2. Invalid if longer word is prefix of shorter (e.g. abc before ab).
  3. Kahn BFS on graph; cycle ⇒ return empty string.
  4. Time complexity: O(C + E)
  5. Space complexity: O(C + E)

68. Cheapest Flights Within K Stops (Leetcode:787)#

Problem Statement

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i_, to_i_, price_i_] indicates that there is a flight from city from_i_ to city to_i_ with cost price_i_.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 Output: 700 Explanation: The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200 Explanation: The graph is shown above. The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0 Output: 500 Explanation: The graph is shown above. The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Constraints:

  • 2 <= n <= 100

  • 0 <= flights.length <= (n * (n - 1) / 2)

  • flights[i].length == 3

  • 0 <= from_i_, to_i_ < n

  • from_i_ != to_i_

  • 1 <= price_i_ <= 104

  • There will not be any multiple flights between two cities.

  • 0 <= src, dst, k < n

  • src != dst

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def findCheapestPrice(
            self, n: int, flights: List[List[int]], src: int, dst: int, k: int
        ) -> int:
            prices = [float("inf")] * n
            prices[src] = 0

            for i in range(k + 1):
                tmpPrices = prices.copy()

                for s, d, p in flights:  # s=source, d=dest, p=price
                    if prices[s] == float("inf"):
                        continue
                    if prices[s] + p < tmpPrices[d]:
                        tmpPrices[d] = prices[s] + p
                prices = tmpPrices
            return -1 if prices[dst] == float("inf") else prices[dst]
    ```
    **Explanation:**

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

69. Clone Graph (Leetcode:133)#

Problem Statement

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

Example 1:

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

Constraints:

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

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

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

        return dfs(node)
Explanation:

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

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


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

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

70. Course Schedule (Leetcode:207)#

Problem Statement

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

Example 1:

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

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # dfs
        preMap = {i: [] for i in range(numCourses)}

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

        visiting = set()

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[course].append(prereq)
        state = [0] * numCourses  # 0=unvisited, 1=visiting, 2=done

        def has_cycle(course: int) -> bool:
            if state[course] == 1:
                return True
            if state[course] == 2:
                return False
            state[course] = 1
            for prereq in graph[course]:
                if has_cycle(prereq):
                    return True
            state[course] = 2
            return False

        return not any(has_cycle(c) for c in range(numCourses) if state[c] == 0)
Explanation:

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

71. Course Schedule II (Leetcode:210)#

Problem Statement

An n x n matrix isConnected represents cities. isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] → Output: 2

Constraints: 1 <= n <= 200

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        prereq = {c: [] for c in range(numCourses)}
        for crs, pre in prerequisites:
            prereq[crs].append(pre)

        output = []
        visit, cycle = set(), set()

        def dfs(crs):
            if crs in cycle:
                return False
            if crs in visit:
                return True

            cycle.add(crs)
            for pre in prereq[crs]:
                if dfs(pre) == False:
                    return False
            cycle.remove(crs)
            visit.add(crs)
            output.append(crs)
            return True

        for c in range(numCourses):
            if dfs(c) == False:
                return []
        return output
Explanation:

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

72. Graph Valid Tree (Leetcode:261)#

Problem Statement

Given n nodes labeled from 0 to n - 1 and a list of undirected edges, write a function to check whether these edges make up a valid tree. A valid tree has no cycles and is fully connected.

Example 1:

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

Constraints:

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • No duplicate edges
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# Problem is free on Lintcode
class Solution:
    """
    @param n: An integer
    @param edges: a list of undirected edges
    @return: true if it's a valid tree, or false
    """

    def validTree(self, n, edges):
        if not n:
            return True
        adj = {i: [] for i in range(n)}
        for n1, n2 in edges:
            adj[n1].append(n2)
            adj[n2].append(n1)

        visit = set()

        def dfs(i, prev):
            if i in visit:
                return False

            visit.add(i)
            for j in adj[i]:
                if j == prev:
                    continue
                if not dfs(j, i):
                    return False
            return True

        return dfs(0, -1) and n == len(visit)



    # alternative solution via DSU O(ElogV) time complexity and 
    # save some space as we don't recreate graph\tree into adjacency list prior dfs and loop over the edge list directly
    class Solution:
    """
    @param n: An integer
    @param edges: a list of undirected edges
    @return: true if it's a valid tree, or false
    """
    def __find(self, n: int) -> int:
        while n != self.parents.get(n, n):
            n = self.parents.get(n, n)
        return n

    def __connect(self, n: int, m: int) -> None:
        pn = self.__find(n)
        pm = self.__find(m)
        if pn == pm:
            return
        if self.heights.get(pn, 1) > self.heights.get(pm, 1):
            self.parents[pn] = pm
        else:
            self.parents[pm] = pn
            self.heights[pm] = self.heights.get(pn, 1) + 1
        self.components -= 1

    def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
        # init here as not sure that ctor will be re-invoked in different tests
        self.parents = {}
        self.heights = {}
        self.components = n

        for e1, e2 in edges:
            if self.__find(e1) == self.__find(e2):  # 'redundant' edge
                return False
            self.__connect(e1, e2)

        return self.components == 1  # forest contains one tree
Explanation:

  1. Tree check: Valid tree with n nodes has exactly n-1 edges.
  2. Union-Find merge: If two nodes already share a root, cycle exists.
  3. No cycle + n-1 edges ⇒ connected tree.
  4. Time complexity: O(n × α(n))
  5. Space complexity: O(n)

73. Max Area of Island (Leetcode:695)#

Problem Statement

An n x n matrix isConnected represents cities. isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] → Output: 2

Constraints: 1 <= n <= 200

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        visit = set()

        def dfs(r, c):
            if (
                r < 0
                or r == ROWS
                or c < 0
                or c == COLS
                or grid[r][c] == 0
                or (r, c) in visit
            ):
                return 0
            visit.add((r, c))
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)

        area = 0
        for r in range(ROWS):
            for c in range(COLS):
                area = max(area, dfs(r, c))
        return area
Explanation:

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

74. Min Cost to Connect All Points (Leetcode:1584)#

Also in DSA Patterns

Minimum Cost to Connect All Points — 10. Greedy Algorithm (may include extra approaches and complexity analysis).

Problem Statement

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 Explanation: We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]] Output: 18

Constraints:

  • 1 <= points.length <= 1000
  • -106 <= xi, yi <= 106
  • All pairs (xi, yi) are distinct.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        N = len(points)
        adj = {i: [] for i in range(N)}  # i : list of [cost, node]
        for i in range(N):
            x1, y1 = points[i]
            for j in range(i + 1, N):
                x2, y2 = points[j]
                dist = abs(x1 - x2) + abs(y1 - y2)
                adj[i].append([dist, j])
                adj[j].append([dist, i])

        # Prim's
        res = 0
        visit = set()
        minH = [[0, 0]]  # [cost, point]
        while len(visit) < N:
            cost, i = heapq.heappop(minH)
            if i in visit:
                continue
            res += cost
            visit.add(i)
            for neiCost, nei in adj[i]:
                if nei not in visit:
                    heapq.heappush(minH, [neiCost, nei])
        return res
Explanation:

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

75. Network Delay Time (Leetcode:743)#

Also in DSA Patterns

Network Delay Time — 10. Greedy Algorithm (may include extra approaches and complexity analysis).

Problem Statement

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1 Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2 Output: -1

Constraints:

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • All the pairs (ui, vi) are unique. (i.e., no multiple edges.)
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        edges = collections.defaultdict(list)
        for u, v, w in times:
            edges[u].append((v, w))

        minHeap = [(0, k)]
        visit = set()
        t = 0
        while minHeap:
            w1, n1 = heapq.heappop(minHeap)
            if n1 in visit:
                continue
            visit.add(n1)
            t = w1

            for n2, w2 in edges[n1]:
                if n2 not in visit:
                    heapq.heappush(minHeap, (w1 + w2, n2))
        return t if len(visit) == n else -1

        # O(E * logV)
Explanation:

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

76. Number of Connected Components in an Undirected Graph (Leetcode:323)#

Problem Statement

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates an undirected edge between nodes ai and bi. Return the number of connected components.

Example 1:

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

Constraints:

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • No duplicate edges
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class UnionFind:
    def __init__(self):
        self.f = {}

    def findParent(self, x):
        y = self.f.get(x, x)
        if x != y:
            y = self.f[x] = self.findParent(y)
        return y

    def union(self, x, y):
        self.f[self.findParent(x)] = self.findParent(y)


class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        dsu = UnionFind()
        for a, b in edges:
            dsu.union(a, b)
        return len(set(dsu.findParent(x) for x in range(n)))
Explanation:

  1. Start with n components.
  2. Union each edge: If nodes in different sets, merge and decrement count.
  3. Return final component count. O(n α(n)).
  4. Time complexity: O(n × α(n))
  5. Space complexity: O(n)

77. Number of Islands (Leetcode:200)#

Problem Statement

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

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

Example 2:

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

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        islands = 0
        visit = set()
        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if (
                r not in range(rows)
                or c not in range(cols)
                or grid[r][c] == "0"
                or (r, c) in visit
            ):
                return

            visit.add((r, c))
            directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            for dr, dc in directions:
                dfs(r + dr, c + dc)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visit:
                    islands += 1
                    dfs(r, c)
        return islands

# DFS O(1) Space and much less code
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        def dfs(r, c):
            if not 0 <= r < len(grid) or not 0 <= c < len(grid[0]) or grid[r][c] == '0':
                return 0
            grid[r][c] = '0'
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
            return 1
        count = 0
        for r in range(rows):
            for c in range(cols):
                count += dfs(r, c)
        return count

# BFS Version From Video
class SolutionBFS:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        visited = set()
        islands = 0

         def bfs(r, c):
             q = deque()
             visited.add((r, c))
             q.append((r, c))

             while q:
                 row, col = q.popleft()
                 directions = [[1, 0],[-1, 0],[0, 1],[0, -1]]

                 for dr, dc in directions:
                     r, c = row + dr, col + dc
                     if (r) in range(rows) and (c) in range(cols) and grid[r][c] == '1' and (r, c) not in visited:

                         q.append((r, c ))
                         visited.add((r, c ))

         for r in range(rows):
             for c in range(cols):

                 if grid[r][c] == "1" and (r, c) not in visited:
                     bfs(r, c)
                     islands += 1 

         return islands
Explanation:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import deque


class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0

        def bfs(r: int, c: int) -> None:
            queue = deque([(r, c)])
            grid[r][c] = '0'
            while queue:
                row, col = queue.popleft()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    bfs(r, c)
        return count
Explanation:

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

78. Pacific Atlantic Water Flow (Leetcode:417)#

Problem Statement

There is an m x n rectangular island bordered by the Pacific Ocean (top and left edges) and Atlantic Ocean (bottom and right edges). Rain water flows to adjacent cells with equal or lower height. Find the list of grid coordinates where water can flow to both oceans.

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Constraints:

  • m == heights.length
  • n == heights[r].length
  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 10^5
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(heights), len(heights[0])
        pac, atl = set(), set()

        def dfs(r, c, visit, prevHeight):
            if (
                (r, c) in visit
                or r < 0
                or c < 0
                or r == ROWS
                or c == COLS
                or heights[r][c] < prevHeight
            ):
                return
            visit.add((r, c))
            dfs(r + 1, c, visit, heights[r][c])
            dfs(r - 1, c, visit, heights[r][c])
            dfs(r, c + 1, visit, heights[r][c])
            dfs(r, c - 1, visit, heights[r][c])

        for c in range(COLS):
            dfs(0, c, pac, heights[0][c])
            dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])

        for r in range(ROWS):
            dfs(r, 0, pac, heights[r][0])
            dfs(r, COLS - 1, atl, heights[r][COLS - 1])

        res = []
        for r in range(ROWS):
            for c in range(COLS):
                if (r, c) in pac and (r, c) in atl:
                    res.append([r, c])
        return res
Explanation:

  1. Reverse the flow: Start DFS from Pacific borders (top/left) and Atlantic borders (bottom/right).
  2. Climb uphill: Move to neighbor if height >= current.
  3. Two reachable sets: Cells in both sets drain to both oceans.
  4. Return intersection. O(mn) time.
  5. Time complexity: O(m × n)
  6. Space complexity: O(m × n)

79. Reconstruct Itinerary (Leetcode:332)#

Problem Statement

An n x n matrix isConnected represents cities. isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] → Output: 2

Constraints: 1 <= n <= 200

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        adj = {src: [] for src, dst in tickets}
        res = []

        for src, dst in tickets:
            adj[src].append(dst)

        for key in adj:
            adj[key].sort()

        def dfs(adj, src):
            if src in adj:
                destinations = adj[src][:]
                while destinations:
                    dest = destinations[0]
                    adj[src].pop(0)
                    dfs(adj, dest)
                    destinations = adj[src][:]
            res.append(src)

        dfs(adj, "JFK")
        res.reverse()

        if len(res) != len(tickets) + 1:
            return []

        return res
Explanation:

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

80. Redundant Connection (Leetcode:684)#

Problem Statement

An n x n matrix isConnected represents cities. isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] → Output: 2

Constraints: 1 <= n <= 200

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        par = [i for i in range(len(edges) + 1)]
        rank = [1] * (len(edges) + 1)

        def find(n):
            p = par[n]
            while p != par[p]:
                par[p] = par[par[p]]
                p = par[p]
            return p

        # return False if already unioned
        def union(n1, n2):
            p1, p2 = find(n1), find(n2)

            if p1 == p2:
                return False
            if rank[p1] > rank[p2]:
                par[p2] = p1
                rank[p1] += rank[p2]
            else:
                par[p1] = p2
                rank[p2] += rank[p1]
            return True

        for n1, n2 in edges:
            if not union(n1, n2):
                return [n1, n2]
Explanation:

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class 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:

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

82. Surrounded Regions (Leetcode:130)#

Problem Statement

An n x n matrix isConnected represents cities. isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

Example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] → Output: 2

Constraints: 1 <= n <= 200

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        rows, cols = len(board), len(board[0])
        flag = set()

        def dfs(r, c):
            if not(r in range(rows) and c in range(cols)) or board[r][c] != 'O' or (r, c) in flag:
                return
            flag.add((r, c))
            return (dfs(r + 1, c), dfs(r - 1, c), dfs(r, c + 1), dfs(r, c - 1))

        # traverse through the board
        for r in range(rows):
            for c in range(cols):
                if( (r == 0 or c == 0 or r == rows - 1 or c == cols - 1) and board[r][c] == 'O'):
                    dfs(r, c)

        # set all of the 'X's to 'O's
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O' and (r, c) not in flag:
                    board[r][c] = 'X'

    '''
    def solve(self, board: List[List[str]]) -> None:
        ROWS, COLS = len(board), len(board[0])

        def capture(r, c):
            if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":
                return
            board[r][c] = "T"
            capture(r + 1, c)
            capture(r - 1, c)
            capture(r, c + 1)
            capture(r, c - 1)

        # 1. (DFS) Capture unsurrounded regions (O -> T)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
                    capture(r, c)

        # 2. Capture surrounded regions (O -> X)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"

        # 3. Uncapture unsurrounded regions (T -> O)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "T":
                    board[r][c] = "O"
    '''
Explanation:

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

83. Swim in Rising Water (Leetcode:778)#

Problem Statement

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

It starts raining, and water gradually rises over time. At time t, the water level is t, meaning any cell with elevation less than equal to t is submerged or reachable.

You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the minimum time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Example 1:

Input: grid = [[0,2],[1,3]] Output: 3 Explanation: At time 0, you are in grid location (0, 0). You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0. You cannot reach point (1, 1) until time 3. When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] Output: 16 Explanation: The final route is shown. We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Constraints:

  • n == grid.length

  • n == grid[i].length

  • 1 <= n <= 50

  • 0 <= grid[i][j] < n2

  • Each value grid[i][j] is unique.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def swimInWater(self, grid: List[List[int]]) -> int:
            N = len(grid)
            visit = set()
            minH = [[grid[0][0], 0, 0]]  # (time/max-height, r, c)
            directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

            visit.add((0, 0))
            while minH:
                t, r, c = heapq.heappop(minH)
                if r == N - 1 and c == N - 1:
                    return t
                for dr, dc in directions:
                    neiR, neiC = r + dr, c + dc
                    if (
                        neiR < 0
                        or neiC < 0
                        or neiR == N
                        or neiC == N
                        or (neiR, neiC) in visit
                    ):
                        continue
                    visit.add((neiR, neiC))
                    heapq.heappush(minH, [max(t, grid[neiR][neiC]), neiR, neiC])
    ```
    **Explanation:**

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

84. Walls and Gates (Leetcode:286)#

Problem Statement

You are given an m x n grid rooms with the following values:

  • -1 represents a wall or an obstacle.
  • 0 represents a gate.
  • INF (2147483647) represents an empty room. We use the value INF so that the distance to a gate is less than INF.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should remain INF.

Example 1:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]] Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2:

Input: rooms = [[-1]] Output: [[-1]]

Constraints:

  • m == rooms.length
  • n == rooms[i].length
  • 1 <= m, n <= 250
  • rooms[i][j] is -1, 0, or 2^31 - 1.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    """
    @param rooms: m x n 2D grid
    @return: nothing
    """

    def walls_and_gates(self, rooms: List[List[int]]):
        ROWS, COLS = len(rooms), len(rooms[0])
        visit = set()
        q = deque()

        def addRooms(r, c):
            if (
                min(r, c) < 0
                or r == ROWS
                or c == COLS
                or (r, c) in visit
                or rooms[r][c] == -1
            ):
                return
            visit.add((r, c))
            q.append([r, c])

        for r in range(ROWS):
            for c in range(COLS):
                if rooms[r][c] == 0:
                    q.append([r, c])
                    visit.add((r, c))

        dist = 0
        while q:
            for i in range(len(q)):
                r, c = q.popleft()
                rooms[r][c] = dist
                addRooms(r + 1, c)
                addRooms(r - 1, c)
                addRooms(r, c + 1)
                addRooms(r, c - 1)
            dist += 1
Explanation:

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

85. Word Ladder (Leetcode:127)#

Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints:

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        nei = collections.defaultdict(list)
        wordList.append(beginWord)
        for word in wordList:
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j + 1 :]
                nei[pattern].append(word)

        visit = set([beginWord])
        q = deque([beginWord])
        res = 1
        while q:
            for i in range(len(q)):
                word = q.popleft()
                if word == endWord:
                    return res
                for j in range(len(word)):
                    pattern = word[:j] + "*" + word[j + 1 :]
                    for neiWord in nei[pattern]:
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            res += 1
        return 0
Explanation:

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

Greedy#

86. Hand of Straights (Leetcode:846)#

Problem Statement

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4 Output: false Explanation: Alice's hand can not be rearranged into groups of 4.

Constraints:

  • 1 <= hand.length <= 104

  • 0 <= hand[i] <= 109

  • 1 <= groupSize <= hand.length

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
            if len(hand) % groupSize:
                return False

            count = {}
            for n in hand:
                count[n] = 1 + count.get(n, 0)

            minH = list(count.keys())
            heapq.heapify(minH)
            while minH:
                first = minH[0]
                for i in range(first, first + groupSize):
                    if i not in count:
                        return False
                    count[i] -= 1
                    if count[i] == 0:
                        if i != minH[0]:
                            return False
                        heapq.heappop(minH)
            return True
    ```
    **Explanation:**

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

87. Merge Triplets to Form Target Triplet (Leetcode:1899)#

Problem Statement

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [a_i_, b_i_, c_i_] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.

To obtain target, you may apply the following operation on triplets any number of times (possibly zero):

  • Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(a_i_, a_j_), max(b_i_, b_j_), max(c_i_, c_j_)].

  • For example, if triplets[i] = [2, 5, 3] and triplets[j] = [1, 7, 5], triplets[j] will be updated to [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5].

Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

Example 1:

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] Output: true Explanation: Perform the following operations: - Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]] The target triplet [2,7,5] is now an element of triplets.

Example 2:

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5] Output: false Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.

Example 3:

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5] Output: true Explanation: Perform the following operations: - Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. - Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]]. The target triplet [5,5,5] is now an element of triplets.

Constraints:

  • 1 <= triplets.length <= 105

  • triplets[i].length == target.length == 3

  • 1 <= a_i_, b_i_, c_i_, x, y, z <= 1000

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
            good = set()

            for t in triplets:
                if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
                    continue
                for i, v in enumerate(t):
                    if v == target[i]:
                        good.add(i)
            return len(good) == 3
    ```
    **Explanation:**

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

88. Partition Labels (Leetcode:763)#

Problem Statement

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string is s.

Return a list of integers representing the size of these parts.

Example 1:

Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij".

Example 2:

Input: s = "eccbbbbdec" Output: [10]

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        count = {}
        res = []
        i, length = 0, len(S)
        for j in range(length):
            c = S[j]
            count[c] = j

        curLen = 0
        goal = 0
        while i < length:
            c = S[i]
            goal = max(goal, count[c])
            curLen += 1

            if goal == i:
                res.append(curLen)
                curLen = 0
            i += 1
        return res
Explanation:

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

89. Valid Parenthesis String (Leetcode:678)#

Problem Statement

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid**.

The following rules define a valid string:

  • Any left parenthesis '(' must have a corresponding right parenthesis ')'.

  • Any right parenthesis ')' must have a corresponding left parenthesis '('.

  • Left parenthesis '(' must go before the corresponding right parenthesis ')'.

  • '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

Input: s = "()" Output: true Example 2:

Input: s = "()" Output: true Example 3:*

Input: s = "())" Output:* true

Constraints:

  • 1 <= s.length <= 100

  • s[i] is '(', ')' or '*'.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    # Dynamic Programming: O(n^2)
    class Solution:
        def checkValidString(self, s: str) -> bool:
            dp = {(len(s), 0): True}  # key=(i, leftCount) -> isValid

            def dfs(i, left):
                if i == len(s) or left < 0:
                    return left == 0
                if (i, left) in dp:
                    return dp[(i, left)]

                if s[i] == "(":
                    dp[(i, left)] = dfs(i + 1, left + 1)
                elif s[i] == ")":
                    dp[(i, left)] = dfs(i + 1, left - 1)
                else:
                    dp[(i, left)] = (
                        dfs(i + 1, left + 1) or dfs(i + 1, left - 1) or dfs(i + 1, left)
                    )
                return dp[(i, left)]

            return dfs(0, 0)


    # Greedy: O(n)
    class Solution:
        def checkValidString(self, s: str) -> bool:
            leftMin, leftMax = 0, 0

            for c in s:
                if c == "(":
                    leftMin, leftMax = leftMin + 1, leftMax + 1
                elif c == ")":
                    leftMin, leftMax = leftMin - 1, leftMax - 1
                else:
                    leftMin, leftMax = leftMin - 1, leftMax + 1
                if leftMax < 0:
                    return False
                if leftMin < 0:  # required because -> s = ( * ) (
                    leftMin = 0
            return leftMin == 0
    ```
    **Explanation:**

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

Heap / Priority Queue#

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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:

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

91. Kth Largest Element in a Stream (Leetcode:703)#

Also in DSA Patterns

Kth Largest Element in a Stream — 15. Heaps (may include extra approaches and complexity analysis).

Problem Statement

You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.

You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores.

Implement the KthLargest class:

  • KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums.
  • int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.

Example 1:

Input: ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output: [null, 4, 5, 5, 8, 8] Explanation: KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8

Example 2:

Input: ["KthLargest", "add", "add", "add", "add"] [[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]] Output: [null, 7, 7, 7, 8] Explanation: KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]); kthLargest.add(2); // return 7 kthLargest.add(10); // return 7 kthLargest.add(9); // return 7 kthLargest.add(9); // return 8

Constraints:

  • 0 <= nums.length <= 104
  • 1 <= k <= nums.length + 1
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • At most 104 calls will be made to add.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        # minHeap w/ K largest integers
        self.minHeap, self.k = nums, k
        heapq.heapify(self.minHeap)
        while len(self.minHeap) > k:
            heapq.heappop(self.minHeap)

    def add(self, val: int) -> int:
        heapq.heappush(self.minHeap, val)
        if len(self.minHeap) > self.k:
            heapq.heappop(self.minHeap)
        return self.minHeap[0]
Explanation:

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

92. Kth Largest Element in an Array (Leetcode:215)#

Also in DSA Patterns

Kth Largest Element in an Array — 15. Heaps (may include extra approaches and complexity analysis).

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

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

Example 2:

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

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# Solution: Sorting
# Time Complexity:
#   - Best Case: O(n*log(k))
#   - Average Case: O(n*log(k))
#   - Worst Case:O(n*log(k))
# Extra Space Complexity: O(k)
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapify(nums)
        while len(nums) > k:
            heappop(nums)
        return nums[0]

# Solution: Sorting
# Time Complexity:
#   - Best Case: O(n)
#   - Average Case: O(n*log(n))
#   - Worst Case:O(n*log(n))
# Extra Space Complexity: O(n)
class Solution1:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[len(nums) - k]


# Solution: QuickSelect
# Time Complexity: O(n)
# Extra Space Complexity: O(n)
class Solution2:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        pivot = random.choice(nums)
        left = [num for num in nums if num > pivot]
        mid = [num for num in nums if num == pivot]
        right = [num for num in nums if num < pivot]

        length_left = len(left)
        length_right = len(right)
        length_mid = len(mid)
        if k <= length_left:
            return self.findKthLargest(left, k)
        elif k > length_left + length_mid:
            return self.findKthLargest(right, k - length_mid - length_left)
        else:
            return mid[0]
Explanation:

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

93. Last Stone Weight (Leetcode:1046)#

Also in DSA Patterns

Last Stone Weight — 15. Heaps (may include extra approaches and complexity analysis).

Problem Statement

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

Input: stones = [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1] Output: 1

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = [-s for s in stones]
        heapq.heapify(stones)

        while len(stones) > 1:
            first = heapq.heappop(stones)
            second = heapq.heappop(stones)
            if second > first:
                heapq.heappush(stones, first - second)

        stones.append(0)
        return abs(stones[0])

# There's a private _heapify_max method.
# https://github.com/python/cpython/blob/1170d5a292b46f754cd29c245a040f1602f70301/Lib/heapq.py#L198
class Solution(object):
    def lastStoneWeight(self, stones):
        heapq._heapify_max(stones)
        while len(stones) > 1:
            max_stone = heapq._heappop_max(stones)
            diff = max_stone - stones[0]
            if diff:
                heapq._heapreplace_max(stones, diff)
            else:
                heapq._heappop_max(stones)

        stones.append(0)
        return stones[0]
Explanation:

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

94. Merge k Sorted Lists (Leetcode:23)#

Also in DSA Patterns

Merge k Sorted Lists — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted linked list: 1->1->2->3->4->4->5->6

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists or len(lists) == 0:
            return None

        while len(lists) > 1:
            mergedLists = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                mergedLists.append(self.mergeList(l1, l2))
            lists = mergedLists
        return lists[0]

    def mergeList(self, l1, l2):
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        if l1:
            tail.next = l1
        if l2:
            tail.next = l2
        return dummy.next
Explanation:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def mergeKLists(self, lists: list[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None

        def merge_two(a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
            dummy = ListNode(0)
            tail = dummy
            while a and b:
                if a.val <= b.val:
                    tail.next = a
                    a = a.next
                else:
                    tail.next = b
                    b = b.next
                tail = tail.next
            tail.next = a or b
            return dummy.next

        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                merged.append(merge_two(lists[i], lists[i + 1] if i + 1 < len(lists) else None))
            lists = merged
        return lists[0]
Explanation:

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def 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:

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

Intervals#

96. Insert Interval (Leetcode:57)#

Also in DSA Patterns

Problem 2. Insert Interval — 04. Overlapping Intervals (may include extra approaches and complexity analysis).

Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti.
You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 10^5

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
                def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
                    answer = []
                    i, n = 0, len(intervals)

                    while i < n and newInterval[0] > intervals[i][0]:
                        answer.append(intervals[i])
                        i += 1

                    if not answer or answer[-1][1]<newInterval[0]:
                        answer.append(newInterval)
                    else:
                        answer[-1][1] = max(answer[-1][1], newInterval[1])

                    while i<n:
                        if answer[-1][1] < intervals[i][0]:
                            answer.append(intervals[i])
                        else:
                            answer[-1][1] = max(answer[-1][1], intervals[i][1])

                        i+=1
                    return answer
Explanation:

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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:

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

98. Meeting Rooms II (Leetcode:253)#

Also in DSA Patterns

Meeting Rooms II — 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], return the minimum number of conference rooms required.

Example 1:

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

Constraints:

  • 1 <= intervals.length <= 10^4
  • 0 <= starti < endi <= 10^6
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: the minimum number of conference rooms required
    """

    def minMeetingRooms(self, intervals):
        start = sorted([i[0] for i in intervals])
        end = sorted([i[1] for i in intervals])

        res, count = 0, 0
        s, e = 0, 0
        while s < len(intervals):
            if start[s] < end[e]:
                s += 1
                count += 1
            else:
                e += 1
                count -= 1
            res = max(res, count)
        return res
Explanation:

  1. Sort by start; min-heap stores end times of active meetings.
  2. Free room: Pop heap while smallest end <= current start.
  3. Push current end; heap size = rooms needed.
  4. O(n log n).
  5. Time complexity: O(n log n)
  6. Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        events = []
        for start, end in intervals:
            events.append((start, 1))
            events.append((end, -1))
        events.sort(key=lambda x: (x[0], x[1]))
        rooms = max_rooms = 0
        for _, delta in events:
            rooms += delta
            max_rooms = max(max_rooms, rooms)
        return max_rooms
Explanation:

  1. Events: +1 at start, -1 at end.
  2. Sort events; sweep counter of active meetings.
  3. Peak counter = minimum rooms.
  4. Same answer, event-based view.
  5. Time complexity: O(n log n)
  6. Space complexity: O(n)

99. Merge Intervals (Leetcode:56)#

Also in DSA Patterns

Problem 1. Merge Intervals — 04. Overlapping Intervals (may include extra approaches and complexity analysis).

Problem Statement

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

1 <= intervals.length <= 10^4 intervals[i].length == 2 0 <= starti <= endi <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda pair: pair[0])
        output = [intervals[0]]

        for start, end in intervals:
            lastEnd = output[-1][1]

            if start <= lastEnd:
                # merge
                output[-1][1] = max(lastEnd, end)
            else:
                output.append([start, end])
        return output
Explanation:

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

100. Minimum Interval to Include Each Query (Leetcode:1851)#

Also in DSA Patterns

Minimum Interval to Include Each Query — 00. Prefix Sum (may include extra approaches and complexity analysis).

Problem Statement

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] Output: [3,3,1,4] Explanation: The queries are processed as follows: - Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3. - Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3. - Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1. - Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22] Output: [2,-1,4,6] Explanation: The queries are processed as follows: - Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2. - Query = 19: None of the intervals contain 19. The answer is -1. - Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4. - Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

Constraints:

  • 1 <= intervals.length <= 105
  • 1 <= queries.length <= 105
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 107
  • 1 <= queries[j] <= 107
Code and Explanation 

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

            class Solution:
                def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
                    intervals.sort(key=lambda interval: interval[1] - interval[0])
                    sorted_queries = sorted((query, index) for index, query in enumerate(queries))

                    result = [-1] * len(queries)
                    min_heap = []
                    interval_index = 0

                    for query, query_index in sorted_queries:
                        while interval_index < len(intervals) and intervals[interval_index][0] <= query:
                            left, right = intervals[interval_index]
                            heapq.heappush(min_heap, (right - left + 1, right))
                            interval_index += 1

                        while min_heap and min_heap[0][1] < query:
                            heapq.heappop(min_heap)

                        if min_heap:
                            result[query_index] = min_heap[0][0]

                    return result
Explanation:

  1. Build the Prefix Sum Array:

Create a new array prefix where each element at index i stores the sum of elements from the start of the array up to index i:

prefix[0] = arr[0] prefix[1] = arr[0] + arr[1] prefix[2] = arr[0] + arr[1] + arr[2]

And so on…

Example:

For arr = [3, 1, 4, 1, 5, 9], the prefix_sum array is [3, 4, 8, 9, 14, 23]. 2. Answer Range Sum Queries:

To find the sum of elements between indices i and j, use:

sum(i, j) = prefix[j] - prefix[i-1]

Example:

For arr = [3, 1, 4, 1, 5, 9], the sum from index 2 to 4:

sum(2, 4) = prefix[4] - prefix[1] = 14 - 4 = 10. 3. Time: O(n) for building the prefix sum array, O(1) per query. 4. Space: O(n) for storing the prefix sum array. 5. NumArray(int[] nums) Initializes the object with the integer array nums.

101. Non-overlapping Intervals (Leetcode:435)#

Also in DSA Patterns

Non-overlapping Intervals — 04. Overlapping Intervals (may include extra approaches and complexity analysis).

Problem Statement

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        merged = [intervals[0]]

        for interval in intervals:
            if merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged
Explanation:

  1. Sort by end time.
  2. Keep track of last kept interval end.
  3. If overlap, increment removal count; else update end.
  4. Max non-overlapping = n - removals.
  5. Time complexity: O(n log n)
  6. Space complexity: O(1)

Linked List#

102. Add Two Numbers (Leetcode:2)#

Also in DSA Patterns

Add Two Numbers — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0] Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        cur = dummy

        carry = 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0

            # new digit
            val = v1 + v2 + carry
            carry = val // 10
            val = val % 10
            cur.next = ListNode(val)

            # update ptrs
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next
Explanation:

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

103. Copy List with Random Pointer (Leetcode:138)#

Also in DSA Patterns

Copy List with Random Pointer — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

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

Example 3:

Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]

Constraints:

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random is null or is pointing to some node in the linked list.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        oldToCopy = {None: None}

        cur = head
        while cur:
            copy = Node(cur.val)
            oldToCopy[cur] = copy
            cur = cur.next
        cur = head
        while cur:
            copy = oldToCopy[cur]
            copy.next = oldToCopy[cur.next]
            copy.random = oldToCopy[cur.random]
            cur = cur.next
        return oldToCopy[head]
Explanation:

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

104. Linked List Cycle (Leetcode:141)#

Also in DSA Patterns

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

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


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

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False
Explanation:

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

1
2
3
4
5
6
7
8
9
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False
Explanation:

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

105. Merge Two Sorted Lists (Leetcode:21)#

Also in DSA Patterns

Merge Two Sorted Lists (Recursive) — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:


Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.
Code and Explanation 

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

# Iterative
class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = node = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                node.next = list1
                list1 = list1.next
            else:
                node.next = list2
                list2 = list2.next
            node = node.next

        node.next = list1 or list2

        return dummy.next

# Recursive
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        lil, big = (list1, list2) if list1.val < list2.val else (list2, list1)
        lil.next = self.mergeTwoLists(lil.next, big)
        return lil
Explanation:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2
Explanation:

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

106. Remove Nth Node From End of List (Leetcode:19)#

Also in DSA Patterns

Remove Nth Node From End of List — 02. Fast and Slow Pointers (may include extra approaches and complexity analysis).

Problem Statement

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

The number of nodes in the list is sz.1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz`

**Follow up: ** Could you do this in one pass?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        left = dummy
        right = head

        while n > 0:
            right = right.next
            n -= 1

        while right:
            left = left.next
            right = right.next

        # delete
        left.next = left.next.next
        return dummy.next
Explanation:

  1. Dummy node handles deleting head edge case.
  2. Fast pointer is n+1 ahead of slow when fast hits end.
  3. Skip node after slow.
  4. One pass.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

107. Reorder List (Leetcode:143)#

Also in DSA Patterns

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

Problem Statement

You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → ... → Ln - 1 → Ln

Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

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

Example 2:

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

Constraints:

The number of nodes in the list is in the range [1, 5 * 10^4].
1 <= Node.val <= 1000

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        second = slow.next
        slow.next = None
        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2
Explanation:

  1. Step 1 — find middle with slow/fast pointers.
  2. Step 2 — reverse second half.
  3. Step 3 — merge alternating nodes from first and reversed second halves.
  4. O(n) time, O(1) space.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


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

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

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

1
2
3
4
5
6
7
8
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:

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

109. Reverse Nodes in k-Group (Leetcode:25)#

Also in DSA Patterns

Reverse Nodes in k-Group — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

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

Example 2:

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

Constraints:

  • The number of nodes in the list is n.
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0, head)
        groupPrev = dummy

        while True:
            kth = self.getKth(groupPrev, k)
            if not kth:
                break
            groupNext = kth.next

            # reverse group
            prev, curr = kth.next, groupPrev.next
            while curr != groupNext:
                tmp = curr.next
                curr.next = prev
                prev = curr
                curr = tmp

            tmp = groupPrev.next
            groupPrev.next = kth
            groupPrev = tmp
        return dummy.next

    def getKth(self, curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1
        return curr
Explanation:

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

Math & Geometry#

110. Detect Squares (Leetcode:2013)#

Also in DSA Patterns

Detect Squares — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

You are given a stream of points on the X-Y plane. Design an algorithm that:

  • Adds new points from the stream into a data structure. Duplicate points are allowed to be added more than once.
  • Counts the number of ways to form axis-aligned squares such that the point (x, y) belongs to the square and has an edge parallel to the X-axis.

Implement the DetectSquares class:

  • DetectSquares() Initializes the object with an empty data structure.
  • void add(int[] point) Adds a new point point = [x, y] to the data structure.
  • int count(int[] point) Counts the number of ways to form axis-aligned squares p belongs to.

Example 1:

Input:
["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
Output: [null, null, null, null, 1, 0, null, 2]

Constraints:

point.length == 2
0 <= x, y <= 1000
At most 3000 calls to add and count.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class DetectSquares:
    def __init__(self):
        self.ptsCount = defaultdict(int)
        self.pts = []

    def add(self, point: List[int]) -> None:
        self.ptsCount[tuple(point)] += 1
        self.pts.append(point)

    def count(self, point: List[int]) -> int:
        res = 0
        px, py = point
        for x, y in self.pts:
            if (abs(py - y) != abs(px - x)) or x == px or y == py:
                continue
            res += self.ptsCount[(x, py)] * self.ptsCount[(px, y)]
        return res
Explanation:

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

111. Multiply Strings (Leetcode:43)#

Problem Statement

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

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = "2", num2 = "3" Output: "6" Example 2:

Input: num1 = "123", num2 = "456" Output: "56088"

Constraints:

  • 1 <= num1.length, num2.length <= 200

  • num1 and num2 consist of digits only.

  • Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def multiply(self, num1: str, num2: str) -> str:
            if "0" in [num1, num2]:
                return "0"

            res = [0] * (len(num1) + len(num2))
            num1, num2 = num1[::-1], num2[::-1]
            for i1 in range(len(num1)):
                for i2 in range(len(num2)):
                    digit = int(num1[i1]) * int(num2[i2])
                    res[i1 + i2] += digit
                    res[i1 + i2 + 1] += res[i1 + i2] // 10
                    res[i1 + i2] = res[i1 + i2] % 10

            res, beg = res[::-1], 0
            while beg < len(res) and res[beg] == 0:
                beg += 1
            res = map(str, res[beg:])
            return "".join(res)
    ```
    **Explanation:**

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

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

113. Pow(x n) (Leetcode:50)#

Also in DSA Patterns

Pow(x, n) — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2⁻² = 1/2² = 1/4 = 0.25

Constraints:

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1
n is an integer.
Either x is not zero or n > 0.
-10^4 <= x^n <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def helper(x, n):
            if x == 0:
                return 0
            if n == 0:
                return 1

            res = helper(x * x, n // 2)
            return x * res if n % 2 else res

        res = helper(x, abs(n))
        return res if n >= 0 else 1 / res
Explanation:

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

114. Reverse Integer (Leetcode:7)#

Problem Statement

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123 Output: 321

Example 2:

Input: x = -123 Output: -321

Example 3:

Input: x = 120 Output: 21

Constraints:

  • -2^31 <= x <= 2^31 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reverse(self, x: int) -> int:
        # Integer.MAX_VALUE = 2147483647 (end with 7)
        # Integer.MIN_VALUE = -2147483648 (end with -8 )

        MIN = -2147483648  # -2^31,
        MAX = 2147483647  #  2^31 - 1

        res = 0
        while x:
            digit = int(math.fmod(x, 10))  # (python dumb) -1 %  10 = 9
            x = int(x / 10)  # (python dumb) -1 // 10 = -1

            if res > MAX // 10 or (res == MAX // 10 and digit > MAX % 10):
                return 0
            if res < MIN // 10 or (res == MIN // 10 and digit < MIN % 10):
                return 0
            res = (res * 10) + digit

        return res
Explanation:

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

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

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

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

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

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

Matrix#

115. Rotate Image (Leetcode:48)#

Also in DSA Patterns

Rotate Image — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise in place.

Example 1:

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

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        l, r = 0, len(matrix) - 1
        while l < r:
            for i in range(r - l):
                top, bottom = l, r

                # save the topleft
                topLeft = matrix[top][l + i]

                # move bottom left into top left
                matrix[top][l + i] = matrix[bottom - i][l]

                # move bottom right into bottom left
                matrix[bottom - i][l] = matrix[bottom][r - i]

                # move top right into bottom right
                matrix[bottom][r - i] = matrix[top + i][r]

                # move top left into top right
                matrix[top + i][r] = topLeft
            r -= 1
            l += 1
Explanation:

  1. Transpose across diagonal swaps [i][j] with [j][i].
  2. Reverse each row for 90° clockwise rotation.
  3. In-place O(n²).
  4. Time complexity: O(n²)
  5. Space complexity: O(1)

116. Set Matrix Zeroes (Leetcode:73)#

Also in DSA Patterns

Set Matrix Zeroes — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Example 1:

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

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        # O(1)
        ROWS, COLS = len(matrix), len(matrix[0])
        rowZero = False

        # determine which rows/cols need to be zero
        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == 0:
                    matrix[0][c] = 0
                    if r > 0:
                        matrix[r][0] = 0
                    else:
                        rowZero = True

        for r in range(1, ROWS):
            for c in range(1, COLS):
                if matrix[0][c] == 0 or matrix[r][0] == 0:
                    matrix[r][c] = 0

        if matrix[0][0] == 0:
            for r in range(ROWS):
                matrix[r][0] = 0

        if rowZero:
            for c in range(COLS):
                matrix[0][c] = 0
Explanation:

  1. Use first row/col as flags for zero rows/columns.
  2. Remember if first row/col themselves had zeros.
  3. Mark from inner cells, apply marks, fix first row/col last.
  4. O(mn) time, O(1) space.
  5. Time complexity: O(m × n)
  6. Space complexity: O(1)

117. Spiral Matrix (Leetcode:54)#

Also in DSA Patterns

Spiral Matrix — 21. Math and Geometry (may include extra approaches and complexity analysis).

Problem Statement

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

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

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        left, right = 0, len(matrix[0])
        top, bottom = 0, len(matrix)

        while left < right and top < bottom:
            # get every i in the top row
            for i in range(left, right):
                res.append(matrix[top][i])
            top += 1
            # get every i in the right col
            for i in range(top, bottom):
                res.append(matrix[i][right - 1])
            right -= 1
            if not (left < right and top < bottom):
                break
            # get every i in the bottom row
            for i in range(right - 1, left - 1, -1):
                res.append(matrix[bottom - 1][i])
            bottom -= 1
            # get every i in the left col
            for i in range(bottom - 1, top - 1, -1):
                res.append(matrix[i][left])
            left += 1

        return res
Explanation:

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

118. Valid Sudoku (Leetcode:36)#

Problem Statement

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  • Each row must contain the digits 1-9 without repetition.

  • Each column must contain the digits 1-9 without repetition.

  • Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.

  • Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] Output: true

Example 2:

Input: board = [["8","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

  • board.length == 9

  • board[i].length == 9

  • board[i][j] is a digit 1-9 or '.'.

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def isValidSudoku(self, board: List[List[str]]) -> bool:
            cols = collections.defaultdict(set)
            rows = collections.defaultdict(set)
            squares = collections.defaultdict(set)  # key = (r /3, c /3)

            for r in range(9):
                for c in range(9):
                    if board[r][c] == ".":
                        continue
                    if (
                        board[r][c] in rows[r]
                        or board[r][c] in cols[c]
                        or board[r][c] in squares[(r // 3, c // 3)]
                    ):
                        return False
                    cols[c].add(board[r][c])
                    rows[r].add(board[r][c])
                    squares[(r // 3, c // 3)].add(board[r][c])

            return True
    ```
    **Explanation:**

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

Sliding Window#

119. Longest Repeating Character Replacement (Leetcode:424)#

Problem Statement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def characterReplacement(s, k):
                freq = [0] * 26
                left = 0
                max_freq = 0
                ans = 0

                for right in range(len(s)):
                    freq[ord(s[right]) - ord('A')] += 1
                    max_freq = max(max_freq, freq[ord(s[right]) - ord('A')])

                    while (right - left + 1) - max_freq > k:
                        freq[ord(s[left]) - ord('A')] -= 1
                        left += 1

                    ans = max(ans, right - left + 1)

                return ans
Explanation:

  1. Window valid if length - count(most_frequent_char) <= k.
  2. Expand right; shrink left while invalid.
  3. Track best window size.
  4. Time complexity: O(n)
  5. Space complexity: O(1)

120. Longest Substring Without Repeating Characters (Leetcode:3)#

Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with length 3.

Constraints:

  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols and spaces
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = best = 0
        for right, ch in enumerate(s):
            if ch in last_seen and last_seen[ch] >= left:
                left = last_seen[ch] + 1
            last_seen[ch] = right
            best = max(best, right - left + 1)
        return best
Explanation:

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

121. Minimum Window Substring (Leetcode:76)#

Also in DSA Patterns

Minimum Window Substring — 03. Sliding Window (may include extra approaches and complexity analysis).

Problem Statement

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window.

Example 3:

nput: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length n == t.length 1 <= m, n <= 105 s and t consist of uppercase and lowercase English letters.

Follow up:

Could you find an algorithm that runs in O(m + n) time?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t):
            return ""

        need: dict[str, int] = {}
        for ch in t:
            need[ch] = need.get(ch, 0) + 1

        have = 0
        required = len(need)
        window: dict[str, int] = {}
        res = (-1, -1)
        res_len = float("inf")
        left = 0

        for right, ch in enumerate(s):
            window[ch] = window.get(ch, 0) + 1
            if ch in need and window[ch] == need[ch]:
                have += 1

            while have == required:
                if (right - left + 1) < res_len:
                    res = (left, right)
                    res_len = right - left + 1
                window[s[left]] -= 1
                if s[left] in need and window[s[left]] < need[s[left]]:
                    have -= 1
                left += 1

        left, right = res
        return s[left : right + 1] if res_len != float("inf") else
Explanation:

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

122. Permutation in String (Leetcode:567)#

Also in DSA Patterns

Permutation in String — 03. Sliding Window (may include extra approaches and complexity analysis).

Problem Statement

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

1 <= s1.length, s2.length <= 10^4
s1 and s2 consist of lowercase English letters.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        s1Count, s2Count = [0] * 26, [0] * 26
        for i in range(len(s1)):
            s1Count[ord(s1[i]) - ord("a")] += 1
            s2Count[ord(s2[i]) - ord("a")] += 1

        matches = 0
        for i in range(26):
            matches += 1 if s1Count[i] == s2Count[i] else 0

        l = 0
        for r in range(len(s1), len(s2)):
            if matches == 26:
                return True

            index = ord(s2[r]) - ord("a")
            s2Count[index] += 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] + 1 == s2Count[index]:
                matches -= 1

            index = ord(s2[l]) - ord("a")
            s2Count[index] -= 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] - 1 == s2Count[index]:
                matches -= 1
            l += 1
        return matches == 26
Explanation:

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

123. Sliding Window Maximum (Leetcode:239)#

Also in DSA Patterns

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

Problem Statement

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window.
Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position Max
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

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

Constraints:

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

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        output = []
        q = collections.deque()  # index
        l = r = 0
        # O(n) O(n)
        while r < len(nums):
            # pop smaller values from q
            while q and nums[q[-1]] < nums[r]:
                q.pop()
            q.append(r)

            # remove left val from window
            if l > q[0]:
                q.popleft()

            if (r + 1) >= k:
                output.append(nums[q[0]])
                l += 1
            r += 1

        return output
Explanation:

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

Stack#

124. Car Fleet (Leetcode:853)#

Problem Statement

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer arrays position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A car fleet is a single car or a group of cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.

Return the number of car fleets that will arrive at the destination.

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Output: 3

Explanation:

  • The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at target.

  • The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.

  • The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Example 2:

Input: target = 10, position = [3], speed = [3]

Output: 1

Explanation:

There is only one car, hence there is only one fleet.

Example 3:

Input: target = 100, position = [0,2,4], speed = [4,2,1]

Output: 1

Explanation:

  • The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The car starting at 4 (speed 1) travels to 5.

  • Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Constraints:

  • n == position.length == speed.length

  • 1 <= n <= 105

  • 0 < target <= 106

  • 0 <= position[i] < target

  • All the values of position are unique.

  • 0 < speed[i] <= 106

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    class Solution:
        def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
            pair = [(p, s) for p, s in zip(position, speed)]
            pair.sort(reverse=True)
            stack = []
            for p, s in pair:  # Reverse Sorted Order
                stack.append((target - p) / s)
                if len(stack) >= 2 and stack[-1] <= stack[-2]:
                    stack.pop()
            return len(stack)
    ```
    **Explanation:**

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

125. Daily Temperatures (Leetcode:739)#

Also in DSA Patterns

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

Problem Statement

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60] Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90] Output: [1,1,0]

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []  # pair: [temp, index]

        for i, t in enumerate(temperatures):
            while stack and t > stack[-1][0]:
                stackT, stackInd = stack.pop()
                res[stackInd] = i - stackInd
            stack.append((t, i))
        return res
Explanation:

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

126. Evaluate Reverse Polish Notation (Leetcode:150)#

Also in DSA Patterns

Evaluate Reverse Polish Notation — 08. Stack (may include extra approaches and complexity analysis).

Problem Statement

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

  • The valid operators are '+', '-', '*', and '/'.
  • Each operand may be an integer or another expression.
  • The division between two integers always truncates toward zero.
  • There will not be any division by zero.
  • The input represents a valid arithmetic expression in a reverse polish notation.
  • The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

Constraints:

  • 1 <= tokens.length <= 104
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for c in tokens:
            if c == "+":
                stack.append(stack.pop() + stack.pop())
            elif c == "-":
                a, b = stack.pop(), stack.pop()
                stack.append(b - a)
            elif c == "*":
                stack.append(stack.pop() * stack.pop())
            elif c == "/":
                a, b = stack.pop(), stack.pop()
                stack.append(int(float(b) / a))
            else:
                stack.append(int(c))
        return stack[0]
Explanation:

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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:

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

128. Valid Parentheses (Leetcode:20)#

Also in DSA Patterns

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

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()" Output: true

Example 2:

Input: s = "()[]{}" Output: true

Example 3:

Input: s = "(]" Output: false

Example 4:

Input: s = "([])" Output: true

Example 5:

Input: s = "([)]" Output: false

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isValid(self, s: str) -> bool:
        bracketMap = {")": "(", "]": "[", "}": "{"}
        stack = []

        for c in s:
            if c not in bracketMap:
                stack.append(c)
                continue
            if not stack or stack[-1] != bracketMap[c]:
                return False
            stack.pop()

        return not stack
Explanation:

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

Trees#

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# 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:

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

130. Binary Tree Level Order Traversal (Leetcode:102)#

Also in DSA Patterns

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

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

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

Example 2:

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

Example 3:

Input: root = [] Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
Code and Explanation 

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


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        q = collections.deque()
        if root:
            q.append(root)

        while q:
            val = []

            for i in range(len(q)):
                node = q.popleft()
                val.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(val)
        return res
Explanation:

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

131. Binary Tree Maximum Path Sum (Leetcode:124)#

Also in DSA Patterns

Maximum Path Sum in Binary Tree — 13. Dynamic Programming (may include extra approaches and complexity analysis).

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can only appear at most once. The path sum is the sum of the node values. Given the root, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3] Output: 6 Explanation: Optimal path is 2 -> 1 -> 3 with sum 6.

Constraints:

  • The number of nodes is in the range [1, 3 * 10^4]
  • -1000 <= Node.val <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        res = [root.val]

        # return max path sum without split
        def dfs(root):
            if not root:
                return 0

            leftMax = dfs(root.left)
            rightMax = dfs(root.right)
            leftMax = max(leftMax, 0)
            rightMax = max(rightMax, 0)

            # compute max path sum WITH split
            res[0] = max(res[0], root.val + leftMax + rightMax)
            return root.val + max(leftMax, rightMax)

        dfs(root)
        return res[0]
Explanation:

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

132. Binary Tree Right Side View (Leetcode:199)#

Also in DSA Patterns

Binary Tree Right Side View — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Example 2:

Example 3:

Example 4:

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        res = []
        q = collections.deque([root])

        while q:
            rightSide = None
            qLen = len(q)

            for i in range(qLen):
                node = q.popleft()
                if node:
                    rightSide = node
                    q.append(node.left)
                    q.append(node.right)
            if rightSide:
                res.append(rightSide.val)
        return res
Explanation:

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

133. Construct Binary Tree from Preorder and Inorder Traversal (Leetcode:105)#

Also in DSA Patterns

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

Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

Constraints:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values
  • Each value appears once in both arrays
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        in_index = {val: i for i, val in enumerate(inorder)}
        pre_idx = 0

        def helper(left: int, right: int) -> Optional[TreeNode]:
            nonlocal pre_idx
            if left > right:
                return None
            root_val = preorder[pre_idx]
            pre_idx += 1
            root = TreeNode(root_val)
            mid = in_index[root_val]
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

        return helper(0, len(inorder) - 1)
Explanation:

  1. Precompute inorder positions: Build in_index = {value: index} from inorder. When we pick a root from preorder, this map instantly tells us where that value splits the inorder array into left and right parts.
  2. Shared preorder pointer: pre_idx reads roots in preorder order (root → left subtree → right subtree). Each recursive call consumes exactly one preorder value — that value is always the root of the subtree being built.
  3. Recurse on index ranges, not slices: helper(left, right) builds the tree for the inorder segment [left..right]. If left > right, the segment is empty → return None.
  4. Split using the root's inorder index: After creating root from preorder[pre_idx], look up mid = in_index[root_val]. Left subtree covers inorder indices [left, mid-1]; right covers [mid+1, right]. No list copying.
  5. Why this is optimal: Each node is visited once with O(1) hash lookups — no repeated slicing or .index() calls.
  6. Time complexity: O(n)
  7. Space complexity: O(n)

1
2
3
4
5
6
7
8
9
class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
        return root
Explanation:

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

134. Count Good Nodes in Binary Tree (Leetcode:1448)#

Problem Statement

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example 1:

Input: root = [3,1,4,3,null,1,5] Output: 4 Explanation: Nodes in blue are good. Root Node (3) is always a good node. Node 4 -> (3,4) is the maximum value in the path starting from the root. Node 5 -> (3,4,5) is the maximum value in the path Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2] Output: 3 Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1] Output: 1 Explanation: Root is considered as good.

Constraints:

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

  • Each node's value is between [-10^4, 10^4].

Code and Explanation 
=== "Optimal"
    ```python linenums="1"
    # 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 goodNodes(self, root: TreeNode) -> int:
            def dfs(node, maxVal):
                if not node:
                    return 0

                res = 1 if node.val >= maxVal else 0
                maxVal = max(maxVal, node.val)
                res += dfs(node.left, maxVal)
                res += dfs(node.right, maxVal)
                return res

            return dfs(root, root.val)
    ```
    **Explanation:**

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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:

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

136. Invert Binary Tree (Leetcode:226)#

Also in DSA Patterns

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

Problem Statement

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        # swap the children
        root.left, root.right = root.right, root.left

        # make 2 recursive calls
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
Explanation:

  1. Swap left and right at each node recursively.
  2. Post-order: invert children then assign.
  3. Time complexity: O(n)
  4. Space complexity: O(h)

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


class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        queue = deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root
Explanation:

  1. Queue nodes; swap children when dequeuing.
  2. Enqueue swapped children for later processing.
  3. Time complexity: O(n)
  4. Space complexity: O(n)

137. Kth Smallest Element in a BST (Leetcode:230)#

Also in DSA Patterns

Kth Smallest Element in a BST — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

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

Constraints:

  • The number of nodes is n where 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        curr = root

        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
            curr = curr.right
Explanation:

  1. Push left spine onto stack.
  2. Pop, visit, go right.
  3. Stop at kth pop.
  4. Time complexity: O(h + k)
  5. Space complexity: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.count = 0
        self.result = 0

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left)
            self.count += 1
            if self.count == k:
                self.result = node.val
                return
            inorder(node.right)

        inorder(root)
        return self.result
Explanation:

  1. Inorder visits BST in sorted order.
  2. Increment count on visit; return at k.
  3. Time complexity: O(h + k)
  4. Space complexity: O(h)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, 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:

  1. Both targets smaller → go left; both larger → go right.
  2. Otherwise current node is LCA.
  3. Uses BST ordering — no full tree search.
  4. Time complexity: O(h)
  5. Space complexity: O(1)

1
2
3
4
5
6
7
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:

  1. Same BST logic recursively.
  2. Recurse left or right based on values vs root.
  3. Return node where paths diverge.
  4. Time complexity: O(h)
  5. Space complexity: O(h)

139. Maximum Depth of Binary Tree (Leetcode:104)#

Also in DSA Patterns

Maximum Depth of Binary Tree — 16. Tree (may include extra approaches and complexity analysis).

Problem Statement

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root down to the farthest leaf.

Example 1:

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

Constraints:

  • The number of nodes is in the range [0, 10^4]
  • -100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# RECURSIVE DFS
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))


# ITERATIVE DFS
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        stack = [[root, 1]]
        res = 0

        while stack:
            node, depth = stack.pop()

            if node:
                res = max(res, depth)
                stack.append([node.left, depth + 1])
                stack.append([node.right, depth + 1])
        return res


# BFS
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        q = deque()
        if root:
            q.append(root)

        level = 0

        while q:

            for i in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return level
Explanation:

  1. Base case: Empty node → depth 0.
  2. Recurse on children; return 1 + max(left, right).
  3. Simple post-order height computation.
  4. Time complexity: O(n)
  5. Space complexity: O(h)

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


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        depth = 0
        queue = deque([root])
        while queue:
            depth += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return depth
Explanation:

  1. Queue level-order traversal.
  2. Increment depth after processing each level's nodes.
  3. Avoids recursion depth limits.
  4. Time complexity: O(n)
  5. Space complexity: O(n)

140. Same Tree (Leetcode:100)#

Also in DSA Patterns

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

Problem Statement

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two trees are the same if they are structurally identical and nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3] Output: true

Constraints:

  • The number of nodes is in the range [0, 100]
  • -10^4 <= Node.val <= 10^4
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if p and q and p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False
Explanation:

  1. Both null → true; one null → false.
  2. Values must match; recurse on both children.
  3. Time complexity: O(n)
  4. Space complexity: O(h)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def 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:

  1. At each node in root, test if subtree matches subRoot.
  2. same() compares structure and values.
  3. DFS left/right if no match here.
  4. Time complexity: O(m × n)
  5. Space complexity: O(h)

142. Validate Binary Search Tree (Leetcode:98)#

Also in DSA Patterns

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

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree only nodes with keys greater than the node's key.

Example 1:

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

Constraints:

  • The number of nodes is in the range [1, 10^4]
  • -2^31 <= Node.val <= 2^31 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def valid(node, left, right):
            if not node:
                return True
            if not (left < node.val < right):
                return False

            return valid(node.left, left, node.val) and valid(
                node.right, node.val, right
            )

        return valid(root, float("-inf"), float("inf"))
Explanation:

  1. Pass valid (min, max) range down recursion.
  2. Node must satisfy min < val < max.
  3. Left child max becomes current val; right child min becomes current val.
  4. Time complexity: O(n)
  5. Space complexity: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = float('-inf')

        def inorder(node: Optional[TreeNode]) -> bool:
            nonlocal prev
            if not node:
                return True
            if not inorder(node.left):
                return False
            if node.val <= prev:
                return False
            prev = node.val
            return inorder(node.right)

        return inorder(root)
Explanation:

  1. BST inorder is strictly increasing.
  2. Track previous visited value.
  3. Invalid if current <= prev.
  4. Time complexity: O(n)
  5. Space complexity: O(h)

Tries#

143. Design Add and Search Words Data Structure (Leetcode:211)#

Also in DSA Patterns

Add and Search Word — 19. Tries (may include extra approaches and complexity analysis).

Problem Statement

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true] Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class TrieNode:
    def __init__(self):
        self.children = {}  # a : TrieNode
        self.word = False


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

    def addWord(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.word = True

    def search(self, word: str) -> bool:
        def dfs(j, root):
            cur = root

            for i in range(j, len(word)):
                c = word[i]
                if c == ".":
                    for child in cur.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if c not in cur.children:
                        return False
                    cur = cur.children[c]
            return cur.word

        return dfs(0, self.root)
Explanation:

  1. Insert words into trie normally.
  2. Search: on '.', try all children recursively.
  3. Match succeeds at end-of-word flag.
  4. Time complexity: O(26^L) worst
  5. Space complexity: O(total chars)

144. Implement Trie (Prefix Tree) (Leetcode:208)#

Also in DSA Patterns

Implement Trie (Prefix Tree) — 19. Tries (may include extra approaches and complexity analysis).

Problem Statement

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true]

Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

Constraints:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.end = False


class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        curr = self.root
        for c in word:
            i = ord(c) - ord("a")
            if curr.children[i] is None:
                curr.children[i] = TrieNode()
            curr = curr.children[i]
        curr.end = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        curr = self.root
        for c in word:
            i = ord(c) - ord("a")
            if curr.children[i] is None:
                return False
            curr = curr.children[i]
        return curr.end

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        curr = self.root
        for c in prefix:
            i = ord(c) - ord("a")
            if curr.children[i] is None:
                return False
            curr = curr.children[i]
        return True
Explanation:

  1. Each node has char → child map and end flag.
  2. insert walks/creates path; search requires end flag; startsWith only needs path.
  3. Time complexity: O(L) per op
  4. Space complexity: O(total chars)

145. Word Search II (Leetcode:212)#

Also in DSA Patterns

Word Search II — 19. Tries (may include extra approaches and complexity analysis).

Problem Statement

Given an m x n board of characters and a list of strings words, return all words on the board.

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

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.
Code and Explanation 

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

    def addWord(self, word):
        cur = self
        cur.refs += 1
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
            cur.refs += 1
        cur.isWord = True

    def removeWord(self, word):
        cur = self
        cur.refs -= 1
        for c in word:
            if c in cur.children:
                cur = cur.children[c]
                cur.refs -= 1


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for w in words:
            root.addWord(w)

        ROWS, COLS = len(board), len(board[0])
        res, visit = set(), set()

        def dfs(r, c, node, word):
            if (
                r not in range(ROWS) 
                or c not in range(COLS)
                or board[r][c] not in node.children
                or node.children[board[r][c]].refs < 1
                or (r, c) in visit
            ):
                return

            visit.add((r, c))
            node = node.children[board[r][c]]
            word += board[r][c]
            if node.isWord:
                node.isWord = False
                res.add(word)
                root.removeWord(word)

            dfs(r + 1, c, node, word)
            dfs(r - 1, c, node, word)
            dfs(r, c + 1, node, word)
            dfs(r, c - 1, node, word)
            visit.remove((r, c))

        for r in range(ROWS):
            for c in range(COLS):
                dfs(r, c, root, "")

        return list(res)
Explanation:

  1. Build trie of all words.
  2. DFS board while walking trie; prune when prefix missing.
  3. Collect word at trie node; mark found to dedupe.
  4. Time complexity: O(m × n × 4^L)
  5. Space complexity: O(total chars)

Two Pointers#

146. 3Sum (Leetcode:15)#

Also in DSA Patterns

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

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: The distinct triplets are [-1,0,1] and [-1,-1,2].

Example 2:

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

Example 3:

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

Constraints:

3 <= nums.length <= 3000 -10^5 <= nums[i] <= 10^5

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def threeSum(nums):
                nums.sort()
                res = []

                for i in range(len(nums) - 2):
                    # Skip duplicates for i
                    if i > 0 and nums[i] == nums[i - 1]:
                        continue

                    left = i + 1
                    right = len(nums) - 1

                    while left < right:
                        curr_sum = nums[i] + nums[left] + nums[right]

                        if curr_sum == 0:
                            res.append([nums[i], nums[left], nums[right]])
                            # Skip duplicates for left and right
                            while left < right and nums[left] == nums[left + 1]:
                                left += 1
                            while left < right and nums[right] == nums[right - 1]:
                                right -= 1

                            left += 1
                            right -= 1

                        elif curr_sum < 0:
                            left += 1
                        else:
                            right -= 1

                return res
Explanation:

  1. Sort first: Enables two-pointer search and duplicate skipping.
  2. Fix one number at i: Set left = i+1, right = n-1, find pairs summing to -nums[i].
  3. Skip duplicates: After finding a triplet or advancing i, skip equal values.
  4. Time complexity: O(n²)
  5. Space complexity: O(1)

147. Container With Most Water (Leetcode:11)#

Also in DSA Patterns

Container With Most Water — 01. Two Pointers (may include extra approaches and complexity analysis).

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The max area of water the container can contain is 49.

Example 2:

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

Constraints:

n == height.length 2 <= n <= 10^5 0 <= height[i] <= 10^4

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0

        while left < right:
            h = min(height[left], height[right])
            w = right - left
            max_area = max(max_area, h * w)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area
Explanation:

  1. Start wide: left = 0, right = n-1.
  2. Area formula: Height = min(height[left], height[right]); width = right - left.
  3. Move shorter side: Advance the pointer at the shorter wall to seek more area.
  4. Why: Keeping the shorter side fixes the height cap. O(n) time.
  5. Time complexity: O(n)
  6. Space complexity: O(1)

148. Trapping Rain Water (Leetcode:42)#

Also in DSA Patterns

Trapping Rain Water — 08. Stack (may include extra approaches and complexity analysis).

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        l, r = 0, len(height) - 1
        leftMax, rightMax = height[l], height[r]
        res = 0
        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
        return res
Explanation:

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

149. Two Sum II - Input Array Is Sorted (Leetcode:167)#

Problem Statement

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers index1 and index2, each incremented by one, as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1

        while l < r:
            curSum = numbers[l] + numbers[r]

            if curSum > target:
                r -= 1
            elif curSum < target:
                l += 1
            else:
                return [l + 1, r + 1]
Explanation:

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

150. Valid Palindrome (Leetcode:125)#

Also in DSA Patterns

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

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True
Explanation:

  1. Move inward skipping non-alphanumeric.
  2. Compare lowercased chars.
  3. O(n) time, O(1) space.
  4. Time complexity: O(n)
  5. Space complexity: O(1)