reveal cards in Increasing order

XXX. Deck Revealed Increasing

Simulation

Sorting

Queue

Problem Statement:

You are given an integer array deck where the elements represent card values. The goal is to arrange the deck in such a way that when revealed in the following manner, the cards appear in increasing order:

• Take the top card and reveal it.
• If there are still cards in the deck, move the next card to the bottom of the deck.
• Repeat until all cards are revealed.

Return the deck arranged in the order needed to achieve this reveal sequence.

Algorithm:

1. Sort the Deck:

   Sort the deck array in ascending order. This ensures that the smallest card is placed first during the reveal process.

2. Simulate Using a Queue:

   Use a queue to simulate the card reveal process:

   • Initialize the queue with indices from 0 to N-1.
   • For each card in the sorted deck:
   • Assign the current card to the position indicated by the front of the queue.
   • Move the next index in the queue to the back to simulate moving a card to the bottom of the deck.
3. Return the Result:

   The resulting array contains the deck arranged in the desired order.

Complexity:

Time Complexity: O(N log N), where N is the size of the deck, due to the sorting operation.
Space Complexity: O(N), due to the use of a queue and the result array.

Java Implementation:

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        int N = deck.length;
        Queue queue = new LinkedList<>();

        // Create a queue of indexes
        for (int i = 0; i < N; i++) 
            queue.add(i);
        
        Arrays.sort(deck);

        // Put cards at correct index in result
        int[] result = new int[N];
        for (int i = 0; i < N; i++) {
            // Reveal Card and place in result
            result[queue.poll()] = deck[i];

            // Move next card to bottom
            if (!queue.isEmpty())
                queue.add(queue.poll());
        }
        return result;
    }
}