Skip to content

1564. Put Boxes Into the Warehouse I 👍

Approach 1: Iterate pre-processed warehouse

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int maxBoxesInWarehouse(vector<int>& boxes, vector<int>& warehouse) {
    vector<int> realWarehouse{warehouse[0]};

    for (int i = 1; i < warehouse.size(); ++i)
      realWarehouse.push_back(min(realWarehouse.back(), warehouse[i]));

    sort(boxes.begin(), boxes.end());
    int i = 0;  // boxes' index
    for (int j = realWarehouse.size() - 1; j >= 0; j--)
      if (i < boxes.size() && boxes[i] <= realWarehouse[j])
        ++i;

    return i;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
    int[] realWarehouse = new int[warehouse.length];
    realWarehouse[0] = warehouse[0];

    for (int i = 1; i < warehouse.length; i++)
      realWarehouse[i] = Math.min(realWarehouse[i - 1], warehouse[i]);

    Arrays.sort(boxes);
    int i = 0; // boxes' index
    for (int j = realWarehouse.length - 1; j >= 0; j--)
      if (i < boxes.length && boxes[i] <= realWarehouse[j])
        ++i;

    return i;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
    realWarehouse = [warehouse[0]]

    for i in range(1, len(warehouse)):
      realWarehouse.append(min(realWarehouse[-1], warehouse[i]))

    boxes.sort()
    i = 0  # boxes' index
    for height in reversed(realWarehouse):
      if i < len(boxes) and boxes[i] <= height:
        i += 1

    return i

Approach 2: Iterate boxes

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int maxBoxesInWarehouse(vector<int>& boxes, vector<int>& warehouse) {
    int i = 0;  // warehouse's index

    sort(boxes.rbegin(), boxes.rend());

    for (const int box : boxes)
      if (i < warehouse.size() && warehouse[i] >= box)
        ++i;

    return i;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
    boxes = Arrays.stream(boxes)
                .boxed()
                .sorted(Collections.reverseOrder())
                .mapToInt(Integer::intValue)
                .toArray();
    int i = 0; // warehouse's index

    for (final int box : boxes)
      if (i < warehouse.length && warehouse[i] >= box)
        ++i;

    return i;
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
    i = 0  # warehouse's index

    for box in sorted(boxes, reverse=True):
      if i < len(warehouse) and warehouse[i] >= box:
        i += 1

    return i