Given a 2D n*m matrix with 0 and 1 representing white and black pixels. All black pixels are connected. Find the bouding rectangle of all black pixels in less than O(mn). For each row, do a binary search to find the maximum y of all black pixels, just think of all the black pixels are projected to a 1D line.
0 0
0 0
0 0 <- Seach for the minimum Y
1 1
1 1
Y Y Y
1 Seach for the maximum Y -> 1
0 0
0 0For x it's similar. Overall time complexity O(nlogm + mlogn)
Given a list of points in a 2D matrix, return an array of number of islands if these points are put into the matrix by order. Just use union find to connect different points, each time two points of different islands are connected, add the result by 1.
Given a list of scores of ballons A, each time burst a ballon at position i, get A[i-1]*A[i]*A[i+1] points (score = 1 for outbound position).
return the maximum score.
Bottom up dp + range dp from the last ballon burst, dp[i][j] is the maximum score could get in the range [i,j]. Overall time complexity O(n^3)
Count of Smaller Numbers After Self, pretty straight forward. This is a pretty straight forward template of binary index tree also. (just shift the array) For other solutions, also merge sort, zkw tree, segment tree also works.
Given a 2D matrix with points indicating if the location is a building or obstacle or nothing. return the minimum distance to all buildings (or -1 if not possible). For all buildings, do BFS and get the shortest distance to other positions. For all possible points, add the shortest distance of each building, if all buildings can reach to that position.
Given two arrays containing only 0-9, return the k-digit maximum number we can get by choose numbers in these two arrays in order. Which means, if arr1[i] is chosen, all numbers before position i in arr1 can not be chosen, this is the only rule. There are some greedy solutions, but it's better to choose some other stupid but trustworthy ones. The idea is simple, first for each assignment of k, get the result of the maximum number we can get from arr1 and arr2 O(n^2) Then merge the two arrays by two pointers O(n), and compare the result with previous ones.