Reveal Cards In Increasing Order Leetcode Solution

Problem Statement

The Reveal Cards In Increasing Order Leetcode Solution – Given an integer Array named “deck”. In this deck of cards, every card has a unique integer. The integer on the i card is deck[i].  Order the deck in any order and all the cards start face down (unrevealed) in one deck.

Now, Follow the steps repeatedly until all cards are revealed:

1. Take the top card of the deck, reveal it, and take it out of the deck.
2. If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
3. If there are still unrevealed cards, go back to step 1. Otherwise, stop.

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

Note that the first entry in the answer is considered to be the top of the deck.

Example

Input:
deck = [17,13,11,2,3,5,7]

Output: 
[2,13,3,11,5,17,7]

 Explanation:

Input: deck = [17,13,11,2,3,5,7]

Output: [2,13,3,11,5,17,7]

Given deck is in the order [17,13,11,2,3,5,7] but the order doesn’t matter at all because we can reorder it. So we need to reorder it such that the cards reveal in increasing order.

After reordering, it will be [2,13,3,11,5,17,7] where 2 is in the top.

bottom

top

1. We reveal 2, and move 13 to the bottom. The deck is now [3,11,5,17,7,13].

bottom

top

2. We reveal 3, and move 11 to the bottom. The deck is now [5,17,7,13,11].

bottom

top

3. We reveal 5, and move 17 to the bottom. The deck is now [7,13,11,17].

4. We reveal 7, and move 13 to the bottom. The deck is now [11,17,13].

5. We reveal 11, and move 17 to the bottom. The deck is now [13,17].

6. We reveal 13, and move 17 to the bottom. The deck is now [17].

7. We reveal 17.

Example 2:

Input: deck = [1,1000]
Output: [1,1000]

Approach

Idea:

As we want to reveal the cards in increasing order so we need to put the smallest card at index 0, then the second smallest card at index 2, the third smallest card at index 4 so on.

1. We need to sort the given array in decreasing order.
2. Then we take a deque to arrange the cards in such a way so that when we reveal them they are all in increasing order and a result vector to store the final answer.
3. For that First, push the largest element of the given array in the deque from the back.
4. Then we need to iterate in the array, pop the last element from the deque, and push it in the front of the deque, after that push the array element in the front of the deque.
5. Finally, we take the front elements of the deque and push them into our result vector one by one.
6. Return the result vector.

Code

C++ Program of  Reveal Cards In Increasing Order Leetcode Solution:

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        vector<int> res;
        sort(deck.begin(), deck.end());
        reverse(deck.begin(), deck.end());
        deque<int> dq;
        dq.push_back(deck[0]);
        for (int i = 1; i < deck.size(); i++) {
            dq.push_front(dq.back());
            dq.pop_back();
            dq.push_front(deck[i]);
        }
        while(!dq.empty()){
            int value=dq.front();
            dq.pop_front();
            res.push_back(value);
        }
        return res;
    }
};

Java Program of  Reveal Cards In Increasing Order Leetcode Solution:

class Solution {
    
    public int[] deckRevealedIncreasing(int[] deck) {
        int N=deck.length, j=0;
        int[] res = new int[N];
        Deque<Integer> dq = new LinkedList();
        Arrays.sort(deck);
        dq.add(deck[N-1]);
        for (int i = N-2; i >= 0; i--){
            dq.addFirst(dq.pollLast());
            dq.addFirst(deck[i]);
        }
            
        while(!dq.isEmpty()) {
            int value = dq.pollFirst();
            res[j]=value;
            j++;
        }

        return res;
    }
}

Complexity Analysis for Reveal Cards In Increasing Order Leetcode Solution:

Time Complexity:

The time complexity for this code is O(NlogN) + O(N).  As O(NlogN) is asymptotically larger, so we can say that the time complexity is O(NlogN).  O(NlogN) is taken to sort the given array and O(N) is taken to traverse the array and store the result.

Space Complexity:

The space complexity of the above code is O(2N) because of the result array and the deque which we used to solve the problem.