# Problem

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.


Example 2:

Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.


Note:

• A will be a permutation of [0, 1, ..., A.length - 1].
• A will have length in range [1, 5000].
• The time limit for this problem has been reduced.

# Solution1: Brute Force (TLE)

Time complexity: O(n^2)

Space complexity: O(1)

C++

# Solution2: MergeSort

Time complexity: O(nlogn)

Space complexity: O(n)

C#

# Solution3: Input Property

Input is a permutation of [0, 1, …, N – 1]

Time Complexity: O(n)

Space Complexity: O(1)

# Problem

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there?  (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
Output: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.


Note:

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. 0 <= grid[i][j] <= 15

# Solution

Time complexity: O(m*n)

Space complexity: O(1)

C++

Given a matrix A, return the transpose of A.

The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]


Example 2:

Input: [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]


Note:

1. 1 <= A.length <= 1000
2. 1 <= A[0].length <= 1000

# Solution: Brute Force

Time complexity: O(mn)

Space complexity: O(mn)

# Problem

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.


# Solution: DP

Time complexity: O(n^2*m)

Space complexity: O(n*m)

C++ / Recursion + Memorization

C++ / DP

# Solution: Binary Search

Time complexity: O(log(sum(nums))*n)

Space complexity: O(1)

# Problem

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots – they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True


Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False


Note:

1. The input array won’t violate no-adjacent-flowers rule.
2. The input array size is in the range of [1, 20000].
3. n is a non-negative integer which won’t exceed the input array size.

# Solution: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

Mission News Theme by Compete Themes.