Problem Solving with Python

• Given a 2d grid map of ’1’s (land) and ’0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
• Want to count the number of islands

• Attempt #1
Copy

• Solution

• You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).

Solution

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

• Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1:
‣
Attempt #1 (TLE and then Accepted after memoization)
Copy
‣

Lessons & Mental Model

💡

- Decorators can be used to wrap functions (like cache) - self in pyton is equivalent to this in javascript - Strategy - use a trie, and do bfs with the trie

Copy

class Trie(object):
  def __init__(self):
    self.cache = {}

  @cache
  def insert(self, word):
    pass

  def cache(f):
    def method(obj, s):
      if s not in obj.cache:
        obj.cache[s] = f(obj, s)
      return obj.cache[s]
    return method

• Solution

• Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

• Solution

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

• Solution

• A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
• The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
• How many possible unique paths are there?

import math


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if(m < 2 or n < 2):
            return (1 if m + n >= 2 else 0)
        A = [[1 for i in range(n)] for j in range(m)]

        for i in range(1, m):
            for j in range(1, n):
                A[i][j] = A[i - 1][j] + A[i][j - 1]
        return A[m - 1][n - 1]

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (s_i < e_i), determine if a person could attend all meetings.

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort(key = lambda x: x[0])

        for i in range(1, len(intervals)):
            if intervals[i-1][1] > intervals[i][0]:
                return False

        return True

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        dp = [1, 1]

        for i in range(2, n + 1):
            dp.append(dp[i - 1] + dp[i - 2])

        return dp[-1]

Recursive Solution: dp[i] = dp[i-1] + dp[i-2]

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = {}
        for num in nums:
            if num in seen:
                return True
            else:
                seen[num] = True
        return False

Solution

Lessons & Mental Model

You can extract unique elements from a list by creating a set object

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        root = ListNode(None)
        node = root
        while(l1 and l2):
            node.next = (l1 if l1.val <= l2.val else l2)
            l1 = l1.next if node.next is l1 else l1
            l2 = l2.next if node.next is l2 else l2
            node = node.next
        node.next = l1 if l1 else l2
        return root.next

Solution

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

First Attempt

Solution

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Solution

Reverse a singly linked list.

Solution

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Solution:
    def cloneGraph(self, node: 'Node', clones={}) -> 'Node':
        if not node:
            return None
        if node in clones:
            return clones[node]
        clone = Node(node.val, [])
        clones[node] = clone
        for nb in node.neighbors:
            clone.neighbors.append(self.cloneGraph(nb, clones))
        return clone

Solution:

Lessons Learned:

1. You want to use a hashmap to hash nodes to their clones and return the cached clone if the node has been seen and cloned before

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Solution: https://leetcode.com/problems/reorder-list/discuss/447242/python-solution

Lessons Learned:

1. Break the problem down into helper functions

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Solution:

https://leetcode.com/problems/word-search/discuss/27660/Python-dfs-solution-with-comments

Lessons Learned:

1. searching for existence usually means dfs
2. deque

• A message containing letters from A-Z is being encoded to numbers using the following mapping:
• ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == "0":
            return 0
        l = len(s)
        dp = [1] + [0] * l

        for i in range(1, l + 1):
            dp[i] += (dp[i - 1] if s[i - 1] != "0" else 0)
            dp[i] += (dp[i - 2] if (i > 1 and 10 <= int(s[i - 2:i]) <= 26) else 0)
        return dp[-1]

Solution

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

First Attempt (TLE)

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Solution

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Solution

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Solution

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

• ⭐️Bonus: Which question is this question similar to? How are they different?

Solution

Bonus: Which question is this question similar to? How are they different?

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

First Attempt

Code:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [1] + [0] * amount
        for coin in coins:
            for i in range(amount + 1):
                if i - coin >= 0:
                    dp[i] += dp[i - coin]
        return dp[amount]

Solution:

https://leetcode.com/problems/coin-change-2/discuss/99222/Video-explaining-how-dynamic-programming-works-with-the-Coin-Change-problem

Lessons Learned:

1. Q: Why is the outer loop the coins and not the amount?

• Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

key = lambda x: x.start

Solution

Given a non-empty array of integers, return the k most frequent elements.

from collections import defaultdict


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        if not nums or not k:
            return None
        frequencyTable = defaultdict(int)
        for num in nums:
            frequencyTable[num] += 1
        return sorted(frequencyTable.keys(), key=lambda x: frequencyTable[x], reverse=True)[:k]

Solution

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4
  / \
 1   2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
Return false.

Solution

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution

Lessons

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

• Follow up: A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?