Reveal Cards In Increasing Order - Leetcode Solution

Problem Statement:

Given an array of integers deck representing a deck of cards, you need to reveal the cards in increasing order one by one.

During the ith turn, you reveal the card with the minimum value in the deck and remove it from the deck, and put it into the output array.

The order of the output array should be such that the first element is the card with the smallest value, the second element is the card with the second smallest value, and so on.

Return an ordering of the deck that would reveal the cards in increasing order.

Note:

• The length of deck will be in the range [1, 1000].
• All the values of deck are unique.

Example 1:

Input: deck = [17,13,11,2,3,5,7] Output: [2,13,3,11,5,17,7] Explanation: We get the deck in the order [17,13,11,2,3,5,7] (this order doesn't matter). We reveal 2, and move the deck to [3,5,7,11,13,17]. We reveal 13, and move the deck to [3,5,7,11,17]. We reveal 3, and move the deck to [5,7,11,17]. We reveal 11, and move the deck to [5,7,17]. We reveal 5, and move the deck to [7,17]. We reveal 17, and move the deck to [7]. We reveal 7, and the deck is now empty.

Example 2:

Input: deck = [1] Output: [1] Explanation: The deck contains only one card, so we reveal it.

Solution Approach:

We need to sort the array in decreasing order, or rather form an increasing array after we solve it. The basic goal is to sort the input array, and then use a stack and simulate the process of putting the card on the bottom of the deck and picking the top card from the remaining deck.

We can first sort the deck, then take one element out at a time, and do some operation to finally achieve the goal. Here are the detailed steps:

• Sort the deck in descending order.
• Create an empty stack and push the first card into it.
• Iterate through the deck, each time we move the top card of the stack to the bottom. Then we push the next card from the deck onto the stack. At the end, the index of the items remaining in the stack exactly represents the output sequence of cards.
• We then reverse this to match our sorted data (which shows up in descending order in this stack).

Time Complexity -

Sorting the deck takes O(NlogN), where N is the length of the deck. The while loop iterates N times, so the total time complexity is O(NlogN). Space Complexity -

In this problem, we use stack, so the space complexity we use is O(N). It is well within our space requirements.

Implementation:

public int[] deckRevealedIncreasing(int[] deck) { int N = deck.length; Arrays.sort(deck); Deque<Integer> index = new LinkedList<>(); for (int i = 0; i < N; i++) { index.add(i); } int[] ans = new int[N]; for (int card : deck) { ans[index.pollFirst()] = card; if (!index.isEmpty()) { index.add(index.pollFirst()); } } return ans; }

1