# Posts tagged as “weekly contest”

## 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); } };

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)

## C++

LeetCode 1021. Remove Outermost Parentheses

Solution: Track # of opened parentheses

Let n denote the # of opened parentheses after current char, keep ‘(‘ if n > 1 and keep ‘)’ if n > 0

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

## C++

LeetCode 1022. Sum of Root To Leaf Binary Numbers

Solution: Recursion + Math

Keep tracking the number from root to current node.

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

## C++

LeetCode 1023. Camelcase Matching

Solution: String…

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

## C++

LeetCode 1024. Video Stitching

Solution 1: DP

Time complexity: O(nT^2)
Space complexity: O(T^2)