1137MediumArrayQueueSortingSimulation

Stacking the Tags to Deal Them in Order

Tracked in this browser only

Trains the technique from

LeetCode 950Reveal Cards In Increasing Order

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 stack of tags is held face down and dealt like this, over and over until nothing is left:

Take the tag at the top of the stack and set it aside.
If any tags remain, move the tag now at the top to the bottom of the stack.

Return an arrangement of the very same tags, listed from top to bottom, whose dealing sets them aside in increasing order. Exactly one arrangement does that.

Examples

Example 1

Input: tags = [1, 2, 3, 4]
Output: [1, 3, 2, 4]

Dealing this arrangement sets aside 1, moves 3 to the bottom, sets aside 2, moves 4 to the bottom, sets aside 3 and finally sets aside 4.

Example 2

Input: tags = [5]
Output: [5]

One tag is set aside straight away with nothing to move.

Example 3

Input: tags = [2, 1]
Output: [1, 2]

The smaller tag goes on top and is set aside first, then the other is moved to the bottom and set aside next.

Constraints

1 <= tags.length <= 1000
1 <= tags[i] <= 10^6
no two tags are the same

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 deck_revealed_increasing(tags: list[int]) -> list[int]:

Java

public int[] deckRevealedIncreasing(int[] tags)

The intended approach

Time O(n log n) for the sort plus O(n) for the walk.Space O(n) for the queue and the answer.

Rather than guess an arrangement and deal it, follow the dealing itself and note which position of the stack is reached at each step. The order those positions come up in is fixed by the rules alone and has nothing to do with the tags. So hold the positions from top to bottom in a queue. Dealing takes the front position, and moving the new top to the bottom sends the next position to the back of the queue. Running that until the queue empties lists the positions in exactly the order the dealing visits them. Then the answer writes itself: put the smallest tag at the first position visited, the next smallest at the second, and so on. Sorting the tags first is what makes the tags come out in increasing order, and the arrangement is forced, which is why only one works.

Pythonentry point: deck_revealed_increasing

def deck_revealed_increasing(tags):
    from collections import deque
    order = sorted(tags)
    spots = deque(range(len(tags)))
    answer = [0] * len(tags)
    for value in order:
        answer[spots.popleft()] = value
        if spots:
            spots.append(spots.popleft())
    return answer

The obvious version

Build the stack backwards. Start with nothing and bring the tags in from largest to smallest, undoing a dealing step each time: send the tag at the bottom back to the top, then put the new tag on top. Once every tag is in, the stack is the arrangement asked for.

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_deck_revealed_increasing(tags):
    from collections import deque
    order = sorted(tags)
    order.reverse()
    stack = deque()
    for value in order:
        if stack:
            stack.appendleft(stack.pop())
        stack.appendleft(value)
    return list(stack)

How this problem was checked

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