DEV Community

DSAwithSM
DSAwithSM

Posted on

5 LeetCode Problems #236, #198, #322, #300, #39 Explained | DSA Decoded

#leetcode #python #algorithms #programming

🧠 5 LeetCode Problems Explained with Code + Video

Part of the DSA Decoded series — step-by-step Python solutions with video walkthroughs.

Problems covered in this post:

  • 🟡 Lowest Common Ancestor of a Binary Tree (LeetCode #236) · Medium · Trees
  • 🟡 House Robber (LeetCode #198) · Medium · Dynamic Programming
  • 🟡 Coin Change (LeetCode #322) · Medium · Dynamic Programming
  • 🟡 Longest Increasing Subsequence (LeetCode #300) · Medium · Dynamic Programming
  • 🟡 Combination Sum (LeetCode #39) · Medium · Backtracking

🟡 Lowest Common Ancestor of a Binary Tree

Difficulty: Medium  |  Topic: Trees  |  LeetCode #236

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q. The LCA is the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).

Solution 

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left  = lowest_common_ancestor(root.left,  p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right
Enter fullscreen mode Exit fullscreen mode

🔗 Solve on LeetCode  ·  📺 Watch video explanation  ·  💻 Full solution + tests on GitHub

🟡 House Robber

Difficulty: Medium  |  Topic: Dynamic Programming  |  LeetCode #198

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. You cannot rob two adjacent houses because the security system will alert the police. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Solution 

def rob(nums):
    rob1, rob2 = 0, 0
    for n in nums:
        new_rob = max(rob1 + n, rob2)
        rob1 = rob2
        rob2 = new_rob
    return rob2
Enter fullscreen mode Exit fullscreen mode

🔗 Solve on LeetCode  ·  📺 Watch video explanation  ·  💻 Full solution + tests on GitHub

🟡 Coin Change

Difficulty: Medium  |  Topic: Dynamic Programming  |  LeetCode #322

Problem

You are given an integer array coins representing coins of various denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

Solution 

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], 1 + dp[a - c])
    return dp[amount] if dp[amount] != float('inf') else -1
Enter fullscreen mode Exit fullscreen mode

🔗 Solve on LeetCode  ·  📺 Watch video explanation  ·  💻 Full solution + tests on GitHub

🟡 Longest Increasing Subsequence

Difficulty: Medium  |  Topic: Dynamic Programming  |  LeetCode #300

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements.

Solution 

def length_of_lis(nums):
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
Enter fullscreen mode Exit fullscreen mode

🔗 Solve on LeetCode  ·  📺 Watch video explanation  ·  💻 Full solution + tests on GitHub

🟡 Combination Sum

Difficulty: Medium  |  Topic: Backtracking  |  LeetCode #39

Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Solution 

def combination_sum(candidates, target):
    result = []

    def backtrack(start, current, total):
        if total == target:
            result.append(list(current))
            return
        if total > target:
            return
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            backtrack(i, current, total + candidates[i])
            current.pop()

    backtrack(0, [], 0)
    return result
Enter fullscreen mode Exit fullscreen mode

🔗 Solve on LeetCode  ·  📺 Watch video explanation  ·  💻 Full solution + tests on GitHub

🔔 Follow Along

New problems every 2 days — subscribe to stay consistent with your DSA prep!

Drop a comment with your approach — always curious to see other solutions!

Top comments (0)