Daniel P. Gleason

Category: LeetCode Solutions

  • LeetCode 219: Contains Duplicate II — Python Solution

    Solve LeetCode 219: Contains Duplicate II in Python with a last-index tracking 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
    TopicHashmap
    Reusable patternlast-index tracking
    ComplexityO(n) time and O(n) space

    What the problem is testing

    Record the most recent index of each value and test whether the distance to the current occurrence is within k.

    Algorithm

    1. Record the most recent index of each value and test whether the distance to the current occurrence is within k.
    2. Maintain this invariant: The map holds the closest possible prior occurrence for every 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 Solution:
    def containsNearbyDuplicate(self, nums, k):
        last = {}
        for i, value in enumerate(nums):
            if value in last and i - last[value] <= k: return True
            last[value] = i
        return False

    Why this is correct

    The proof follows the maintained state: The map holds the closest possible prior occurrence for every 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(n) time and O(n) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    k equal to zero can never match distinct indices.

    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: 202. Happy Number · Next: 128. Longest Consecutive Sequence

  • LeetCode 128: Longest Consecutive Sequence — Python Solution

    Solve LeetCode 128: Longest Consecutive Sequence in Python with a set sequence starts 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
    TopicHashmap
    Reusable patternset sequence starts
    ComplexityO(n) expected time and O(n) space

    What the problem is testing

    Insert all values into a set and count forward only from values whose predecessor is absent.

    Algorithm

    1. Insert all values into a set and count forward only from values whose predecessor is absent.
    2. Maintain this invariant: Every consecutive run is counted exactly once from its unique smallest 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 Solution:
    def longestConsecutive(self, nums):
        values, best = set(nums), 0
        for value in values:
            if value - 1 not in values:
                end = value
                while end in values: end += 1
                best = max(best, end - value)
        return best

    Why this is correct

    The proof follows the maintained state: Every consecutive run is counted exactly once from its unique smallest 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(n) expected time and O(n) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Duplicates disappear in the set; negative and unsorted values behave normally.

    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: 219. Contains Duplicate II · Next: 228. Summary Ranges

  • LeetCode 228: Summary Ranges — Python Solution

    Solve LeetCode 228: Summary Ranges in Python with a run detection 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
    TopicIntervals
    Reusable patternrun detection
    ComplexityO(n) time and O(1) extra space excluding output

    What the problem is testing

    Start a range at each unprocessed value and extend while consecutive values differ by one, then format the endpoints.

    Algorithm

    1. Start a range at each unprocessed value and extend while consecutive values differ by one, then format the endpoints.
    2. Maintain this invariant: All values before the scan index have been represented by disjoint maximal ranges.
    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 summaryRanges(self, nums):
        answer, i = [], 0
        while i < len(nums):
            start = nums[i]
            while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1: i += 1
            end = nums[i]
            answer.append(str(start) if start == end else f"{start}->{end}")
            i += 1
        return answer

    Why this is correct

    The proof follows the maintained state: All values before the scan index have been represented by disjoint maximal ranges. 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 output. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Single-value runs use one number rather than an arrow.

    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: 128. Longest Consecutive Sequence · Next: 56. Merge Intervals

  • LeetCode 56: Merge Intervals — Python Solution

    Solve LeetCode 56: Merge Intervals in Python with a sorted sweep 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
    TopicIntervals
    Reusable patternsorted sweep
    ComplexityO(n log n) time and O(n) output space

    What the problem is testing

    Sort by start time and either extend the last merged interval or append a new disjoint interval.

    Algorithm

    1. Sort by start time and either extend the last merged interval or append a new disjoint interval.
    2. Maintain this invariant: The output is sorted, disjoint, and exactly covers every processed interval.
    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 merge(self, intervals):
        intervals.sort(key=lambda pair: pair[0])
        merged = []
        for start, end in intervals:
            if not merged or start > merged[-1][1]: merged.append([start, end])
            else: merged[-1][1] = max(merged[-1][1], end)
        return merged

    Why this is correct

    The proof follows the maintained state: The output is sorted, disjoint, and exactly covers every processed interval. 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(n) output space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Touching endpoints overlap under the problem definition.

    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: 228. Summary Ranges · Next: 57. Insert Interval

  • LeetCode 57: Insert Interval — Python Solution

    Solve LeetCode 57: Insert Interval in Python with a three-phase interval 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
    TopicIntervals
    Reusable patternthree-phase interval scan
    ComplexityO(n) time and O(n) output space

    What the problem is testing

    Append intervals ending before the new one, merge every overlap into the new interval, then append the remaining intervals.

    Algorithm

    1. Append intervals ending before the new one, merge every overlap into the new interval, then append the remaining intervals.
    2. Maintain this invariant: Before the merge phase, output intervals are disjoint and strictly before the interval being inserted.
    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 insert(self, intervals, newInterval):
        answer, i = [], 0
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            answer.append(intervals[i]); i += 1
        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1]); i += 1
        return answer + [newInterval] + intervals[i:]

    Why this is correct

    The proof follows the maintained state: Before the merge phase, output intervals are disjoint and strictly before the interval being inserted. 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(n) output space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    The new interval can belong first, last, or cover every existing interval.

    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: 56. Merge Intervals · Next: 452. Minimum Number of Arrows to Burst Balloons

  • LeetCode 205: Isomorphic Strings — Python Solution

    Solve LeetCode 205: Isomorphic Strings in Python with a bidirectional mapping 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
    TopicHashmap
    Reusable patternbidirectional mapping
    ComplexityO(n) time and O(k) space

    What the problem is testing

    Maintain mappings in both directions so each character corresponds to exactly one partner and no two source characters share a target.

    Algorithm

    1. Maintain mappings in both directions so each character corresponds to exactly one partner and no two source characters share a target.
    2. Maintain this invariant: Both maps describe a one-to-one correspondence for every processed character pair.
    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 isIsomorphic(self, s, t):
        if len(s) != len(t): return False
        forward, backward = {}, {}
        for a, b in zip(s, t):
            if (a in forward and forward[a] != b) or (b in backward and backward[b] != a): return False
            forward[a], backward[b] = b, a
        return True

    Why this is correct

    The proof follows the maintained state: Both maps describe a one-to-one correspondence for every processed character pair. 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(k) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Length mismatch fails; repeated patterns must match in both strings.

    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: 383. Ransom Note · Next: 290. Word Pattern

  • LeetCode 290: Word Pattern — Python Solution

    Solve LeetCode 290: Word Pattern in Python with a bidirectional token mapping 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
    TopicHashmap
    Reusable patternbidirectional token mapping
    ComplexityO(n) time and O(k) space

    What the problem is testing

    Split the sentence into words and enforce a one-to-one mapping between pattern characters and words.

    Algorithm

    1. Split the sentence into words and enforce a one-to-one mapping between pattern characters and words.
    2. Maintain this invariant: Both maps agree for every processed pattern-word pair.
    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 wordPattern(self, pattern, s):
        words = s.split()
        if len(pattern) != len(words): return False
        forward, backward = {}, {}
        for char, word in zip(pattern, words):
            if (char in forward and forward[char] != word) or (word in backward and backward[word] != char): return False
            forward[char], backward[word] = word, char
        return True

    Why this is correct

    The proof follows the maintained state: Both maps agree for every processed pattern-word pair. 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(k) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    The number of words must equal the pattern length.

    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: 205. Isomorphic Strings · Next: 242. Valid Anagram

  • LeetCode 242: Valid Anagram — Python Solution

    Solve LeetCode 242: Valid Anagram in Python with a frequency equality 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
    TopicHashmap
    Reusable patternfrequency equality
    ComplexityO(n) time and O(k) space

    What the problem is testing

    Count characters in one string and subtract characters from the other; all counts must finish at zero.

    Algorithm

    1. Count characters in one string and subtract characters from the other; all counts must finish at zero.
    2. Maintain this invariant: The counter equals the frequency difference for the processed characters.
    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 isAnagram(self, s, t):
        return Counter(s) == Counter(t)

    Why this is correct

    The proof follows the maintained state: The counter equals the frequency difference for the processed characters. 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(k) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Different lengths cannot be anagrams; Unicode characters work as dictionary keys.

    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: 290. Word Pattern · Next: 49. Group Anagrams

  • LeetCode 49: Group Anagrams — Python Solution

    Solve LeetCode 49: Group Anagrams in Python with a canonical frequency key 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
    TopicHashmap
    Reusable patterncanonical frequency key
    ComplexityO(total characters) time and O(total characters) output space

    What the problem is testing

    Convert each word into a 26-count tuple and group words sharing that immutable signature.

    Algorithm

    1. Convert each word into a 26-count tuple and group words sharing that immutable signature.
    2. Maintain this invariant: Words share a group exactly when their character-count signatures match.
    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 groupAnagrams(self, strs):
        groups = defaultdict(list)
        for word in strs:
            counts = [0] * 26
            for char in word: counts[ord(char) - ord("a")] += 1
            groups[tuple(counts)].append(word)
        return list(groups.values())

    Why this is correct

    The proof follows the maintained state: Words share a group exactly when their character-count signatures match. 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 characters) time and O(total characters) output space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Empty strings share the all-zero signature; repeated words remain repeated outputs.

    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: 242. Valid Anagram · Next: 1. Two Sum

  • LeetCode 1: Two Sum — Python Solution

    Solve LeetCode 1: Two Sum in Python with a complement lookup 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
    TopicHashmap
    Reusable patterncomplement lookup
    ComplexityO(n) time and O(n) space

    What the problem is testing

    For each value, check whether its required complement was seen earlier, then record the current index.

    Algorithm

    1. For each value, check whether its required complement was seen earlier, then record the current index.
    2. Maintain this invariant: The map contains one usable prior index for each processed 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 Solution:
    def twoSum(self, nums, target):
        seen = {}
        for i, value in enumerate(nums):
            if target - value in seen: return [seen[target - value], i]
            seen[value] = i

    Why this is correct

    The proof follows the maintained state: The map contains one usable prior index for each processed 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(n) time and O(n) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Duplicate values can form the answer when the target is twice that value.

    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: 49. Group Anagrams · Next: 202. Happy Number