In this HackerEarth Disk tower problem solution Your task is to construct a tower in N days by following these conditions:
  1. Every day you are provided with one disk of distinct size.
  2. The disk with larger sizes should be placed at the bottom of the tower.
  3. The disk with smaller sizes should be placed at the top of the tower.
The order in which the tower must be constructed is as follows:
  1. You cannot put a new disk on the top of the tower until all the larger disks that are given to you get placed.
Print N lines denoting the disk sizes that can be put on the tower on an ith day.


HackerEarth Disk tower problem solution


HackerEarth Disk tower problem solution.

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.AbstractCollection;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.io.InputStream;

public class Main {
    public static void main(String[] ARGS) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream IS = System.in;
        OutputStream OS = System.out;
        ScanReader in = new ScanReader(IS);
        PrintWriter out = new PrintWriter(OS);
        DiskTower disktower = new DiskTower();
        disktower.solve(1, in, out);
        out.close();
    }

    static class DiskTower {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int current_need = n;
            PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {

                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });
            for (int i = 0; i < n; i++) {
                int x = in.scanInt();
                if (current_need == x) {
                    out.print(x + " ");
                    current_need--;

                    while (!queue.isEmpty() && current_need == queue.peek()) {
                        out.print(queue.poll() + " ");
                        current_need--;
                    }
                } else {
                    queue.add(x);
                }

                out.println();
            }
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int Total_Char;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= Total_Char) {
                index = 0;
                try {
                    Total_Char = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (Total_Char <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

Second solution

#include<bits/stdc++.h>
using namespace std;

vector<vector<int> > SolveTower (int N, vector<int> a) {
   // Write your code here
   vector<vector<int> > ans;
   int done = N;
   priority_queue<int> pq;
   for(auto x: a){
      pq.push(x);
      vector<int> aux;
      while(!pq.empty() && pq.top() == done){
         aux.push_back(done);
         pq.pop();
         done--;
      }
      ans.push_back(aux);
   }
   sort(a.begin(), a.end());
   a.resize(unique(a.begin(), a.end()) - a.begin());
   assert(a.size() == N);
   return ans;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    assert(1 <= N && N <= 1e6);
    vector<int> a(N);
    for(int i_a = 0; i_a < N; i_a++)
    {
        cin >> a[i_a];
    }

    vector<vector<int> > out_;
    out_ = SolveTower(N, a);
    for(int i = 0; i < out_.size(); i++){
       for(int j = 0; j < out_[i].size(); j++){
          cout << out_[i][j] << " ";
       }
       cout << "\n";
    }
}