# Posts tagged as “weekly”

## 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

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)

## 1017. Convert to Base -2

Solution: Math / Simulation

Time complexity: O(logn)
Space complexity: O(logn)

## 1018. Binary Prefix Divisible By 5

Solution: Math

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

## 1019. Next Greater Node In Linked List

Solution: Reverse + Monotonic Stack

Process in reverse order and keep a monotonically increasing stack, pop all the elements that are smaller than the current one, then the top of the stack (if exists) will be the next greater node.

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

## 1020. Number of Enclaves

Solution: DFS / Connected Components

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

## 1020. Partition Array Into Three Parts With Equal Sum

Return true if there is a 2/3*sum prefix sum after a 1/3 prefix sum

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

## 1021. Best Sightseeing Pair

Greedy, only keep the best A[i] + i so far and pair with A[j] – j, i < j

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

## 1022. Smallest Integer Divisible by K

Math

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

## 1023. Binary String With Substrings Representing 1 To N

Brute Force, try all possible substrings and convert them into decimals.

Time complexity: O(|S|*log(N)^2)