Skip to content

Blind 75#

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

Explore overlaps

Compare this sheet with others in the DSA Venn Explorer.

How to use

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Dynamic Programming#

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

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

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

24. Combination Sum IV (Leetcode:377)#

Problem Statement

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

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

Example 1:

Input: nums = [1,2,3], target = 4 Output: 7 Explanation: The possible combination ways are: (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 3), (2, 1, 1), (2, 2), (3, 1)

Example 2:

Input: nums = [9], target = 3 Output: 0

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • All the elements of nums are unique.
  • 1 <= target <= 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 combinationSum4(self, nums: List[int], target: int) -> int:
        cache = {0: 1}

        for total in range(1, target + 1):
            cache[total] = 0
            for n in nums:
                cache[total] += cache.get(total - n, 0)
        return cache[target]

        def dfs(total):
            if total == target:
                return 1
            if total > target:
                return 0
            if total in cache:
                return cache[total]

            cache[total] = 0
            for n in nums:
                cache[total] += dfs(total + n)
            return cache[total]

        return dfs(0)
Explanation:

  1. Use bottom-up dynamic programming where dp[i] counts combinations summing to i.
  2. Initialize dp[0] = 1 because one empty combination forms sum zero.
  3. For each total, add combinations from every coin that can contribute to it.

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

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

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

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

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

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

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

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

33. 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²)

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

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

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

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

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

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

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

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

Heap / Priority Queue#

42. Merge k Sorted Lists (Leetcode:23)#

Also in DSA Patterns

Merge k Sorted Lists — 07. Linked List (may include extra approaches and complexity analysis).

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted linked list: 1->1->2->3->4->4->5->6

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists or len(lists) == 0:
            return None

        while len(lists) > 1:
            mergedLists = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                mergedLists.append(self.mergeList(l1, l2))
            lists = mergedLists
        return lists[0]

    def mergeList(self, l1, l2):
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        if l1:
            tail.next = l1
        if l2:
            tail.next = l2
        return dummy.next
Explanation:

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

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

        def merge_two(a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
            dummy = ListNode(0)
            tail = dummy
            while a and b:
                if a.val <= b.val:
                    tail.next = a
                    a = a.next
                else:
                    tail.next = b
                    b = b.next
                tail = tail.next
            tail.next = a or b
            return dummy.next

        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                merged.append(merge_two(lists[i], lists[i + 1] if i + 1 < len(lists) else None))
            lists = merged
        return lists[0]
Explanation:

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

Intervals#

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

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

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

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

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

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

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

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

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

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

Matrix#

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

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

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

Sliding Window#

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

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

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

Stack#

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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