Daniel P. Gleason

Category: LeetCode Solutions

  • LeetCode 202: Happy Number — Python Solution

    Solve LeetCode 202: Happy Number in Python with a cycle 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
    TopicHashmap
    Reusable patterncycle detection
    ComplexityO(log n) space per generated state and bounded practical time

    What the problem is testing

    Repeatedly replace the number with the sum of squared digits. Stop at one or when a previously seen value proves a cycle.

    Algorithm

    1. Repeatedly replace the number with the sum of squared digits. Stop at one or when a previously seen value proves a cycle.
    2. Maintain this invariant: Every generated value is recorded once, so a repeat identifies a non-one cycle.
    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 isHappy(self, n):
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = sum(int(digit) ** 2 for digit in str(n))
        return n == 1

    Why this is correct

    The proof follows the maintained state: Every generated value is recorded once, so a repeat identifies a non-one cycle. 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(log n) space per generated state and bounded practical time. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Single-digit values other than one may still enter a longer cycle.

    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: 1. Two Sum · Next: 219. Contains Duplicate II

  • LeetCode 36: Valid Sudoku — Python Solution

    Solve LeetCode 36: Valid Sudoku in Python with a row-column-box sets 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
    TopicMatrix
    Reusable patternrow-column-box sets
    ComplexityO(1) time and O(1) space for a fixed 9×9 board

    What the problem is testing

    Track seen digits independently for each row, column, and 3×3 box; any duplicate violates the board.

    Algorithm

    1. Track seen digits independently for each row, column, and 3×3 box; any duplicate violates the board.
    2. Maintain this invariant: Each tracking set contains exactly the nonempty digits processed in its region.
    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 isValidSudoku(self, board):
        rows = [set() for _ in range(9)]; cols = [set() for _ in range(9)]; boxes = [set() for _ in range(9)]
        for r in range(9):
            for c in range(9):
                value = board[r][c]
                if value == ".": continue
                box = (r // 3) * 3 + c // 3
                if value in rows[r] or value in cols[c] or value in boxes[box]: return False
                rows[r].add(value); cols[c].add(value); boxes[box].add(value)
        return True

    Why this is correct

    The proof follows the maintained state: Each tracking set contains exactly the nonempty digits processed in its region. 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) space for a fixed 9×9 board. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Ignore empty cells; the board need not be solvable to be valid.

    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: 76. Minimum Window Substring · Next: 54. Spiral Matrix

  • LeetCode 54: Spiral Matrix — Python Solution

    Solve LeetCode 54: Spiral Matrix in Python with a shrinking boundaries 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
    TopicMatrix
    Reusable patternshrinking boundaries
    ComplexityO(mn) time and O(1) extra space excluding output

    What the problem is testing

    Traverse top, right, bottom, and left boundaries, then shrink them while checking whether each boundary still exists.

    Algorithm

    1. Traverse top, right, bottom, and left boundaries, then shrink them while checking whether each boundary still exists.
    2. Maintain this invariant: All cells outside the current boundaries have been emitted exactly once.
    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 spiralOrder(self, matrix):
        if not matrix: return []
        top, bottom, left, right, answer = 0, len(matrix) - 1, 0, len(matrix[0]) - 1, []
        while top <= bottom and left <= right:
            answer.extend(matrix[top][left:right + 1]); top += 1
            for r in range(top, bottom + 1): answer.append(matrix[r][right])
            right -= 1
            if top <= bottom:
                answer.extend(reversed(matrix[bottom][left:right + 1])); bottom -= 1
            if left <= right:
                for r in range(bottom, top - 1, -1): answer.append(matrix[r][left])
                left += 1
        return answer

    Why this is correct

    The proof follows the maintained state: All cells outside the current boundaries have been emitted exactly once. 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(mn) 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 remaining rows or columns must not be traversed twice.

    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: 36. Valid Sudoku · Next: 48. Rotate Image

  • LeetCode 48: Rotate Image — Python Solution

    Solve LeetCode 48: Rotate Image in Python with a transpose then reverse rows 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
    TopicMatrix
    Reusable patterntranspose then reverse rows
    ComplexityO(n^2) time and O(1) extra space

    What the problem is testing

    Transpose across the main diagonal, then reverse every row to obtain a clockwise quarter-turn in place.

    Algorithm

    1. Transpose across the main diagonal, then reverse every row to obtain a clockwise quarter-turn in place.
    2. Maintain this invariant: After transposition and row reversal, original cell (r,c) reaches (c,n-1-r).
    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 rotate(self, matrix):
        n = len(matrix)
        for r in range(n):
            for c in range(r + 1, n):
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
        for row in matrix: row.reverse()

    Why this is correct

    The proof follows the maintained state: After transposition and row reversal, original cell (r,c) reaches (c,n-1-r). 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^2) 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 operation mutates the square matrix; a 1×1 matrix remains unchanged.

    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: 54. Spiral Matrix · Next: 73. Set Matrix Zeroes

  • LeetCode 73: Set Matrix Zeroes — Python Solution

    Solve LeetCode 73: Set Matrix Zeroes in Python with a first-row marker compression 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
    TopicMatrix
    Reusable patternfirst-row marker compression
    ComplexityO(mn) time and O(1) extra space

    What the problem is testing

    Use the first row and column as marker storage, preserving separate flags for whether those marker lines originally contained zero.

    Algorithm

    1. Use the first row and column as marker storage, preserving separate flags for whether those marker lines originally contained zero.
    2. Maintain this invariant: A marker at row r or column c records that every cell on that line must become zero.
    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 setZeroes(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        first_row = any(matrix[0][c] == 0 for c in range(cols))
        first_col = any(matrix[r][0] == 0 for r in range(rows))
        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][c] == 0: matrix[r][0] = matrix[0][c] = 0
        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][0] == 0 or matrix[0][c] == 0: matrix[r][c] = 0
        if first_row:
            for c in range(cols): matrix[0][c] = 0
        if first_col:
            for r in range(rows): matrix[r][0] = 0

    Why this is correct

    The proof follows the maintained state: A marker at row r or column c records that every cell on that line must become zero. 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(mn) 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 top-left cell is shared by both marker lines, so row and column flags must be separate.

    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: 48. Rotate Image · Next: 289. Game of Life

  • LeetCode 289: Game of Life — Python Solution

    Solve LeetCode 289: Game of Life in Python with a encoded in-place transition 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
    TopicMatrix
    Reusable patternencoded in-place transition
    ComplexityO(mn) time and O(1) extra space

    What the problem is testing

    Store old and new binary states in different bits of each cell, compute every neighbor count from the old bit, then shift to reveal the next state.

    Algorithm

    1. Store old and new binary states in different bits of each cell, compute every neighbor count from the old bit, then shift to reveal the next state.
    2. Maintain this invariant: The low bit of every cell remains the original generation until all transitions are computed.
    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 gameOfLife(self, board):
        rows, cols = len(board), len(board[0])
        for r in range(rows):
            for c in range(cols):
                live = 0
                for dr in (-1, 0, 1):
                    for dc in (-1, 0, 1):
                        if (dr or dc) and 0 <= r + dr < rows and 0 <= c + dc < cols:
                            live += board[r + dr][c + dc] & 1
                old = board[r][c] & 1
                if live == 3 or (old and live == 2): board[r][c] |= 2
        for r in range(rows):
            for c in range(cols): board[r][c] >>= 1

    Why this is correct

    The proof follows the maintained state: The low bit of every cell remains the original generation until all transitions are computed. 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(mn) 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

    Bounds exclude off-board neighbors; all cells update simultaneously.

    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: 73. Set Matrix Zeroes · Next: 383. Ransom Note

  • LeetCode 383: Ransom Note — Python Solution

    Solve LeetCode 383: Ransom Note in Python with a frequency consumption 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 consumption
    ComplexityO(n+m) time and O(k) space

    What the problem is testing

    Count available magazine characters and decrement for every requested character, failing when a count is exhausted.

    Algorithm

    1. Count available magazine characters and decrement for every requested character, failing when a count is exhausted.
    2. Maintain this invariant: Counts represent unused magazine characters after satisfying the processed 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 canConstruct(self, ransomNote, magazine):
        available = Counter(magazine)
        for char in ransomNote:
            available[char] -= 1
            if available[char] < 0: return False
        return True

    Why this is correct

    The proof follows the maintained state: Counts represent unused magazine characters after satisfying the processed 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+m) 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 requested letters require separate available copies.

    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: 289. Game of Life · Next: 205. Isomorphic Strings

  • LeetCode 167: Two Sum II – Input Array Is Sorted — Python Solution

    Solve LeetCode 167: Two Sum II – Input Array Is Sorted in Python with a opposing 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.

    DifficultyMedium
    TopicTwo Pointers
    Reusable patternopposing two pointers
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Compare the endpoint sum with the target. A small sum requires a larger left value; a large sum requires a smaller right value.

    Algorithm

    1. Compare the endpoint sum with the target. A small sum requires a larger left value; a large sum requires a smaller right value.
    2. Maintain this invariant: Every discarded endpoint is impossible to use in a solution with any remaining partner.
    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, numbers, target):
        left, right = 0, len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            if total == target: return [left + 1, right + 1]
            if total < target: left += 1
            else: right -= 1

    Why this is correct

    The proof follows the maintained state: Every discarded endpoint is impossible to use in a solution with any remaining partner. 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 one-based indices and never reuse the same element.

    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: 392. Is Subsequence · Next: 11. Container With Most Water

  • LeetCode 11: Container With Most Water — Python Solution

    Solve LeetCode 11: Container With Most Water in Python with a greedy boundary movement 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
    TopicTwo Pointers
    Reusable patterngreedy boundary movement
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Measure the area between the endpoints, then move the shorter wall because keeping it cannot improve area at a smaller width.

    Algorithm

    1. Measure the area between the endpoints, then move the shorter wall because keeping it cannot improve area at a smaller width.
    2. Maintain this invariant: The best area using every discarded shorter boundary has already been considered.
    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 maxArea(self, height):
        left, right, best = 0, len(height) - 1, 0
        while left < right:
            best = max(best, (right - left) * min(height[left], height[right]))
            if height[left] <= height[right]: left += 1
            else: right -= 1
        return best

    Why this is correct

    The proof follows the maintained state: The best area using every discarded shorter boundary has already been considered. 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

    Equal walls may move either side; width decreases each iteration.

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

  • LeetCode 15: 3Sum — Python Solution

    Solve LeetCode 15: 3Sum in Python with a sort plus 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.

    DifficultyMedium
    TopicTwo Pointers
    Reusable patternsort plus two pointers
    ComplexityO(n^2) time and O(1) auxiliary space aside from sorting

    What the problem is testing

    Sort the values, fix one number, and use two pointers to find complementary pairs while skipping duplicates.

    Algorithm

    1. Sort the values, fix one number, and use two pointers to find complementary pairs while skipping duplicates.
    2. Maintain this invariant: For each fixed value, pointer moves discard sums that cannot reach zero, and emitted triples are unique.
    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 threeSum(self, nums):
        nums.sort(); answer = []
        for i in range(len(nums) - 2):
            if i and nums[i] == nums[i - 1]: continue
            if nums[i] > 0: break
            left, right = i + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0: left += 1
                elif total > 0: right -= 1
                else:
                    answer.append([nums[i], nums[left], nums[right]])
                    left += 1; right -= 1
                    while left < right and nums[left] == nums[left - 1]: left += 1
                    while left < right and nums[right] == nums[right + 1]: right -= 1
        return answer

    Why this is correct

    The proof follows the maintained state: For each fixed value, pointer moves discard sums that cannot reach zero, and emitted triples are unique. 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^2) 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

    Skip duplicate fixed values and duplicate pointer values after every 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: 11. Container With Most Water · Next: 209. Minimum Size Subarray Sum