Press "Enter" to skip to content

Posts published in “Search”

花花酱 LeetCode 90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.


Solution: DFS

The key to this problem is how to remove/avoid duplicates efficiently.

For the same depth, among the same numbers, only the first number can be used.

Time complexity: O(2^n * n)
Space complexity: O(n)


花花酱 LeetCode 838. Push Dominoes

here are N dominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string “S” representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.

Return a string representing the final state. 

Example 1:

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:

Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.


  1. 0 <= N <= 10^5
  2. String dominoes contains only 'L‘, 'R' and '.'

Solution: Simulation

Simulate the push process, record the steps from L and R for each domino.
steps(L) == steps(R) => “.”
steps(L) < steps(R) => “L”
steps(L) > steps(R) => “R”

Time complexity: O(n)
Space complexity: O(n)


花花酱 8 Puzzles – Bidirectional A* vs Bidirectional BFS

8 Puzzles # nodes expended of 1000 solvable instances


Nodes expended: BiDirectional A* << A* (Manhattan) <= Bidirectional BFS < A* Hamming << BFS
Running time: BiDirectional A* < Bidirectional BFS <= A* (Manhattan) < A* Hamming << BFS


C++ Version

花花酱 LeetCode 417. Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.


  1. The order of returned grid coordinates does not matter.
  2. Both m and n are less than 150.


Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic


[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

Solution: DFS/BFS

Be careful with the input range, easy to TLE with a naive implementation. Have to search from the boards.

Time complexity: O(mn)
Space complexity: O(mn)




花花酱 LeetCode 996. Number of Squareful Arrays

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful.  Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Input: [1,17,8]
Output: 2
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1


  1. 1 <= A.length <= 12
  2. 0 <= A[i] <= 1e9

Solution1: DFS

Try all permutations with pruning.

Time complexity: O(n!)
Space complexity: O(n)


Solution 2: DP Hamiltonian Path

dp[s][i] := # of ways to reach state s (binary mask of nodes visited) that ends with node i

dp[s | (1 << j)][j] += dp[s][i] if g[i][j]

Time complexity: O(n^2*2^n)
Space complexity: O(2^n)


Related Problems