Queue-Array: April POTD

Day 14/75:

Question: Reveal Cards In Increasing Order -(Medium)

You are given an integer array deck. There is a deck of cards where every card has a unique integer. The integer on the ith card is deck[i].

You can order the deck in any order you want. Initially, all the cards start face down (unrevealed) in one deck.

You will do the following 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.

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

Intuition :

Given in question: Resultant order should reveal the card in Increasing Order

So, I considered result order and followed steps, to check if it is actually giving increasing order: Output: [2,13,3,11,5,17,7]

Steps: Reveal 1st and put next top at the back and continue till all cards are revealed.

Approach

1. Sort the deck.
2. Initialize , i(traverse deck) , j(traverse result) , skip(find pos to insert)
3. Start Traversing through deck.
4. Check,if res[j] is empty and Skip==false , then Assign deck[i] to res[j]. Increment both deck and result pointer.
5. Now, skip next position.But if Skip=true and res[j] is empty ,we can not insert, so increment res position and Skip=falseNow,if value is already present(value !=0 ) in res pointer, so simply move to next position.
6. Return Result array.

Code :

Complexity :

• Time complexity: O(nlogn) ( As we used sorted array )
• Space complexity: O(1) - As we used auxiliary space of O(n) to store result ,which we can ignore.

Approach2:

Here, We won't be using skip flag to indicate position to place value in res.

1. Requirement : Sorted Deck , Queue( indices ) will used to find position of result ( consists of index from 0 to deck.length).
2. Insert all index from 0 to n-1 in queue (Indices), which will decide position of element in result.
3. Now, Start Traversing Deck will follow given condtions.
4. Take top of queue(idx) ,and insert deck[i] at idx position in result.
5. Now,Remove next top index from indices (queue) and push it at back of queue.Continue this,till queue is not empty.
6. Return result array.

Code :

Time Complexity : O(nlogn)

Space Complexity: O(n): As Queue is used to store indices.

My Leetocode Solution: https://leetcode.com/problems/reveal-cards-in-increasing-order/solutions/5008457/100-easy-explanation-with-solution-java/