Faits :
A.
A._ a été condamné par jugement du Tribunal correctionnel genevois du 25 novembre 2014, à une peine privative de liberté de 35 mois, sous déduction de 158 jours de détention avant jugement. Il a été incarcéré à la prison de Champ-Dollon du 22 juin 2014 au 17 mai 2016.
A._ a requis le constat de l'illicéité de ses conditions de détention du 23 juin 2014 au 15 février 2015 ainsi que l'indemnisation du tort moral qui en a résulté.
Par décision du 20 juin 2017, le Département de la sécurité, de l'emploi et de la santé du canton de Genève (ci-après: le département) a déclaré irrecevable la requête en indemnisation formée par A._, faute de compétence et a constaté que les conditions dans lesquelles s'était déroulée sa détention du 23 juin 2014 au 15 février 2015, au sein de la prison de Champ-Dollon étaient licites.
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 A._, dans la mesure de sa recevabilité.
Par arrêt 6B_1205/2018 du 22 février 2019, le Tribunal fédéral a admis le recours formé par A._ contre l'arrêt du 16 octobre 2018, lequel le privait de son droit à une enquête prompte et impartiale, respectivement à une constatation du caractère licite ou non de ses conditions de détention. L'arrêt cantonal a été annulé et la cause renvoyée à la cour cantonale pour nouvelle décision. La cour cantonale était invitée à apprécier l'ensemble des données de la cause, considérées globalement sur l'entier de la durée de la détention, tant antérieure que postérieure à la condamnation (arrêt 6B_1205/2018 du 22 février 2019 consid. 3).
B.
Statuant sur renvoi, la Chambre administrative de la Cour de justice genevoise a, par arrêt du 20 décembre 2019, admis partiellement le recours formé par A._ et a constaté le caractère illicite de ses conditions de détention avant jugement pendant une période de 89 jours du 23 juin au 19 septembre 2014. Sans que cela ne ressorte du dispositif, la cour cantonale a rejeté le recours pour le surplus et considéré que les conditions de détention entre le 25 septembre [recte: novembre] 2014 et le 22 février 2015 n'étaient pas illicites.
En substance l'arrêt cantonal repose sur les faits suivants.
Du 23 juin 2014 au 22 février 2015, A._ a occupé, avec deux codétenus, des cellules dont la surface individuelle a oscillé entre 3,39 m 2et 3,7 m 2 (3,61 m 2 dès le 30 juillet 2014), hormis les 16 et 26 juillet 2014 où il a bénéficié d'une surface individuelle de plus de 5 m 2. Pendant cette période, A._ a bénéficié 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.
Dès le 19 septembre 2014, un des codétenus de A._ a travaillé à l'atelier de reliure, de sorte qu'il était absent 5 heures par jour, les jours ouvrés. Dès le 13 octobre 2014, le second codétenu a travaillé à l'atelier cuisine où il était occupé tous les jours 3 heures une semaine et 5 heures 45 la semaine suivante.
A._ a occupé un poste de nettoyeur de tables du 12 au 20 janvier 2015 pendant une heure par jour, 7 jours sur 7, puis un poste à la cuisine à partir du 16 février 2015.
C.
A._ forme un recours constitutionnel subsidiaire contre l'arrêt cantonal auprès du Tribunal fédéral 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 du 23 juin 2014 au 15 février 2015. Subsidiairement, il conclut au renvoi de la cause à la cour cantonale pour nouvelle décision. Il sollicite pour le surplus l'assistance judiciaire.
D.
Invités à se déterminer sur le mémoire de recours, le département a conclu à son irrecevabilité, subsidiairement à son rejet, et la cour cantonale a renoncé à déposer des observations. Les prises de position ont été communiquées à A._, lequel ne s'est pas déterminé dans le délai imparti.

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. 10 al. 3 Cst. et 3 et 13 CEDH, 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, contrairement à ce que soulève le département, 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 recourant considère qu'en niant le caractère illicite de ses conditions de détention pour l'entier de la période allant du 23 juin 2014 au 15 février 2015, la cour cantonale a fait preuve d'arbitraire dans l'appréciation des faits et a violé les art. 3 et 13 CEDH et 7, 9 et 10 al. 3 Cst. Il reproche à la cour cantonale de ne pas avoir apprécié la période de détention dans sa globalité et d'avoir scindé son raisonnement en deux phases (période avant jugement et période post-jugement) de manière purement artificielle.
2.1. Au niveau conventionnel, 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.
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; arrêt 6B_103/2020 du 10 mars 2020 consid. 2.1.2; cf. également arrêt 1B_115/2019 du 18 décembre 2019 consid. 2.3 destiné à la publication).
2.1.1. Pour le domaine spécifique de la détention, la Suisse a ratifié, le 7 octobre 1988, la Convention européenne de 1987 pour la prévention de la torture et des peines ou traitements inhumains ou dégradants (RS 0.106). L'art. 1 de cette Convention institue un " Comité européen pour la prévention de la torture et des peines ou traitements inhumains ou dégradants " (ci-après: CPT).
Le 15 décembre 2015, le CPT a édité une norme sur l'espace vital par détenu dans les établissements pénitentiaires. Il en ressort que la norme minimale concernant l'espace vital devrait exclure les sanitaires qui se trouvent à l'intérieur d'une cellule. Ainsi, une cellule individuelle devrait mesurer 6 m2 auxquels on ajouterait la superficie nécessaire à une annexe sanitaire (généralement de 1 à 2 m2). De même, l'espace occupé par l'annexe sanitaire devrait être exclu du calcul des 4 m2 par personne dans les cellules collectives. De plus, l'annexe sanitaire de ces dernières devrait être entièrement cloisonnée.
Par ailleurs, le Comité des ministres du Conseil de l'Europe, en application de l'art. 15 (b) du Statut du Conseil de l'Europe (RS 0.192.030), a adopté le 11 janvier 2006 la Recommandation Rec (2006) 2 sur les Règles pénitentiaires européennes (ci-après; RPE), lesquelles s'inscrivent dans les précédentes recommandations établies dès 1989. Ces règles prennent notamment en compte le travail mené par le CPT ainsi que les normes qu'il a développées dans ses rapports généraux, et visent à garantir des conditions de détention qui ne portent pas atteinte à la dignité humaine. Les règles 17 à 22 RPE traitent des locaux de détention, de l'hygiène, de la literie et du régime alimentaire: ainsi, les locaux de détention doivent satisfaire aux exigences de respect de la dignité humaine et, dans la mesure du possible, de la vie privée, et répondre aux conditions minimales requises en matière de santé et d'hygiène, compte tenu des conditions climatiques.
2.1.2. Se prononçant sur la situation de la prison genevoise de Champ-Dollon, le Tribunal fédéral a jugé qu'en cas de surpopulation carcérale, l'occupation d'une cellule dite individuelle par trois détenus - chacun disposant d'un espace individuel de 4 m 2, restreint du mobilier, - est une condition de détention difficile; elle n'est cependant pas constitutive d'une violation de l'art. 3 CEDH et ne représente pas un traitement dégradant portant atteinte à la dignité humaine des prévenus. En revanche, l'occupation d'une cellule dite triple par six détenus avec une surface individuelle inférieure à 3,83 m 2 - restreinte encore par le mobilier - peut constituer une violation de l'art. 3 CEDH si elle s'étend sur une longue période et si elle s'accompagne d'autres mauvaises conditions de détention. Il faut dès lors considérer la période pendant laquelle l'intéressé a été détenu dans les conditions incriminées. Une durée qui s'approche de trois mois consécutifs (délai que l'on retrouve en matière de contrôle périodique de la détention provisoire ou pour des motifs de sûreté; cf. art. 227 al. 7 CPP) apparaît comme la limite au-delà de laquelle les conditions de détention susmentionnées ne peuvent plus être tolérées (<ref-ruling> consid. 3.6.3 p. 138 s.). Depuis lors, le Tribunal fédéral - s'inspirant également de la jurisprudence de la Cour européenne des droits de l'homme (cf. arrêts cités à l'<ref-ruling> consid. 3.4 p. 134 s.) - s'en est tenu au critère de la surface individuelle inférieure à 4 m 2.
2.1.3. Dans un arrêt de principe Mursic contre Croatie du 20 octobre 2016, la Grande Chambre de la Cour européenne des droits de l'homme s'est cependant écartée de cet ordre de grandeur de 4 m 2; désormais, la Cour retient qu'une surface de 3 m 2 au sol par détenu constitue la norme minimale pertinente (arrêt CourEDH Mursic c. Croatie du 20 octobre 2016, requête n° 7334/13, § 110 à 115). Selon cet arrêt, lorsque la surface au sol dont dispose un détenu en cellule collective est inférieure à 3 m2, le manque d'espace personnel est considéré comme étant à ce point grave qu'il donne lieu à une forte présomption de violation de l'article 3 CEDH. Cette forte présomption peut être réfutée si tous les facteurs suivants sont réunis: 1) les réductions de l'espace personnel par rapport au minimum requis de 3 m2 sont courtes, occasionnelles et mineures; 2) elles s'accompagnent d'une liberté de circulation suffisante hors de la cellule et d'activités hors cellule adéquates; 3) le requérant est incarcéré dans un établissement offrant, de manière générale, des conditions de détention décentes (arrêt Mursic c. Croatie précité, § 137, 138).
Pour qu'il y ait une liberté de circulation suffisante, les détenus doivent bénéficier d'au moins une heure d'exercice en plein air chaque jour, de préférence dans le cadre d'un programme plus large d'activités hors cellule, la cour de promenade devant être raisonnablement spacieuse et, autant que possible, offrir un abri contre les intempéries. Ils doivent pouvoir passer une partie raisonnable de la journée hors de leur cellule pour pratiquer des activités motivantes de nature variée (travail, loisirs, formation) (arrêt Mursic c. Croatie précité, § 133).
Lorsqu'un détenu dispose dans la cellule d'un espace personnel compris entre 3 et 4 m 2, le facteur spatial demeure un élément de poids dans l'appréciation du caractère adéquat des conditions de détention. Il y a lieu de conclure à une violation de l'art. 3 CEDH si le manque d'espace s'accompagne d'autres mauvaises conditions matérielles de détention, notamment d'un défaut d'accès à la cour de promenade ou à l'air et à la lumière naturels, d'une mauvaise aération, d'une température insuffisante ou trop élevée dans les locaux, d'une absence d'intimité aux toilettes ou de mauvaises conditions sanitaires et hygiéniques (arrêt CourEDH Mursic c. Croatie précité, § 139).
Lorsqu'on évalue les conditions de détention, il y a lieu de tenir compte de leurs effets cumulatifs ainsi que des allégations spécifiques du requérant. La durée de détention d'une personne dans des conditions particulières doit elle aussi être prise en considération (arrêt CourEDH Mursic c. Croatie précité, § 101 et 131 et les arrêts cités).
2.2. Dans un premier temps, se concentrant sur la période de détention avant jugement (du 22 juin au 24 novembre 2014), la cour cantonale a retenu que le confinement du recourant et la surface au sol dont il a pu bénéficier ne répondaient pas aux critères d'une détention conforme au droit du 23 juin au 19 septembre 2014, date à laquelle un de ses codétenu a commencé à travailler à l'atelier de reliure (5 heures par jour, les jours ouvrés). La cour cantonale a ainsi retenu que les conditions de détention du recourant avaient été illicites durant 89 jours " de sa détention avant jugement " (arrêt entrepris consid. 6.a).
Dans un second temps, examinant la période de détention postérieure au jugement (du 25 novembre 2014 au 22 février 2015), la cour cantonale a considéré que, du fait que l'occupation de la cellule pendant toute la journée n'était pas complète au minimum pendant trois heures durant la période concernée, d'une durée inférieure à trois mois, les conditions de détention devaient être considérées comme difficiles mais pas illicites (arrêt entrepris consid. 6.b).
2.3. Le raisonnement de la cour cantonale, en deux étapes, ne résiste pas à l'examen. Ainsi que le relève le recourant, la cour cantonale a opéré une césure artificielle entre la période de détention avant jugement et celle postérieure au jugement, alors même qu'il demeurait dans des conditions de détention identiques (surface au sol, confinement [hormis du 12 au 20 janvier 2015], nombre de codétenus) pendant ces deux périodes. Au lieu de scinder l'examen des conditions de détention de la sorte, elle aurait dû procéder à l'appréciation globale de l'ensemble des circonstances pendant la durée complète de détention, ainsi que cela ressort expressément de l'arrêt de renvoi (arrêt 6B_1205/2018 du 22 février 2019 consid. 3) et de la jurisprudence constante (cf. supra consid. 2.1).
En l'occurrence, le recourant a passé une période de 236 jours (près de 8 mois), confiné 22 à 23 heures sur 24 dans une cellule lui offrant une surface individuelle de moins de 3,7 m 2 (à l'exception de deux nuits à plus de 5 m 2). Cette durée dépasse largement les trois mois consécutifs apparaissant comme la limite au-delà de laquelle les conditions de détention susmentionnées ne peuvent plus être tolérées (<ref-ruling> consid. 3.6.3 p. 138). La précision apportée par le département, selon laquelle, en cas de détention provisoire se prolongeant au-delà de trois mois, les conditions de détention doivent satisfaire à des exigences plus élevées (<ref-ruling> consid. 3.3 p. 134), ne justifie pas de césure de l'examen des conditions de détention après 3 mois.
Le recourant n'a bénéficié d'aucune activité hors cellule, hormis la promenade quotidienne d'une heure, et trois à quatre heures de sport hebdomadaires. L'activité de nettoyeur de tables pendant 8 jours (du 12 au 20 janvier 2015) lui permettant de sortir de sa cellule une heure de plus quotidiennement apparaît très marginale dans l'examen global des conditions de détention. Dans la configuration d'espèce, les activités occupant les codétenus du recourant ont tout au plus eu comme effet d'agrandir l'espace au sol disponible quelques heures par jour mais n'ont eu aucun impact sur le confinement du recourant et sur la surface individuelle disponible la majeure partie du temps. Aussi, le manque d'espace individuel, quand bien même il ne donne pas lieu, à lui seul, à une forte présomption de violation de l'art. 3 CEDH, s'est accompagné d'autres mauvaises conditions matérielles de détention et s'est étendu sur une longue période.
En étant confiné 22h à 23h sur 24h (hormis 1 heure quotidienne pendant 8 jours) dans une cellule occupée par trois détenus n'offrant pas plus de 3,7 m 2 de surface individuelle sur une durée de près de 8 mois, le recourant a subi des conditions de détention contraires à la dignité humaine au sens de l'art. 3 CEDH.
Le fait que le recourant a bénéficié, après le 15 février 2015, d'une surface individuelle au sol conforme au droit ne permet pas de réparer le caractère illicite des conditions de détention antérieures, contrairement à ce que suggère le département.
2.4. Il s'ensuit que le recours doit être admis et l'arrêt attaqué annulé. Dans la constatation du nombre de jours pendant lesquels les conditions de détention ont été illicites, il faut retrancher les jours durant lesquels les conditions de détention ont été conformes à la dignité humaine, à savoir durant 2 jours (les 16 et 26 juillet 2014; espace individuel de plus de 5 m 2). Il y a donc lieu de constater que les conditions de détention du recourant n'ont pas été conformes aux standards minimaux pendant 234 jours entre le 23 juin 2014 et le 15 février 2015.
3.
Le recours doit être admis. Le recourant, qui obtient gain de cause avec l'assistance d'un avocat, a droit à des dépens, à la charge du canton de Genève (art. 68 al. 1 LTF). Sa demande d'assistance judiciaire pour la présente procédure est sans objet. Il n'y a pas lieu de percevoir des frais judiciaires (art. 66 al. 4 LTF).
Les frais et dépens de la procédure cantonale peuvent également être fixés dans le présent arrêt (art. 67 et 68 al. 5 LTF). Les dépens sont ainsi arrêtés de manière globale pour les procédures cantonale et fédérale à 4'000 francs (comprenant une indemnité de 1'000 francs pour la procédure cantonale), et les frais judiciaires de l'instance cantonale sont laissés à la charge du canton de Genève.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis. L'arrêt cantonal est annulé et réformé, en ce sens qu'il est constaté que les conditions dans lesquelles s'est déroulée la détention de A._ ont été illicites pendant 234 jours entre le 23 juin 2014 et le 15 février 2015.
2.
Il n'est pas perçu de frais judiciaires.
3.
Une indemnité de dépens globale de 4'000 francs est allouée au mandataire du recourant, pour les procédures fédérale et cantonale, à la charge du canton de Genève.
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, 1ère section.
Lausanne, le 18 mai 2020
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke