Warehouse Bin Grid
A parts warehouse stores bins on a wall of shelves. Each bin has a code. The codes grow from left to right along a shelf, and each shelf starts with a code larger than the last code on the shelf above it. Some codes were retired, so the numbers skip.
A picker gets an order for a code and wants to know, before climbing a ladder, whether that bin exists anywhere on the wall.
Your task
Write hasBin(grid, code). grid[r][c] is the code on shelf r, position c. Every shelf has the same number of bins. Reading the shelves top to bottom, each left to right, gives one strictly increasing sequence.
Return true if code is in the grid, otherwise false. An empty grid (no shelves) returns false. Aim for O(log(rows × cols)).
hasBin(grid: int[][], code: int) → bool
Examples
grid = [[103, 108, 115, 121], [130, 134, 142, 150], [162, 170, 181, 199]] code = 142
true
Laid end to end, the 12 codes form one sorted line. 142 is at position 6 of that line, which is shelf 1, slot 2.
grid = [[103, 108, 115, 121], [130, 134, 142, 150], [162, 170, 181, 199]] code = 125
false
125 would sit between 121 (end of shelf 0) and 130 (start of shelf 1). Neither is 125, and nothing else can be, so the bin does not exist.
Constraints
- 0 ≤ rows ≤ 200, and 1 ≤ cols ≤ 200 when rows > 0
- 1 ≤ grid[r][c], code ≤ 1,000,000
- Read row by row, the codes are strictly increasing.
Start with brute force
Check every bin, shelf by shelf. That is O(rows × cols): 40,000 bins for a 200 × 200 wall.
A middle ground is to binary search each shelf separately, O(rows × log cols). Better, but it still ignores that the shelves are sorted against each other. One binary search over the whole wall needs about 16 looks.
Hints
0 of 4 shown- Hint 1
Imagine unbolting the shelves and placing them end to end in one long row. Is that row sorted?
- Hint 2
It is: 103, 108, 115, 121, 130, 134, … So this is ordinary binary search on a list of
rows × colsitems. The only question is how to read item numberpwithout building the list. - Hint 3
With 4 bins per shelf, item 6 of the long row is on shelf 1 (6 ÷ 4, rounded down) at slot 2 (the remainder). How does that generalise?
- Hint 4
Binary search over positions
0torows × cols - 1. For a middle positionp, readgrid[floor(p / cols)][p % cols]and compare withcodeas usual.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The grid is just a sorted list folded into rows. Search it as one list, and convert a position to a shelf and slot only when you need to read a value: shelf = floor(p / cols), slot = p % cols.
Trace the 3 × 4 example looking for 142. Positions run from 0 to 11:
lo = 0,hi = 11,mid = 5: shelf 1, slot 1, code 134. Too small.lo = 6.lo = 6,hi = 11,mid = 8: shelf 2, slot 0, code 162. Too big.hi = 7.lo = 6,hi = 7,mid = 6: shelf 1, slot 2, code 142. Found.
A common slip is dividing by the number of rows instead of the number of columns. The column count is how many positions each shelf uses up, so it is what you divide by. The single-column and single-row tests catch the mix-up.
function hasBin(grid, code) {
if (grid.length === 0) return false;
const cols = grid[0].length;
let lo = 0, hi = grid.length * cols - 1; // positions in the long row
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
const value = grid[Math.floor(mid / cols)][mid % cols];
if (value === code) return true;
if (value < code) lo = mid + 1;
else hi = mid - 1;
}
return false;
}def has_bin(grid, code):
if not grid:
return False
cols = len(grid[0])
lo, hi = 0, len(grid) * cols - 1 # positions in the long row
while lo <= hi:
mid = (lo + hi) // 2
value = grid[mid // cols][mid % cols]
if value == code:
return True
if value < code:
lo = mid + 1
else:
hi = mid - 1
return FalseRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.