Daniel P. Gleason

Category: LeetCode Solutions

  • LeetCode 209: Minimum Size Subarray Sum — Python Solution

    Solve LeetCode 209: Minimum Size Subarray Sum in Python with a positive sliding window 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
    TopicSliding Window
    Reusable patternpositive sliding window
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Expand until the positive-number sum reaches the target, then shrink as much as possible while recording the shortest valid length.

    Algorithm

    1. Expand until the positive-number sum reaches the target, then shrink as much as possible while recording the shortest valid length.
    2. Maintain this invariant: Before each expansion, the current window is the shortest examined suffix for its right boundary.
    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 minSubArrayLen(self, target, nums):
        left = total = 0; best = len(nums) + 1
        for right, value in enumerate(nums):
            total += value
            while total >= target:
                best = min(best, right - left + 1)
                total -= nums[left]; left += 1
        return 0 if best > len(nums) else best

    Why this is correct

    The proof follows the maintained state: Before each expansion, the current window is the shortest examined suffix for its right boundary. 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

    Return zero when no window reaches the target.

    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: 15. 3Sum · Next: 3. Longest Substring Without Repeating Characters

  • LeetCode 3: Longest Substring Without Repeating Characters — Python Solution

    Solve LeetCode 3: Longest Substring Without Repeating Characters in Python with a last-seen sliding window 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
    TopicSliding Window
    Reusable patternlast-seen sliding window
    ComplexityO(n) time and O(k) space

    What the problem is testing

    Track each character’s latest index and move the left boundary past a repeated occurrence when it lies inside the current window.

    Algorithm

    1. Track each character’s latest index and move the left boundary past a repeated occurrence when it lies inside the current window.
    2. Maintain this invariant: The active window contains no duplicate 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 lengthOfLongestSubstring(self, s):
        last = {}; left = best = 0
        for right, char in enumerate(s):
            if char in last and last[char] >= left: left = last[char] + 1
            last[char] = right
            best = max(best, right - left + 1)
        return best

    Why this is correct

    The proof follows the maintained state: The active window contains no duplicate 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

    The repeated character may have occurred before the current window and should then be ignored.

    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: 209. Minimum Size Subarray Sum · Next: 30. Substring with Concatenation of All Words

  • LeetCode 30: Substring with Concatenation of All Words — Python Solution

    Solve LeetCode 30: Substring with Concatenation of All Words in Python with a word-aligned windows 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
    TopicSliding Window
    Reusable patternword-aligned windows
    ComplexityO(n) time and O(number of distinct words) space

    What the problem is testing

    Run one sliding window for each offset modulo the word length. Count fixed-size tokens, shrinking whenever a token exceeds its required frequency.

    Algorithm

    1. Run one sliding window for each offset modulo the word length. Count fixed-size tokens, shrinking whenever a token exceeds its required frequency.
    2. Maintain this invariant: Every active aligned window contains only known words and never exceeds a required frequency.
    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 findSubstring(self, s, words):
        if not s or not words: return []
        width, need, answer = len(words[0]), Counter(words), []
        for offset in range(width):
            left = offset; used = 0; have = defaultdict(int)
            for right in range(offset, len(s) - width + 1, width):
                word = s[right:right + width]
                if word not in need:
                    have.clear(); used = 0; left = right + width; continue
                have[word] += 1; used += 1
                while have[word] > need[word]:
                    old = s[left:left + width]; have[old] -= 1; used -= 1; left += width
                if used == len(words):
                    answer.append(left)
                    old = s[left:left + width]; have[old] -= 1; used -= 1; left += width
        return answer

    Why this is correct

    The proof follows the maintained state: Every active aligned window contains only known words and never exceeds a required frequency. 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(number of distinct words) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Duplicate words require frequency counts; invalid tokens reset the window.

    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: 3. Longest Substring Without Repeating Characters · Next: 76. Minimum Window Substring

  • LeetCode 76: Minimum Window Substring — Python Solution

    Solve LeetCode 76: Minimum Window Substring in Python with a deficit-count window 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
    TopicSliding Window
    Reusable patterndeficit-count window
    ComplexityO(n) time and O(k) space

    What the problem is testing

    Expand while satisfying required character counts, then shrink while the window remains valid to minimize it.

    Algorithm

    1. Expand while satisfying required character counts, then shrink while the window remains valid to minimize it.
    2. Maintain this invariant: formed counts how many required character classes currently meet their exact demand.
    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 minWindow(self, s, t):
        if not t: return ""
        need, have = Counter(t), defaultdict(int)
        required, formed, left = len(need), 0, 0
        best = (float("inf"), 0, 0)
        for right, char in enumerate(s):
            have[char] += 1
            if char in need and have[char] == need[char]: formed += 1
            while formed == required:
                if right - left + 1 < best[0]: best = (right - left + 1, left, right)
                old = s[left]; have[old] -= 1; left += 1
                if old in need and have[old] < need[old]: formed -= 1
        return "" if best[0] == float("inf") else s[best[1]:best[2] + 1]

    Why this is correct

    The proof follows the maintained state: formed counts how many required character classes currently meet their exact demand. 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

    Repeated required characters matter; return an empty string if no valid window exists.

    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: 30. Substring with Concatenation of All Words · Next: 36. Valid Sudoku

  • LeetCode 151: Reverse Words in a String — Python Solution

    Solve LeetCode 151: Reverse Words in a String in Python with a token normalization 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 patterntoken normalization
    ComplexityO(n) time and O(n) space

    What the problem is testing

    Split on whitespace to discard extra spaces, reverse the word sequence, and join with single spaces.

    Algorithm

    1. Split on whitespace to discard extra spaces, reverse the word sequence, and join with single spaces.
    2. Maintain this invariant: The output contains exactly the processed words in reverse order with normalized spacing.
    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 reverseWords(self, s):
        return " ".join(reversed(s.split()))

    Why this is correct

    The proof follows the maintained state: The output contains exactly the processed words in reverse order with normalized spacing. 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

    Leading, trailing, and repeated internal spaces are removed.

    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: 14. Longest Common Prefix · Next: 6. Zigzag Conversion

  • LeetCode 6: Zigzag Conversion — Python Solution

    Solve LeetCode 6: Zigzag Conversion in Python with a row simulation 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 patternrow simulation
    ComplexityO(n) time and O(n) space

    What the problem is testing

    Walk down and up across row buffers, reversing direction at the first and last row, then concatenate the rows.

    Algorithm

    1. Walk down and up across row buffers, reversing direction at the first and last row, then concatenate the rows.
    2. Maintain this invariant: Each processed character is appended to the row visited by the zigzag cursor.
    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 convert(self, s, numRows):
        if numRows == 1 or numRows >= len(s):
            return s
        rows = ["" for _ in range(numRows)]
        row, direction = 0, 1
        for char in s:
            rows[row] += char
            if row == 0:
                direction = 1
            elif row == numRows - 1:
                direction = -1
            row += direction
        return "".join(rows)

    Why this is correct

    The proof follows the maintained state: Each processed character is appended to the row visited by the zigzag cursor. 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

    One row or at least as many rows as characters returns the original string.

    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: 151. Reverse Words in a String · Next: 28. Find the Index of the First Occurrence in a String

  • LeetCode 28: Find the Index of the First Occurrence in a String — Python Solution

    Solve LeetCode 28: Find the Index of the First Occurrence in a String in Python with a substring 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 patternsubstring scan
    ComplexityO((n-m+1)m) worst-case time and O(1) extra space

    What the problem is testing

    Check every feasible starting position and return the first slice equal to the needle.

    Algorithm

    1. Check every feasible starting position and return the first slice equal to the needle.
    2. Maintain this invariant: All starts before the current position have already been proven not to 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 strStr(self, haystack, needle):
        if needle == "":
            return 0
        for start in range(len(haystack) - len(needle) + 1):
            if haystack[start:start + len(needle)] == needle:
                return start
        return -1

    Why this is correct

    The proof follows the maintained state: All starts before the current position have already been proven not to 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((n-m+1)m) 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

    An empty needle matches at zero; a longer needle cannot match.

    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: 6. Zigzag Conversion · Next: 68. Text Justification

  • LeetCode 68: Text Justification — Python Solution

    Solve LeetCode 68: Text Justification in Python with a greedy line packing 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 patterngreedy line packing
    ComplexityO(total characters) time and O(width) temporary space

    What the problem is testing

    Greedily pack the maximum words per line, then distribute spaces evenly with any remainder assigned to leftmost gaps. Left-justify the final line.

    Algorithm

    1. Greedily pack the maximum words per line, then distribute spaces evenly with any remainder assigned to leftmost gaps. Left-justify the final line.
    2. Maintain this invariant: Each emitted nonfinal line has exactly the required width and contains the maximum feasible next group of words.
    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 fullJustify(self, words, maxWidth):
        lines, i = [], 0
        while i < len(words):
            j, letters = i, 0
            while j < len(words) and letters + len(words[j]) + (j - i) <= maxWidth:
                letters += len(words[j])
                j += 1
            gaps = j - i - 1
            if j == len(words) or gaps == 0:
                line = " ".join(words[i:j]).ljust(maxWidth)
            else:
                spaces, extra = divmod(maxWidth - letters, gaps)
                pieces = []
                for gap in range(gaps):
                    pieces.append(words[i + gap])
                    pieces.append(" " * (spaces + (gap < extra)))
                pieces.append(words[j - 1])
                line = "".join(pieces)
            lines.append(line)
            i = j
        return lines

    Why this is correct

    The proof follows the maintained state: Each emitted nonfinal line has exactly the required width and contains the maximum feasible next group of words. 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(width) temporary space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Single-word lines and the final line use trailing spaces instead of divided gaps.

    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: 28. Find the Index of the First Occurrence in a String · Next: 125. Valid Palindrome

  • LeetCode 125: Valid Palindrome — Python Solution

    Solve LeetCode 125: Valid Palindrome in Python with a filtered two pointers 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
    TopicTwo Pointers
    Reusable patternfiltered two pointers
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Move inward while skipping non-alphanumeric characters and compare lowercase characters at the remaining positions.

    Algorithm

    1. Move inward while skipping non-alphanumeric characters and compare lowercase characters at the remaining positions.
    2. Maintain this invariant: Everything outside the pointers has matched under the normalization rule.
    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 isPalindrome(self, s):
        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, right = left + 1, right - 1
        return True

    Why this is correct

    The proof follows the maintained state: Everything outside the pointers has matched under the normalization rule. 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

    Punctuation-only and empty strings are valid palindromes.

    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: 68. Text Justification · Next: 392. Is Subsequence

  • LeetCode 392: Is Subsequence — Python Solution

    Solve LeetCode 392: Is Subsequence in Python with a subsequence pointer 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
    TopicTwo Pointers
    Reusable patternsubsequence pointer
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Advance the target pointer only when the current source character matches it.

    Algorithm

    1. Advance the target pointer only when the current source character matches it.
    2. Maintain this invariant: The matched prefix is the longest prefix of s that can be formed from the processed part of t.
    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 isSubsequence(self, s, t):
        i = 0
        for char in t:
            if i < len(s) and s[i] == char:
                i += 1
        return i == len(s)

    Why this is correct

    The proof follows the maintained state: The matched prefix is the longest prefix of s that can be formed from the processed part of t. 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

    An empty s always succeeds; repeated characters must preserve order.

    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: 125. Valid Palindrome · Next: 167. Two Sum II – Input Array Is Sorted