Tap here to switch tabs
Problem
Submissions

Problem: Put Boxes Into the Warehouse II

Put Boxes Into the Warehouse II gives box and room heights; place the maximum number of boxes in one-box rooms, pushing from either end without crossing a shorter room.

Statement

You are given two arrays of positive integers, boxes and warehouse, representing the heights of various boxes of unit width and the heights of nn rooms in a warehouse of unit width, respectively. The warehouse rooms are ordered from left to right, indexed from 00 to n−1n - 1.

Boxes can be pushed into the warehouse from either the left entrance (room 00) or the right entrance (room n−1n - 1). The placement of boxes is subject to the following rules:

  • Each room can hold at most 11 box.

  • A box cannot pass through any room that has a height strictly less than the height of the box.

  • Once a box is placed in a room, it remains there and cannot be moved, preventing any other boxes from passing through that room.

Return the maximum number of boxes that can be placed in the warehouse.

Constraints:

  • n ==== warehouse.length

  • 1≤1 \leq boxes.length, warehouse.length ≤105\leq 10^5

  • 1≤1 \leq boxes[i], warehouse[i] ≤109\leq 10^9

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Put Boxes Into the Warehouse II

Put Boxes Into the Warehouse II gives box and room heights; place the maximum number of boxes in one-box rooms, pushing from either end without crossing a shorter room.

Statement

You are given two arrays of positive integers, boxes and warehouse, representing the heights of various boxes of unit width and the heights of nn rooms in a warehouse of unit width, respectively. The warehouse rooms are ordered from left to right, indexed from 00 to n−1n - 1.

Boxes can be pushed into the warehouse from either the left entrance (room 00) or the right entrance (room n−1n - 1). The placement of boxes is subject to the following rules:

  • Each room can hold at most 11 box.

  • A box cannot pass through any room that has a height strictly less than the height of the box.

  • Once a box is placed in a room, it remains there and cannot be moved, preventing any other boxes from passing through that room.

Return the maximum number of boxes that can be placed in the warehouse.

Constraints:

  • n ==== warehouse.length

  • 1≤1 \leq boxes.length, warehouse.length ≤105\leq 10^5

  • 1≤1 \leq boxes[i], warehouse[i] ≤109\leq 10^9