# Posts published in “Array”

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Example 1:

Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation:
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]


Note:

1. A.length <= 30000
2. 0 <= S <= A.length
3. A[i] is either 0 or 1.

## Solution: Prefix Sum

counts[s] := # of subarrays start from 0 that have sum of s
ans += counts[s – S] if s >= S

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

## C++

In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the i-th domino.  (A domino is a tile with two numbers from 1 to 6 – one on each half of the tile.)

We may rotate the i-th domino, so that A[i] and B[i] swap values.

Return the minimum number of rotations so that all the values in A are the same, or all the values in B are the same.

If it cannot be done, return -1.

Example 1:

Input: A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
Output: 2
Explanation:
The first figure represents the dominoes as given by A and B: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.


Example 2:

Input: A = [3,5,1,2,3], B = [3,6,3,3,4]
Output: -1
Explanation:
In this case, it is not possible to rotate the dominoes to make one row of values equal.


Note:

1. 1 <= A[i], B[i] <= 6
2. 2 <= A.length == B.length <= 20000

## Solution: Brute Force

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

## C++

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]


Example 2:

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


• A straight forward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

## Solution 1

Use two arrays to track whether the i-th row / j-th column need to be zeroed.

Time complexity: O(mn)
Space complexity: O(m+n)

## Solution 2

Use the first row / first col to indicate whether the i-th row / j-th column need be zeroed.

# Problem

Given an array A of integers, return true if and only if it is a valid mountain array.

Recall that A is a mountain array if and only if:

• A.length >= 3
• There exists some i with 0 < i < A.length - 1 such that:
• A[0] < A[1] < ... A[i-1] < A[i]
• A[i] > A[i+1] > ... > A[B.length - 1]

Example 1:

Input: [2,1]
Output: false


Example 2:

Input: [3,5,5]
Output: false


Example 3:

Input: [0,3,2,1]
Output: true

Note:

1. 0 <= A.length <= 10000
2. 0 <= A[i] <= 10000

# Solution

Use has_up and has_down to track whether we have A[i] > A[i – 1] and A[i] < A[i – 1] receptively.

return false if any of the following happened:

1. size(A) < 3
2. has_down happened before has_up
3. not has_down or not has_up
4. A[i – 1] < A[i] after has_down
5. A[i – 1] > A[i] before has_up

Time complexity: O(n)

Space complexity: O(n)

# Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

# Solution

Find the last acceding element x, swap with the smallest number y, y is after x that and y is greater than x.

Reverse the elements after x.

Time complexity: O(n)

Space complexity: O(1)

## Python3

Mission News Theme by Compete Themes.