Noddy's Largest House: Solving the Max-Gap Problem

The Noddy house-gap problem has one moving part: find the largest consecutive gap after sorting houses by position, then return the two house numbers that flank it.

The Problem at a Glance

In the city of Toy Land, N houses sit in a straight line. Each house has a house number and a position measured from the city’s entry point. Noddy wants to build the largest possible house, which means he needs the widest available plot of land. Your task: return the two house numbers (in ascending order) that sit on either side of that widest gap.

The input format:

• numOfHouse: total number of houses (integer)
• houseList: a list of pairs, where each pair is [house_number, position]

Constraints from the problem specification:

• 2 < numOfHouse < 10^6
• 1 <= houseList[i][0] <= numOfHouse
• 0 < houseList[i][1] < 10^6
• No two houses share the same position

Output: a list of two house numbers in ascending order.

Tiebreaker: when multiple gaps share the same maximum size, return the pair whose left boundary position is closest to zero.

Algorithm: Sort by Position, Then Scan

The core insight is that “adjacent” here means adjacent by position on the street, not adjacent by house number. House number 1 might sit at position 9 while house number 2 sits at position 0. They are not physical neighbours. Sorting by position first is what makes consecutive iteration meaningful.

To see why this matters, consider what happens without the sort. If you iterate through the input as given, you compute gaps between houses in the order they appear in the list, not the order they appear on the street. In the worked example, the input order would give you the gap between house 3 (position 7) and house 1 (position 9) as the first pair, computing a gap of 2. That tells you nothing about the available land between those two physical locations unless you know they are actually neighbours. Only after sorting by position do you know which houses are genuinely adjacent.

The algorithm runs in two stages.

Stage 1: Sort

Call sorted(house_list, key=lambda h: h[1]) to produce a new list ordered by position from smallest to largest. Python’s built-in Timsort runs in O(n log n) worst case and O(n) when the input is already ordered, because Timsort detects natural runs. The sort produces a new list; the original input is not modified.

Stage 2: Scan Left to Right

Iterate through the sorted list from index 0 to len - 2. For each consecutive pair at indices i and i + 1:

• Compute the gap: sorted_houses[i + 1][1] - sorted_houses[i][1]
• If this gap is strictly greater than the current maximum, update the maximum and record the two house numbers

Using strict > (not >=) handles the tiebreaker automatically. Iterating left to right through position-sorted houses means the first occurrence of any gap size is the one with the smallest left-boundary position, which is the pair closest to zero. A strict > keeps that first occurrence intact; a >= would overwrite it with later occurrences of the same size.

After the scan, return the two recorded house numbers sorted in ascending order.

Time complexity: O(n log n) from the sort. The scan adds O(n). Overall: O(n log n). Space complexity: O(n) for the sorted copy.

Worked Example, Step by Step

Given numOfHouse = 5 and houseList = [[3, 7], [1, 9], [2, 0], [5, 15], [4, 30]].

After Sorting by Position

House Number	Position
2	0
3	7
1	9
5	15
4	30

Consecutive Gap Scan

• Pair (house 2, house 3): positions 0 and 7, gap = 7. First update; max = 7, record houses 2 and 3.
• Pair (house 3, house 1): positions 7 and 9, gap = 2. Not greater than 7. No update.
• Pair (house 1, house 5): positions 9 and 15, gap = 6. Not greater than 7. No update.
• Pair (house 5, house 4): positions 15 and 30, gap = 15. Greater than 7; max = 15, record houses 5 and 4.

The maximum gap is 15, between house 5 at position 15 and house 4 at position 30. Sorted ascending: [4, 5].

There is no tie in this example, so the tiebreaker does not change the result. The original problem’s expected output of [4, 5] is confirmed correct.

Python Solution

def find_house_numbers(num_of_house, house_list):
    """
    Returns the two house numbers flanking the largest gap.
    In case of a tie, returns the pair closest to position 0.
    """
    # Sort by position (second element of each pair)
    sorted_houses = sorted(house_list, key=lambda h: h[1])

    max_gap = 0
    result = []

    for i in range(len(sorted_houses) - 1):
        gap = sorted_houses[i + 1][1] - sorted_houses[i][1]
        # Strict > preserves the leftmost (closest to position 0) pair on ties
        if gap > max_gap:
            max_gap = gap
            h1 = sorted_houses[i][0]
            h2 = sorted_houses[i + 1][0]
            result = sorted([h1, h2])

    return result


# Verify against the given example
num_of_house = 5
house_list = [[3, 7], [1, 9], [2, 0], [5, 15], [4, 30]]
print(find_house_numbers(num_of_house, house_list))  # Output: [4, 5]

The inner sorted([h1, h2]) call handles the ascending-order requirement without a conditional. If h1 is less than h2 the output is [h1, h2]; if h1 is greater it becomes [h2, h1]. The function never mutates the input list, which makes it safe to call in competitive contexts where the input is reused across test cases.

Edge Cases Worth Knowing

Minimum Valid Input

The constraint is numOfHouse > 2, so the smallest input has three houses. The loop runs len(sorted_houses) - 1 iterations, which is two iterations for three houses. No special handling is needed; the logic is identical to larger inputs.

Already-Sorted Input

An already-position-sorted input does not break correctness or significantly affect runtime. Timsort detects the natural run and completes in O(n). The gap scan is always O(n). So the best case is faster than O(n log n) overall, not broken.

All Consecutive Gaps Equal

If every consecutive gap in the sorted list is the same size, the algorithm records the first pair encountered. That is the pair with the smallest left-boundary position, which is precisely what the tiebreaker requires. No second pass or post-processing is needed.

Large Input

With numOfHouse approaching 10^6, a naive nested loop would run in O(n^2) and time out. The single scan after sorting stays within time limits because the scan step is O(n). The total cost is bounded by the sort at O(n log n).

Minimum Possible Gap

The constraint ensures no two houses share the same position, so the minimum gap between any two consecutive houses in the sorted list is 1. There is no risk of a zero-gap or negative-gap result because positions are distinct positive integers.

Return Value Format

The problem asks for house numbers in ascending order, not positions. The function records house numbers (the first element of each pair) and sorts them before returning. Positions are only used for gap computation and are never included in the output.

Where This Pattern Appears in Placement Rounds

The gap-scan approach belongs to the broader class of sort-then-scan problems. You sort objects by one attribute, then make a single pass to find a maximum, minimum, or running aggregate. TCS Code Vita warmup zones include problems in this class regularly. Spotting the sort-then-scan pattern early in a round leaves more time for harder problems.

For IT jobs for freshers, screening tests at TCS, Wipro, and Infosys typically include at least one sorting-based problem. The position-sorted gap scan is efficient and readable, and it stays well within time limits. Sorting by position rather than house number shows the candidate grasps the problem, not just the mechanics of sorting.

Companies with algorithm-heavy interviews, like those in the Texas Instruments interview questions guide, expect time and space complexity alongside the code. For this problem: O(n log n) time, O(n) space, and an explanation of why strict > handles the tiebreaker in one pass without a second scan.

The sort-then-stride pattern in this solution recurs in variants across placement coding rounds for both IT services and product roles. If you want to see how an LLM walks you through an unfamiliar variant of this problem class or generates stress-test inputs on demand, TinkerLLM is ₹299 for a month of access. Use it to generate problem variants, stress-test inputs, and walk through tiebreaker edge cases on demand.