# Posts published in “Leetcode”

## 1046. Last Stone Weight

Solution: Simulation (priority_queue)

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

## 1047. Remove All Adjacent Duplicates In String

Solution: Stack / Deque

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

## 1048. Longest String Chain

Solution: DP

dp[i] := max length of chain of (A[0] ~ A[i-1])

dp[i] = max{dp[j] + 1} if A[j] is prederrsor of A[i], 1 <= j <i

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

## 1049. Last Stone Weight II

Solution: DP / target sum

Time complexity: O(n * S) = O(n * 100)

Space complexity: O(S) = O(100)

## LeetCode 1037. Valid Boomerang

Solution: Math
Time complexity: O(1)
Space complexity: O(1)

## LeetCode 1038. Binary Search Tree to Greater Sum Tree

Solution: Recursion: right, root, left

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

## 1039. Minimum Score Triangulation of Polygon

Solution: DP

Init: dp[i][j] = 0 if 0 <= j – i <= 1
dp[i][j] := min score to triangulate A[i] ~ A[j]
dp[i][j] = min{dp[i][k] + dp[k][j] + A[i]*A[k]*A[j]), i < k < j

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

## 1040. Moving Stones Until Consecutive II

Solution: Sliding Window

Time complexity: O(nlogn)
Space complexity: O(1)

## 1033. Moving Stones Until Consecutive

Solution: Math

Time complexity: O(1)
Space complexity: O(1)

## 1034. Coloring A Border

Solution: DFS

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

## 1035. Uncrossed Lines

Solution: LCS

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

## 1036. Escape a Large Maze

Solution: limited search

Time complexity: O(b^2)
Space complexity: O(b^2)

## C++

// Author: Huahua, running time: 168 ms, 49.7 MB class Solution { public: bool isEscapePossible(vector>& blocked, vector& source, vector& target) { for (const auto& p : blocked) b.insert(static_cast(p[0]) << 32 | p[1]); seen = 0; t = target; bool first = dfs(source[0], source[1]); t = source; bool second = dfs(target[0], target[1]); return first && second; } private: const static int kMaxN = 1000000; const static int kMaxSeen = 20000; unordered_set b; vector t; int seen; int tx; int ty; bool dfs(int x, int y) { if (x < 0 || y < 0 || x >= kMaxN || y >= kMaxN) return false; if (x == t[0] && y == t[1]) return true; long key = static_cast(x) << 32 | y; if (b.find(key) != b.end()) return false; b.insert(key); if (++seen > kMaxSeen) return true; return dfs(x + 1, y) || dfs(x – 1, y) || dfs(x, y + 1) || dfs(x, y – 1); } };

## LeetCode 1029 Two City Scheduling

Solution1: DP

dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]

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

## C++

Solution 2: Greedy

Sort by cost_a – cost_b

Choose the first n/2 people for A, rest for B

Time complexity: O(nlogn)
Space complexity: O(1)

## 1030. Matrix Cells in Distance Order

Solution: Sorting

Time complexity: O(RC*log(RC))
Space complexity: O(RC)

## 1031. Maximum Sum of Two Non-Overlapping Subarrays

Solution: Prefix sum

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

## 1032. Stream of Characters

Solution: Trie

Time complexity:

• build O(sum(len(w))
• query O(max(len(w))

Space complexity: O(sum(len(w))

## Java

1025. Divisor Game

Solution: Recursion with Memoization

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

## C++

1026. Maximum Difference Between Node and Ancestor

Solution: Resolution, pass min / max of ancestor nodes

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

## C++

1027. Longest Arithmetic Sequence

Solution 1: Brute Force + Pruning

Time complexity: O(n^3) ~ O(n^2) in practice
Space complexity: O(n)

## C++

1028. Recover a Tree From Preorder Traversal

Solution: Recursion

Check the current depth and expected depth, if don’t match, return nullptr.

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