Leetcode solution 213. House Robber II

Problem Statement 

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.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

 Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube
  
• B站

Thought Process

This is very similar to House Robber I problem where the only difference is the houses now form a circle (French fancy way calls it cul-de-sac). It's same DP algorithm except now we need to consider two cases: whether we rob the first house or not. If we rob the first house, we should not rob the last house. If we do not rob the first house, we can rob the last house. We can even reuse the rob() function in House Robber I problem

Solutions

Use DP

Time Complexity: O(N), N is the array size
Space Complexity: O(N) since we use extra arrays

References

• House Robber I problem solution
  
• Leetcode discussion solution

Leetcode solution 198. House Robber

Problem Statement 

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that 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.

 

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

 

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

 Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube
  
• B站

Thought Process

Easy problem and Dynamic Programming(DP) should jump into mind given it's only asking for max values (Just think about different combo we have to do without using DP, a little less than 2^N)

The mathematical induction formula is below, for any current max money at index i, you either choose to use the i-1 or i-2 + current house's money to not trigger police.

max[i] = max(max[i - 2] + a[i], max[i-1])

Solutions

DP

Time Complexity: O(N) N is the array size
Space Complexity: O(N) since we used an extra array

References

• Leetcode official solution

Leetcode solution 200. Number of Islands (Using BFS, DFS & Disjoint Set)

Problem Statement 

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.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

 Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube BFS & DFS solution in 2015
  
• Youtube Disjoint Solution
  
• B站

Thought Process

I have recorded a video back in 2015 (5 years ago, Geez time flies) using BFS and DFS. The essential idea is every time we see a land (i.e., "1"), we would trigger a BFS or DFS search to mark all the connected grids and increase the island counts to 1.

Another solution is to use Disjoint Set (aka Union Find). There is a generic solution where we could implement a DisjointSet data structure and perform "union" steps first to assign each grid a "parent". In the 2nd iteration we can perform "find" step to count how many distinct "parents", which is the number of islands.

A quick summary of some classic use cases

• Disjoint Set / Union Find (Disjoint set is the data structure while union find is the algorithm, people normally use it interchangeably)  can often be used to solve if a graph is connected or not, such as phone contact problem (who knows who, how many isolated groups are there)
  
• To detect if a directed graph has cycle, use Kahn's algorithm for topological sort
• To detect if a un-directed graph has cycle
• We could use normal BFS or DFS
  
• We should use Union Find with edge list graph representation
  

Solutions

Use BFS

Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grids

Use DFS

Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grids

Use Disjoint Set / Union Find

Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grids using a map

References

• Leetcode official solution

Leetcode solution 207. Course Schedule

Problem Statement 

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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?

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

 

Constraints:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
• You may assume that there are no duplicate edges in the input prerequisites.
• 1 <= numCourses <= 10^5

 Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• Youtube BFS in 2015, Youtube DFS in 2015
  
• B站

Thought Process

It is a classic dependency graph problem. We can translate this problem to direct if there is a cycle in a directed graph or not. A text book solution is Kahn's algorithm for topological sorting. We can have a simple way to represent the graph or use a more proper adjacency lists (a little bit overkill for this problem though)

Solutions

Use adjacency lists BFS

Time Complexity: O(V), since each vertex is visited only once during BFS
Space Complexity: O(V+E) since we use adjacency lists to represent a directed graph

Use simple hashmap BFS

Time Complexity: O(V), since each vertex is visited only once during BFS

Space Complexity: O(V) since we are using a hashmap

Use recursion DFS

Time Complexity: O(V), since each vertex is visited only once during BFS

Space Complexity: O(V) since we used a lookup hashmap for memorization purpose (not considering function stack space)

References

• Leetcode official solution
• GeeksforGeeks Detect Cycle in a directly graph using topological sort