Ranking: 133 / 14301 😋😋😋

# Q1. 1502. Can Make Arithmetic Progression From Sequence

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

## Note

Was not clear about the description at the very beginning.

The question is easy after fully understand the description.

1 | class Solution: |

# Q2. 1503. Last Moment Before All Ants Fall Out of a Plank

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank.

## Note

Again, spend a while to understand the description.

## Key observation

`When two ants moving in two different directions meet at some point, they change their directions and continue moving again.`

This is a trap. The rule is a redundant, which can be ignore.

Once we understand this point, the answer is very straight forward.

Be careful about the corner case where `left`

or `right`

is empty.

1 | class Solution: |

# Q3. 1504. Count Submatrices With All Ones

Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.

Example 1:

Input: mat =

[[1,0,1],

[1,1,0],

[1,1,0]] .

Output: 13

Explanation:

There are 6 rectangles of side 1x1.

There are 2 rectangles of side 1x2.

There are 3 rectangles of side 2x1.

There is 1 rectangle of side 2x2.

There is 1 rectangle of side 3x1.

Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

## Intuition

This looks like a DP problem at first glance.

But I was not able to define a clear `state transformation formula`

.

End up as a greedy solution.

Very similar to 85. Maximal Rectangle

1 | class Solution: |

# Q4. 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits…

Given a string num representing the digits of a very large integer and an integer k.

You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

E.g. num = “4321”, k = 4 ->>>> “1342”

E.g. Input: num = “100”, k = 1 ->>>>> “010”

## Intuition

### Key observation

You can move a digit k steps with k time of adjacent swapping.

With that in mind, we start from the most significant digit (left most). Find smallest digit within the range of K and move it the the beginning.

Repeat the above algo and update K until K == 0, we will find the answer.

### Naive solution

1 | # O(N^2) |

## Binary Index Tree

Wikipedia: A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

1 | class BIT: |

## Self Balanced Tree in Python

1 | from sortedcontainers import SortedList |

# Summary

`Binary Index Tree`

is not that hard to remember and implement.`from sortedcontainers import SortedList`

is the counter part of C++’s`multiset`

in Python