Uncalibrated Shelf Scans
Group indices of arrays equivalent under uniform shifts and reversal
A library is comparing electronic scans of its shelves. Each scan contains one integer reading per book, in the order the scanner encountered the books.
Two scans describe the same shelf layout if they have the same length and one can be obtained from the other by:
- adding a single integer offset to every reading, and
- optionally reversing the order of all readings.
The offset accounts for different scanner calibrations. Reversal accounts for scanning from the opposite end of a shelf. No readings may be removed or rearranged in any other way.
Given scans, group the zero-based scan indices by shelf layout. Every index must appear in exactly one group, including indices whose layouts have no match.
Return the groups with indices in increasing order within each group, and order the groups by their smallest index. Return an empty list if there are no scans.
Examples
Example 1
Input: scans = [[2,5,9],[12,15,19],[29,25,22],[2,5,10]] Output: [[0,1,2],[3]]
Scans 0 and 1 differ by a uniform offset. Scan 2 matches scan 0 after reversal and an offset. These three indices belong together, while scan 3 has different spacing between its readings.
Example 2
Input: scans = [[7],[-3],[5,5],[100,100],[0]] Output: [[0,1,4],[2,3]]
All one-reading scans describe the same layout because an offset can match any two readings. The two constant two-reading scans also match each other, but cannot match a one-reading scan.
Example 3
Input: scans = [] Output: []
With no scans, there are no groups.
Constraints
- 0 <= scans.length <= 10000
- Every scan contains at least one reading.
- The total number of readings across all scans is at most 10000.
- -1000000000 <= scans[i][j] <= 1000000000
- All readings are integers.
Let T be the total number of readings. The intended solution takes O(T) time and O(T) space, including stored signatures and the returned groups. Offsets are unrestricted integers; only the supplied readings must satisfy the reading bounds.
Hints
Show hint 1Hint 1
What information about a scan remains unchanged when the same offset is added to every reading?
Show hint 2Hint 2
Consider how the differences between neighboring readings change under reversal, then choose a consistent representative for the two possible directions.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the grouping rule if scanners could not scan in reverse?
- How would you maintain these groups as new scans arrive, without reprocessing earlier scans?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem