Faits :
A.
X._ a été incarcéré à la prison de Champ-Dollon du 22 juin 2014 au 24 novembre 2014 en détention provisoire, puis du 25 novembre 2014 au 17 mai 2016 en exécution de peine en application du jugement du Tribunal correctionnel du 25 novembre 2014 le condamnant à une peine privative de liberté de 34 mois, sous déduction de 158 jours de détention avant jugement.
B.
Le 10 décembre 2016, X._ a sollicité du Département de la sécurité du canton de Genève (ci-après: le département) la vérification de la licéité de ses conditions de détention en prison avant jugement et durant l'exécution de la peine.
C.
Par décision du 20 juin 2017, le département a déclaré irrecevable la requête en indemnisation, faute de compétence et a constaté que les conditions dans lesquelles s'était déroulée la détention de X._ du 23 juin 2014 au 15 février 2015 au sein de la prison étaient licites.
En substance, le département s'est déclaré incompétent pour connaître de la requête en indemnisation, indiquant que celle-ci relève de la compétence du Tribunal de première instance (en référence à la loi genevoise sur la responsabilité de l'Etat et des communes). En revanche, le département s'est déclaré compétent pour se prononcer sur la licéité des conditions de détention avant jugement et en exécution de peine.
D.
Par arrêt du 16 octobre 2018, la Chambre administrative de la Cour de justice de la République et canton de Genève a rejeté le recours de X._, dans la mesure de sa recevabilité.
D.a. En substance, elle a déclaré que le recours était irrecevable s'agissant des prétentions de X._ en réparation du préjudice résultant des conditions de détention prétendument illicites, faute de compétence.
Concernant la constatation de l'illicéité des conditions de détention, la cour cantonale a distingué la période de détention provisoire de celle postérieure au jugement du tribunal correctionnel. S'agissant de la période de détention avant jugement pénal, la cour cantonale a déclaré le recours irrecevable, faute d'intérêt pour agir de X._. S'agissant de la période de détention après jugement pénal, la cour cantonale a rejeté le recours, constatant que les conditions de détention de X._ étaient licites.
D.b. En substance l'arrêt cantonal repose sur les faits suivants.
A quelques exceptions près, du 25 juin 2014 au 22 février 2015, X._ a occupé, avec deux codétenus, des cellules dont la surface individuelle a oscillé entre 3.39 m2 et 3.61 m2.
Pendant cette période, X._ bénéficiait d'une heure de promenade quotidienne et d'une heure de sport hebdomadaire dans la grande salle de gymnastique. Il avait la possibilité d'accéder à la petite salle de sport, à sa demande, pendant une heure, deux ou trois jours par semaine de manière cyclique. Il a occupé un poste de nettoyeur de tables du 12 au 20 janvier 2015 pendant une heure par jour, 7 jours sur 7 et un poste à la cuisine du 16 février 2015 au 17 mai 2016, lequel impliquait une présence quotidienne de 8h00 à 11h00 une semaine sur deux et de 12h45 à 18h30 l'autre semaine.
Du 26 juillet 2014 au 26 mai 2015, les deux codétenus de X._ ont travaillé aux ateliers de reliure et de cuisine. L'atelier cuisine occupait tous les jours un codétenu 3h une semaine et 5h45 la semaine suivante. Le codétenu travaillant à l'atelier de reliure était absent 5h par jour, les jours ouvrés.
E.
X._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt cantonal et conclut, avec suite de frais et dépens, à sa réforme en ce sens qu'il est constaté que ses conditions de détention ont été illicites pendant 236 jours consécutifs du 23 juin 2014 au 15 février 2015. Subsidiairement, il conclut au renvoi de la cause à la cour cantonale pour nouvelle décision dans le sens des considérants. Il requiert le bénéfice de l'assistance judiciaire.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (art. 29 al. 1 LTF) et contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 358).
Selon l'art. 33 let. a du Règlement du 20 novembre 2006 du Tribunal fédéral (RTF; RS 173.110.131), la Cour de droit pénal traite les recours en matière pénale ainsi que les recours en matière de droit public et les recours constitutionnels subsidiaires en matière pénale dans les domaines relevant du droit pénal matériel (y compris l'exécution des peines et des mesures).
Le litige porte sur l'éventuelle responsabilité du canton de Genève à l'égard du recourant résultant de ses conditions de détention avant et après jugement. L'arrêt attaqué peut en principe faire l'objet d'un recours en matière de droit public au Tribunal fédéral (art. 82 let. a LTF; cf. arrêts 6B_1085/2016 du 28 août 2017 consid. 1; 6B_703/2016 du 2 juin 2017 consid. 1). Dans la mesure où le recourant fait valoir une violation des art. 3 et 13 CEDH et reproche à la cour cantonale d'avoir commis un déni de justice (cf. art. 29 al. 1 Cst.), il invoque des droits de nature constitutionnelle (cf. <ref-ruling> consid. 1.3.1 p. 79 s.; arrêt 6B_1244/2016 du 31 octobre 2017 consid. 1.3 et la référence citée). En cela, le recours constitutionnel subsidiaire est ouvert (cf. art. 116 LTF), indépendamment de la question de la valeur litigieuse (cf. art. 85 al. 1 let. a LTF).
2.
Le recours est expressément circonscrit au refus de statuer sur l'illicéité des conditions de détention avant jugement et au constat du caractère licite des conditions de détention en exécution de peine (mémoire de recours, let. B p. 5).
Dans un premier temps, le recourant considère que la cour cantonale a violé les art. 3 et 13 CEDH et commis un déni de justice en déclarant son recours irrecevable s'agissant du constat du caractère illicite des conditions de détention avant jugement.
2.1. L'art. 3 CEDH prévoit que nul ne peut être soumis à la torture ni à des peines ou traitements inhumains ou dégradants. Sur le plan constitutionnel, l'art. 7 Cst. prescrit de son côté que la dignité humaine doit être respectée et protégée. A teneur de l'art. 10 al. 3 Cst., la torture et tout autre traitement ou peine cruels, inhumains ou dégradants sont interdits. En se référant à la Recommandation Rec (2006) 2 sur les Règles pénitentiaires européennes (ci-après: RPE) édictée par le Comité des ministres du Conseil de l'Europe le 11 janvier 2006, ainsi qu'au Commentaire de ces règles émanant du Comité européen pour la prévention de la torture et des peines ou traitements inhumains ou dégradants (CPT), la jurisprudence a déduit de l'art. 3 CEDH ainsi que des autres normes protégeant la dignité humaine, en droit international et en droit interne, un certain nombre de critères permettant d'évaluer si les conditions concrètes de détention se situent en deçà ou au-delà du seuil du traitement inhumain ou dégradant. Un traitement dénoncé comme contraire à l'art. 3 CEDH doit atteindre un niveau d'humiliation ou d'avilissement supérieur à ce qu'emporte habituellement la privation de liberté. La gravité de cette atteinte est appréciée au regard de l'ensemble des données de la cause, considérées globalement, notamment de la nature et du contexte du traitement ainsi que de sa durée (<ref-ruling> consid. 6.3.4 p. 146 s.; <ref-ruling> consid. 4 p. 278 et les arrêts cités). Celle-ci est susceptible de rendre incompatible avec la dignité humaine une situation qui ne le serait pas nécessairement sur une courte période. Sans viser à l'exhaustivité, il s'agit d'apprécier, notamment, si le lieu de détention répond à des exigences minimales quant à l'hygiène (propreté; accès aux installations de bain et de douche et aux sanitaires; protection de l'intimité), à la literie, à la nourriture (régime alimentaire; hygiène de la préparation et de la distribution; accès à l'eau potable), à l'espace au sol, au volume d'air, à l'éclairage et à l'aération, en tenant compte notamment des conditions climatiques locales et des possibilités d'effectuer des exercices à l'air libre (arrêts 6B_1244/2016 du 31 octobre 2017 consid. 2.1; 6B_688/2015 du 19 mai 2016 consid. 7.2).
S'agissant de l'espace au sol, le Tribunal fédéral a jugé qu'en cas de surpopulation carcérale telle que la connaît la prison de Champ-Dollon, l'occupation d'une cellule dite individuelle par trois détenus - chacun disposant d'un espace individuel de 4 m2 restreint du mobilier - est une condition difficile mais ne représente pas un traitement dégradant portant atteinte à la dignité humaine des détenus. En revanche, l'occupation d'une cellule dite triple par six détenus avec une surface individuelle de 3,83 m2 - restreinte encore par le mobilier - peut constituer une violation de l'art. 3 CEDH si elle s'étend sur une longue période (s'approchant, à titre indicatif, de trois mois) et si elle s'accompagne d'autres mauvaises conditions de détention, en particulier lorsque le détenu n'est autorisé qu'à passer un temps très limité hors de sa cellule (une heure de promenade en plein air par jour; voir <ref-ruling> consid. 3.6.3 p. 138 ss; voir aussi l'arrêt 6B_456/2015 du 21 mars 2016 consid. 2.1 et les arrêts cités).
2.1.1. Aux termes de l'art. 29 al. 1 Cst., toute personne a droit, dans une procédure judiciaire ou administrative, à ce que sa cause soit traitée équitablement et jugée dans un délai raisonnable. Il y a déni de justice formel lorsqu'une autorité n'applique pas ou applique d'une façon incorrecte une règle de procédure, de sorte qu'elle ferme l'accès à la justice au particulier qui, normalement, y aurait droit. L'autorité qui se refuse à statuer, ou ne le fait que partiellement, viole l'art. 29 al. 1 Cst. (cf. <ref-ruling> consid. 3.1 p. 192 et les références citées).
2.1.2. Selon la jurisprudence, lorsqu'une irrégularité constitutive d'une violation d'une garantie conventionnelle ou constitutionnelle a entaché la procédure relative à la détention provisoire, celle-ci peut être réparée par une décision de constatation (<ref-ruling> consid. 2.1 p. 352; <ref-ruling> consid. 2.5.1 p. 250; <ref-ruling> consid. 2.4 p. 85). Une telle décision vaut notamment lorsque les conditions de détention provisoire illicites sont invoquées devant le juge de la détention. A un tel stade de la procédure, seul un constat peut donc en principe intervenir et celui-ci n'a pas pour conséquence la remise en liberté du prévenu (<ref-ruling> consid. 3.4 p. 45). Il appartient ensuite à l'autorité de jugement d'examiner les possibles conséquences des violations constatées, par exemple par le biais d'une indemnisation fondée sur l'art. 431 CPP ou, cas échéant, par une réduction de la peine (<ref-ruling> consid. 2.1 p. 352; <ref-ruling> consid. 2.5.1 p. 250; <ref-ruling> consid. 2.1 p. 128; <ref-ruling> consid. 3.4 p. 45).
Les conclusions en constatation de droit ne sont recevables que lorsque des conclusions condamnatoires ou formatrices sont exclues. Sauf situations particulières, les conclusions constatatoires ont donc un caractère subsidiaire. Cette règle est cependant tempérée par le droit, déduit de l'art. 13 CEDH, qu'ont les personnes qui se prétendent victimes de traitements prohibés au sens des art. 10 al. 3 Cst. et 3 CEDH de bénéficier d'une enquête prompte et impartiale devant aboutir, s'il y a lieu, à la condamnation pénale des responsables. Il est, par exemple, admis que l'autorité chargée du contrôle de la détention, si elle est saisie d'allégations de mauvais traitements au sens de l'art. 3 CEDH, se doit de vérifier si la détention a lieu dans des conditions acceptables; dans de telles situations, il faut assurer immédiatement une enquête prompte et sérieuse. Il existe également un intérêt à faire constater immédiatement de telles violations lorsqu'est éloignée l'occasion de requérir devant le juge du fond une réduction de peine ou éventuellement une indemnisation (<ref-ruling> consid. 3.4.2 p. 356 et les arrêts cités).
Conformément à l'art. 13 CEDH, toute personne dont les droits et libertés reconnus dans cette convention ont été violés, a droit à l'octroi d'un recours effectif devant une instance nationale, alors même que la violation aurait été commise par des personnes agissant dans l'exercice de leurs fonctions officielles. Pour qu'un système de protection des droits des détenus garantis par l'art. 3 CEDH soit effectif, des remèdes préventifs et compensatoires doivent exister de façon complémentaire. L'importance particulière de cette disposition impose que les États établissent, au-delà d'un simple recours indemnitaire, un mécanisme effectif permettant de mettre rapidement un terme à tout traitement contraire à l'art. 3 CEDH (cf. arrêts 6B_1097/2016 du 13 septembre 2017 consid. 2.2 et 2.3, 6B_1008/2015 et 6B_1071/2015 du 18 juillet 2016 consid. 6.1 et les références citées).
2.1.3. Dans un arrêt traitant du droit d'obtenir un constat de l'illicéité des conditions de détention, le Tribunal fédéral a considéré que le seul fait, pour le détenu, de ne pas réclamer l'examen de ses conditions de détention durant la procédure pénale ne pouvait valoir renonciation, dans la mesure où aucun élément ne permettait de supposer qu'il avait contrevenu à la bonne foi en procédure (arrêt 6B_1005/2015 du 13 avril 2016 consid. 2). Il ressort de cet arrêt qu'il n'est d'ailleurs pas en soi exclu d'obtenir un constat postérieurement au jugement de condamnation, même si les conditions de détention avant jugement doivent en principe être examinées dans le cadre dudit jugement. Dans le cas précis, le recourant avait déposé une requête tendant au constat et à la réparation des conditions illicites de détention, un an et quatre mois après le jugement au fond, respectivement, deux ans et demi après son incarcération (arrêt 6B_1005/2015 du 13 avril 2016 consid. 2).
2.2. En l'espèce, la cour cantonale a rappelé que l'action en constatation prévue par l'art. 49 al. 2 de la loi sur la procédure administrative genevoise (LPA/GE - E 5 10) était subsidiaire à une action en condamnation.
Relevant que la durée de détention subie, selon le recourant, dans des conditions illicites s'étendait sur une durée supérieure à celle jugée problématique par la jurisprudence, à savoir environ trois mois (156 jours: du 22 juin 2014 au 23 novembre 2014), la cour cantonale a considéré que le recourant aurait pu faire valoir les conditions illicites de cette détention devant le juge pénal. En ne formulant sa demande de constat qu'après l'entrée en force du jugement pénal, le recourant avait mis l'Etat devant l'impossibilité de réparer une éventuelle détention dans des conditions illicites autrement que par une indemnité. Dans ce cas, le recourant ne démontrait pas avoir un intérêt à la constatation immédiate indépendamment d'une satisfaction équitable, éventuellement pécuniaire. En définitive, la cour cantonale a déclaré le recours irrecevable, faute d'intérêt pour agir du recourant, s'agissant du constat de l'illicéité des conditions de détention avant jugement (du 22 juin au 24 novembre 2014).
2.3. Le raisonnement de la cour cantonale ne saurait être suivi.
Saisi d'une requête de constatation des conditions de détention illicites, le département est entré en matière sur la demande et a, au fond, constaté que les conditions de détention étaient licites. Dès lors que le recourant entendait faire valoir des conclusions en réparation résultant directement du constat des conditions de détention subie, il avait un intérêt à recourir contre cette décision pour qu'il soit constaté que ses conditions de détention étaient illicites. En effet, la procédure ne portait pas exclusivement sur les conclusions en constatation du recourant. Celles-ci sont le préalable à la réparation à laquelle il prétend. La dichotomie procédurale qu'implique la pratique genevoise ne saurait justifier l'irrecevabilité d'un recours dirigé contre une décision constatant la licéité des conditions de détention. Le refus d'entrer en matière sur ce point par la cour cantonale entraîne l'entrée en force de la décision du département, partant, la perte de l'éventuelle prétention en réparation, sans que la décision n'ait pu faire l'objet d'un recours effectif.
Par ailleurs, la cour cantonale a dénié la qualité pour agir du recourant en se limitant à relever qu'il avait mis l'Etat devant l'impossibilité de réparer une éventuelle détention dans des conditions illicites autrement que par une indemnité, du fait qu'il n'avait pas agi devant le juge pénal dans le cadre de la procédure pénale. Or, si l'on peut se demander pour quelle raison le recourant, dûment assisté, n'a pas immédiatement dénoncé ses conditions de détention, il ne ressort pas de l'arrêt entrepris, que le recourant aurait requis le constat de conditions de détention illicites, respectivement la réparation du tort moral, en visant des fins étrangères au but déduit des art. 3 et 13 CEDH (cf. supra consid. 2.1.2). En particulier, il n'est pas établi que le recourant aurait intentionnellement laissé les conditions qu'il dénonce se prolonger dans le temps et attendu que la procédure pénale se termine, afin d'obtenir une indemnisation financière plutôt qu'une réduction de peine en réparation du prétendu tort moral subi (cf. sur le mode de réparation, cf. <ref-ruling> consid. 4 p. 248 s.). Il n'apparaît pas davantage qu'il aurait renoncé à ses droits. Le comportement du recourant, tel que décrit dans l'arrêt entrepris, ne permet pas de retenir qu'il aurait contrevenu à la bonne foi en procédure.
La décision entreprise prive le recourant de son droit à une enquête prompte et impartiale, respectivement à une constatation de ses conditions de détention.
Au vu de ce qui précède, la cour cantonale a violé le droit fédéral en refusant d'entrer en matière sur un recours dirigé contre une décision qui constate que les conditions de détention étaient licites.
Le recours doit être admis sur ce point, la cause renvoyée à la cour cantonale afin qu'elle entre en matière sur le recours et qu'elle se prononce sur le caractère licite ou non des conditions de détention avant jugement.
3.
S'agissant de la phase postérieure au jugement, le recourant invoque une violation des art. 3 et 13 CEDH, 74 CP, 7, 10 al. 3 et 36 al. 4 Cst. et 3 CPP.
Dans la mesure où la cour cantonale devra statuer sur la licéité des conditions de la détention provisoire, il lui appartiendra d'apprécier l'ensemble des données de la cause, considérées globalement (en particulier celles relatives au confinement et à l'espace au sol) sur l'entier de la durée de la détention dénoncée, tant antérieure que postérieure à la condamnation (cf. supra consid. 2.1). Aussi, il n'y a pas lieu d'examiner ce point plus avant à ce stade.
4.
Le recours doit être admis. Le recourant, qui obtient gain de cause, ne supporte pas de frais judiciaires (art. 66 al. 1 LTF). Il peut prétendre à une indemnité de dépens, à la charge du canton de Genève. La demande d'assistance judiciaire devient ainsi sans objet (art. 64 al. 1 LTF). Il est statué sans frais. Au regard de la nature procédurale du vice examiné et dès lors que le Tribunal fédéral n'a pas traité la cause sur le fond, ne préjugeant ainsi pas de l'issue de la cause, il peut être procédé au renvoi sans ordonner préalablement un échange d'écritures (cf. <ref-ruling> consid. 3.4.2 p. 296; arrêts 6B_1024/2016 du 17 novembre 2017 consid. 3; 6B_986/2016 du 20 septembre 2017 consid. 2.2 et les références citées).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à la cour cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton de Genève versera au conseil du recourant une indemnité de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lausanne, le 22 février 2019
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke