Songfacts®:

• On this introspective cut, Cole chronicles the thoughts that went through his mind when he first laid eyes on a particular girl at a club. He tries to muster the courage to approach the woman before the night ends.
  
  Last call at the bar ladies get a drink, nigga get some balls
  Ain't no telling you gonna see that bitch tomorrow
  Stop holding up the wall waiting for the right song
  Better holla cause you know they bout to cut the lights on
  
  Cole may be recalling the time he first saw his current wife, Melissa Heholt at a club. She and the rapper met while attending St. John's University, and it's not known when they got married. She's a wedding planner with a M.S. in childhood education.
• Vinylz and Boi-1da's production sounds similar to Florida beatsmith Foreign Teck's instrumentation for Bryson Tiller's ballad, "Exchange." Upon release of the 4 Your Eyez Only album, there was some controversy as to whom really made the "Exchange" beat first. Vinylz accused Foreign Teck of jacking their beat, explaining that Cole's track was recorded before Tiller's, and that after he sent the Florida producer a video of him making the instrumentation to "Deja Vu," Teck posted on Instagram not long after a beat with the same drums.
  
  Vinylz also alleged that Foreign Teck reverse engineered his beat, gave it to Tiller and then tried to cover it up by allegedly offering Boi-1da and Vinylz publishing on Tiller's tune.
  
  In response, Teck accused Boi-1da and Vinylz of being petty. "Got more money than me, wayyyy more placements than me and still come for me on a daily. yall the definition of petty lol," he tweeted.
  
  J. Cole's manager, Ibrahim "Ib" Hamad addressed the controversy over the beat during an interview with Billboard magazine. He explained the song was initially made for Cole's 2104 Forest Hills Drive album, but ended up saving it and using it on 4 Your Eyez Only.
  
  "I wouldn't say there was any hesitation because I felt like it's just two totally different songs," Hamad said of the beat. "We had already made 'Déjà Vu,' like that song was literally made for his last album and we just knew it would fit better because of the story he wanted to tell on the album."
  
  "Cole had already made the song, so when Bryson's album came out and we heard it, it was a feeling like, 'Damn, he used the same sample;" he continued. "But to Cole, it don't matter. He's not competing with Bryson. What Bryson's song did was incredible, and to Cole, it was like, 'It's a part of the story I want to tell, so I'm gonna use [the beat].' We didn't really know the backstory at the time of what happened with Vinylz and Boi1da and [ForeignTeck] who made the beat. That was none of our concern."
• The titular phrase "Deja vu" (from French "already seen") doesn't appear in the lyrics. However the use of the term is probably intended to describe the familiar nervous feeling that Cole felt in approaching the girl to ask for her number. Other artists that have recorded songs about the sensation of feeling like you've experienced a certain situation or event before include John Fogerty, Beyonce, Crosby, Stills, Nash & Young, Dionne Warwick, Eminem, Post Malone and Twenty88.
• As in "Exchange," the song samples throughout K.P. & Envyi's 1998 hit single, "Swing My Way."
• When this debuted at #7 on the Hot 100 it became Cole's first ever Top 10 hit on the chart.