0512MediumArrayGreedySorting

Shaved Course Wall

Tracked in this browser only

Trains the technique from

LeetCode 1846Maximum Element After Decreasing and Rearranging

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 mason has one block per entry of blocks, and blocks[i] is how many courses of brick block i currently stands. Before building, the mason may apply either operation as often as wanted, in any order:

shave a block down to any smaller whole number of courses, never below 1 and never taller than it already is;
swap two blocks, so the blocks may end up in any order along the wall.

The finished wall, read left to right, must satisfy both rules:

the leftmost block stands exactly 1 course;
neighbouring blocks differ by at most 1 course.

Every block must be used. Return the largest number of courses any block can stand in a finished wall.

Examples

Example 1

Input: blocks = [2, 2, 1, 1, 3]
Output: 3

Shaving the two blocks of three courses down and ordering the wall as 1, 1, 2, 2, 3 obeys both rules, and its tallest block stands 3 courses.

Example 2

Input: blocks = [1, 1, 5]
Output: 2

Ordering the wall as 1, 1, 2 after shaving the tall block from 5 courses to 2 obeys both rules, and its tallest block stands 2 courses.

Example 3

Input: blocks = [1000000000, 1, 1000000000]
Output: 3

Shaving the two tall blocks to 2 and 3 courses and ordering the wall as 1, 2, 3 obeys both rules, and its tallest block stands 3 courses.

Constraints

1 <= blocks.length <= 10^5
1 <= blocks[i] <= 10^9

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 tallest_after_shaving(blocks: list[int]) -> int:

Java

public int tallestAfterShaving(int[] blocks)

The intended approach

Time O(n log n): dominated by the sort, then one linear walk.Space O(1) auxiliary beyond sorting the input in place.

Sort the blocks and walk them left to right, keeping the height of the position just built. The first position is forced to one course. At each later position the height may rise by one course only if the block standing there is tall enough to reach it, and otherwise the block is shaved flush with the previous height, which keeps the neighbour rule and loses nothing. The running height after the last block is the answer.

Pythonentry point: tallest_after_shaving

def tallest_after_shaving(blocks):
    # Sorting puts the blocks in the only order worth building: a shorter block
    # can never carry a taller position than a taller block placed in the same
    # slot. Walking the sorted list, each block either lifts the running height by
    # one course, which needs it to stand above the current height, or is shaved
    # flush with the running height.
    # O(n log n) time, O(1) auxiliary space beyond sorting in place.
    blocks.sort()
    height = 1
    for i in range(1, len(blocks)):
        if blocks[i] > height:
            height += 1
    return height

The obvious version

Try every ordering of the blocks. For a fixed ordering, the tallest each position can stand is one more than the previous position when the block allows it and the block's own height otherwise, so play that forward and keep the tallest position seen across all orderings. Factorial time.

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_tallest_after_shaving(blocks):
    from itertools import permutations
    best = 1
    for order in permutations(blocks):
        run = 1
        top = 1
        for value in order[1:]:
            run = run + 1 if value > run else value
            if run > top:
                top = run
        if top > best:
            best = top
    return best

How this problem was checked

Reference solution executed against 13 test cases — 13 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