Divide/Conquer/Combine? Recursion? Greedy? DP?

932. Beautiful Array

This is the first question in leetcode which contains all ideas from Divide/Conquer/Combine, Recursion, Greedy and DP. I dislike this problem at the earlier beginning as I don’t know how to solve it until I found the beauty of this problem after understanding other people’s solutions.

Here are the basic ideas of how to solve the problem.

if we have a list A and A is beautiful. Then 2A is beautiful, 2A+1 is beautiful. It can be easier to prove by contradiction. For example,
A = [1, 3, 2]
2A-1 = [1, 5, 3], 2A = [2, 6, 4]
then (2A-1) + (2A) will also a beautiful array. The proof contains four parts:

1. 2A-1 is beautiful. Proved
2. 2A is beautiful. Proved
3. one elements from 2A-1, two from 2A. Easy to prove as shown here (because i+j will be odd however 2k will be even) :

i      k                j
-------------------------
1      2,4,6,8,10...
3      2,4,6,8,10...
5      2,4,6,8,10...
7      2,4,6,8,10...
9      2,4,6,8,10...
......

4. one elements from 2A, two from 2A-1. Proof is similar to case 3.

Keep on repeating this process, we can build more beautiful array. This is bottom up. If we do it top down, we will solve the problem. Python code for reference.

The python code is here:

from functools import lru_cache
class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        @lru_cache(None)
        def dp(N):
            if N == 1:return [1]
            odds = [2*a-1 for a in dp((N+1)//2)]
            evens = [2*a for a in dp(N//2)]
            return odds+evens
        return dp(N)

From this problem, we can see that we divide the whole problem into left and right part. And left part is all odd numbers and right part is all even numbers. This is a kind of divide/conquer/combine idea. Then “odds = [2*a-1 for a in dp((N+1)//2)]” is using recursion. Since the recursion has overlap subproblems, we can use cache to speed up. This is the DP idea. As it has two branches, it has some similarities as Fibonacci numbers. As the depth of this complete recursion tree is logn. The naive without memo solution complexity is n2^(logn). The cached one is nlogn.

What’s more, the whole problem solving process is using greedy method as we are generating the solution using a greedy way.

A similar but simpler problem is: 1238. Circular Permutation in Binary Representation

The critical step is building a 0 to 2^n-1 number list by a special way to satisfy the requirement of only one bit is different.
one bit, when n==1.
0
1
two bits, when n==2
step 1) add 0 to the left
0 0
0 1
step 2) add 1 to the left, in order to have only one bit different, add ‘1’ to left of reversed n==1 result.
1 1
1 0
Then the whole list satisfies the one-bit different requirement even for the first one and last one.
You can verify this for n==3 case.
0 00
0 01
0 11
0 10

1 10
1 11
1 01
1 00

After figuring out this, the code is simple.

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        def dp(n):
            if n==1:return ['0', '1']
            a = dp(n-1)
            return ['0'+_ for _ in a]+['1'+_ for _ in a[::-1]]
        res = dp(n)
        res = [int(_, 2) for _ in res]
        idx = res.index(start)
        return res[idx:]+res[:idx]

Thanks for reading.

Reference

Odd + Even Pattern, O(N) - LeetCode Discuss

https://leetcode.com/problems/beautiful-array/discuss/186901/JavaScript-How-I-understand-the-solution-(with-verification-of-the-solution)

https://leetcode.com/problems/circular-permutation-in-binary-representation/discuss/414147/Python-recursion/384745/