Fit a Box Inside Every Saved Rectangle
Susquehanna International Group (SIG)● MediumFULLTIMEOAProblem statement
Process operations from left to right. Each operation has three integers:
[0, a, b]: save a rectangle with sidesaandb.[1, a, b]: decide whether a box with sidesaandbcan fit inside every rectangle saved before this operation.
A box fits when both of its sides are at most the matching sides of the saved rectangle. You may rotate by 90 degrees. Compare the box with each saved rectangle independently; the required orientation may differ between rectangles. Equal sides fit. A query does not save a rectangle.
If no rectangle has been saved, the query answer is true. Return a Boolean array containing only query answers, in query order. If there are no queries, return an empty array.
Function
fitsEveryRectangle(operations: int[][]) → boolean[]Examples
Example 1
operations = [[1,1,1]]return = [true]There are no saved rectangles, so the only query returns true.
Example 2
operations = [[0,100000,100000]]return = []The only operation saves a rectangle. There are no queries, so the result is empty.
Example 3
operations = [[0,3,3],[0,5,2],[1,3,2],[1,2,4]]return = [true,false]The 3 × 2 box fits inside both 3 × 3 and 5 × 2. The 2 × 4 box cannot fit inside 3 × 3 in either orientation, so the second answer is false.
Constraints
1 <= operations.length <= 100000- Each operation contains exactly three integers.
0 <= operations[i][j] <= 1000000000- Each row is
[type, a, b], where type is 0 or 1 and both sides are positive.