Reveal Cards In Increasing Order

Medium

Asked by:

+2

More companies

14 views

Topics:

Arrays

You are given an integer array deck. There is a deck of cards where every card has a unique integer. The integer on the i^th 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:

Take the top card of the deck, reveal it, and take it out of the deck.
If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
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 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 does not matter), and reorder it.
After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck.
We reveal 2, and move 13 to the bottom.  The deck is now [3,11,5,17,7,13].
We reveal 3, and move 11 to the bottom.  The deck is now [5,17,7,13,11].
We reveal 5, and move 17 to the bottom.  The deck is now [7,13,11,17].
We reveal 7, and move 13 to the bottom.  The deck is now [11,17,13].
We reveal 11, and move 17 to the bottom.  The deck is now [13,17].
We reveal 13, and move 17 to the bottom.  The deck is now [17].
We reveal 17.
Since all the cards revealed are in increasing order, the answer is correct.

Example 2:

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

Constraints:

1 <= deck.length <= 1000
1 <= deck[i] <= 10⁶
All the values of deck are unique.

Try coding it in LeetCode

Reveal Cards In Increasing Order

Medium

Asked by:

14 views

Topics:

Arrays

You are given an integer array deck. There is a deck of cards where every card has a unique integer. The integer on the i^th 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:

Take the top card of the deck, reveal it, and take it out of the deck.
If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
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 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 does not matter), and reorder it.
After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck.
We reveal 2, and move 13 to the bottom.  The deck is now [3,11,5,17,7,13].
We reveal 3, and move 11 to the bottom.  The deck is now [5,17,7,13,11].
We reveal 5, and move 17 to the bottom.  The deck is now [7,13,11,17].
We reveal 7, and move 13 to the bottom.  The deck is now [11,17,13].
We reveal 11, and move 17 to the bottom.  The deck is now [13,17].
We reveal 13, and move 17 to the bottom.  The deck is now [17].
We reveal 17.
Since all the cards revealed are in increasing order, the answer is correct.

Example 2:

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

Constraints:

1 <= deck.length <= 1000
1 <= deck[i] <= 10⁶
All the values of deck are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Can the input array contain duplicate values?
What should I return if the input array is empty or null?
Can you clarify what 'increasing order' refers to in the context of revealing the cards? Should the *values* revealed be strictly increasing, or is it sufficient that the *indices* at which they are revealed correspond to an increasing sequence?
If multiple valid orderings exist that satisfy the revealing condition, is any valid ordering acceptable, or is there a specific ordering I should aim to produce?

Brute Force Solution

Approach

The brute force method for revealing cards involves trying every possible order of the cards. We want to find the order that satisfies the card revealing rules. This means we will generate each possible arrangement and test if it works.

Here's how the algorithm would work step-by-step:

Consider all possible arrangements, or shuffles, of the cards.
For each arrangement, simulate the process of revealing the cards one by one according to the given rules.
Specifically, in each simulation check if the next revealed card is indeed the next smallest unrevealed card.
If the card revealing process completes successfully without violating the rule, that arrangement is a valid answer.
If not, discard that arrangement.
After checking all arrangements, the valid arrangements are the solutions.

Code Implementation

import itertools

def reveal_cards_in_increasing_order_brute_force(deck):
    number_of_cards = len(deck)
    possible_arrangements = list(itertools.permutations(deck))

    valid_arrangements = []

    for arrangement in possible_arrangements:
        arrangement_list = list(arrangement)
        revealed = [False] * number_of_cards
        current_index = 0
        revealed_cards = []
        successful = True

        #Iterate to reveal the cards
        for _ in range(number_of_cards):
            # Find the next unrevealed card
            while revealed[current_index % number_of_cards]:
                current_index += 1

            current_index %= number_of_cards
            revealed_cards.append(arrangement_list[current_index])
            revealed[current_index] = True

            current_index += 1

        sorted_deck = sorted(deck)
        #If we reveal the cards in increasing order then this is a valid arrangement
        if revealed_cards == sorted_deck:
            valid_arrangements.append(arrangement_list)

    return valid_arrangements

Big(O) Analysis

Time Complexity

O(n * n!) – The algorithm considers all possible arrangements (permutations) of the deck of cards. There are n! (n factorial) such arrangements for an input deck of size n. For each of these n! permutations, the algorithm simulates the revealing process, which involves iterating through the cards (up to n cards) to determine if the current arrangement is valid. This validation process, for each permutation, takes O(n) time. Therefore, the overall time complexity is O(n * n!).

Space Complexity

O(N) – The brute force approach generates all possible arrangements (permutations) of the input array of size N. While the generation itself might be done in place, storing a single arrangement temporarily requires an auxiliary array of size N. The algorithm checks each arrangement, so it needs space to hold at least one permutation at a time. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The core idea is to simulate the card revealing process backwards. We'll figure out the final card order by figuring out the order we'd place them if we knew how the deck was shuffled.

Here's how the algorithm would work step-by-step:

First, sort all the cards so you know their increasing order.
Imagine an empty list representing the deck with empty spots.
Start filling the deck backwards. The largest card goes into the last revealed position.
To find the last revealed position, simulate the revealing process from the beginning, but instead of revealing, just skip over filled spots. After a reveal, we put the next card in a revealed location after one discarded card.
Every time a 'reveal' happens, we find the next empty spot using the same process and fill it with the next largest card.
Repeat this until all the cards are placed. The resulting deck will be in the order it should be in initially.

Code Implementation

def reveal_cards_in_increasing_order(deck_of_cards):
    number_of_cards = len(deck_of_cards)
    result = [None] * number_of_cards
    card_indices = list(range(number_of_cards))
    sorted_cards = sorted(deck_of_cards)

    # Process cards in decreasing order
    for card in reversed(sorted_cards):
        current_index = card_indices.pop(0)
        result[current_index] = card

        # Simulate discard and reveal
        if card_indices:
            card_indices.append(card_indices.pop(0))

    return result

Big(O) Analysis

Time Complexity

O(n log n) – Sorting the input array of size n initially takes O(n log n) time. The card placement simulation involves iterating up to n times (once for each card). Finding the correct reveal position in each iteration requires traversing the deck, but crucially, we are not necessarily inspecting every position in each iteration. However, given that the plain English explanation focuses on skipping filled spots during the reveal simulation, in the worst case, finding the next empty spot in the deck could involve a nearly linear traversal, making each placement O(n) in the worst case, but more realistically closer to O(1) if the deck fills evenly. Despite this, since this step could potentially lead to the deck being completely traversed for each placement of n cards, we should also consider the sort. Therefore, the dominant cost is the initial sort, and while the revealing process could lead to O(n^2) in a worse-case scenario, its amortized cost is better than the initial sorting cost. Thus, the complexity is O(n log n).

Space Complexity

O(N) – The algorithm sorts the input cards, potentially using O(N) auxiliary space depending on the sorting algorithm. Additionally, an empty list representing the deck of size N is created. Therefore, the dominant factor in space complexity is the creation of a list to store the final deck order, which scales linearly with the input size N.

Edge Cases

Case	How to Handle
Null input array	Throw IllegalArgumentException or return null/empty list based on the API contract.
Empty input array	Return an empty list, as there are no cards to reveal.
Input array with a single element	Return the array containing the single element directly.
Input array with all identical values	The algorithm should correctly reveal these identical values in the specified order.
Input array already sorted in ascending order	The algorithm should correctly handle this case and produce the reveal order.
Input array sorted in descending order	The algorithm should correctly rearrange the cards to reveal in increasing order.
Maximum-sized input array (considering memory constraints)	Ensure that the algorithm's memory usage remains within acceptable limits, potentially using an in-place algorithm if applicable.
Array contains duplicate numbers	The algorithm should correctly handle duplicates, revealing them in the appropriate order based on the reshuffling process.