\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{amitkrr001}
\pdfinfo{
  /Title (dsa-cheetsheet.pdf)
  /Creator (Cheatography)
  /Author (amitkrr001)
  /Subject (DSA Cheetsheet Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{9E1919}
\definecolor{LightBackground}{HTML}{FBF7F7}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{DSA Cheetsheet Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{amitkrr001} via \textcolor{DarkBackground}{\uline{cheatography.com/205692/cs/43905/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}amitkrr001 \\
  \uline{cheatography.com/amitkrr001} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Not Yet Published.\\
   Updated 3rd August, 2024.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{2}

\begin{tabularx}{8.4cm}{p{2.64 cm} x{5.36 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{8.4cm}}{\bf\textcolor{white}{Expected Time Complexity}}  \tn
% Row 0
\SetRowColor{LightBackground}
10\textasciicircum{}12 & O(√n) \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
10\textasciicircum{}8 & O(n) \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
10\textasciicircum{}6 & O(nlogn) \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
10\textasciicircum{}5 & O(n√n) \tn 
% Row Count 4 (+ 1)
% Row 4
\SetRowColor{LightBackground}
10\textasciicircum{}4 & O(n\textasciicircum{}2) \tn 
% Row Count 5 (+ 1)
% Row 5
\SetRowColor{white}
10\textasciicircum{}3 & O(n\textasciicircum{}2√n) \tn 
% Row Count 6 (+ 1)
% Row 6
\SetRowColor{LightBackground}
n\textless{}=25 & O(2\textasciicircum{}n) \tn 
% Row Count 7 (+ 1)
% Row 7
\SetRowColor{white}
n\textless{}=10 & O(n!) \tn 
% Row Count 8 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Sliding Window (Shrinkable)}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{// Time: O(N) \newline // Space: O(1) \newline class Solution \{ \newline public: \newline     int longestSubarray(vector\textless{}int\textgreater{}\& A) \{ \newline         int i = 0, j = 0, N = A.size(), cnt = 0, ans = 0; \newline         for (; j \textless{} N; ++j) \{ \newline             cnt += A{[}j{]} == 0; \newline             while (cnt \textgreater{} 1) cnt -= A{[}i++{]} == 0; \newline             ans = max(ans, j - i); // note that the window is of size `j - i + 1`. We use `j - i` here because we need to delete a number. \newline         \} \newline         return ans; \newline     \} \newline \};} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{find All Substrings}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{vector\textless{}string\textgreater{} findAllSubstrings(const string\& s) \{ \newline     vector\textless{}string\textgreater{} substrings; \newline     int length = s.length(); \newline      \newline     // Generate all possible substrings \newline     for (int start = 0; start \textless{} length; ++start) \{ \newline         for (int end = start + 1; end \textless{}= length; ++end) \{ \newline             \seqsplit{substrings.push\_back(s.substr(start}, end - start)); \newline         \} \newline     \} \newline      \newline     return substrings; \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{BFS}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{void bsf(int start,vector\textless{}int\textgreater{} adj{[}{]},vector\textless{}bool\textgreater{}\&vis,vector\textless{}int\textgreater{}\&result)\{ \newline         queue\textless{}int\textgreater{}que; \newline         que.push(start); \newline         vis{[}start{]}=true; \newline         \seqsplit{result.push\_back(start);} \newline         while(!que.empty())\{ \newline             int u=que.front(); \newline             que.pop(); \newline             for(auto x:adj{[}u{]})\{ \newline                 if(!vis{[}x{]})\{ \newline                     que.push(x); \newline                     vis{[}x{]}=true; \newline                     result.push\_back(x); \newline                 \} \newline             \} \newline         \} \newline     \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{DFS}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{void dfs( unordered\_map\textless{}int,vector\textless{}int\textgreater{}\textgreater{} adj,int start,vector\textless{}bool\textgreater{}\&vis,vector\textless{}int\textgreater{}\&result)\{ \newline         if(vis{[}start{]}==true) return; \newline         vis{[}start{]}=true; \newline         \seqsplit{result.push\_back(start);} \newline         for(auto x:adj{[}start{]})\{ \newline             if(!vis{[}x{]})\{ \newline                 dfs(adj,x,vis,result); \newline             \} \newline              \newline         \} \newline     \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{x{1.36 cm} x{6.64 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{8.4cm}}{\bf\textcolor{white}{Time Complexity \& Algorithms}}  \tn
% Row 0
\SetRowColor{LightBackground}
\seqsplit{O(logn)} & Binary Search, Balanced Binary Search Trees (AVL Tree, Red-Black Tree), Heap Operations \tn 
% Row Count 3 (+ 3)
% Row 1
\SetRowColor{white}
O(n) & Breadth-First Search (BFS), Depth-First Search (DFS), Single-pass Hash Table Operations, Prefix Sum Array Calculation \tn 
% Row Count 7 (+ 4)
% Row 2
\SetRowColor{LightBackground}
\seqsplit{O(nlogn)} & Sorting algorithms (general), heap \tn 
% Row Count 9 (+ 2)
% Row 3
\SetRowColor{white}
O(n\textasciicircum{}2) & dp, Brute-force \tn 
% Row Count 10 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Sliding Window ( Non-Shrinkable)}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{// Time: O(N) \newline // Space: O(1) \newline class Solution \{ \newline public: \newline     int longestSubarray(vector\textless{}int\textgreater{}\& A) \{ \newline         int i = 0, j = 0, N = A.size(), cnt = 0; \newline         for (; j \textless{} N; ++j) \{ \newline             cnt += A{[}j{]} == 0; \newline             if (cnt \textgreater{} 1) cnt -= A{[}i++{]} == 0; \newline         \} \newline         return j - i - 1; \newline     \} \newline \};} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Binary Search}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{int binarySearch(vector\textless{}int\textgreater{}\& nums, int target)\{ \newline   if(nums.size() == 0) \newline     return -1; \newline  \newline   int left = 0, right = nums.size() - 1; \newline   while(left \textless{}= right)\{ \newline     // Prevent (left + right) overflow \newline     int mid = left + (right - left) / 2; \newline     if(nums{[}mid{]} == target)\{ return mid; \} \newline     else if(nums{[}mid{]} \textless{} target) \{ left = mid + 1; \} \newline     else \{ right = mid - 1; \} \newline   \} \newline  \newline   // End Condition: left \textgreater{} right \newline   return -1; \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Dynamic Programming Patterns}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{- Minimum (Maximum) Path to Reach a Target} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Approach:}}\{\{nl\}\} Choose the minimum (or maximum) path among all possible paths before the current state, then add the value for the current state. \{\{nl\}\} {\bf{ Formula:}}routes{[}i{]} = min(routes{[}i-1{]}, routes{[}i-2{]}, ..., routes{[}i-k{]}) + cost{[}i{]}} \tn 
% Row Count 6 (+ 5)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{- Distinct Ways} \tn 
% Row Count 7 (+ 1)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Approach:}} \{\{nl\}\} Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.\{\{nl\}\}{\bf{ Formula:}} routes{[}i{]} = routes{[}i-1{]} + routes{[}i-2{]}, ... , + routes{[}i-k{]}} \tn 
% Row Count 12 (+ 5)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{- Merging Intervals} \tn 
% Row Count 13 (+ 1)
% Row 5
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Approach:}}\{\{nl\}\} Find all optimal solutions for every interval and return the best possible answer\{\{nl\}\} {\bf{ Formula:}} dp{[}i{]}{[}j{]} = dp{[}i{]}{[}k{]} + result{[}k{]} + dp{[}k+1{]}{[}j{]}} \tn 
% Row Count 17 (+ 4)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{- DP on Strings} \tn 
% Row Count 18 (+ 1)
% Row 7
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Approach:}}\{\{nl\}\} Compare 2 chars of String or 2 Strings. Do whatever you do. Return.\{\{nl\}\}{\bf{ Formula:}} if s1{[}i-1{]} == s2{[}j-1{]} then dp{[}i{]}{[}j{]} = //code. Else dp{[}i{]}{[}j{]} = //code} \tn 
% Row Count 22 (+ 4)
% Row 8
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{- Decision Making} \tn 
% Row Count 23 (+ 1)
% Row 9
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Approach:}}\{\{nl\}\} If you decide to choose the current value use the previous result where the value was ignored; vice-versa, if you decide to ignore the current value use previous result where value was used.\{\{nl\}\} {\bf{ Formula:}} dp{[}i{]}{[}j{]} = max(\{dp{[}i{]}{[}j{]}, dp{[}i-1{]}{[}j{]} + arr{[}i{]}, dp{[}i-1{]}{[}j-1{]}\}); dp{[}i{]}{[}j-1{]} = max(\{dp{[}i{]}{[}j-1{]}, dp{[}i-1{]}{[}j-1{]} + arr{[}i{]}, arr{[}i{]}\});} \tn 
% Row Count 31 (+ 8)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}