\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{burcuco}
\pdfinfo{
  /Title (data-structures-and-algorithms.pdf)
  /Creator (Cheatography)
  /Author (burcuco)
  /Subject (Data Structures and Algorithms 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}{82638F}
\definecolor{LightBackground}{HTML}{F7F5F8}
\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{Data Structures and Algorithms Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{burcuco} via \textcolor{DarkBackground}{\uline{cheatography.com/133629/cs/27343/}}}
\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}burcuco \\
  \uline{cheatography.com/burcuco} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Published 30th March, 2021.\\
   Updated 30th March, 2021.\\
   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}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Arrays \& Strings}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{Stores data elements based on an sequential, most commonly 0 based, index.} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Time Complexity}} \{\{nl\}\} ● {\bf{Indexing:}} Linear array: O(1), Dynamic array: O(1) \{\{nl\}\}● {\bf{Search:}} Linear array: O(n), Dynamic array: O(n) \{\{nl\}\}● {\bf{Optimized Search:}} Linear array: O(log n), Dynamic array: O(log n) \{\{nl\}\}● {\bf{Insertion:}} Linear array: n/a, Dynamic array: O(n)} \tn 
% Row Count 8 (+ 6)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Bonus}}:\{\{nl\}\}  ● type{[}{]} name = \{val1, val2, ...\}\{\{nl\}\} ● Arrays.sort(arr) -\textgreater{} O(n log(n))\{\{nl\}\} ● Collections.sort(list) -\textgreater{} O(n log(n))\{\{nl\}\} ● int digit = '4' - '0' -\textgreater{} 4\{\{nl\}\} ● String s = String.valueOf('e') -\textgreater{} "e"\{\{nl\}\} ● (int) 'a' -\textgreater{} 97 (ASCII)\{\{nl\}\} ● new String(char{[}{]} arr) {[}'a','e'{]} -\textgreater{} "ae"\{\{nl\}\} ● (char) ('a' + 1) -\textgreater{} 'b'\{\{nl\}\} ● \seqsplit{Character.isLetterOrDigit(char)} -\textgreater{} true/false\{\{nl\}\} ● new ArrayList\textless{}\textgreater{}(anotherList); -\textgreater{} list w/ items\{\{nl\}\} ● StringBuilder.append(char||String)\{\{nl\}\}} \tn 
% Row Count 19 (+ 11)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Linked List}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{Stores data with nodes that point to other nodes.} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Time Complexity}} \{\{nl\}\}● {\bf{Indexing:}} O(n) \{\{nl\}\}● {\bf{Search:}} O(n) \{\{nl\}\}● {\bf{Optimized Search:}} O(n) \{\{nl\}\}● {\bf{Append:}} O(1) \{\{nl\}\}● {\bf{Prepend:}} O(1) \{\{nl\}\}● {\bf{Insertion:}} O(n)} \tn 
% Row Count 5 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{HashTable}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{Stores data with key-value pairs.} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Time Complexity}} \{\{nl\}\}● {\bf{Indexing:}} O(1) \{\{nl\}\}● {\bf{Search:}} O(1) \{\{nl\}\}● {\bf{Insertion:}} O(1)} \tn 
% Row Count 4 (+ 3)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Bonus}}:\{\{nl\}\}  ● \{1, -1, 0, 2, -2\} into map\{\{nl\}\} HashMap \{-1, 0, 2, 1, -2\} -\textgreater{} any order\{\{nl\}\} LinkedHashMap \{1, -1, 0, 2, -2\} -\textgreater{} insertion order\{\{nl\}\} TreeMap \{-2, -1, 0, 1, 2\} -\textgreater{} sorted\{\{nl\}\} ● Set doesn't allow duplicates.\{\{nl\}\} ● \seqsplit{map.getOrDefaultValue(key}, default value)\{\{nl\}\}} \tn 
% Row Count 10 (+ 6)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{x{1.8 cm} x{1.8 cm} x{1.8 cm} x{1.8 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{4}{x{8.4cm}}{\bf\textcolor{white}{Stack/Queue/Deque}}  \tn
% Row 0
\SetRowColor{LightBackground}
Stack & Queue & Deque & Heap \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
Last In First Out & First In Last Out & Provides \seqsplit{first/last} & Ascending Order \tn 
% Row Count 3 (+ 2)
% Row 2
\SetRowColor{LightBackground}
push(val) \{\{nl\}\}pop()\{\{nl\}\} peek()\{\{nl\}\} & offer(val)\{\{nl\}\} poll()\{\{nl\}\} peek()\{\{nl\}\} & offer(val)\{\{nl\}\} poll()\{\{nl\}\}peek()\{\{nl\}\} & offer(val)\{\{nl\}\} poll()\{\{nl\}\}peek()\{\{nl\}\} \tn 
% Row Count 8 (+ 5)
\hhline{>{\arrayrulecolor{DarkBackground}}----}
\SetRowColor{LightBackground}
\mymulticolumn{4}{x{8.4cm}}{Implementation in Java:  \newline ● Stack\textless{}E\textgreater{} stack = new Stack(); \newline ● Queue\textless{}E\textgreater{} queue = new LinkedList(); \newline ● Deque\textless{}E\textgreater{} deque = new LinkedList(); \newline ● PriorityQueue\textless{}E\textgreater{} pq = new PriorityQueue();}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}----}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{x{2.204 cm} x{2.508 cm} x{2.888 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{3}{x{8.4cm}}{\bf\textcolor{white}{DFS \& BFS Big O Notation}}  \tn
% Row 0
\SetRowColor{LightBackground}
 & {\bf{Time}} & {\bf{Space}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
{\bf{DFS}} & O(E+V) & O(Height) \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
{\bf{BFS}} & O(E+V) & O(Length) \tn 
% Row Count 3 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\SetRowColor{LightBackground}
\mymulticolumn{3}{x{8.4cm}}{{\bf{V \& E}} -\textgreater{} where V is the number of vertices and E is the number of edges. \newline {\bf{Height}} -\textgreater{} where h is the maximum height of the tree. \newline {\bf{Length}} -\textgreater{} where l is the maximum number of nodes in a single level.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{x{4 cm} x{4 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{8.4cm}}{\bf\textcolor{white}{DFS vs BFS}}  \tn
% Row 0
\SetRowColor{LightBackground}
DFS & BFS \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
●Better when target is closer to Source.\{\{nl\}\} ●Stack -\textgreater{} LIFO\{\{nl\}\} ●Preorder, Inorder, Postorder Search\{\{nl\}\} ●Goes deep\{\{nl\}\}  ●Recursive\{\{nl\}\} ●Fast\{\{nl\}\} & ●Better when target is far from Source.\{\{nl\}\} ●Queue -\textgreater{} FIFO\{\{nl\}\} ●Level Order Search\{\{nl\}\} ●Goes wide\{\{nl\}\} ●Iterative\{\{nl\}\} ●Slow\{\{nl\}\} \tn 
% Row Count 10 (+ 9)
\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 Impl for Graph}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{public boolean {\bf{connected}}(int{[}{]}{[}{]} graph, int start, int end) \{ \newline   Set\textless{}Integer\textgreater{} visited = new HashSet\textless{}\textgreater{}(); \newline   Queue\textless{}Integer\textgreater{} toVisit = new LinkedList\textless{}\textgreater{}(); \newline   toVisit.enqueue(start); \newline   while (!toVisit.isEmpty()) \{ \newline   	  int curr = toVisit.dequeue(); \newline   	  if (visited.contains(curr)) {\bf{continue}}; \newline   	  if (curr == end) {\bf{return}} true; \newline   	  for (int i : graph{[}start{]}) \{ \newline      toVisit.enqueue(i); \newline    \} \newline   	  visited.add(curr); \newline    \} \newline   {\bf{return}} false; \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 Impl for Graph}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{public boolean {\bf{connected}}(int{[}{]}{[}{]} graph, int start, int end) \{ \newline   Set\textless{}Integer\textgreater{} visited = new HashSet\textless{}\textgreater{}(); \newline   {\bf{return}} connected(graph, start, end, visited); \newline \} \newline  \newline  \newline private boolean {\bf{connected}}(int{[}{]}{[}{]} graph, int start, int end, Set\textless{}Integer\textgreater{} visited) \{ \newline   if (start == end) {\bf{return}} true; \newline   if \seqsplit{(visited.contains(start))} {\bf{return}} false; \newline   visited.add(start); \newline   for (int i : graph{[}start{]}) \{ \newline     if (connected(graph, i, end, visited)) \{ \newline       {\bf{return}} true; \newline     \} \newline   \} \newline   {\bf{return}} false; \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 Impl. for Level-order Tree Traversal}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{private void {\bf{printLevelOrder}}(TreeNode root) \{ \newline   Queue\textless{}TreeNode\textgreater{} queue = new LinkedList\textless{}\textgreater{}(); \newline   queue.offer(root); \newline   while (!queue.isEmpty()) \{ \newline     TreeNode tempNode = queue.poll(); \newline     print(tempNode.data + " "); \newline   \newline     //{\emph{add left child}} \newline     if (tempNode.left != null) \{ \newline        \seqsplit{queue.offer(tempNode.left);} \newline     \} \newline   \newline     //{\emph{add right right child}} \newline     if (tempNode.right != null) \{ \newline        \seqsplit{queue.offer(tempNode.right);} \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 Impl. for In-order Tree Traversal}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{private void {\bf{inorder}}(TreeNode TreeNode) \{ \newline     if (TreeNode == null) \newline         {\bf{return}}; \newline  \newline     // Traverse left \newline     inorder(TreeNode.left); \newline  \newline     // Traverse root \newline     print(TreeNode.data + " "); \newline  \newline     // Traverse right \newline     inorder(TreeNode.right); \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}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{● Dynamic programming is the technique of storing repeated computations in memory, rather than recomputing them every time you need them.  \newline % Row Count 3 (+ 3)
● The ultimate goal of this process is to improve runtime.  \newline % Row Count 5 (+ 2)
● Dynamic programming allows you to use more space to take less time.% Row Count 7 (+ 2)
} \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 minimum (maximum) path among all possible paths before the current state, then add value for the current state.  \{\{nl\}\}{\bf{Formula:}} \{\{nl\}\}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:}} \{\{nl\}\}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:}} \{\{nl\}\}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:}} \{\{nl\}\} if s1{[}i-1{]} == s2{[}j-1{]} then dp{[}i{]}{[}j{]} = //code. \{\{nl\}\}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:}} \{\{nl\}\} dp{[}i{]}{[}j{]} = max(\{dp{[}i{]}{[}j{]}, dp{[}i-1{]}{[}j{]} + arr{[}i{]}, dp{[}i-1{]}{[}j-1{]}\}); \{\{nl\}\} 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}

\begin{tabularx}{8.4cm}{x{3.8 cm} x{1.824 cm} x{1.976 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{3}{x{8.4cm}}{\bf\textcolor{white}{Binary Search Big O Notation}}  \tn
% Row 0
\SetRowColor{LightBackground}
 & {\bf{Time}} & {\bf{Space}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
{\bf{Binary Search}} & O(log n) & O(1) \tn 
% Row Count 2 (+ 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}{Binary Search - Recursive}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{public int {\bf{binarySearch}}(int search, int{[}{]} array, int start, int end) {\bf{\{}} \newline    int middle = start + ((end - start) / 2); \newline    if(end \textless{} start) \{ \newline       {\bf{return}} -1; \newline    \}  \newline  \newline    if (search == array{[}middle{]}) \{ \newline       {\bf{return}} middle;  \newline    \} else if (search \textless{} array{[}middle{]}) \{ \newline       {\bf{return}} binarySearch(search, array, start, middle - 1); \newline    \} else \{ \newline       {\bf{return}} binarySearch(search, array, middle + 1, end); \newline    \} \newline {\bf{\}}}} \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 - Iterative}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{public int {\bf{binarySearch}}(int target, int{[}{]} array) {\bf{\{}} \newline    int start = 0; \newline    int end = array.length - 1; \newline    while (start \textless{}= end) \{ \newline       int middle = start + ((end - start) / 2); \newline       if (target == array{[}middle{]}) \{ \newline           {\bf{return}} target; \newline       \} else if (search \textless{} array{[}middle{]}) \{ \newline           end = middle - 1; \newline       \} else \{ \newline           start = middle + 1; \newline       \} \newline    \} \newline    {\bf{return}} -1; \newline {\bf{\}}}} \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}{Bit Manipulation}}  \tn
% Row 0
\SetRowColor{LightBackground}
Sign Bit & 0 -\textgreater{} Positive, 1 -\textgreater{} Negative \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
AND & 0 \& 0 -\textgreater{} 0\{\{nl\}\} 0 \& 1 -\textgreater{} 0\{\{nl\}\} 1 \& 1 -\textgreater{} 1 \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
OR & 0 | 0 -\textgreater{} 0 \{\{nl\}\} 0 | 1 -\textgreater{} 1 \{\{nl\}\} 1 | 1 -\textgreater{} 1 \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
XOR & 0 \textasciicircum{} 0 -\textgreater{} 0\{\{nl\}\} 0 \textasciicircum{} 1 -\textgreater{} 1 \{\{nl\}\}1 \textasciicircum{} 1 -\textgreater{} 0 \tn 
% Row Count 8 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\seqsplit{INVERT} & \textasciitilde{} 0 -\textgreater{} 1\{\{nl\}\} \textasciitilde{} 1 -\textgreater{} 0 \tn 
% Row Count 9 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{8.4cm}}{{\bf{Bonus:}} \newline ● {\bf{Shifting}} \newline - Left Shift \newline 0001 \textless{}\textless{} 0010 (Multiply by 2) \newline - Right Shift \newline 0010 \textgreater{}\textgreater{} 0001 (Division by 2) \newline  \newline ● Count 1's of n, Remove last bit \newline n = n \& (n-1); \newline ●  Extract last bit  \newline n\&-n or n\&\textasciitilde{}(n-1) or n\textasciicircum{}(n\&(n-1)) \newline ●  n \textasciicircum{} n -\textgreater{} 0 \newline ●  n \textasciicircum{} 0 -\textgreater{} n}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{x{2.736 cm} x{1.584 cm} x{1.584 cm} x{1.296 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{4}{x{8.4cm}}{\bf\textcolor{white}{Sorting Big O Notation}}  \tn
% Row 0
\SetRowColor{LightBackground}
 & {\bf{Best}} & {\bf{Average}} & {\bf{Space}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\bf{Merge Sort}} & O(n log(n)) & O(n log(n)) & O(n) \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
{\bf{Heap Sort}} & O(n log(n)) & O(n log(n)) & O(1) \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
{\bf{Quick Sort}} & O(n log(n)) & O(n log(n)) & \seqsplit{O(log(n))} \tn 
% Row Count 8 (+ 2)
% Row 4
\SetRowColor{LightBackground}
{\bf{Insertion Sort}} & O(n) & O(n\textasciicircum{}2) & O(1) \tn 
% Row Count 10 (+ 2)
% Row 5
\SetRowColor{white}
{\bf{Selection Sort}} & O(n\textasciicircum{}2) & O(n\textasciicircum{}2) & O(1) \tn 
% Row Count 12 (+ 2)
% Row 6
\SetRowColor{LightBackground}
{\bf{Bubble Sort}} & O(n) & O(n\textasciicircum{}2) & O(1) \tn 
% Row Count 13 (+ 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}{Merge Sort}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{private void {\bf{mergesort}}(int low, int high) {\bf{\{}}\{\{nl\}\}         if (low \textless{} high) \{\{\{nl\}\}             ~~~~int middle = low + (high - low) / 2;\{\{nl\}\}             ~~~~mergesort(low, middle);\{\{nl\}\}             ~~~~mergesort(middle + 1, high);\{\{nl\}\}             ~~~~merge(low, middle, high);\{\{nl\}\}         ~~\}\{\{nl\}\} {\bf{\}}} \newline  \newline private void {\bf{merge}}(int low, int middle, int high) {\bf{\{}}\{\{nl\}\}          for (int i = low; i \textless{}= high; i++) \{\{\{nl\}\}             ~~~~helper{[}i{]} = numbers{[}i{]};\{\{nl\}\}         \}\{\{nl\}\}          int i = low;\{\{nl\}\}         int j = middle + 1;\{\{nl\}\}         int k = low;\{\{nl\}\}         while (i \textless{}= middle \&\& j \textless{}= high) \{\{\{nl\}\}             ~~if (helper{[}i{]} \textless{}= helper{[}j{]}) \{\{\{nl\}\}                 ~~~~numbers{[}k{]} = helper{[}i{]};\{\{nl\}\}                ~~~~i++;\{\{nl\}\}            ~~\} else \{\{\{nl\}\}                 ~~~~numbers{[}k{]} = helper{[}j{]};\{\{nl\}\}                 ~~~~j++;\{\{nl\}\}             ~~\}\{\{nl\}\}             ~~k++;\{\{nl\}\}         \}\{\{nl\}\}         while (i \textless{}= middle) \{\{\{nl\}\}             ~~numbers{[}k{]} = helper{[}i{]};\{\{nl\}\}             ~~k++;\{\{nl\}\}              ~~i++;\{\{nl\}\}         ~\}\{\{nl\}\}     {\bf{\}}}\{\{nl\}\}} \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}{Quick Sort}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{private void {\bf{quicksort}}(int low, int high) {\bf{\{}}\{\{nl\}\}         int i = low, j = high;\{\{nl\}\}         int pivot = numbers{[}low + (high-low)/2{]};\{\{nl\}\}         while (i \textless{}= j) \{\{\{nl\}\}             ~~~~while (numbers{[}i{]} \textless{} pivot) \{\{\{nl\}\}                 ~~~~~~i++;\{\{nl\}\}             ~~ ~\}\{\{nl\}\}             ~~ ~while (numbers{[}j{]} \textgreater{} pivot) \{\{\{nl\}\}                  ~~~~~~j-{}-;\{\{nl\}\}              ~~~~\}\{\{nl\}\}               ~~~~if (i \textless{}= j) \{\{\{nl\}\}                 ~~~~~~exchange(i, j);\{\{nl\}\}                 ~~~~~~i++;\{\{nl\}\}                 ~~~~~~j-{}-;\{\{nl\}\}              ~~~~\}\{\{nl\}\}         \}\{\{nl\}\}          if (low \textless{} j)\{\{nl\}\}             ~~~~quicksort(low, j);\{\{nl\}\}         if (i \textless{} high)\{\{nl\}\}             ~~~~quicksort(i, high);\{\{nl\}\}     {\bf{\}}}\{\{nl\}\}} \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}{Insertion Sort}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{void {\bf{insertionSort}}(int arr{[}{]}) \{ \newline   int n = arr.length; \newline   for (int i = 1; i \textless{} n; ++i) \{ \newline       int key = arr{[}i{]}; \newline       int j = i - 1; \newline       while (j \textgreater{}= 0 \&\& arr{[}j{]} \textgreater{} key) \{ \newline            arr{[}j + 1{]} = arr{[}j{]}; \newline            j = j - 1; \newline       \} \newline       arr{[}j + 1{]} = key; \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}{Combinations Backtrack Pattern}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{{\bf{- Combination}} \newline public List\textless{}List\textless{}Integer\textgreater{}\textgreater{} {\bf{combinationSum}}(int{[}{]} nums, int target) \{ \newline     List\textless{}List\textless{}Integer\textgreater{}\textgreater{} list = new ArrayList\textless{}\textgreater{}(); \newline     Arrays.sort(nums); \newline     backtrack(list, new ArrayList\textless{}\textgreater{}(), nums, target, 0); \newline     return list; \newline \} \newline  \newline private void {\bf{backtrack}}(List\textless{}List\textless{}Integer\textgreater{}\textgreater{} list, List\textless{}Integer\textgreater{} tempList, int {[}{]} nums, int remain, int start)\{ \newline     if(remain \textless{} 0) return; \newline     else if(remain == 0) list.add(new ArrayList\textless{}\textgreater{}(tempList)); \newline     else\{  \newline         for(int i = start; i \textless{} nums.length; i++)\{ \newline             tempList.add(nums{[}i{]}); \newline             {\bf{// not i + 1 because we can reuse same elements}} \newline             backtrack(list, tempList, nums, remain - nums{[}i{]}, i);  \newline             {\bf{// not i + 1 because we can reuse same elements}} \newline             \seqsplit{tempList.remove(tempList.size()} - 1); \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}{Palindrome Backtrack Pattern}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{{\bf{- Palindrome Partitioning}} \newline public List\textless{}List\textless{}String\textgreater{}\textgreater{} {\bf{partition}}(String s) \{ \newline    List\textless{}List\textless{}String\textgreater{}\textgreater{} list = new ArrayList\textless{}\textgreater{}(); \newline    backtrack(list, new ArrayList\textless{}\textgreater{}(), s, 0); \newline    return list; \newline \} \newline  \newline public void {\bf{backtrack}}(List\textless{}List\textless{}String\textgreater{}\textgreater{} list, List\textless{}String\textgreater{} tempList, String s, int start)\{ \newline    if(start == s.length()) \newline       list.add(new ArrayList\textless{}\textgreater{}(tempList)); \newline    else\{ \newline       for(int i = start; i \textless{} s.length(); i++)\{ \newline          if(isPalindrome(s, start, i))\{ \newline             \seqsplit{tempList.add(s.substring(start}, i + 1)); \newline             backtrack(list, tempList, s, i + 1); \newline             \seqsplit{tempList.remove(tempList.size()} - 1); \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}{Subsets Backtrack Pattern}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{- {\bf{Subsets}} \newline public List\textless{}List\textless{}Integer\textgreater{}\textgreater{} {\bf{subsets}}(int{[}{]} nums) \{ \newline     List\textless{}List\textless{}Integer\textgreater{}\textgreater{} list = new ArrayList\textless{}\textgreater{}(); \newline     Arrays.sort(nums); \newline     backtrack(list, new ArrayList\textless{}\textgreater{}(), nums, 0); \newline     return list; \newline \} \newline  \newline private void {\bf{backtrack}}(List\textless{}List\textless{}Integer\textgreater{}\textgreater{} list, List\textless{}Integer\textgreater{} tempList, int {[}{]} nums, int start)\{ \newline     list.add(new ArrayList\textless{}\textgreater{}(tempList)); \newline     for(int i = start; i \textless{} nums.length; i++)\{ \newline         {\bf{// skip duplicates }} \newline         if(i \textgreater{} start \&\& nums{[}i{]} == nums{[}i-1{]}) continue; \newline        {\bf{ // skip duplicates }} \newline         tempList.add(nums{[}i{]}); \newline         backtrack(list, tempList, nums, i + 1); \newline         \seqsplit{tempList.remove(tempList.size()} - 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}{Permutations Backtrack Pattern}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{{\bf{- Permutations}} \newline public List\textless{}List\textless{}Integer\textgreater{}\textgreater{} {\bf{permute}}(int{[}{]} nums) \{ \newline    List\textless{}List\textless{}Integer\textgreater{}\textgreater{} list = new ArrayList\textless{}\textgreater{}(); \newline   {\bf{ // Arrays.sort(nums); // not necessary}} \newline    backtrack(list, new ArrayList\textless{}\textgreater{}(), nums); \newline    return list; \newline \} \newline  \newline private void {\bf{backtrack}}(List\textless{}List\textless{}Integer\textgreater{}\textgreater{} list, List\textless{}Integer\textgreater{} tempList, int {[}{]} nums)\{ \newline    if(tempList.size() == nums.length)\{ \newline       list.add(new ArrayList\textless{}\textgreater{}(tempList)); \newline    \} else\{ \newline       for(int i = 0; i \textless{} nums.length; i++)\{  \newline         {\bf{ // element already exists, skip}} \newline          if(tempList.contains(nums{[}i{]})) continue; \newline          {\bf{// element already exists, skip }} \newline          tempList.add(nums{[}i{]}); \newline          backtrack(list, tempList, nums); \newline          \seqsplit{tempList.remove(tempList.size()} - 1); \newline       \} \newline    \} \newline \}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


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

\end{document}