0494EasyArrayHash TableSorting

Absent Marker Posts

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A survey crew walks a trail and notes the number stamped on every marker post it comes across. found[i] is the number on the i-th post noted down. The crew doubles back a few times, so the notes are in no particular order and a post can appear in them more than once.

Take the smallest number in found and the largest number in found. Return, in increasing order, every whole number that lies strictly between those two and does not appear anywhere in found. Return an empty list when there is no such number.

Examples

Example 1

Input: found = [17, 12, 20, 12, 15]
Output: [13, 14, 16, 18, 19]

The notes run from 12 up to 20, and of the numbers in between only 15 and 17 were noted, so the rest are reported.

Example 2

Input: found = [63, 61, 62]
Output: []

The span from 61 to 63 has just 62 inside it, and 62 was noted, so nothing is missing.

Example 3

Input: found = [88, 88]
Output: []

The smallest and largest notes are the same number, so the span between them holds nothing at all.

Constraints

2 <= found.length <= 100
1 <= found[i] <= 100

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def absent_posts(found: list[int]) -> list[int]:

Java

public List<Integer> absentPosts(int[] found)

The intended approach

Time O(n + span)Space O(n)

Only the smallest and largest notes matter for the span, and only membership matters inside it, so put every note into a set and take the smallest and largest in the same sweep. Then count upward through the open span and collect the numbers the set does not hold, which comes out in increasing order for free.

Pythonentry point: absent_posts

def absent_posts(found):
    # The span to inspect runs between the smallest and largest numbers written
    # down, and membership only needs a set, so one pass over that span is enough.
    # time O(n + span), space O(n) for the set of numbers seen
    seen = set(found)
    low = min(found)
    high = max(found)
    gaps = []
    for value in range(low + 1, high):
        if value not in seen:
            gaps.append(value)
    return gaps

The obvious version

Find the extreme notes with a plain scan, then walk every number the constraints allow and, for the ones inside the open span, rescan the whole note list to see whether the number is there. Uses no set and no sort.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_absent_posts(found):
    low = found[0]
    high = found[0]
    for x in found:
        if x < low:
            low = x
        if x > high:
            high = x
    out = []
    for value in range(1, 101):
        if low < value < high:
            present = False
            for x in found:
                if x == value:
                    present = True
                    break
            if not present:
                out.append(value)
    return out

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in