Quick Overview

Given the left coordinates of document bounding boxes listed from top to bottom, group the boxes into indentation levels using a 0.01 tolerance, number the levels from left to right, and return each box's level in input order. Tests tolerance-based grouping of floating-point values, chained closeness and mapping groups back to positions.

Group Document Bounding Boxes into Indentation Levels with a 0.01 Left Tolerance

Company: Reducto

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A document parser returns the text blocks of a document as bounding boxes, listed from top to bottom. Each box has `left`, `top`, `width`, `height` and `page` fields. Group the boxes into indentation levels by their `left` coordinate, treating `left` values that differ by at most `0.01` as the same indentation, number the levels from left to right, and return the level number of every box in the original input order. Only `left` determines the grouping: the other fields are not used, and boxes on different pages are grouped together. The function therefore receives just the `left` value of each box, in input order. ### Function Signature ```python def group_indentation_levels(lefts: list[float]) -> list[int]: ``` ### Rules - Two boxes are *close* when their `left` values differ by at most `0.01`. - Two boxes are in the same level exactly when they are connected by a chain of close boxes: box `a` is close to box `b`, `b` is close to `c`, and so on. Two boxes in the same level can therefore differ by more than `0.01` when boxes between them link them. - Boxes with equal `left` values are always in the same level. - Levels are numbered `1, 2, 3, ...` from left to right: every `left` in level `g` is smaller than every `left` in level `g + 1`. - `answer[i]` is the level number of the box at index `i`. The first box need not be in level 1, and later boxes may return to an earlier level. ### Constraints - `1 <= len(lefts) <= 10^5` - `0.0 <= lefts[i] <= 1.0` (normalized page coordinates) - No two values in `lefts` differ by an amount within `10^-9` of `0.01`, so floating-point rounding never decides whether two boxes are close. - Every output value is an integer between `1` and `len(lefts)`. ### Examples **Example 1** ```text Input: lefts = [0.30, 0.10, 0.305, 0.105] Output: [2, 1, 2, 1] ``` `0.10` and `0.105` differ by `0.005` and form level 1; `0.30` and `0.305` form level 2. The first box is not in the leftmost level. **Example 2** ```text Input: lefts = [0.20, 0.05, 0.12, 0.055, 0.125, 0.20, 0.048] Output: [3, 1, 2, 1, 2, 3, 1] ``` The levels are `{0.048, 0.05, 0.055}`, `{0.12, 0.125}` and `{0.20, 0.20}`. Later boxes keep returning to earlier levels. **Example 3** ```text Input: lefts = [0.116, 0.100, 0.108, 0.300] Output: [1, 1, 1, 2] ``` `0.100` and `0.116` differ by `0.016`, more than the tolerance, but each is within `0.01` of `0.108`, so the chain puts all three boxes in level 1.

Overview: Given the left coordinates of document bounding boxes listed from top to bottom, group the boxes into indentation levels using a 0.01 tolerance, number the levels from left to right, and return each box's level in input order. Tests tolerance-based grouping of floating-point values, chained closeness and mapping groups back to positions.

A document parser returns the text blocks of a document as bounding boxes, listed from top to bottom. Each box has `left`, `top`, `width`, `height` and `page` fields. Group the boxes into indentation levels by their `left` coordinate, treating `left` values that differ by at most `0.01` as the same indentation, number the levels from left to right, and return the level number of every box in the original input order. Only `left` determines the grouping: the other fields are not used, and boxes on different pages are grouped together. The function therefore receives just the `left` value of each box, in input order, as the list `lefts`. Implement `group_indentation_levels(lefts)`, which returns a list `answer` holding one integer per box. ### Rules - Two boxes are *close* when their `left` values differ by at most `0.01`. - Two boxes are in the same level exactly when they are connected by a chain of close boxes: box `a` is close to box `b`, `b` is close to `c`, and so on. Two boxes in the same level can therefore differ by more than `0.01` when boxes between them link them. - Boxes with equal `left` values are always in the same level. - Levels are numbered `1, 2, 3, ...` from left to right: every `left` in level `g` is smaller than every `left` in level `g + 1`. - `answer[i]` is the level number of the box at index `i`. The first box need not be in level 1, and later boxes may return to an earlier level. ### Example 1 ```text Input: lefts = [0.30, 0.10, 0.305, 0.105] Output: [2, 1, 2, 1] ``` `0.10` and `0.105` differ by `0.005` and form level 1; `0.30` and `0.305` form level 2. The first box is not in the leftmost level. ### Example 2 ```text Input: lefts = [0.116, 0.100, 0.108, 0.300] Output: [1, 1, 1, 2] ``` `0.100` and `0.116` differ by `0.016`, more than the tolerance, but each is within `0.01` of `0.108`, so the chain puts all three boxes in level 1. `0.300` is not close to any of them and forms level 2. ### Constraints - `1 <= len(lefts) <= 10^5` - `0.0 <= lefts[i] <= 1.0` (normalized page coordinates) - No two values in `lefts` differ by an amount within `10^-9` of `0.01`, so floating-point rounding never decides whether two boxes are close. - Every output value is an integer between `1` and `len(lefts)`. The inputs are double-precision floating-point numbers (Java `double[]`, C++ `std::vector<double>`). No output value can exceed `10^5`, so none exceeds `2^31 - 1` and a 32-bit integer suffices.

Constraints

  • 1 <= len(lefts) <= 10^5
  • 0.0 <= lefts[i] <= 1.0 (normalized page coordinates)
  • No two values in lefts differ by an amount within 10^-9 of 0.01, so floating-point rounding never decides whether two boxes are close.
  • Every output value is an integer between 1 and len(lefts).

Examples

Input: ([0.42],)

Expected Output: [1]

Explanation: Minimum valid input: a single box forms level 1.

Input: ([1.0, 0.0],)

Expected Output: [2, 1]

Explanation: Both coordinate bounds: 0.0 and 1.0 are 1.0 apart, so they are separate levels and the first box is in level 2.

Hints

  1. Two boxes can share a level even when their lefts differ by more than 0.01. What must lie between them for that to happen?
  2. Level numbers follow left-to-right position, not the order in which boxes appear in the input.
  3. Boxes with equal lefts always share a level, so a value that repeats later in the input returns to the level it already has.

Loading coding console...

Show the approach

Approach

Algorithm: sort the boxes by left while remembering their original indices, then sweep the sorted order once. The first box opens level 1; every later box opens a new level when its gap to its sorted predecessor exceeds 0.01, and otherwise joins the current level. Each level number is written back at the box's original index, so the answer follows input order.

Invariant: after the sweep has processed the first k sorted values, every level assigned so far is a maximal run of consecutive sorted values whose neighbouring gaps are all at most 0.01, and the runs are numbered in increasing order of left.

Correctness: two neighbouring sorted values with a gap of at most 0.01 are close, so a run of such gaps is one chain and belongs to one level, even when its total span exceeds 0.01. Where the gap between neighbours s[k-1] and s[k] exceeds 0.01, every value at or below s[k-1] differs by more than 0.01 from every value at or above s[k], so no close pair, and therefore no chain, crosses that gap. The levels are therefore exactly the runs. The runs occupy disjoint, increasing ranges of left, so numbering them in sweep order gives 1, 2, 3, ... from left to right. Equal values have a gap of 0 and always share a level. Each value must be compared with its sorted neighbour, not with the first value of the current level; otherwise a long chain would be split.

Floating point: no two inputs differ by an amount within 10^-9 of 0.01, while a double subtraction of values in [0, 1] errs by about 10^-16, so the comparison gap > 0.01 gives the exact-arithmetic answer in every language.

Edge cases: a single box returns [1]; all-equal input returns all 1s; the first box may sit in any level, and later boxes may return to earlier levels.

Time complexity:
O(n log n)
Space complexity:
O(n)