Faits:
A.
Par jugement du 11 janvier 2013, le Tribunal de police du canton de Genève a déclaré A._ coupable de séquestration et d'enlèvement (<ref-law>), de tentative d'extorsion et de chantage (art. 23 al. 1 et 156 ch. 1 CP), de violation de domicile (<ref-law>) et de voies de fait (<ref-law>). Il l'a condamné à une peine privative de liberté de sept mois, sous déduction de 185 jours de détention avant jugement, ainsi qu'à une amende de 300 francs assortie du prononcé d'une peine privative de liberté de substitution de trois jours. Le maintien en détention pour des motifs de sûreté a été ordonné. Par lettres des 16 et 17 janvier 2013, les parties plaignantes ont annoncé vouloir appeler du jugement, en raison d'acquittements partiels. Le Ministère public n'a pas recouru contre ledit jugement.
Par décision du 16 janvier 2013, le Président du Tribunal de police a refusé la demande de libération immédiate formée par A._ le 15 janvier 2013. Par ordonnance du 21 janvier 2013, le Tribunal des mesures de contrainte du canton de Genève (Tmc) a confirmé le refus de libération immédiate. Par ordonnance du 28 janvier 2013, il a prolongé la détention pour des motifs de sûreté jusqu'au 28 avril 2013. Les 4 et 11 février 2013, A._ a recouru contre les ordonnances rendues par le Tmc respectivement le 21 et le 28 janvier 2013 auprès de la Chambre pénale de recours.
Par arrêt du 15 février 2013, la Chambre pénale de recours de la Cour de justice du canton de Genève a admis partiellement le recours interjeté par le prénommé contre l'ordonnance du 21 janvier 2013 et renvoyé la cause au Tmc. Par ordonnance du même jour, la Chambre pénale de recours a sursis à statuer sur le recours contre l'ordonnance du 28 janvier 2013 jusqu'à droit jugé sur le recours contre l'ordonnance du 21 janvier 2013. Par ordonnance du 18 février 2013, le Tmc s'est déclaré incompétent, dès lors que le dossier avait été transmis à la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève.
B.
Parallèlement à la procédure en cours devant la Chambre pénale de recours, A._ a déposé, le 5 février 2013, une nouvelle demande de libération devant le tribunal de première instance. Le Tribunal de police a fait suivre la demande à la Chambre pénale de recours de la Cour de justice du canton de Genève, pour raison de compétence, laquelle en a accusé réception le 14 février 2013.
C.
P ar ordonnance du 22 février 2013, la Chambre pénale d'appel et de révision a ordonné la libération immédiate de A._ et l'a "débouté de ses autres conclusions". Elle a considéré en substance que le principe de la proportionnalité n'avait pas été violé, compte tenu de la marge de manoeuvre qu'implique la procédure en appel. Elle a tenu la demande de A._ tendant à obtenir une indemnisation pour détention injustifiée pour non légitime et prématurée.
D.
Par arrêt du 12 mars 2013, la Chambre pénale de recours a révoqué son ordonnance du 15 février 2013 et s'est déclarée incompétente pour statuer sur le recours interjeté le 11 février 2013 par A._ contre l'ordonnance rendue par le Tmc le 28 janvier 2013. Subsidiairement, elle a déclaré le recours irrecevable.
E.
A._ a déposé deux recours en matière pénale au Tribunal fédéral. Le premier est dirigé contre l'ordonnance du 22 février 2013 qu'il demande d'annuler en tant qu'elle le déboute de ses autres conclusions. Il requiert principalement la constatation des violations du principe de célérité, du principe de proportionnalité, du droit d'être entendu et la condamnation de l'Etat de Genève à lui verser une indemnité réparatrice pour ces trois violations de ses droits formels. Il conclut subsidiairement au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants (cause 1B_129/2013).
Dans son second recours, A._ demande principalement au Tribunal fédéral d'annuler l'arrêt du 12 mars 2013 et de le réformer en ce sens qu'il est constaté que la Chambre pénale de recours est compétente pour statuer sur le recours interjeté contre l'ordonnance du Tmc du 28 janvier 2013, que ledit recours est recevable et que la cause est renvoyée à l'instance précédente pour qu'elle tranche les conclusions constatatoires et en allocation d'indemnités et de dépens, prises dans le recours. Il conclut subsidiairement au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants (cause 1B_145/2013).
Il requiert en outre l'assistance judiciaire dans les deux causes.
La Chambre pénale d'appel et de révision et la Chambre pénale de recours persistent dans les termes de leurs décisions respectives. Le Ministère public conclut au rejet des recours. Le recourant a répliqué par courrier du 15 avril 2013.

Considérant en droit:
1.
Les deux recours ont trait à la même procédure pénale. Ils sont dirigés contre des décisions formellement distinctes mais qui concernent le même complexe de faits et soulèvent les mêmes questions juridiques. Il se justifie dès lors de joindre les causes 1B_129/2013 et 1B_145/2013, pour des motifs d'économie de procédure, et de statuer à leur sujet dans un seul arrêt (<ref-law> applicable par analogie vu le renvoi de l'<ref-law>).
2.
Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis.
2.1. Selon l'<ref-law>, le recours en matière pénale est ouvert contre les décisions rendues en matière pénale, dont font partie les décisions relatives à la détention provisoire ou pour des motifs de sûreté au sens des <ref-law> (<ref-ruling> consid. 1 p. 23).
2.2. La recevabilité du recours en matière pénale dépend notamment de l'existence d'un intérêt juridique actuel à l'annulation de la décision entreprise (<ref-law>). De cette manière, les tribunaux sont assurés de trancher uniquement des questions concrètes et non de prendre des décisions à caractère théorique, ce qui répond à un souci d'économie de procédure (<ref-ruling> consid. 1.3 p. 276). Ainsi, une partie qui n'est pas concrètement lésée par la décision ne possède pas la qualité pour recourir. Il faut, en d'autres termes, que la décision de la juridiction supérieure lui procure l'avantage de droit matériel qu'il recherche. Dans la négative, un tel recours est irrecevable ( Niklaus Oberholzer, Grundzüge des Strafprozessrechts, 3ème édition 2012, n. 1561; Piquerez/Macaluso, Procédure pénale suisse, 3ème édition 2011, n. 1911).
Selon un principe général de procédure, 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 (arrêt 1C_79/2009 du 24 septembre 2009 consid. 3.5 publié in ZBl 2011 p. 275). 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 de l'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 (<ref-ruling> consid. 3.1.1 p. 88). En matière de détention, la jurisprudence a ainsi admis que l'autorité chargée du contrôle de celle-ci, si elle était saisie d'allégations de mauvais traitements au sens de l'art. 3 CEDH, se devait de vérifier si la détention avait lieu dans des conditions acceptables; ces constatations pouvaient certes conduire à une indemnisation à l'issue de la procédure, devant le juge du fond, mais il importait d'assurer immédiatement une enquête prompte et sérieuse (<ref-ruling> consid. 3.4 p. 45).
Lorsque le détenu - qui sollicite son élargissement - a été remis en liberté, un intérêt pratique et actuel fait en principe défaut. A titre exceptionnel, un examen au fond des griefs soulevés peut néanmoins avoir lieu lorsque le recourant invoque une violation manifeste de la CEDH, en demandant une réparation qui peut lui être accordée immédiatement par la constatation de cette violation et une répartition des frais qui lui serait plus favorable (<ref-ruling> consid. 1.3 p. 276 s.; <ref-ruling> consid. 4a p. 397). Dans une telle situation, il existe un intérêt digne de protection à la constatation immédiate d'un état juridique (cf. Eloi Jeannerat, Note relative à l'arrêt précité 1C_79/2009, RDAF 2012 p. 418).
2.3. En l'espèce, le recourant a été libéré le 22 février 2013, les frais de la procédure cantonale ont été laissés à la charge de l'Etat et les honoraires de son avocat d'office sont, en l'état, pris en charge par l'assistance judiciaire cantonale. On ne distingue donc pas d'emblée son intérêt pratique et actuel à recourir. Ses conclusions visent d'ailleurs essentiellement (cf. consid. 2.4) à ce que soit constatée la violation de différents droits de nature formelle. Il se pose donc la question de la recevabilité de telles conclusions.
La jurisprudence reconnaît la nécessité d'engager une enquête prompte et impartiale pour faire constater la présence de traitements prohibés au sens de la CEDH. 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 indemnisation (<ref-law>), ou éventuellement une réduction de peine (cf. <ref-ruling> consid. 2.2 p. 151 s.; <ref-ruling> consid. 2c p. 141).
La présente situation est cependant différente. Le recourant a d'ores et déjà été jugé en première instance, le 11 janvier 2013. L'instance d'appel, saisie par les parties plaignantes à la suite d'acquittements partiels, a reçu le dossier le 14 février 2013. Il lui appartient désormais d'organiser la procédure conformément aux <ref-law>. Si elle entre en matière, elle rendra un jugement qui remplacera le jugement de première instance (<ref-law>). Ce jugement statuera notamment sur les frais et indemnités (art. 81 al. 4 let. d en lien avec l'art. 399 al. 4 let. f CPP), au terme de débats dans le cadre desquels le juge du fond disposera d'un plein pouvoir d'appréciation (<ref-law>). Dans ces conditions, le recourant dispose à bref délai d'une procédure effective, susceptible de conduire au versement d'indemnités fondées sur la prétendue violation des droits qu'il dénonce (<ref-law>). L'économie de procédure commande ainsi que le recourant fasse valoir ses prétentions directement auprès de l'instance d'appel d'ores et déjà saisie.
Par conséquent, les conditions pour un examen à titre exceptionnel des conclusions en constatation de droit par le juge de la détention ne sont pas remplies. Pour les mêmes motifs, le recourant n'a pas non plus d'intérêt juridique actuel à recourir contre l'arrêt dans lequel la Chambre pénale de recours se déclare incompétente en raison de la saisine de la Chambre pénale d'appel et de révision qui a ordonné la libération du recourant et qui a statué sur les autres prétentions de l'intéressé. Le mémoire de recours ne contient du reste pas la démonstration de l'existence ou du risque d'un tel intérêt juridique actuel, alors qu'il incombe au recourant de présenter une argumentation motivée sur ce point (<ref-law>; cf. <ref-ruling> consid. 1.1 p. 329).
2.4. Dans la cause 1B_129/2013, le recours énonce encore une conclusion visant à faire condamner l'Etat de Genève à verser au recourant une indemnité réparatrice pour la violation du principe de célérité, du droit d'être entendu et du principe de proportionnalité. Le recourant reconnaît cependant lui-même qu'il "est peut-être prématuré de solliciter l'indemnisation financière pour la détention injustifiée". Le corps du recours ne contient d'ailleurs aucun développement sur ce sujet alors que la décision entreprise a consacré un considérant entier à la question. A défaut de toute critique dirigée contre la décision entreprise sur ce point, cette conclusion est déjà irrecevable à ce titre (cf. <ref-law>). En outre, comme on l'a vu, le juge du fond compétent en matière d'allocations d'indemnités, est d'ores déjà saisi et dispose des éléments suffisants pour apprécier cette question. Il n'y a donc pas non plus lieu, pour ce motif, d'entrer en matière.
2.5. Au vu de ce qui précède, les recours sont irrecevables, soit pour défaut d'intérêt pratique et actuel du recourant, soit pour absence d'une motivation suffisante. Le recourant pourra saisir le juge du fond à cet égard.
3.
Dès lors que le recourant est dans le besoin et que ses conclusions ne paraissaient pas d'emblée vouées à l'échec, l'assistance judiciaire doit lui être accordée (<ref-law>). Il y a lieu de désigner Me Ilir Cenko en qualité d'avocat d'office et de fixer ses honoraires, qui seront supportés par la caisse du Tribunal fédéral (<ref-law>). Le recourant est en outre dispensé des frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Les causes 1B_129/2013 et 1B_145/2013 sont jointes.
2.
Les recours sont irrecevables.
3.
La demande d'assistance judiciaire est admise. Me Ilir Cenko est désigné comme avocat d'office du recourant et ses honoraires, supportés par la caisse du Tribunal fédéral, sont fixés à 1'500 francs.
4.
Il n'est pas perçu de frais judiciaires.
5.
Le présent arrêt est communiqué au mandataire du recourant, au Ministère public et à la Cour de justice du canton de Genève, Chambre pénale d'appel et de révision et Chambre pénale de recours.
Lausanne, le 26 juin 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
La Greffière: Tornay Schaller