# Q1. 1534. Count Good Triplets

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length

|arr[i] - arr[j]| <= a

|arr[j] - arr[k]| <= b

|arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.Return the number of good triplets.

## Note

From constrain `3 <= arr.length <= 100`

, we know this can be solved by `complete search`

aka `Brute force`

1 | class Solution: |

# Q2. 1535. Find the Winner of an Array Game

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

## Note

Stuck here for a long time.

Key point is once we have visited the entire array once, the greatest number will be kept at idx-0.

Hence, we can simply simulate the game and find the first number win k times.

1 | class Solution: |

# 3. 1536. Minimum Swaps to Arrange a Binary Grid

See details in link

## Note

After you realize that this question is about permutation of array, it is not that hard.

Convert matrix into array of numbers by counting the length of continuous `0`

from right side.

1 | class Solution: |

# Q4. 1537. Get the Maximum Score FAILED

See details in link

## Note

I thought this must be a DP problem hence we can easily tell how the state is transit from previous state.

Start with a 2-D DP which cause TLE/MLE.

Was not realize that we should have 2 dictionaries to store the states.

That will reduce the memory/time complexity from M^2 to 2M.

## DP

1 | class Solution: |

## Greedy

1 | class Solution: |

# Summary

- Usually, Q1 Q2 has not magic. Simple complete search or simulation is enough.
- Surprisingly,
`@lru_cache`

cause MLE while native dictionary works.