Night Guard Round
A hotel's corridor is a loop. The rooms along it are numbered in increasing order, and after the highest-numbered room the loop comes back to the lowest. Each night the guard starts the round at a different room and walks the whole loop once, ticking off rooms on a sheet.
So tonight's sheet might read 410, 415, 502, 517, 108, 112, 230, 301: sorted, except that it wraps around once. A guest calls about room 112. Where on the sheet is it?
Your task
Write findRoom(round, room). round holds distinct room numbers: a strictly increasing list that may have been rotated (some prefix moved to the back). Return the index of room in round, or -1 if it is not there.
The rotation may be zero, so the list may be fully sorted. An empty list returns -1. Aim for O(log n).
findRoom(round: int[], room: int) → int
Examples
round = [410, 415, 502, 517, 108, 112, 230, 301] room = 112
5
The sheet climbs from 410 to 517, wraps, and climbs again from 108 to 301. Room 112 is in the second climb, at index 5.
round = [410, 415, 502, 517, 108, 112, 230, 301] room = 300
-1
300 would belong in the second climb between 230 and 301, but there is no room 300.
Constraints
- 0 ≤ round.length ≤ 100,000
- 1 ≤ round[i], room ≤ 1,000,000
- All room numbers are different; round is an increasing list rotated by some amount.
Start with brute force
Read the sheet from the top until you find the room. O(n), up to 100,000 checks.
Plain binary search does not work either: it assumes the whole list is sorted. Searching for 112 in the example, it sees 517 in the middle, decides 112 must be to the left, and never finds it.
Hints
0 of 4 shown- Hint 1
Cut the first example in half at index 3:
[410, 415, 502, 517]and[108, 112, 230, 301]. Is one of the halves sorted? Pick other cut points. Is one side always sorted? - Hint 2
Yes: wherever you cut, at least one side contains no wrap, so it is a normal sorted run. You can tell which by comparing its two ends.
- Hint 3
On the sorted side you can check in O(1) whether
roomlies between its first and last value. If it does, search there. If not, it can only be on the other side. - Hint 4
Standard
lo/hiloop. Atmid: if it is the room, return. Ifround[lo] <= round[mid], the left part is sorted: go left whenround[lo] <= room < round[mid], else go right. Otherwise the right part is sorted: go right whenround[mid] < room <= round[hi], else go left.
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 list wraps at most once, so any cut leaves at least one side that is plainly sorted. Find that side by comparing its ends, ask whether the room fits inside its range, and keep the half that can hold it.
Trace [410, 415, 502, 517, 108, 112, 230, 301] looking for 112:
lo = 0,hi = 7,mid = 3(517). 410 ≤ 517, so the left side 410..517 is sorted. 112 is not between 410 and 517, so it must be on the right.lo = 4.lo = 4,hi = 7,mid = 5(112). Found it: return 5.
A search for 301 takes longer: at mid = 3 the left is sorted and 301 is outside 410..517, so lo = 4; at mid = 5 (112), 108 ≤ 112 so the left 108..112 is sorted, 301 is outside, lo = 6; at mid = 6 (230) the left is sorted, 301 is outside, lo = 7; and mid = 7 finds it.
Watch the <= in round[lo] <= round[mid]. When only two rooms are left, lo and mid are the same index. With a strict <, the code would decide the right side is sorted when it is not, and the two-room tests fail.
function findRoom(round, room) {
let lo = 0, hi = round.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (round[mid] === room) return mid;
if (round[lo] <= round[mid]) {
// lo..mid has no wrap: it is sorted
if (round[lo] <= room && room < round[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
// mid..hi has no wrap: it is sorted
if (round[mid] < room && room <= round[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}def find_room(round, room):
lo, hi = 0, len(round) - 1
while lo <= hi:
mid = (lo + hi) // 2
if round[mid] == room:
return mid
if round[lo] <= round[mid]:
# lo..mid has no wrap: it is sorted
if round[lo] <= room < round[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# mid..hi has no wrap: it is sorted
if round[mid] < room <= round[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.