Daniel P. Gleason

Category: LeetCode Solutions

  • LeetCode 135: Candy — Python Solution

    Solve LeetCode 135: Candy in Python with a two directional passes 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 directional passes
    ComplexityO(n) time and O(n) space

    What the problem is testing

    Give each child one candy, scan left-to-right for increasing ratings, then right-to-left for decreasing ratings while taking the larger requirement.

    Algorithm

    1. Give each child one candy, scan left-to-right for increasing ratings, then right-to-left for decreasing ratings while taking the larger requirement.
    2. Maintain this invariant: After both passes every higher-rated neighbor has strictly more candy while each allocation is minimal for its slope.
    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 candy(self, ratings):
        sweets = [1] * len(ratings)
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                sweets[i] = sweets[i - 1] + 1
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                sweets[i] = max(sweets[i], sweets[i + 1] + 1)
        return sum(sweets)

    Why this is correct

    The proof follows the maintained state: After both passes every higher-rated neighbor has strictly more candy while each allocation is minimal for its slope. 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

    Plateaus reset to one; peaks must satisfy both directions.

    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: 134. Gas Station · Next: 42. Trapping Rain Water

  • LeetCode 169: Majority Element — Python Solution

    Solve LeetCode 169: Majority Element in Python with a Boyer-Moore voting 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 patternBoyer-Moore voting
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Treat equal values as votes for the current candidate and different values as cancellations. A guaranteed majority survives every possible cancellation.

    Algorithm

    1. Treat equal values as votes for the current candidate and different values as cancellations. A guaranteed majority survives every possible cancellation.
    2. Maintain this invariant: The candidate represents the unmatched votes in 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 majorityElement(self, nums):
        candidate, votes = None, 0
        for value in nums:
            if votes == 0:
                candidate = value
            votes += 1 if value == candidate else -1
        return candidate

    Why this is correct

    The proof follows the maintained state: The candidate represents the unmatched votes in 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) 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 majority can change as the scan progresses; negative values are ordinary 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: 80. Remove Duplicates from Sorted Array II · Next: 189. Rotate Array

  • LeetCode 189: Rotate Array — Python Solution

    Solve LeetCode 189: Rotate Array in Python with a three reversals 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 patternthree reversals
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Normalize k, reverse the whole array, then reverse the two rotated segments. Reversal moves both groups into their final cyclic order.

    Algorithm

    1. Normalize k, reverse the whole array, then reverse the two rotated segments. Reversal moves both groups into their final cyclic order.
    2. Maintain this invariant: After the three reversals, each original index maps to (index + k) modulo n.
    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, nums, k):
        if not nums:
            return
        k %= len(nums)
        nums.reverse()
        nums[:k] = reversed(nums[:k])
        nums[k:] = reversed(nums[k:])

    Why this is correct

    The proof follows the maintained state: After the three reversals, each original index maps to (index + k) modulo n. 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

    Reduce k modulo the length; an empty array and k equal to zero need no work.

    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: 169. Majority Element · Next: 121. Best Time to Buy and Sell Stock

  • LeetCode 121: Best Time to Buy and Sell Stock — Python Solution

    Solve LeetCode 121: Best Time to Buy and Sell Stock in Python with a running minimum 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 patternrunning minimum
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Track the cheapest price seen before today and the best profit from selling today or earlier.

    Algorithm

    1. Track the cheapest price seen before today and the best profit from selling today or earlier.
    2. Maintain this invariant: The minimum is the best legal buy price for the current sell day.
    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 maxProfit(self, prices):
        cheapest, best = float("inf"), 0
        for price in prices:
            cheapest = min(cheapest, price)
            best = max(best, price - cheapest)
        return best

    Why this is correct

    The proof follows the maintained state: The minimum is the best legal buy price for the current sell day. 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

    Descending prices return zero; the buy must occur before the sale.

    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: 189. Rotate Array · Next: 122. Best Time to Buy and Sell Stock II

  • LeetCode 122: Best Time to Buy and Sell Stock II — Python Solution

    Solve LeetCode 122: Best Time to Buy and Sell Stock II in Python with a greedy positive differences 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 positive differences
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Add every positive day-to-day increase. Each rising run contributes the same profit as buying at its start and selling at its end.

    Algorithm

    1. Add every positive day-to-day increase. Each rising run contributes the same profit as buying at its start and selling at its end.
    2. Maintain this invariant: Accumulated profit equals the maximum realizable profit over processed days with no overlapping positions.
    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 maxProfit(self, prices):
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))

    Why this is correct

    The proof follows the maintained state: Accumulated profit equals the maximum realizable profit over processed days with no overlapping positions. 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

    Flat and falling transitions contribute nothing.

    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: 121. Best Time to Buy and Sell Stock · Next: 55. Jump Game

  • LeetCode 55: Jump Game — Python Solution

    Solve LeetCode 55: Jump Game in Python with a greedy reachability 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 reachability
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Maintain the farthest reachable index. If the scan reaches an index beyond that frontier, progress is impossible; otherwise extend the frontier.

    Algorithm

    1. Maintain the farthest reachable index. If the scan reaches an index beyond that frontier, progress is impossible; otherwise extend the frontier.
    2. Maintain this invariant: Every index at or before farthest is reachable from the start.
    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 canJump(self, nums):
        farthest = 0
        for i, jump in enumerate(nums):
            if i > farthest:
                return False
            farthest = max(farthest, i + jump)
        return True

    Why this is correct

    The proof follows the maintained state: Every index at or before farthest is reachable from the start. 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 one-element array succeeds; zeros matter only when they stop the frontier.

    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: 122. Best Time to Buy and Sell Stock II · Next: 45. Jump Game II

  • LeetCode 27: Remove Element — Python Solution

    Solve LeetCode 27: Remove Element in Python with a write 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
    TopicArray / String
    Reusable patternwrite pointer
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Scan once and copy only values that should remain into the next output position. The prefix before the write pointer is the compacted result.

    Algorithm

    1. Scan once and copy only values that should remain into the next output position. The prefix before the write pointer is the compacted result.
    2. Maintain this invariant: The prefix before write contains exactly the retained values seen so far.
    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 removeElement(self, nums, val):
        write = 0
        for value in nums:
            if value != val:
                nums[write] = value
                write += 1
        return write

    Why this is correct

    The proof follows the maintained state: The prefix before write contains exactly the retained values seen so far. 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

    All values may be removed, or none may match 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: 88. Merge Sorted Array · Next: 26. Remove Duplicates from Sorted Array

  • LeetCode 26: Remove Duplicates from Sorted Array — Python Solution

    Solve LeetCode 26: Remove Duplicates from Sorted Array in Python with a sorted write 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
    TopicArray / String
    Reusable patternsorted write pointer
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Keep one write position for the next distinct value. Because the input is sorted, comparing with the last written value is sufficient.

    Algorithm

    1. Keep one write position for the next distinct value. Because the input is sorted, comparing with the last written value is sufficient.
    2. Maintain this invariant: The written prefix contains one copy of every distinct value in sorted order.
    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 removeDuplicates(self, nums):
        if not nums:
            return 0
        write = 1
        for read in range(1, len(nums)):
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write += 1
        return write

    Why this is correct

    The proof follows the maintained state: The written prefix contains one copy of every distinct value in sorted order. 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

    Handle an empty array and arrays containing only one repeated 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: 27. Remove Element · Next: 80. Remove Duplicates from Sorted Array II

  • LeetCode 80: Remove Duplicates from Sorted Array II — Python Solution

    Solve LeetCode 80: Remove Duplicates from Sorted Array II in Python with a bounded write 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.

    DifficultyMedium
    TopicArray / String
    Reusable patternbounded write pointer
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Allow a value when fewer than two values have been written or when it differs from the value two output positions back.

    Algorithm

    1. Allow a value when fewer than two values have been written or when it differs from the value two output positions back.
    2. Maintain this invariant: No value occurs more than twice in the written prefix, and every permitted occurrence is retained.
    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 removeDuplicates(self, nums):
        write = 0
        for value in nums:
            if write < 2 or value != nums[write - 2]:
                nums[write] = value
                write += 1
        return write

    Why this is correct

    The proof follows the maintained state: No value occurs more than twice in the written prefix, and every permitted occurrence is retained. 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

    Short arrays need no special rewriting; long duplicate runs collapse to two values.

    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: 26. Remove Duplicates from Sorted Array · Next: 169. Majority Element

  • LeetCode 88: Merge Sorted Array — Python Solution

    Solve LeetCode 88: Merge Sorted Array in Python with a reverse 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
    TopicArray / String
    Reusable patternreverse two pointers
    ComplexityO(m+n) time and O(1) extra space

    What the problem is testing

    Compare the largest unused values and write into the final open slot of nums1. Working backward avoids overwriting values that have not been compared.

    Algorithm

    1. Compare the largest unused values and write into the final open slot of nums1. Working backward avoids overwriting values that have not been compared.
    2. Maintain this invariant: Every position after the write pointer already contains the correct largest remaining 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 merge(self, nums1, m, nums2, n):
        i, j, write = m - 1, n - 1, m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[write] = nums1[i]
                i -= 1
            else:
                nums1[write] = nums2[j]
                j -= 1
            write -= 1

    Why this is correct

    The proof follows the maintained state: Every position after the write pointer already contains the correct largest remaining 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(m+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

    Either input can be empty; equal values and duplicate runs are 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. Next: 27. Remove Element