950. Reveal Cards In Increasing Order - Explanation

Problem Link



1. Simulation Using Queue - I

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        deck.sort()
        res = [0] * len(deck)
        q = deque(range(len(deck)))

        for num in deck:
            i = q.popleft()
            res[i] = num
            if q:
                q.append(q.popleft())

        return res

Time & Space Complexity

  • Time complexity: O(nlogn)O(n \log n)
  • Space complexity: O(n)O(n)

2. Simuation Using Queue - II

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        deck.sort()
        q = deque()
        for i in range(len(deck) - 1, -1, -1):
            if q:
                q.append(q.popleft())
            q.append(deck[i])
        return list(q)[::-1]

Time & Space Complexity

  • Time complexity: O(nlogn)O(n \log n)
  • Space complexity: O(n)O(n)

3. Simulation Using Deque

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        deck.sort()
        dq = deque()
        dq.append(deck.pop())
        for i in range(len(deck) - 1, -1, -1):
            dq.appendleft(dq.pop())
            dq.appendleft(deck[i])
        return list(dq)

Time & Space Complexity

  • Time complexity: O(nlogn)O(n \log n)
  • Space complexity: O(n)O(n)

4. Simulation Using Two Pointers

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        n = len(deck)
        res = [0] * n
        skip = False
        deckIndex, i = 0, 0

        deck.sort()

        while deckIndex < n:
            if res[i] == 0:
                if not skip:
                    res[i] = deck[deckIndex]
                    deckIndex += 1
                skip = not skip
            i = (i + 1) % n

        return res

Time & Space Complexity

  • Time complexity: O(nlogn)O(n \log n)
  • Space complexity:
    • O(1)O(1) or O(n)O(n) space depending on the sorting algorithm.
    • O(n)O(n) space for the output array.