Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

  • Cool! Following that idea, I wrote this one completely by myself, nice!
  • Idea:
    • use a queue to hold all zero-degree vertex
    • loop through all other vertices, whenever one vertex’s indegree becomes zero, offer it into the q
    • when finished iterating the set, make sure to check if all indegree[] equals to zero, if not, that means there’s a cycle within the graph, in that case, just return an empty array as the problem requires, otherwise, return vertices in the queue
public int[] findOrder(int numCourses, int[][] prerequisites) {

int[] indegree = new int[numCourses];
for(int i = 0; i < prerequisites.length; i++){
indegree[prerequisites[i][0]]++;
}

Set<Integer> zeroDegree = new HashSet();
Queue<Integer> q = new LinkedList<Integer>();
for(int i = 0; i < numCourses; i++){
if(indegree[i] == 0) {
zeroDegree.add(i);
q.offer(i);
}
}

while(!zeroDegree.isEmpty()){
Iterator<Integer> it = zeroDegree.iterator();
int course = it.next();
zeroDegree.remove(course);
for(int[] edge : prerequisites){
if(edge[1] == course){
indegree[edge[0]]--;
if(indegree[edge[0]] == 0){
zeroDegree.add(edge[0]);
q.offer(edge[0]);
}
}
}
}

for(int i = 0; i < numCourses; i++){
if(indegree[i] != 0) return new int[0];
}

int[] order = new int[numCourses];
int i = 0;
while(!q.isEmpty() && i < numCourses){
order[i] = q.poll();
i++;
}

return order;

}

 

Advertisements

Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/

I attempted to solve it on my own, but didn’t sort out the ideas, turned to Discuss: jeantimex@ post is easy to follow: https://discuss.leetcode.com/topic/28827/share-my-java-bfs-solution

  • I still need to be bold enough to think that BFS will have to traverse all possible paths which means a lot of times, like in this case, jeantimex@ traversed all possible strings, thumbs-up!
  • I rewrite the isValid() function to make it more readable than that post. Thumbs up for his brevity again!
public List<String> removeInvalidParentheses(String s) {

List<String> result = new ArrayList<>();
if(s == null) return result;

Set<String> visited = new HashSet<String>();
Queue<String> q = new LinkedList<String>();

q.offer(s);
visited.add(s);

boolean found = false;

while(!q.isEmpty()){
String curr = q.poll();
if(isValid(curr)){
found = true;
result.add(curr);
}

if(found) continue;//this means if the initial input is already a valid one, we'll just directly return it and there's actually only one valid result

for(int i = 0; i < curr.length(); i++){
if(curr.charAt(i) != '(' && curr.charAt(i) != ')') continue;//this is to rule out those non-parentheses characters

String next = curr.substring(0, i) + curr.substring(i+1);
if(!visited.contains(next)){
q.offer(next);
visited.add(next);
}
}

}
return result;

}

private boolean isValid(String str) {
char[] chars = str.toCharArray();
int count = 0;
for(char c : chars){
if(c == '(') count++;
else if (c == ')'){
count--;
if(count == -1) return false;
}
}
return count == 0;
}

Shortest Distance from All Buildings

https://leetcode.com/problems/shortest-distance-from-all-buildings/

Inspired by this post: https://discuss.leetcode.com/topic/31925/java-solution-with-explanation-and-time-complexity-analysis

Kind of complex BFS, I guess this is why it’s rated as HARD.

As that post explains, it’s pretty straightforward to follow, I just need to be bold to think that we’ll have to do BFS for every single building (grid with value == 1) and calculate the distance for each one of them. Also:

  • count the total number of buildings during the outer most two for loops
  • update reach[][] array in each BFS
  • update distance[][] array in each BFS
  • how the shift[] array is ordered is super important and cannot be randomly changed, because it denotes how to get the four neighbors of each cell
  • don’t forget to add (grid[nextRow][nextCol] == 0) as one of the conditions in the innermost if condition
public int shortestDistance(int[][] grid) {
int m = grid.length;
if(m == 0) return -1;
int n = grid[0].length;
int[][] reach = new int[m][n];
int[][] distance = new int[m][n];
int[] shift = new int[]{0, 1, 0, -1, 0};//how these five elements is ordered is important since it denotes the neighbor of the current node
int numBuilding = 0;

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
numBuilding++;
int dist = 1;
boolean[][] visited = new boolean[m][n];

Queue<int[]> q = new LinkedList<int[]>();
q.offer(new int[]{i, j});
while(!q.isEmpty()){
int size = q.size();
for(int l = 0; l < size; l++){
int[] current = q.poll();
for(int k = 0; k < 4; k++){
int nextRow = current[0] + shift[k];
int nextCol = current[1] + shift[k+1];
if(nextRow >= 0 && nextRow < m && nextCol >= 0
&& nextCol < n && !visited[nextRow][nextCol] && grid[nextRow][nextCol] == 0){
distance[nextRow][nextCol] += dist;
visited[nextRow][nextCol] = true;
reach[nextRow][nextCol]++;
q.offer(new int[]{nextRow, nextCol});
}
}
}
dist++;
}
}
}
}

int result = Integer.MAX_VALUE;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 0 && reach[i][j] == numBuilding && distance[i][j] < result){
result = distance[i][j];
}
}
}
return result == Integer.MAX_VALUE ? -1 : result;
}

Find K Pairs with Smallest Sums

https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

StefanPochmann won again, amazed by his post: https://discuss.leetcode.com/topic/50450/slow-1-liner-to-fast-solutions

First off, as StefanPochmann pointed out, “I found it helpful to visualize the input as an m×n matrix of sums, for example for nums1=[1,7,11], and nums2=[2,4,6]:”

2  4  6
+————
1   | 3  5  7
7  | 9 11 13
11 | 13 15 17

The above very visually friendly matrix is the basis for the following understanding/algorithms:

Approach 1: use a heap (a priority queue in Java) to store the next possible candidates and pop them out in ascending order.

  • The number in the above matrix means the sum from the two given arrays, i.e. m[0][1] = 5 = 1+4 = nums1[0] + nums2[1]
  • After finding the first smallest sum which is at m[0][0], the next smallest possible sums are at m[0][1] or m[1][0], which one pop() first? we use a PriorityQueue (minHeap) to achieve this.
  • We need to create a new class called Node to denote each point in the matrix
  • We need to implement the so-called anonymous comparator in the newly created Node class: compare the node class based on its sum
  • How does the min heap or the PriorityQueue in Java come into play?
    • there might be multiple candidates in the queue for the poll() action, which one poll() first? the one with the highest priority, i.e. based on how we customize the comparator function.
  • We do a BFS starting from (0,0) and mark each visited node to avoid re-visit.

Inspired by this post: https://discuss.leetcode.com/topic/50435/java-easy-understandable-bfs-with-priorityqueue


public class Solution {
final int[][] neighbors = new int[][]{{1,0}, {0,1}};
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> result = new ArrayList<int[]>();
if(nums1 == null || nums2 == null || k == 0 || nums1.length == 0 || nums2.length == 0) return result;
Queue<Node> meanHeap = new PriorityQueue<Node>();
meanHeap.offer(new Node(0, 0, nums1[0] + nums2[0]));
boolean[][] visited = new boolean[nums1.length][nums2.length];
visited[0][0] = true;//we start form (0,0), so mark it as visited
while(k > 0 && !meanHeap.isEmpty()){
Node node = meanHeap.poll();
result.add(new int[]{nums1[node.row], nums2[node.col]});
k--;
for(int[] neighbor : neighbors){
int nextRow = node.row + neighbor[0];
int nextCol = node.col + neighbor[1];
if(nextRow < 0 || nextCol < 0 || nextRow >= nums1.length || nextCol >= nums2.length || visited[nextRow][nextCol]) continue;
visited[nextRow][nextCol] = true;
meanHeap.offer(new Node(nextRow, nextCol, nums1[nextRow] + nums2[nextCol]));
}
}
return result;
}

private class Node implements Comparable<Node>{
int row;
int col;
int sum;

public Node(int row, int col, int sum){
this.row = row;
this.col = col;
this.sum = sum;
}

@Override
public int compareTo(Node that) {
return this.sum - that.sum;
}
}
}

 

 

Approach 2: brute force, enumerate all of the products and sort them, return the first k, I thought of doing it in Java, using a HashMap to store int[] as key and product as value, and then sort the map based on its values and then return the first k keys. But I’ll have to write my own comparator to do the sorting. Then I turned to StefanPochmann’s super clean python code:


def kSmallestPairs(self, nums1, nums2, k):

return sorted(itertools.product(nums1, nums2), key=sum)[:k]

Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Very excited that I got this problem AC’ed completely by myself. Hooray!

My algorithm: use BFS to do level order traversal, and use Integer.MAX_VALUE to denote terminator.

Apparently, there’s a restraint to this approach, what if the TreeNode’s value contains Integer.MAX_VALUE as its val? This approach won’t work since I’m using Integer.MAX_VALUE as the tree terminator.

[TODO] figure out a better way.

[Uber] Followup: what is the TreeNode.val is NOT int, what if TreeNode.val is a String? and this String could any random String, including “\n”?

  • Answer: escape them, define an exhaustive set for all of these special strings that need to be escaped and escape them twice for them.
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null) return "";
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
StringBuilder sb = new StringBuilder();
while(!q.isEmpty()){
int size = q.size();
for(int i = 0; i < size; i++){
TreeNode node = q.poll();
if(node.val == Integer.MAX_VALUE) {
sb.append(Integer.MAX_VALUE + ",");
continue;
}
sb.append(node.val + ",");
if(node.left != null) q.offer(node.left);
else if(node.left == null) q.offer(new TreeNode(Integer.MAX_VALUE));
if(node.right != null) q.offer(node.right);
else if(node.right == null) q.offer(new TreeNode(Integer.MAX_VALUE));
}
}
return sb.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data == null || data.equals("")) return null;
String[] stringValues = data.split(",");
int[] values = new int[stringValues.length];
for(int j = 0; j < stringValues.length; j++){
values[j] = Integer.parseInt(stringValues[j]);
}
TreeNode root = new TreeNode(Integer.valueOf(values[0]));
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
int i = 1;
while(!q.isEmpty() && i < values.length){
int size = q.size();
int nodeCount = 0;
while(nodeCount < size && i < values.length){
TreeNode node = q.poll();
if(values[i] == Integer.MAX_VALUE){
node.left = null;
} else if((Integer) values[i] != null) {
TreeNode left = new TreeNode(values[i]);
node.left = left;
q.offer(left);
}
if(values[i+1] == Integer.MAX_VALUE){
node.right = null;
} else if((Integer) values[i+1] != null){
TreeNode right = new TreeNode(values[i+1]);
node.right = right;
q.offer(right);
}
nodeCount++;
i +=2;
}
}
return root;
}