# Posts published in “Medium”

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Example 2:

Note:

• arr will have length in range [1, 10].
• arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Solution 1: Max so far / Set

Time complexity: O(nlogn)

Space complexity: O(n)

C++

Solution 2: Max so far

Time complexity: O(n)

Space complexity: O(1)

C++

Java

Python3

Problem:

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Solution 0: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

Python

Solution 1: Greedy

Time complexity: O(n)

Space complexity: O(26/128)

C++

Java

Python3

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Note:

1. The length of the given array is positive and will not exceed 20.
2. The sum of elements in the given array will not exceed 1000.
3. Your output answer is guaranteed to be fitted in a 32-bit integer.

# Solution 1: DP

Time complexity: O(n*sum)

Space complexity: O(n*sum)

# Solution 2: DFS

Time complexity: O(2^n)

Space complexity: O(n)

# Solution 3: Subset sum

Time complexity: O(n*sum)

Space complexity: O(sum)

## C++ w/o copy

Problem:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Idea:

DP /knapsack

Search

Solution1:

C++ / DP

Time complexity: O(n*amount^2)

Space complexity: O(amount)

Solution2:

C++ / DP

Time complexity: O(n*amount)

Space complexity: O(amount)

Python3

Solution3:

C++ / DFS

Time complexity: O(amount^n/(coin_0*coin_1*…*coin_n))

Space complexity: O(n)

Python3

652. Find Duplicate SubtreesMedium730151FavoriteShare

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

The following are two duplicate subtrees:

        1
/ \
2   3
/   / \
4   2   4
/
4

2
/
4

and

4

Therefore, you need to return above trees’ root in the form of a list.

## Solution 1: Serialization

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

## C++

Solution 2: int id for each unique subtree

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