Sachverhalt:
A.
A._ (Serbe; 1980) heiratete am 13. September 2006 eine in der Schweiz niederlassungsberechtigte Ausländerin (1979), weshalb er in der Folge eine Aufenthaltsbewilligung erhielt. Am 14. Januar 2007wurde der gemeinsame Haushalt aufgehoben; in der Zwischenzeit sind die Eheleute geschieden. Die gemeinsame Tochter wurde am 3. August 2007 geboren. Mit Verfügung vom 3. August 2008 wurde die Aufenthaltsbewilligung von A._ nicht mehr verlängert und er wurde per 4. September 2009 aus der Schweiz weggewiesen. Die Rechtsmittel dagegen waren erfolglos.
B.
Am 10. August 2015 verheiratete sich A._ in Serbien mit der deutschen Staatsangehörigen B._ (1962), welche über eine Aufenthaltsbewilligung in der Schweiz verfügt. Trotz des Verdachts auf eine Scheinehe erteilte die Migrationsbehörde ihm eine Aufenthaltsbewilligung (18. November 2016). Am 24. August 2017 besuchte die Kantonspolizei die Wohnung der Eheleute. Gestützt darauf widerrief die Migrationsbehörde des Kantons Solothurn am 20. März 2018 die Aufenthaltsbewilligung von A._. Die Beschwerde dagegen war vor dem Verwaltungsgericht des Kantons Solothurn erfolglos (Urteil vom 24. Oktober 2018).
C.
Vor Bundesgericht beantragt A._, das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 24. Oktober 2018 und den Widerruf seiner Aufenthaltsbewilligung aufzuheben. Zudem beantragt er unentgeltliche Rechtspflege.
Das Verwaltungsgericht und das Migrationsamt des Kantons Solothurn beantragen unter Verzicht einer Vernehmlassung die Abweisung der Beschwerde.
Mit Verfügung vom 27. November 2018 hat der Präsident der II. öffentlich-rechtlichen Abeilung der Beschwerde aufschiebende Wirkung zuerkannt.

Erwägungen:
1.
Der Beschwerdeführer beruft sich in einer nicht zum Vornherein aussichtslosen Weise (Art. 83 lit. c e contrario BGG) als Angehöriger einer EU-Bürgerin auf Rechtsansprüche aus dem Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (FZA; SR 0.142.112.681). Die weiteren Sachurteilsvoraussetzungen (Art. 42 Abs. 1 und 2, Art. 82 lit. a, Art. 86 Abs. 1 lit. d, Art. 89 Abs. 1, Art. 90, Art. 100 Abs. 1 BGG) sind erfüllt, weshalb auf die Beschwerde einzutreten ist.
2.
2.1. Nach Art. 3 Anh. I FZA hat der Beschwerdeführer einen abgeleiteten Anspruch auf Verlängerung des Aufenthaltsrechts, solange die Ehe formell fortdauert. Dieses Recht steht unter dem Vorbehalt des Rechtsmissbrauchs (<ref-ruling> E. 2.1 S. 395). Fehlt der Wille zur Gemeinschaft und dient das formelle Eheband ausschliesslich dazu, die ausländerrechtlichen Zulassungsvorschriften zu umgehen, fällt der Anspruch dahin (<ref-ruling> E. 2.1 S. 395 mit Hinweisen). Das vom originär anwesenheitsberechtigten EU-Bürger abgeleitete Aufenthaltsrecht des Drittstaatsangehörigen kann infolge Wegfalls der Voraussetzungen für das Aufenthaltsrecht gestützt auf Art. 23 Abs. 1 VEP (SR 142.203) widerrufen oder nicht (mehr) verlängert werden, da das Freizügigkeitsabkommen diesbezüglich keine eigenen abweichenden Bestimmungen enthält (vgl. Art. 2 Abs. 2 AIG; SR 142.20; bis zum 1. Januar 2019: AuG [AS 2007 5437]).
2.2. Ob die Ehe bloss (noch) formell besteht, entzieht sich in der Regel dem direkten Beweis und kann nur durch Indizien erstellt werden (<ref-ruling> E. 4.2 S. 9 f.). Solche Indizien können äussere Begebenheiten sein wie eine drohende Wegweisung, das Fehlen einer Wohngemeinschaft, ein erheblicher Altersunterschied, Schwierigkeiten in der Kommunikation, fehlende Kenntnisse über den Ehepartner und dessen Familie oder die Bezahlung einer Entschädigung. Die Indizien können aber auch psychische Vorgänge betreffen (tatsächlicher Wille). In beiden Fällen handelt es sich um tatsächliche Feststellungen, welche das Bundesgericht nur auf offensichtliche Unrichtigkeit oder Rechtsverletzungen hin überprüft (Art. 97 Abs. 1 BGG; <ref-ruling> E. 2.3 S. 152). In die vorinstanzliche Beweiswürdigung greift es nur ein, wenn diese willkürlich ist (Urteile 2C_752/2016 vom 16. September 2016 E. 3.2; 2C_1141/2015 vom 18. Juli 2016 E. 2.2; zur Willkür in der Beweiswürdigung vgl. <ref-ruling> E. 4.4 S. 444). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung fremdenpolizeilicher Vorschriften (<ref-ruling> E. 2.3 S. 152).
2.3. Eine Umgehungsehe liegt umgekehrt nicht bereits dann vor, wenn auch ausländerrechtliche Motive die Fortdauer der Lebensgemeinschaft beeinflusst haben. Erforderlich ist, dass der Wille zur Führung der Lebensgemeinschaft im Sinn einer auf Dauer angelegten wirtschaftlichen, körperlichen und spirituellen Verbindung zumindest bei einem der Ehepartner fehlt (<ref-ruling> E. 3b S. 102). Grundsätzlich muss die Migrationsbehörde nachweisen, dass die Ehe nur noch formell besteht. Dass die Ehe nur zum Schein fortgeführt wird, darf dabei nicht leichthin angenommen werden (<ref-ruling> E. 4.2 S. 10). Die Behörden müssen den Sachverhalt von Amtes wegen möglichst zuverlässig abklären; indessen wird der Untersuchungsgrundsatz durch die Mitwirkungspflicht der Parteien relativiert (vgl. Art. 90 AIG). Diese kommt naturgemäss bei Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vertretbarem Aufwand erhoben werden können (<ref-ruling> E. 8.6.4 S. 496 f.). Das gilt insbesondere, wenn bereits gewichtige Hinweise für eine Scheinehe sprechen; dann wird von den Eheleuten erwartet, dass sie von sich aus Umstände vorbringen und belegen, um den echten Ehewillen glaubhaft zu machen (Urteil 2C_1019/2016 vom 9. Mai 2017 E. 2.3). Umso mehr muss in diesen Fällen indes gelten, dass die Behörden die Beweisangebote der Eheleute anzunehmen haben (vgl. Urteil 2C_518/2016 vom 7. September 2017 E. 2.4 i.f.).
3.
3.1. Am 18. November 2016 erteilte die Migrationsbehörde dem Beschwerdeführer eine Aufenthaltsbewilligung, obwohl sie zu diesem Zeitpunkt gewisse Zweifel hatte. In der Folge veranlasste sie deshalb eine Polizeikontrolle in der Wohnung der Eheleute, welche am 24. August 2017 stattfand. Wie sich aus dem vorinstanzlich festgestellten Sachverhalt ergibt, war die Ehefrau zu diesem Zeitpunkt in Deutschland bei ihrer kranken Schwester. Die Vorinstanz hält weiter fest: Die Wohnung sei nur spärlich eingerichtet gewesen (Wohnzimmer: Sofa, Salontisch, Fernseher mit Fernsehmöbel; Schlafzimmer: Bett, ein Nachttisch, Kiste; Küche: kleiner Esstisch, zwei Hocker; "Gästezimmer": nicht bezogenes Bett, ein kleiner Schrank). Lampen seien nur im Wohnzimmer und in der Küche vorhanden gewesen. Im Eingangsbereich seien fünf Paar Männerschuhe, jedoch keine Frauenschuhe gestanden. Auf dem Küchentisch sei ein Computer aufgestellt und angeschlossen gewesen. Aufgrund dessen sei kaum Platz für eine Person am Tisch gewesen. Weiter seien die Küchenschränke minimal mit Küchenutensilien und Nahrungsmitteln gefüllt gewesen. Ebenfalls sei der Kühlschrank fast leer gewesen. Bilder oder Fotos hätten keine festgestellt werden können. Im Schlafzimmer sei das Bett mit einem Kopfkissen und einer Decke bedeckt gewesen. In der Ecke sei eine Kiste mit Männerkleidern gestanden. Weiter hätten sich keine Möbel im Schlafzimmer befunden. Im Badezimmer habe auf dem Waschbecken ein Becher mit zwei Zahnbürsten gestanden. Im Spiegelkasten hätten lediglich Pflegeprodukte und Parfüms von Männern festgestellt werden können. Auch ansonsten hätten sich im Badezimmer keine Frauenprodukte befunden. Die Vorinstanz folgert daraus, dass das Ergebnis der Abklärung durch die Polizei klar sei: Zum Zeitpunkt der Kontrolle am 24. August 2017 bestand keine Wohngemeinschaft zwischen dem Beschwerdeführer und seiner Ehefrau. Die vom Beschwerdeführer bereits im erstinstanzlichen Verfahren eingereichten Fotos der Wohnungseinrichtung und die bestrittenen Sachverhaltsdarstellungen würden nichts an diesem Befund ändern.
3.2. Der Beschwerdeführer macht geltend, dass aus der spärlichen Wohnungseinrichtung nicht auf den fehlenden Ehewillen geschlossen werden könne und die Wohnung noch nicht fertig eingerichtet gewesen sei, wie die bereits im erstinstanzlichen Verfahren eingereichten Bilder zeigten, dass die Ehefrau während längerer Zeit bei ihrer kranken Schwester in Deutschland gewesen sei, die Eheleute in getrennten Schlafzimmern schlafen würden, im Zimmer der Ehefrau ein Schrank mit ihren Kleidern und Damenschuhen gestanden habe, was die Polizeibeamten nicht untersucht hätten, Kosmetika der Ehefrau durchaus im Badezimmer vorhanden gewesen seien und sich die Vorinstanz mit den vom Beschwerdeführer eingereichten Schreiben von Nachbarn, der Arbeitgeberin und weiteren Personen nicht auseinandergesetzt habe.
4.
4.1. Der Bericht der Polizei hält auf knapp einer Dreiviertelseite fest, was sich im Eingangsbereich, im Wohn-, Schlaf- und Badzimmer sowie in der Küche der Wohnung in U._ befand. Der Bericht ist wenig aussagekräftig, benennt er doch vor allem die Wohnungseinrichtung. Aus dem Umstand, dass die Wohnung spärlich eingerichtet ist, lässt sich - wie der Beschwerdeführer zu Recht moniert - kein fehlender Ehewille nachweisen. Dasselbe trifft auch auf den Nahrungsmittel- sowie Kühlschrank zu. Abgesehen davon ist in Rechnung zu stellen, dass die Einrichtung der Wohnung in aller Regel eine gemeinsame Sache der Eheleute ist, die Ehefrau aber für längere Zeit bei ihrer kranken Schwester in Deutschland weilte und der Beschwerdeführer im Zeitpunkt der Inspektion erst seit rund sieben Monaten im Besitz der Aufenthaltsbewilligung war. Angesichts dessen ist es nicht verwunderlich, dass die Wohnung noch nicht voll eingerichtet war. Die Vorinstanz und der Polizeibericht halten ferner fest, dass im Eingangsbereich keine Frauenschuhe und sonstwie keine Frauenkleider vorhanden gewesen seien. Der Beschwerdeführer führt diesbezüglich aus, dass das von der Polizei als Gästezimmer bezeichnete Zimmer das Schlafzimmer der Ehefrau sei. Dort stehe ein Kleiderkasten mit den Kleidern der Ehefrau, welche sie nicht nach Deutschland mitgenommen habe. Im Polizeibericht ist zwar erwähnt, dass in diesem Zimmer ein solcher Schrank gestanden habe, es ergibt sich daraus aber nicht, ob die Polizei diesen untersucht hat. Insofern ergibt sich daraus auch nichts zu Ungunsten des Beschwerdeführers. Da die Ehefrau des Beschwerdeführers während längerer Zeit bei ihrer kranken Schwester gewesen war, ist auch davon auszugehen, dass sie einige Kleider mitgenommen hat. Angesichts des Umstands, dass der Beschwerdeführer nicht viele Kleider hat ("eine Kiste mit Männerkleidern"), ist es plausibel, dass auch die Ehefrau des Beschwerdeführers wenige Kleider besitzt und diese, sofern sie diese nicht zu ihrer Schwester mitgenommen hat, allesamt in ihrem Kleiderkasten versorgt gewesen waren. Dass die Ehefrau ein eigenes Schlafzimmer hat, ist nichts Ungewöhnliches und sagt - wie der Beschwerdeführer zu Recht ausgeführt hat - ebenfalls nichts über einen Ehewillen aus. Aus dem Bericht ergibt sich sodann, dass im Badezimmer keine Parfüms und Pflegeprodukte für Frauen vorhanden gewesen wären. Immerhin enthielt das Zahnputzglas zwei Zahnbürsten.
Unbestritten ist, dass die Schwester der Ehefrau des Beschwerdeführers im Spital war und die Ehefrau ihre Schwester für eine gewisse Zeit in Deutschland unterstützt hat. Angesichts dessen und des Umstands, dass die Eheleute noch nicht lange verheiratet waren, ist es nachvollziehbar, dass die Wohnung beim Besuch der Polizei eher wie ein Einpersonenhaushalt ausgesehen hat. Im Wissen darum, dass die Ehefrau im Zeitpunkt der Inspektion in Deutschland verweilte, wäre es - wie der Beschwerdeführer zu Recht moniert - für ein abschliessendes Urteil über den Ehewillen notwendig gewesen, nach Rückkehr der Ehefrau des Beschwerdeführers weitere polizeiliche Besuche vorzunehmen.
4.2. Die Vorinstanz ist davon ausgegangen, dass aufgrund der polizeilichen Inspektion keine Wohngemeinschaft zwischen dem Beschwerdeführer und seiner Ehefrau bestanden habe, weshalb die von ihm eingereichten Bestätigungen der Nachbarn und der Arbeitgeberin als blosse Gefälligkeitsschreiben qualifiziert werden müssten. Wenn die Vorinstanz davon ausgegangen ist, dass die Indizien so stark sind, dass dem Beschwerdeführer der Gegenbeweis obliegen würde (vgl. Urteil 2C_138/2018 vom 16. Januar 2019 E. 3.2 zweiter Abs.), können die angebotenen Beweise nicht leichthin abgelehnt werden, da ansonsten die Verfahrensrechte des zur Mitwirkung Verpflichteten ausgehebelt würden (vgl. oben E. 2.3 i.f.; Urteil 2C_518/2016 vom 7. September 2017 E. 3.3). Die Vorinstanz hat in einem Satz die angebotenen Beweise als Gefälligkeitsschreiben bezeichnet und sich nicht damit auseinandergesetzt.
4.3. Eine Auseinandersetzung wäre hier umso naheliegender gewesen, als es sich um eine Beziehung handelt, welche dem FZA unterliegt. Das Bundesgericht hat sich in <ref-ruling> der Rechtsprechung des EuGH zur rechtsmissbräuchlichen Berufung auf Ansprüche im Bereich der Personenfreizügigkeit angeschlossen (E. 9.3 und 9.4) und zugleich festgehalten, dass die einfache Tatsache des Getrenntlebens keinem Rechtsmissbrauch gleichkomme (E. 9.5 und 10.3 S. 134 bzw. 136). Insofern ist auch der von der Vorinstanz vorgenommene Schluss, dass rechtsmissbräuchlich formell an der Ehe festgehalten werde, da die Ehefrau nicht in der Wohnung des Beschwerdeführers lebe, unzulässig. In diesem Fall hätten sich weitere Sachverhaltsabklärungen aufgedrängt (vgl. <ref-ruling> E. 10.3 und 10.4 S. 135 ff.). Nachzuweisen ist der fehlende Ehewille. Im Übrigen sind der Beschwerdeführer und seine Ehefrau auf den 1. Juli 2018 zusammen nach V._ umgezogen. Der Mietvertrag ist von beiden unterzeichnet und beide wohnen offenbar dort (vgl. Art. 105 Abs. 2 BGG).
5.
Nach dem Gesagten erweist sich die Beschwerde als begründet und ist gutzuheissen. Dem Ausgang des bundesgerichtlichen Verfahrens entsprechend sind keine Gerichtskosten zu erheben (vgl. Art. 66 Abs. 4BGG). Der Kanton Solothurn hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (vgl. Art. 68 Abs. 1 BGG). Für die Neuregelung der Frage der Kosten- und Entschädigungsfolgen in den kantonalen Verfahren ist die Angelegenheit an das Verwaltungsgericht des Kantons Solothurn zurückzuweisen (vgl. Art. 107 Abs. 2 i.V.m. Art. 67 BGG). Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung für das bundesgerichtliche Verfahren ist dem Ausgang des Verfahrens entsprechend als gegenstandslos abzuschreiben.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 24. Oktober 2018 aufgehoben.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Solothurn hat die Rechtsvertreterin des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung für das bundesgerichtliche Verfahren wird als gegenstandslos abgeschrieben.
5.
Zur Neuregelung der Kosten- und Entschädigungsfrage im kantonalen Verfahren wird die Sache an das Verwaltungsgericht des Kantons Solothurn zurückgewiesen.
6.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 21. März 2019
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Errass