Ranking: 678 / 8571

# Q1. 1475. Final Prices With a Special Discount in a Shop

Given the array prices where prices[i] is the price of the ith item in a shop. There is a special discount for items in the shop, if you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i], otherwise, you will not receive any discount at all.

Return an array where the ith element is the final price you will pay for the ith item of the shop considering the special discount.

Solved it by using brute force in contest. O(N^2)

1 | class Solution: |

## Intuition

- Subtract each value by next smaller number
- Equivalent to subtract each value from all its previous greater number
- Monotonic stack !!!

1 | class Solution: |

# Q2. 1476. Subrectangle Queries

Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports two methods:

- updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

Updates all values with newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is (row2,col2).- getValue(int row, int col)

Returns the current value of the coordinate (row,col) from the rectangle.

Solved it by using brute force in contest.

1 | class SubrectangleQueries: |

## Intuition

- Value updates -> Snapshot search
- Share the same idea with 1146. Snapshot Array

1 | class SubrectangleQueries: |

# Q3. 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

## Intuition

- Easy to find the shortest subarray with target sum
- Iterate through each index and find the smallest length of valid subarray from left and right side

1 | class Solution: |

## Cleaner code

Add some DP thinking here.

1 | class Solution: |

# Q4. [**FAILED**] 1478. Allocate Mailboxes

Directly heading to `3D`

DP during contest which end up as `Time Limit Exceeded`

.

### 3D DP -> TLE

1 | class Solution: |

# 2D DP

1 | class Solution: |

# Summary

- Try
`monotonic stack / queue`

when its related to`next/prev`

`greater/smaller`

element. - Try to record less status when a higher dimension DP is too slow.