Daniel P. Gleason

Category: LeetCode Solutions

  • LeetCode 42: Trapping Rain Water — Python Solution

    Solve LeetCode 42: Trapping Rain Water in Python with a two pointers with bounded sides approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyHard
    TopicArray / String
    Reusable patterntwo pointers with bounded sides
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Move the side with the lower current maximum. That lower boundary already determines how much water can be trapped at its pointer.

    Algorithm

    1. Move the side with the lower current maximum. That lower boundary already determines how much water can be trapped at its pointer.
    2. Maintain this invariant: Processed positions have their final water amount because their limiting boundary is known.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def trap(self, height):
        left, right = 0, len(height) - 1
        left_max = right_max = water = 0
        while left <= right:
            if left_max <= right_max:
                left_max = max(left_max, height[left])
                water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                water += right_max - height[right]
                right -= 1
        return water

    Why this is correct

    The proof follows the maintained state: Processed positions have their final water amount because their limiting boundary is known. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(1) extra space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Fewer than three bars trap nothing; equal-height walls are handled by either side.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 135. Candy · Next: 13. Roman to Integer

  • LeetCode 13: Roman to Integer — Python Solution

    Solve LeetCode 13: Roman to Integer in Python with a look-ahead parsing approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyEasy
    TopicArray / String
    Reusable patternlook-ahead parsing
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Add a symbol unless it is smaller than the following symbol, in which case subtract it.

    Algorithm

    1. Add a symbol unless it is smaller than the following symbol, in which case subtract it.
    2. Maintain this invariant: The running total equals the value of every fully resolved symbol in the prefix.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def romanToInt(self, s):
        values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        total = 0
        for i, symbol in enumerate(s):
            value = values[symbol]
            total += -value if i + 1 < len(s) and value < values[s[i + 1]] else value
        return total

    Why this is correct

    The proof follows the maintained state: The running total equals the value of every fully resolved symbol in the prefix. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(1) extra space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    The final symbol is always added; subtractive pairs are resolved by the look-ahead rule.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 42. Trapping Rain Water · Next: 12. Integer to Roman

  • LeetCode 12: Integer to Roman — Python Solution

    Solve LeetCode 12: Integer to Roman in Python with a greedy token emission approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicArray / String
    Reusable patterngreedy token emission
    ComplexityO(1) time and O(1) extra space for the bounded Roman range

    What the problem is testing

    Iterate Roman tokens from largest to smallest, including subtractive forms, and emit each token as many times as it fits.

    Algorithm

    1. Iterate Roman tokens from largest to smallest, including subtractive forms, and emit each token as many times as it fits.
    2. Maintain this invariant: After each token, the output encodes the consumed value and the remainder is smaller than that token.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def intToRoman(self, num):
        tokens = [(1000,"M"),(900,"CM"),(500,"D"),(400,"CD"),(100,"C"),(90,"XC"),
                  (50,"L"),(40,"XL"),(10,"X"),(9,"IX"),(5,"V"),(4,"IV"),(1,"I")]
        output = []
        for value, symbol in tokens:
            count, num = divmod(num, value)
            output.append(symbol * count)
        return "".join(output)

    Why this is correct

    The proof follows the maintained state: After each token, the output encodes the consumed value and the remainder is smaller than that token. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(1) time and O(1) extra space for the bounded Roman range. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Subtractive values such as 4, 9, 40, and 900 must precede their component symbols.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 13. Roman to Integer · Next: 58. Length of Last Word

  • LeetCode 58: Length of Last Word — Python Solution

    Solve LeetCode 58: Length of Last Word in Python with a reverse scan approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyEasy
    TopicArray / String
    Reusable patternreverse scan
    ComplexityO(n) worst-case time and O(1) extra space

    What the problem is testing

    Skip trailing spaces, then count characters until the next space or the beginning.

    Algorithm

    1. Skip trailing spaces, then count characters until the next space or the beginning.
    2. Maintain this invariant: Once trailing spaces are skipped, every counted character belongs to the final word.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def lengthOfLastWord(self, s):
        i = len(s) - 1
        while i >= 0 and s[i] == " ":
            i -= 1
        end = i
        while i >= 0 and s[i] != " ":
            i -= 1
        return end - i

    Why this is correct

    The proof follows the maintained state: Once trailing spaces are skipped, every counted character belongs to the final word. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) worst-case time and O(1) extra space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    There may be several trailing spaces or only one word.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 12. Integer to Roman · Next: 14. Longest Common Prefix

  • LeetCode 14: Longest Common Prefix — Python Solution

    Solve LeetCode 14: Longest Common Prefix in Python with a vertical character scan approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyEasy
    TopicArray / String
    Reusable patternvertical character scan
    ComplexityO(total compared characters) time and O(1) extra space

    What the problem is testing

    Compare characters column by column against the first string and stop at the first missing or different character.

    Algorithm

    1. Compare characters column by column against the first string and stop at the first missing or different character.
    2. Maintain this invariant: Every character before the current column matches in all strings.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        for i, char in enumerate(strs[0]):
            if any(i == len(word) or word[i] != char for word in strs[1:]):
                return strs[0][:i]
        return strs[0]

    Why this is correct

    The proof follows the maintained state: Every character before the current column matches in all strings. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(total compared characters) time and O(1) extra space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    An empty list or an empty string yields an empty prefix.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 58. Length of Last Word · Next: 151. Reverse Words in a String

  • LeetCode 45: Jump Game II — Python Solution

    Solve LeetCode 45: Jump Game II in Python with a greedy BFS frontier approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicArray / String
    Reusable patterngreedy BFS frontier
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Scan the current jump range while computing the farthest next range. Crossing the current range boundary commits exactly one additional jump.

    Algorithm

    1. Scan the current jump range while computing the farthest next range. Crossing the current range boundary commits exactly one additional jump.
    2. Maintain this invariant: The current boundary contains exactly the indices reachable with the current jump count.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def jump(self, nums):
        jumps = end = farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == end:
                jumps += 1
                end = farthest
        return jumps

    Why this is correct

    The proof follows the maintained state: The current boundary contains exactly the indices reachable with the current jump count. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(1) extra space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    The input guarantees reachability; a one-element input needs zero jumps.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 55. Jump Game · Next: 274. H-Index

  • LeetCode 274: H-Index — Python Solution

    Solve LeetCode 274: H-Index in Python with a sorting and threshold scan approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicArray / String
    Reusable patternsorting and threshold scan
    ComplexityO(n log n) time and O(1) auxiliary space aside from sorting

    What the problem is testing

    Sort citations descending and find the largest rank whose citation count is at least that rank.

    Algorithm

    1. Sort citations descending and find the largest rank whose citation count is at least that rank.
    2. Maintain this invariant: The first h sorted papers each have at least h citations.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def hIndex(self, citations):
        citations.sort(reverse=True)
        answer = 0
        for rank, count in enumerate(citations, 1):
            if count < rank:
                break
            answer = rank
        return answer

    Why this is correct

    The proof follows the maintained state: The first h sorted papers each have at least h citations. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n log n) time and O(1) auxiliary space aside from sorting. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    The answer can be zero or the number of papers.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 45. Jump Game II · Next: 380. Insert Delete GetRandom O(1)

  • LeetCode 380: Insert Delete GetRandom O(1) — Python Solution

    Solve LeetCode 380: Insert Delete GetRandom O(1) in Python with a array plus index map approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicArray / String
    Reusable patternarray plus index map
    ComplexityO(1) average time per operation and O(n) space

    What the problem is testing

    Store values densely in an array and map each value to its index. Removal swaps the target with the last value before popping.

    Algorithm

    1. Store values densely in an array and map each value to its index. Removal swaps the target with the last value before popping.
    2. Maintain this invariant: The map always records the current array index of every stored value.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class RandomizedSet:
    def __init__(self):
        self.values = []
        self.index = {}

    def insert(self, val):
        if val in self.index:
            return False
        self.index[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val):
        if val not in self.index:
            return False
        i = self.index.pop(val)
        last = self.values.pop()
        if i < len(self.values):
            self.values[i] = last
            self.index[last] = i
        return True

    def getRandom(self):
        return random.choice(self.values)

    Why this is correct

    The proof follows the maintained state: The map always records the current array index of every stored value. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(1) average time per operation and O(n) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Removing the final element and reinserting a deleted value must update both structures.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 274. H-Index · Next: 238. Product of Array Except Self

  • LeetCode 238: Product of Array Except Self — Python Solution

    Solve LeetCode 238: Product of Array Except Self in Python with a prefix and suffix products approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicArray / String
    Reusable patternprefix and suffix products
    ComplexityO(n) time and O(1) extra space excluding the output

    What the problem is testing

    Write prefix products into the answer, then multiply by a running suffix product in a reverse pass.

    Algorithm

    1. Write prefix products into the answer, then multiply by a running suffix product in a reverse pass.
    2. Maintain this invariant: Before the reverse pass reaches i, the answer holds the product left of i and suffix holds the product right of i.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def productExceptSelf(self, nums):
        answer = [1] * len(nums)
        prefix = 1
        for i, value in enumerate(nums):
            answer[i] = prefix
            prefix *= value
        suffix = 1
        for i in range(len(nums) - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]
        return answer

    Why this is correct

    The proof follows the maintained state: Before the reverse pass reaches i, the answer holds the product left of i and suffix holds the product right of i. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(1) extra space excluding the output. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    The method naturally handles one or multiple zeros without division.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 380. Insert Delete GetRandom O(1) · Next: 134. Gas Station

  • LeetCode 134: Gas Station — Python Solution

    Solve LeetCode 134: Gas Station in Python with a greedy restart approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicArray / String
    Reusable patterngreedy restart
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    If total fuel is insufficient no start works. While scanning, a negative running tank invalidates every start since the previous candidate, so restart after it.

    Algorithm

    1. If total fuel is insufficient no start works. While scanning, a negative running tank invalidates every start since the previous candidate, so restart after it.
    2. Maintain this invariant: The current candidate can reach every station processed since it was chosen.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def canCompleteCircuit(self, gas, cost):
        if sum(gas) < sum(cost):
            return -1
        start = tank = 0
        for i, (fuel, price) in enumerate(zip(gas, cost)):
            tank += fuel - price
            if tank < 0:
                start, tank = i + 1, 0
        return start

    Why this is correct

    The proof follows the maintained state: The current candidate can reach every station processed since it was chosen. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(1) extra space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    A valid start may be the final station; the total balance decides impossibility.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 238. Product of Array Except Self · Next: 135. Candy