Daily Question – 950. Reveal Cards In Increasing Order

Description: https://leetcode.com/problems/reveal-cards-in-increasing-order/description/?envType=daily-question&envId=2024-04-10

Code: Time Complexity O(n2)

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        if (deck.length == 1) return deck;
        Arrays.sort(deck);
        int[] result = new int[deck.length];
        List<Integer> temp = new ArrayList<>();
        for (int i = deck.length-1; i>=0; i--) {
            temp.clear();
            result[i] = deck[i];
            temp.add(result[result.length-1]);
            for (int j = i+1; j < result.length-1;j++ ) temp.add(result[j]);
            for (int j = i+1; j< result.length;j++) result[j] = temp.get(j-i-1);
        }
        return result;
    }
}

Improvement:

This approach is genius. https://leetcode.com/problems/reveal-cards-in-increasing-order/solutions/5001220/beats-94-easy-approach-using-deque-with-explanation

Deque in Java is a double-ended queue that allows you to add, with syntax deque. addFirst(“”); or deque. addLast(“”); , or remove elements, with syntax, deque. removeFirst(); or deque. removeLast(); from both ends.

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        int n=deck.length;
        Arrays.sort(deck);
        Deque <Integer> st=new ArrayDeque<>();
        st.addFirst(deck[n-1]);
        for(int i=n-2;i>=0;i--){
            st.addFirst(st.removeLast());
            st.addFirst(deck[i]);
        }
        //we can either create a new array or change the existing since we dont need it right??but it is not recommended 

        for(int i=0;i<n;i++){
            deck[i]=(int)st.removeFirst();
        }
        return deck;
    }
}