{"id":1150,"date":"2023-08-24T15:09:24","date_gmt":"2023-08-24T15:09:24","guid":{"rendered":"https:\/\/spacican.com\/notes\/?p=1150"},"modified":"2023-12-17T09:51:19","modified_gmt":"2023-12-17T09:51:19","slug":"dsa-notes","status":"publish","type":"post","link":"https:\/\/spacican.com\/notes\/dsa-notes\/","title":{"rendered":"Data Structure Notes"},"content":{"rendered":"\n<h3 class=\"wp-block-heading\">Classification of Data structure<\/h3>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<ul>\n<li><strong>Linear Data Structures<\/strong>: Arrays, Queue, Stack\n<ul>\n<li>Static: Fixed size<\/li>\n\n\n\n<li>Dynamic: unfixed size<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Non-Linear Data strcutures<\/strong>: Tree, Graph<\/li>\n<\/ul>\n<\/div>\n\n\n\n<h3 class=\"wp-block-heading\">Types of Data Strcutures with Related Algorithms:<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">Array DS<\/h4>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p class=\"accordion-button tertiary collapsed accordion-title\">Rotate Array Algorithms<\/p><div class=\"accordion-panel collapsed\">\n<ul>\n<li><strong>Juggling Algorithm<\/strong>: Optimized version of brute force where elements are shifted one by one (see <a href=\"https:\/\/stackoverflow.com\/a\/23321270\">explaination<\/a> of using GCD in juggling algorithm)<\/li>\n\n\n\n<li><strong><a href=\"https:\/\/www.geeksforgeeks.org\/block-swap-algorithm-for-array-rotation\/\">Block Swap Algorithm<\/a>:<\/strong> recursive steps:<br>rotate 1, 2, 3, 4, 5, 6, 7 by 4 places to left to get final array 5, 6, 7, 1, 2, 3, 4\n<ul>\n<li>swap [<mark>1, 2, 3<\/mark>] and [<mark>5, 6, 7<\/mark>] to get [<mark>5, 6, 7<\/mark>, 4, <mark>1, 2, 3<\/mark>]<\/li>\n\n\n\n<li>perform recursive rotation on [4, 1, 2, 3] i.e, rotate this array by 1 place to the left to get [1, 2, 3, 4]\n<ul>\n<li>swap [<mark>4]<\/mark> and [<mark>3]<\/mark> to get [<mark>3<\/mark>, 1, 2, <mark>4<\/mark>]<\/li>\n\n\n\n<li>perform recursive rotation on [3, 1, 2] i.e rotate this array by 1 place to the left to get [1, 2, 3]<\/li>\n\n\n\n<li>&#8230;.. keep performing this recursion until we get everything swapped to get final array<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Reversal algorithm for array rotation<\/strong>:\n<ul>\n<li>To rotate array of length n by d place, do following:\n<ul>\n<li>reverse 0 to d<\/li>\n\n\n\n<li>reverse d + 1 to n<\/li>\n\n\n\n<li>reverse 0 to n<\/li>\n\n\n\n<li>the final array is a rotated array by d place<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n\n\n\n<p class=\"accordion-button tertiary collapsed accordion-title\">Sort Array Algorithms<\/p><div class=\"accordion-panel collapsed\">\n<ol>\n<li><strong>Selection Sort<\/strong>: Brute force O(n<sub><sup>2<\/sup><\/sub>) time, O(1) space\n<ul>\n<li class=\"has-small-font-size\"><pre class=\"code_syntax\" style=\"margin:0;margin-top:-1em;line-height:1.25;color:#000000;background:#ffffff;\"><span class=\"line_wrapper\">for (int cur from 0 to last) <span style=\"color:#800080; \">{<\/span><\/span>\n<span class=\"line_wrapper\">    <span style=\"color:#bb7977; \">int<\/span> smallest <span style=\"color:#808030; \">=<\/span> index of smallest element after current element <span style=\"color:#808030; \">[<\/span>O<span style=\"color:#808030; \">(<\/span>n<span style=\"color:#808030; \">)<\/span><span style=\"color:#808030; \">]<\/span><\/span>\n<span class=\"line_wrapper\">    swap<span style=\"color:#808030; \">(<\/span>array<span style=\"color:#808030; \">,<\/span> cur<span style=\"color:#808030; \">,<\/span> smallest<span style=\"color:#808030; \">)<\/span><\/span>\n<span class=\"line_wrapper\"><span style=\"color:#800080; \">}<\/span><\/span><\/pre><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Bubble sort<\/strong>: Brute force O(n<sub><sup>2<\/sup><\/sub>) time, O(1) space\n<ul>\n<li class=\"has-small-font-size\"><pre class=\"code_syntax\" style=\"line-height:1.25;margin:0;margin-top:-1em;color:#000000;background:#ffffff;\"><span class=\"line_wrapper\">int last = arr.length - 1<span style=\"color:#808030; \">;<\/span><\/span>\n<span class=\"line_wrapper\">boolean swapped = true<span style=\"color:#808030; \">;<\/span><\/span>\n<span class=\"line_wrapper\">while (swapped) <span style=\"color:#800080; \">{<\/span><\/span>\n<span class=\"line_wrapper\">    swapped <span style=\"color:#808030; \">=<\/span> <span style=\"color:#800000; font-weight:bold; \">false<\/span><span style=\"color:#800080; \">;<\/span><\/span>\n<span class=\"line_wrapper\">    <span style=\"color:#800000; font-weight:bold; \">for<\/span> <span style=\"color:#808030; \">(<\/span><span style=\"color:#bb7977; \">int<\/span> i <span style=\"color:#808030; \">=<\/span> <span style=\"color:#008c00; \">1<\/span><span style=\"color:#800080; \">;<\/span> i <span style=\"color:#808030; \">&lt;<\/span><span style=\"color:#808030; \">=<\/span> last<span style=\"color:#800080; \">;<\/span> i<span style=\"color:#808030; \">+<\/span><span style=\"color:#808030; \">+<\/span><span style=\"color:#808030; \">)<\/span> <span style=\"color:#800080; \">{<\/span><\/span>\n<span class=\"line_wrapper\">        <span style=\"color:#800000; font-weight:bold; \">if<\/span> <span style=\"color:#808030; \">(<\/span>arr<span style=\"color:#808030; \">[<\/span>i<span style=\"color:#808030; \">]<\/span> <span style=\"color:#808030; \">&lt;<\/span> arr<span style=\"color:#808030; \">[<\/span>i <span style=\"color:#808030; \">-<\/span> <span style=\"color:#008c00; \">1<\/span><span style=\"color:#808030; \">]<\/span><span style=\"color:#808030; \">)<\/span> <span style=\"color:#800080; \">{<\/span><\/span>\n<span class=\"line_wrapper\">            swap<span style=\"color:#808030; \">(<\/span>arr<span style=\"color:#808030; \">,<\/span> i<span style=\"color:#808030; \">,<\/span> i <span style=\"color:#808030; \">-<\/span> <span style=\"color:#008c00; \">1<\/span><span style=\"color:#808030; \">)<\/span><span style=\"color:#800080; \">;<\/span><\/span>\n<span class=\"line_wrapper\">            swapped <span style=\"color:#808030; \">=<\/span> <span style=\"color:#800000; font-weight:bold; \">true<\/span><span style=\"color:#800080; \">;<\/span><\/span>\n<span class=\"line_wrapper\">        <span style=\"color:#800080; \">}<\/span><\/span>\n<span class=\"line_wrapper\">    <span style=\"color:#800080; \">}<\/span><\/span>\n<span class=\"line_wrapper\">    last<span style=\"color:#808030; \">-<\/span><span style=\"color:#808030; \">-<\/span><span style=\"color:#800080; \">;<\/span><\/span>\n<span class=\"line_wrapper\"><span style=\"color:#800080; \">}<\/span><\/span><\/pre><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Heap sort<\/strong>: convert array to heap with buildHeap(), keep collecting the root node to the end while constantly heapifying<\/li>\n\n\n\n<li><strong>Merge sort<\/strong>: split array into two parts, recursively Merge sort splitted parts -&gt; then merge two sorted parts back using comparison<\/li>\n<\/ol>\n<\/div>\n\n\n\n<p class=\"accordion-button tertiary collapsed accordion-title\">Problems<\/p><div class=\"accordion-panel collapsed\">\n<ul>\n<li>Sort array containing 1 to n values, only swap is allowed (<a href=\"https:\/\/www.geeksforgeeks.org\/sort-array-contain-1-n-values\/\">link<\/a>)<\/li>\n\n\n\n<li>Count the number of possible triangles using two pointers in O(n<sup>2<\/sup>) (<a href=\"https:\/\/www.geeksforgeeks.org\/find-number-of-triangles-possible\/\">link<\/a>)<\/li>\n\n\n\n<li>Rearrange positive and negative alternatively in O(n) time &amp; O(1) space: (<a href=\"https:\/\/www.geeksforgeeks.org\/rearrange-positive-and-negative-numbers-publish\/\">link<\/a>)<\/li>\n\n\n\n<li>Put negative in front and positive at back without maintaining order | O(n) time &amp; O(1) space. (<a href=\"https:\/\/leetcode.com\/problems\/sort-array-by-parity\/submissions\/1061345541\/?envType=daily-question&amp;envId=2023-09-28\">link<\/a>)<\/li>\n\n\n\n<li>Put negative in front and positve at back <span style=\"text-decoration: underline;\">while maintaining order<\/span> | O(nlogn) time &amp; O(logn) space: (<a href=\"https:\/\/practice.geeksforgeeks.org\/problems\/arranging-the-array1131\/1\">link<\/a>)<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n<h4 class=\"wp-block-heading\">String<\/h4>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<ul>\n<li>Trie Data Structure (Prefix Tree)<\/li>\n\n\n\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Longest_palindromic_substring#Manacher's_algorithm\" data-type=\"link\" data-id=\"https:\/\/en.wikipedia.org\/wiki\/Longest_palindromic_substring#Manacher's_algorithm\">Manacher&#8217;s Algorithm<\/a> \n<ul>\n<li>Used for palindrome related problems, generally resulting in O(n) runtime.<\/li>\n\n\n\n<li>If left portion of a palindromic substring has already been explored, then no need to re-explore right portion of same palindromic substring as this is going to be mirror of already explored left portion.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>TODO: Knuth\u2013Morris\u2013Pratt (KMP) algorithm <span class=\"hint-tooltip\"> for searching substring in string in O(n) time<\/span> <span class=\"hint-tooltip\">Longest proper prefix\/suffix table is created using given string pattern to avoid comparison repetition.<\/span><\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">String Problems<\/h5>\n\n\n\n<ul>\n<li><a href=\"https:\/\/leetcode.com\/problems\/shortest-palindrome\/description\/\">Shortest Palindrome<\/a>. <span class=\"hint-tooltip\"><a href=\"https:\/\/leetcode.com\/problems\/shortest-palindrome\/submissions\/1093007598\">Solution<\/a> in O(n) using Manacher&#8217;s Algorithm.<\/span><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.com\/problems\/longest-palindromic-substring\/description\/\">Longest Palindromic Substring<\/a>. <span class=\"hint-tooltip\"><a href=\"https:\/\/leetcode.com\/problems\/longest-palindromic-substring\/submissions\/1085974386\">Solution<\/a> in O(n) using Manacher&#8217;s Algorithm.<\/span><\/li>\n\n\n\n<li><a href=\"https:\/\/leetcode.com\/problems\/repeated-substring-pattern\/description\/\">Repeated Substring Pattern<\/a>. <span class=\"hint-tooltip\">One liner <a href=\"https:\/\/leetcode.com\/problems\/repeated-substring-pattern\/solutions\/94334\/easy-python-solution-with-explaination\/\">solution<\/a> in O(n). Another <a href=\"https:\/\/leetcode.com\/problems\/repeated-substring-pattern\/submissions\/1093021396\">solution<\/a> in O(n) using KMP Algorithm.<\/span><\/li>\n<\/ul>\n<\/div>\n\n\n\n<h4 class=\"wp-block-heading\">Heap<\/h4>\n\n\n\n<p>A <mark>complete binary tree<\/mark> data strcuture, where value of <mark>parent node &gt;= children node<\/mark>. The comparison of values can be based on any kind of comparator.<\/p>\n\n\n\n<ul>\n<li><strong>Max heap<\/strong>: Value of parent node &gt;= value of children node<\/li>\n\n\n\n<li><strong>Min heap<\/strong>: Value of parent node &lt;= value of children node<\/li>\n\n\n\n<li>Since it&#8217;s a <span style=\"text-decoration: underline;\">complete<\/span> binary tree, heap can be easily implemented on simple arrays, because <span style=\"text-decoration: underline;\">zero based<\/span> index of left and right children of any node having index \\( i \\) can be calculated as \\( 2i+1 \\) and \\( 2i+2 \\)<\/li>\n\n\n\n<li><mark>heapify()<\/mark> is the main function used in heaps, this is usually a recursive function<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Stack<\/h4>\n\n\n\n<ul>\n<li>Supports push, pop, peek operations<\/li>\n\n\n\n<li>Java has <code>LinkedList&lt;Object&gt;<\/code> class to perform stack operation. <code>push<\/code>, <code>pop<\/code>, and <code>peek <\/code>methods can be used to perform stack operations<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<h5 class=\"wp-block-heading\">Monotonic Stack<\/h5>\n\n\n\n<ul>\n<li>The stack stores element in sorted order (increasing\/decreasing).<\/li>\n<\/ul>\n\n\n\n<ul>\n<li>If any element to be pushed breaks the sorted order of stack, the stack is continuously popped until the element to be pushed no longer breaks the sorted order of the stack.<\/li>\n\n\n\n<li><mark>Use cases<\/mark>:\n<ul>\n<li>To determine the next\/previouis smaller\/larger element for each element in array. This can be achieved in O(n) operations using monotonic stack.<\/li>\n\n\n\n<li>To determine the Minimum\/Maximum of next\/previous N elements for each element of array<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p class=\"accordion-button tertiary collapsed accordion-title\">(code) Determine minimum of previous K elements for each element of array<\/p><div class=\"accordion-panel collapsed\">\n<!-- HTML generated using hilite.me --><div style=\"background: #ffffff; overflow:auto;width:auto;background: #f0f3f3; overflow:auto;width:auto;border:none;font-size:small;\"><table><tr><td><pre style=\"margin: 0; line-height: 125%\"> 1\n 2\n 3\n 4\n 5\n 6\n 7\n 8\n 9\n10\n11\n12\n13\n14<\/pre><\/td><td><pre style=\"margin: 0; line-height: 125%\">    <span style=\"color: #008800; font-weight: bold\">private<\/span> <span style=\"color: #008800; font-weight: bold\">static<\/span> <span style=\"color: #333399; font-weight: bold\">int<\/span><span style=\"color: #333333\">[]<\/span> <span style=\"color: #0066BB; font-weight: bold\">minimumInPreviousK<\/span><span style=\"color: #333333\">(<\/span><span style=\"color: #333399; font-weight: bold\">int<\/span><span style=\"color: #333333\">[]<\/span> arr<span style=\"color: #333333\">,<\/span> <span style=\"color: #333399; font-weight: bold\">int<\/span> k<span style=\"color: #333333\">)<\/span> <span style=\"color: #333333\">{<\/span>\n        <span style=\"color: #333399; font-weight: bold\">int<\/span> result<span style=\"color: #333333\">[]<\/span> <span style=\"color: #333333\">=<\/span> <span style=\"color: #008800; font-weight: bold\">new<\/span> <span style=\"color: #333399; font-weight: bold\">int<\/span><span style=\"color: #333333\">[<\/span>arr<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">length<\/span><span style=\"color: #333333\">];<\/span>\n        LinkedList<span style=\"color: #333333\">&lt;<\/span><span style=\"color: #333399; font-weight: bold\">int<\/span><span style=\"color: #333333\">[]&gt;<\/span> ms <span style=\"color: #333333\">=<\/span> <span style=\"color: #008800; font-weight: bold\">new<\/span> LinkedList<span style=\"color: #333333\">&lt;&gt;();<\/span>\n        <span style=\"color: #008800; font-weight: bold\">for<\/span> <span style=\"color: #333333\">(<\/span><span style=\"color: #333399; font-weight: bold\">int<\/span> i <span style=\"color: #333333\">=<\/span> <span style=\"color: #0000DD; font-weight: bold\">0<\/span><span style=\"color: #333333\">;<\/span> i <span style=\"color: #333333\">&lt;<\/span> arr<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">length<\/span><span style=\"color: #333333\">;<\/span> i<span style=\"color: #333333\">++)<\/span> <span style=\"color: #333333\">{<\/span>\n            <span style=\"color: #008800; font-weight: bold\">while<\/span> <span style=\"color: #333333\">(!<\/span>ms<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">isEmpty<\/span><span style=\"color: #333333\">()<\/span> <span style=\"color: #333333\">&amp;&amp;<\/span> ms<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">peekFirst<\/span><span style=\"color: #333333\">()[<\/span><span style=\"color: #0000DD; font-weight: bold\">1<\/span><span style=\"color: #333333\">]<\/span> <span style=\"color: #333333\">&lt;<\/span> i <span style=\"color: #333333\">-<\/span> k<span style=\"color: #333333\">)<\/span>\n                ms<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">removeFirst<\/span><span style=\"color: #333333\">();<\/span>\n            <span style=\"color: #008800; font-weight: bold\">while<\/span> <span style=\"color: #333333\">(!<\/span>ms<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">isEmpty<\/span><span style=\"color: #333333\">()<\/span> <span style=\"color: #333333\">&amp;&amp;<\/span> ms<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">peekLast<\/span><span style=\"color: #333333\">()[<\/span><span style=\"color: #0000DD; font-weight: bold\">0<\/span><span style=\"color: #333333\">]<\/span> <span style=\"color: #333333\">&gt;=<\/span> arr<span style=\"color: #333333\">[<\/span>i<span style=\"color: #333333\">])<\/span>\n                ms<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">removeLast<\/span><span style=\"color: #333333\">();<\/span>\n            ms<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">addLast<\/span><span style=\"color: #333333\">(<\/span><span style=\"color: #008800; font-weight: bold\">new<\/span> <span style=\"color: #333399; font-weight: bold\">int<\/span><span style=\"color: #333333\">[]{<\/span>arr<span style=\"color: #333333\">[<\/span>i<span style=\"color: #333333\">],<\/span> i<span style=\"color: #333333\">});<\/span>\n            result<span style=\"color: #333333\">[<\/span>i<span style=\"color: #333333\">]<\/span> <span style=\"color: #333333\">=<\/span> ms<span style=\"color: #333333\">.<\/span><span style=\"color: #0000CC\">peekFirst<\/span><span style=\"color: #333333\">()[<\/span><span style=\"color: #0000DD; font-weight: bold\">0<\/span><span style=\"color: #333333\">];<\/span>\n        <span style=\"color: #333333\">}<\/span>\n        <span style=\"color: #888888\">\/\/result[] is an array where result[i] = min(result[i], result[i - 1], result[i - 2] ... result[i - k])<\/span>\n        <span style=\"color: #008800; font-weight: bold\">return<\/span> result<span style=\"color: #333333\">;<\/span>\n    <span style=\"color: #333333\">}<\/span>\n<\/pre><\/td><\/tr><\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<p><\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Priority Queue<\/h4>\n\n\n\n<ul>\n<li>supports Queue\/Deque (or Offer\/Poll). Both have time complexity \\( O\\left(\\log n\\right) \\).<\/li>\n\n\n\n<li>Maintains elements in sorted form at all time, whenever deque is performed, the first element of sorted list is returned.<\/li>\n\n\n\n<li><mark>Access of sorted elements using index is not supported<\/mark>. For eg. accessing K<sub>th<\/sub> smallest\/largest element in the Priority Queue is not possible without deque-ing the first K-1 smallest\/largest elements from queue.<\/li>\n\n\n\n<li>Usually <mark>Implemented using Heaps<\/mark>.<\/li>\n\n\n\n<li>Java has <code>PriorityQueue&lt;T&gt;<\/code> implemented in <code>java.util<\/code> package.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<h5 class=\"wp-block-heading\">Indexed Priority Queue (IPQ)<\/h5>\n\n\n\n<ul>\n<li>Access of sorted elements <mark>using index is possible<\/mark>.<\/li>\n\n\n\n<li>During implementation of IPQ, Indexes of elements inside IPQ are tracked manually, whenever any element is queued or dequeued, the indexes are updated.<\/li>\n\n\n\n<li>Java doesn&#8217;t have built-in IPQ data structure. It has to be implemented manually (can be done using heap).<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">Removing objects from Prioryt Queue in O(logn) time<\/h5>\n\n\n\n<ul>\n<li>The <code>remove(object)<\/code> method removes the matching object from Priority queue, This typically executes in O(n) time<\/li>\n\n\n\n<li>Changing the value of objects stored in priority queue with the help of some reference variable does NOT automatically re-arranges the priority queue.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p class=\"accordion-button tertiary collapsed accordion-title\">Example of changing object value in Priority Queue<\/p><div class=\"accordion-panel collapsed\">\n<pre class=\"hljs\" style=\"font-size:small;display: block; background: rgb(255, 255, 255); padding: 0.5em; color: rgb(51, 51, 51); overflow-x: auto;\"><span class=\"hljs-class\"><span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">class<\/span> <span class=\"hljs-title\" style=\"color: rgb(121, 93, 163);\">MyObj<\/span> <\/span>{\n    <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">public<\/span> <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val;\n    MyObj (<span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val) {\n        <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">this<\/span>.val = val;\n    }\n}\n\nMyObj obj1 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">4<\/span>);\nMyObj obj2 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">2<\/span>);\n\nPriorityQueue&lt;MyObj&gt; pq = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> PriorityQueue&lt;&gt;((x, y) -&gt; Integer.compare(x.val, y.val));\n\npq.offer(obj1);\npq.offer(obj2);\n\nSystem.out.println(pq.peek().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 2, as 2 is the smallest element<\/span>\n\nobj2.val = <span class=\"hljs-number\">6<\/span>; <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/value of object is modified with the help of reference variable, the priority queue will not be re-sorted<\/span>\n\nSystem.out.println(pq.peek().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 6, however 6 is not the smallest element<\/span><\/pre>\n<\/div>\n<\/div>\n\n\n\n<ul>\n<li>To maintain the sorted order of objects in Priority queue while updating the value, we must first remove the older object value from PQ, then add the new updated value.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p class=\"accordion-button tertiary collapsed accordion-title\">Example code of calling remove() before adding the updated value in Priority Queue<\/p><div class=\"accordion-panel collapsed\">\n<pre class=\"hljs\" style=\"font-size:small;display: block; background: rgb(255, 255, 255); padding: 0.5em; color: rgb(51, 51, 51); overflow-x: auto;\"><span class=\"hljs-class\"><span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">class<\/span> <span class=\"hljs-title\" style=\"color: rgb(121, 93, 163);\">MyObj<\/span> <\/span>{\n    <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">public<\/span> <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val;\n    MyObj (<span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val) {\n        <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">this<\/span>.val = val;\n    }\n}\n\nMyObj obj1 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">4<\/span>);\nMyObj obj2 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">2<\/span>);\n\nPriorityQueue&lt;MyObj&gt; pq = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> PriorityQueue&lt;&gt;((x, y) -&gt; Integer.compare(x.val, y.val));\n\npq.offer(obj1);\npq.offer(obj2);\n\nSystem.out.println(pq.peek().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 2, as 2 is the smallest element<\/span>\n\npq.remove(obj2); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/remove old value (takes O(n))<\/span>\nobj2.val = <span class=\"hljs-number\">6<\/span>;   <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ update<\/span>\npq.offer(obj2); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ add again<\/span>\n\nSystem.out.println(pq.peek().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 4 now, which is also the smallest elementt<\/span><\/pre>\n<\/div>\n<\/div>\n\n\n\n<ul>\n<li>There are multiple workarounds to avoid performing remove operation and spending O(n) time:<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p><strong>Method 1:<\/strong> Add a boolean property named &#8220;obsolete&#8221; to each of the object. If an object has to be removed, instead of calling remove() method, just set the obsolete property to true. This way, whenever poll() or peek() is performed on priority queue, if the found object is set as obsolete, we poll that object from priority queue.<\/p>\n\n\n\n<p class=\"accordion-button tertiary collapsed accordion-title\">Example<\/p><div class=\"accordion-panel collapsed\">\n<pre class=\"hljs\" style=\"font-size:small;display: block; background: rgb(255, 255, 255); padding: 0.5em; color: rgb(51, 51, 51); overflow-x: auto;\"><span class=\"hljs-class\"><span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">class<\/span> <span class=\"hljs-title\" style=\"color: rgb(121, 93, 163);\">MyObj<\/span> <\/span>{\n    <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">public<\/span> <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">boolean<\/span> obsolete = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">false<\/span>; <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ by default, the object is not obsolete<\/span>\n    <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">public<\/span> <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val;\n    MyObj (<span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val) {\n        <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">this<\/span>.val = val;\n    }\n}\n\nMyObj obj1 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">4<\/span>);\nMyObj obj2 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">2<\/span>);\n\nPriorityQueue&lt;MyObj&gt; pq = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> PriorityQueue&lt;&gt;((x, y) -&gt; Integer.compare(x.val, y.val));\n\npq.offer(obj1);\npq.offer(obj2);\n\nSystem.out.println(pq.peek().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 2, as 2 is the smallest element<\/span>\n\nobj2.obsolete = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">true<\/span>;       <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/mark the old object instance as obsolete<\/span>\nobj2 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">6<\/span>);    <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/create new object instance with updated value<\/span>\npq.offer(obj2);             <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/add the new object instance<\/span>\n\n<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/The following loop should always be used before performing the peek() operation on priority queue<\/span>\n<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/The following loop executes at most 'm' iterations in total, where m is the number of updates made to objects in priority queue<\/span>\n<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/therefore, this while loop executes only one iteration for each update<\/span>\n<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/that means, this while loop can be considered O(log(n)) for each update performed where O(log(n)) is time taken by method poll()<\/span>\n<span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">while<\/span> (!pq.isEmpty() &amp;&amp; pq.peek().obsolete) pq.poll();\n\nSystem.out.println(pq.peek().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 4 now, which is also the smallest element<\/span><\/pre>\n<\/div>\n\n\n\n<p><strong>Method 2:<\/strong> If adding a new property to the object\/class is not possible, then a Hash Set can be used to store the obsolete property of the object<\/p>\n\n\n\n<p class=\"accordion-button tertiary collapsed accordion-title\">Example<\/p><div class=\"accordion-panel collapsed\">\n<pre class=\"hljs\" style=\"font-size:small;display: block; background: rgb(255, 255, 255); padding: 0.5em; color: rgb(51, 51, 51); overflow-x: auto;\"><span class=\"hljs-class\"><span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">class<\/span> <span class=\"hljs-title\" style=\"color: rgb(121, 93, 163);\">MyObj<\/span> <\/span>{\n    <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">public<\/span> <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val;\n    MyObj (<span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val) {\n        <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">this<\/span>.val = val;\n    }\n}\n\nSet&lt;MyObj&gt; isObsolete = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> HashSet&lt;&gt;();<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ use HashSet to store the obsolete property of object<\/span>\n\nMyObj obj1 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">4<\/span>);\nMyObj obj2 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">2<\/span>);\n\nPriorityQueue&lt;MyObj&gt; pq = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> PriorityQueue&lt;&gt;((x, y) -&gt; Integer.compare(x.val, y.val));\n\npq.offer(obj1);\npq.offer(obj2);\n\nSystem.out.println(pq.peek().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 2, as 2 is the smallest element<\/span>\n\nisObsolete.add(obj2);       <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/this suggests that old instance of obj2 is not obsolete<\/span>\nobj2 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">6<\/span>);    <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/create new object instance with updated value<\/span>\npq.offer(obj2);             <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/add the new object instance<\/span>\n\n<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/The following loop should always be executed before performing the peek() operation on priority queue<\/span>\n<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/The following loop executes at most 'm' iterations in total, where m is the number of updates made to objects in priority queue<\/span>\n<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/therefore, this while loop executes only one iteration for each update<\/span>\n<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/that means, this while loop can be considered O(log(n)) for each update performed where O(log(n)) is time taken by method poll()<\/span>\n<span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">while<\/span> (!pq.isEmpty() &amp;&amp; isObsolete.remove(pq.peek())) pq.poll();\n<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/pay attention to the remove() method call made above, this frees the memory as long as it is no longer needed<\/span>\n    \nSystem.out.println(pq.peek().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 4 now, which is also the smallest element<\/span><\/pre>\n<\/div>\n\n\n\n<p>Using this workaround avoids the call to remove() method hence increasing the time efficiency. However downside of such workaround is that it takes more space to store an additional property for each object. And since now the priority queue can also contain the obsolete objects along with new updated objects, this also adds up to the space complexity.<\/p>\n\n\n\n<p><strong>Method 3<\/strong>: Use Ordered Set, which works similar to priority queue, however ordered set can&#8217;t have multiple objects with equal values. <\/p>\n\n\n\n<p class=\"accordion-button tertiary collapsed accordion-title\">Example<\/p><div class=\"accordion-panel collapsed\">\n<pre class=\"hljs\" style=\"font-size:small;display: block; background: rgb(255, 255, 255); padding: 0.5em; color: rgb(51, 51, 51); overflow-x: auto;\"><span class=\"hljs-class\"><span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">class<\/span> <span class=\"hljs-title\" style=\"color: rgb(121, 93, 163);\">MyObj<\/span> <\/span>{\n    <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">public<\/span> <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val;\n    MyObj (<span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">int<\/span> val) {\n        <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">this<\/span>.val = val;\n    }\n}\n\nMyObj obj1 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">4<\/span>);\nMyObj obj2 = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> MyObj(<span class=\"hljs-number\">2<\/span>);\n\nTreeSet&lt;MyObj&gt; ts = <span class=\"hljs-keyword\" style=\"color: rgb(167, 29, 93);\">new<\/span> TreeSet&lt;&gt;((x, y) -&gt; Integer.compare(x.val, y.val));\n\nts.add(obj1);\nts.add(obj2);\n\nSystem.out.println(ts.first().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 2, as 2 is the smallest element<\/span>\nobj2.val = <span class=\"hljs-number\">6<\/span>; <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/object 6 has been modified, however this doesn't re-sorts the tree set<\/span>\nSystem.out.println(ts.first().val); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ prints 6, the updated value of object, which is not the smallest element<\/span>\n\n\nobj2.val = <span class=\"hljs-number\">2<\/span>; <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/ restore the value, so that tree set can identify it again<\/span>\nts.remove(obj2); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/removes obj2 in O(logN) time<\/span>\nobj2.val = <span class=\"hljs-number\">6<\/span>; <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/modify the value<\/span>\nts.add(obj2); <span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/adds obj2 again to trigger re-sorting<\/span>\nSystem.out.println(ts.first().val);<span class=\"hljs-comment\" style=\"color: rgb(150, 152, 150);\">\/\/prints 4 now, which is now the smallest element<\/span><\/pre>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<h4 class=\"wp-block-heading\">Graph<\/h4>\n\n\n\n<ul>\n<li>Collection of nodes connected together with edges.\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n<ul>\n<li><mark>Directed Graph<\/mark>: Direction of edges matter.<\/li>\n\n\n\n<li><mark>Undirected or Bidirected Graph<\/mark>: Direction of edges doesn&#8217;t matter.<\/li>\n\n\n\n<li><span class=\"highlight-red2\">Cyclic Graph:<\/span> Graph that contains cycles (loops).<\/li>\n\n\n\n<li><span class=\"highlight-red2\">Acyclic Graph<\/span>: Graph doesn&#8217;t contain cycles.<\/li>\n\n\n\n<li><mark>Direct Acyclic Graph:<\/mark> A <span style=\"text-decoration: underline;\">directed graph<\/span> which does not contain cycles when traversing through edges respecting the direction of edges. The graph however may contain cycles when direction of edges is not considered.<\/li>\n\n\n\n<li><span class=\"highlight-red2\">Connected Graph<\/span>: All nodes are connected, there is only one group, every node is reachable from every other node in the graph.<\/li>\n\n\n\n<li><span class=\"highlight-red2\">Disconnected Graph<\/span>: All nodes are not connected, there can be multiple groups of nodes.<\/li>\n\n\n\n<li><strong>Weighted graph<\/strong>: Each edge is associated with some value\/cost.<\/li>\n\n\n\n<li><strong>Complete Graph<\/strong>: A graph in which each pair of vertices are connected with a single edge. (Every possible edge exists). A complete graph with \\( n \\) vertices has \\[ \\frac{n\\left(n-1\\right)}{2} \\] edges.<\/li>\n\n\n\n<li><strong>Diameter of Graph<\/strong>: The greatest minimum distance between any pair of vertices in a graph. In other words, two find diameter of graph -&gt; find shortest distance between each pair of vertices of graph -&gt; the maximum of those distances is the diameter of graph.<\/li>\n<\/ul>\n\n\n\n<ul>\n<li><strong>Bipartite Graph<\/strong>: A graph in which nodes can be divided into two groups such that every edge connecting the nodes are also divided into to parts. I.e, graph is bipartite if it&#8217;s possible to divide graph in two groups, such that for each edge in the graph, the two endpoints of the edge lie in different groups.\n<ul>\n<li><mark>All Acyclic graph are Bipartite graph<\/mark><\/li>\n\n\n\n<li>A cyclic graph is Bipartite if, each cycle of the graph has even length (even number of edges).<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Isomorphic Graphs<\/strong>: Two graphs are Isomorphic if both of them are <mark>structurally the same<\/mark>. Position of nodes doesn&#8217;t matter, as long as structure of two graphs are same.<\/li>\n\n\n\n<li><mark>In-degree of a node<\/mark>: The number of incoming edges attached to the node.<\/li>\n\n\n\n<li><mark>Out-degree of a node<\/mark>: The number of outgoing edges attached to the node.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<h5 class=\"wp-block-heading\">Graph Algorithms<\/h5>\n\n\n\n<ul>\n<li><strong><u class=\"underline\"><mark>Union Find algorithm<\/mark><\/u><\/strong>: Also called Disjoint Set Union (DSU) algorithm\n<ul>\n<li>Used to find groups in graph. Each group is represented by it&#8217;s <mark>representative node<\/mark>. <\/li>\n\n\n\n<li>Implementation contains two functions <code>union()<\/code> and <code>find()<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"alignright size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"500\" height=\"161\" src=\"https:\/\/spacican.com\/notes\/wp-content\/uploads\/2023\/08\/path429.png\" alt=\"Topological Sort\" class=\"wp-image-1329\" style=\"width:331px;height:107px\"\/><figcaption class=\"wp-element-caption\">Topological Sort<\/figcaption><\/figure><\/div>\n\n\n<ul start=\"2\">\n<li><strong>Topological Sorting<\/strong> of graph: Sorting the nodes of graph in a way such that, when nodes are placed linearly one after another, the direction of all edges are from left to right.\n<ul>\n<li>A single graph <mark>can be topologically sorted in multiple ways<\/mark>. (non-unique solution)<\/li>\n\n\n\n<li>Use case: Program build dependency, Course prerequisite completion<\/li>\n\n\n\n<li><strong><mark><u class=\"underline\">Topological Sort Algorithms<\/u><\/mark><\/strong>:<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p class=\"accordion-button tertiary collapsed accordion-title\">DFS for topological sort. O(n) time O(n) space<\/p><div class=\"accordion-panel collapsed\">\n<ul>\n<li>Create global <code>visited[node]<\/code> array<\/li>\n\n\n\n<li>Create global <code>result[]<\/code> array<\/li>\n\n\n\n<li>Perform DFS on each node\n<ul>\n<li>For <span style=\"text-decoration: underline;\">current node<\/span> in DFS, find all it&#8217;s outgoing nodes which are not in <code>visited[node]<\/code>. Perform DFS on those nodes.<\/li>\n\n\n\n<li>After performing DFS on all it&#8217;s outgoing nodes, Add current node to <code>result[]<\/code> array<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Reverse <code>result[]<\/code> array <\/li>\n\n\n\n<li><a href=\"https:\/\/youtu.be\/eL-KzMXSXXI?si=fLwfgFwHtw6FpYlq&amp;t=385\">Tutorial Link<\/a><\/li>\n<\/ul>\n<\/div>\n\n\n\n<p class=\"accordion-button tertiary collapsed accordion-title\">Kahn&#8217;s Algorithm for topological sort. O(n) time O(n) space<\/p><div class=\"accordion-panel collapsed\">\n<ul>\n<li>Create global <code>indegree[node]<\/code> hashmap and global result[] array.<\/li>\n\n\n\n<li>Queue all nodes with zero in-degree.<\/li>\n\n\n\n<li>While Queue is not empty:\n<ul>\n<li>Poll single node, push it to result array<\/li>\n\n\n\n<li>Update <code>indegree[outgoing nodes]<\/code>. (Subtract 1 from each outgoing node of currently polled node)<\/li>\n\n\n\n<li>If new in-degree of any outgoing node becomes zero, add this outgoing node to queue.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><code>result[]<\/code> array is topologically sorted<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n<ul start=\"3\">\n<li><strong>Single source shortest path (SSSP)<\/strong>: For any given node, find shortest path\/distance of all other nodes from given node.\n<ul>\n<li>Used with <span style=\"text-decoration: underline;\">weighted<\/span> direct acyclic graphs (DAG)<\/li>\n\n\n\n<li>TODO: SSSP algorithms: Dijkstra, bellman ford, floyd warshall<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Minimum Spanning Tree:<\/strong>\n<ul>\n<li>TODO: Krukshal algorithm, Prim&#8217;s algorithm<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">Graph Problems<\/h5>\n\n\n\n<ol>\n<li><mark>Check if graph is bipartite:<\/mark> Can be achived by checking if graph is acyclic. In case if graph is found to be cyclic, making sure that each cycle has even number of edges. This can be achived by DFS as well as BFS<\/li>\n\n\n\n<li><mark>Find Center or Diameter of acyclic undirected graph (Tree)<\/mark>: Center of undirected acyclic graph (Tree) is the center node which falls under the longest path in the Tree (undirected acyclic graph). The longest path is called diameter of the Tree.<\/li>\n<\/ol>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p class=\"accordion-button tertiary collapsed accordion-title\">Two approaches to find center of Tree<\/p><div class=\"accordion-panel collapsed\">\n<ol>\n<li>Queue all the leaf nodes\/vertices of the graph. Delete them one by one and keep adding newly formed leaf nodes to queue until a single node is left in the queue, which is the center of the Tree.<br>Time and space complexity: \\( O\\left(n\\right) \\)<\/li>\n\n\n\n<li>Use recursion to find two end nodes of the longest path. and then recursion again to find the middle path.<br>Time complexity: \\( O\\left(n\\right) \\), Space complexity: \\( O\\left(1\\right) \\)<br> <a href=\"https:\/\/www.geeksforgeeks.org\/find-the-node-at-the-centre-of-an-n-ary-tree\/\" data-type=\"link\" data-id=\"https:\/\/www.geeksforgeeks.org\/find-the-node-at-the-centre-of-an-n-ary-tree\/\">This solution<\/a> uses this technique to find center of tree, however, after finding two end nodes of the tree, the code uses an array to figure out the center of the longest parth. Using array can be avoided and center can be figured out without extra space (ignoring the space used for recursion).<\/li>\n<\/ol>\n<\/div>\n<\/div>\n\n\n\n<ul>\n<li>TODO: <mark>Check if two graphs are isomorphic.<\/mark><\/li>\n<\/ul>\n<\/div>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\"><\/div>\n\n\n\n<h4 class=\"wp-block-heading\">Tree<\/h4>\n\n\n\n<p>Trees are <mark>Acyclic connected Graph<\/mark> where any node of the graph can be represented as Root of the tree.<\/p>\n\n\n\n<p><strong>Rooted Tree<\/strong>: Directed acyclic connected graph, where direction of edges start from root of tree to the end\/leaf node of tree.<\/p>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<h5 class=\"wp-block-heading\">Rooted Tree Problems<\/h5>\n\n\n\n<ul>\n<li>Find diameter of rooted tree. O(n). (<a href=\"https:\/\/leetcode.com\/problems\/diameter-of-binary-tree\/\">Link<\/a>)<\/li>\n\n\n\n<li>TODO: Isomorphic trees<\/li>\n\n\n\n<li>TODO: encoding and decoding Trees<\/li>\n<\/ul>\n<\/div>\n\n\n\n<h4 class=\"wp-block-heading\">Segment Tree<\/h4>\n\n\n\n<ul>\n<li>Binary (usually) tree based data structure used to store information of ranges as well as perform operations on the ranges of the arrays. Any array can be broken into multiple segments\/ranges and information of these ranges can be stored in a binary tree where each node accounts for storing information of some range of the array in binary tree fashion.<\/li>\n\n\n\n<li>A simple and general implementation of segment tree is used for querying sum\/min\/max of range of array in O(logN) and do the point updates of values of array in O(logN) time.<\/li>\n\n\n\n<li>Segment tree works with ranges which are additive in nature, i.e. if \\( f\\left(a,b\\right) \\) is value of range \\( a \\) to \\( b\\), and \\( f\\left(c,d\\right) \\) is value of range \\( c \\) to \\( d \\), then \\( f\\left(a,d\\right)=f\\left(a,b\\right)+f\\left(c,d\\right) \\) should satisfy.<\/li>\n\n\n\n<li>Segment tree is better when frequent query as well as updates are performed. Otherwise prefix sum can be used just to get range sum in constant time.<\/li>\n\n\n\n<li>Segment tree are also used to calculate GCD\/LCM of range of arrays.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<h5 class=\"wp-block-heading\">Implementation of Segment Tree<\/h5>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p class=\"accordion-button tertiary collapsed accordion-title\">Node based implementation<\/p><div class=\"accordion-panel collapsed\">\n<p>Each node stores it&#8217;s own data (Low\/High range, value, etc). Following is the implementation:<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;border:none;font-size:small;\"><table><tr><td><pre style=\"margin: 0; line-height: 125%\"> 1\n 2\n 3\n 4\n 5\n 6\n 7\n 8\n 9\n10\n11\n12\n13\n14\n15\n16\n17\n18\n19\n20\n21\n22\n23\n24\n25\n26\n27\n28\n29\n30\n31\n32\n33\n34\n35\n36\n37\n38\n39\n40\n41\n42\n43\n44\n45\n46\n47\n48\n49\n50\n51\n52\n53\n54\n55\n56\n57\n58\n59\n60\n61\n62\n63\n64\n65\n66\n67\n68\n69<\/pre><\/td><td><pre style=\"margin: 0; line-height: 125%\"><span style=\"color: #0099FF; font-style: italic\">\/\/Range Sum Segment Tree<\/span>\n<span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">St<\/span> <span style=\"color: #555555\">{<\/span>\n    <span style=\"color: #006699; font-weight: bold\">private<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> low<span style=\"color: #555555\">,<\/span> high<span style=\"color: #555555\">,<\/span> val<span style=\"color: #555555\">;<\/span>\n    <span style=\"color: #006699; font-weight: bold\">private<\/span> St left<span style=\"color: #555555\">,<\/span> right<span style=\"color: #555555\">;<\/span>\n    \n    <span style=\"color: #0099FF; font-style: italic\">\/\/constructor 1 : build a dummy segment tree of fixed length\/range.<\/span>\n    <span style=\"color: #0099FF; font-style: italic\">\/\/the segment tree can be populated later by calling pointUpdate() for each index<\/span>\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #CC00FF\">St<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> low<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> high<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">low<\/span> <span style=\"color: #555555\">=<\/span> low<span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">high<\/span> <span style=\"color: #555555\">=<\/span> high<span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">=<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">;<\/span>\n        \n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>low <span style=\"color: #555555\">==<\/span> high<span style=\"color: #555555\">)<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        \n        <span style=\"color: #007788; font-weight: bold\">int<\/span> mid <span style=\"color: #555555\">=<\/span> low <span style=\"color: #555555\">+<\/span> <span style=\"color: #555555\">(<\/span>high <span style=\"color: #555555\">-<\/span> low<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">\/<\/span> <span style=\"color: #FF6600\">2<\/span><span style=\"color: #555555\">;<\/span>\n        \n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">left<\/span> <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">new<\/span> St<span style=\"color: #555555\">(<\/span>low<span style=\"color: #555555\">,<\/span> mid<span style=\"color: #555555\">);<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">right<\/span> <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">new<\/span> St<span style=\"color: #555555\">(<\/span>mid <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">,<\/span> high<span style=\"color: #555555\">);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #0099FF; font-style: italic\">\/\/constructor 2 : build and populate segment tree on the go, by passing array to constructor<\/span>\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #CC00FF\">St<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> arr<span style=\"color: #555555\">[],<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> low<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> high<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">low<\/span> <span style=\"color: #555555\">=<\/span> low<span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">high<\/span> <span style=\"color: #555555\">=<\/span> high<span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>low <span style=\"color: #555555\">==<\/span> high<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n            <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">=<\/span> arr<span style=\"color: #555555\">[<\/span>low<span style=\"color: #555555\">];<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #555555\">}<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> mid <span style=\"color: #555555\">=<\/span> low <span style=\"color: #555555\">+<\/span> <span style=\"color: #555555\">(<\/span>high <span style=\"color: #555555\">-<\/span> low<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">\/<\/span> <span style=\"color: #FF6600\">2<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">left<\/span> <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">new<\/span> St<span style=\"color: #555555\">(<\/span>arr<span style=\"color: #555555\">,<\/span> low<span style=\"color: #555555\">,<\/span> mid<span style=\"color: #555555\">);<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">right<\/span> <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">new<\/span> St<span style=\"color: #555555\">(<\/span>arr<span style=\"color: #555555\">,<\/span> mid <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">,<\/span> high<span style=\"color: #555555\">);<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">left<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">+<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">right<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span><span style=\"color: #555555\">;<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">pointUpdate<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> idx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> val<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span><span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">low<\/span> <span style=\"color: #555555\">&gt;<\/span> idx <span style=\"color: #555555\">||<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">high<\/span> <span style=\"color: #555555\">&lt;<\/span> idx<span style=\"color: #555555\">)<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span><span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">low<\/span> <span style=\"color: #555555\">==<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">high<\/span><span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n            <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">=<\/span> val<span style=\"color: #555555\">;<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #555555\">}<\/span>\n\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">left<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">pointUpdate<\/span><span style=\"color: #555555\">(<\/span>idx<span style=\"color: #555555\">,<\/span> val<span style=\"color: #555555\">);<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">right<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">pointUpdate<\/span><span style=\"color: #555555\">(<\/span>idx<span style=\"color: #555555\">,<\/span> val<span style=\"color: #555555\">);<\/span>\n\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">left<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">+<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">right<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span><span style=\"color: #555555\">;<\/span>\n    <span style=\"color: #555555\">}<\/span>\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">pointAdd<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> idx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> addVal<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span><span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">low<\/span> <span style=\"color: #555555\">&gt;<\/span> idx <span style=\"color: #555555\">||<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">high<\/span> <span style=\"color: #555555\">&lt;<\/span> idx<span style=\"color: #555555\">)<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span><span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">low<\/span> <span style=\"color: #555555\">==<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">high<\/span><span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n            <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">+=<\/span> addVal<span style=\"color: #555555\">;<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #555555\">}<\/span>\n        \n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">left<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">pointAdd<\/span><span style=\"color: #555555\">(<\/span>idx<span style=\"color: #555555\">,<\/span> addVal<span style=\"color: #555555\">);<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">right<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">pointAdd<\/span><span style=\"color: #555555\">(<\/span>idx<span style=\"color: #555555\">,<\/span> addVal<span style=\"color: #555555\">);<\/span>\n\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">left<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span> <span style=\"color: #555555\">+<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">right<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span><span style=\"color: #555555\">;<\/span>\n    <span style=\"color: #555555\">}<\/span>\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> <span style=\"color: #CC00FF\">rangeSum<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> queryLow<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> queryHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>queryLow <span style=\"color: #555555\">&gt;<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">high<\/span> <span style=\"color: #555555\">||<\/span> queryHigh <span style=\"color: #555555\">&lt;<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">low<\/span><span style=\"color: #555555\">)<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>queryLow <span style=\"color: #555555\">&lt;=<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">low<\/span> <span style=\"color: #555555\">&amp;&amp;<\/span> queryHigh <span style=\"color: #555555\">&gt;=<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">high<\/span><span style=\"color: #555555\">)<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">val<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">return<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">left<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">rangeSum<\/span><span style=\"color: #555555\">(<\/span>queryLow<span style=\"color: #555555\">,<\/span> queryHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">+<\/span> <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">right<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">rangeSum<\/span><span style=\"color: #555555\">(<\/span>queryLow<span style=\"color: #555555\">,<\/span> queryHigh<span style=\"color: #555555\">);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n<span style=\"color: #555555\">}<\/span>\n<\/pre><\/td><\/tr><\/table><\/div>\n<\/div>\n\n\n\n<p class=\"accordion-button tertiary collapsed accordion-title\">Array based implementation<\/p><div class=\"accordion-panel collapsed\">\n<p>Uses array to store the data, following is the implementation:<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;border:none;font-size:small;\"><table><tr><td><pre style=\"margin: 0; line-height: 125%\"> 1\n 2\n 3\n 4\n 5\n 6\n 7\n 8\n 9\n10\n11\n12\n13\n14\n15\n16\n17\n18\n19\n20\n21\n22\n23\n24\n25\n26\n27\n28\n29\n30\n31\n32\n33\n34\n35\n36\n37\n38\n39\n40\n41\n42\n43\n44\n45\n46\n47\n48\n49\n50\n51\n52\n53\n54\n55\n56\n57\n58\n59\n60\n61\n62\n63\n64\n65\n66\n67\n68\n69\n70\n71\n72\n73\n74\n75\n76\n77<\/pre><\/td><td><pre style=\"margin: 0; line-height: 125%\"><span style=\"color: #0099FF; font-style: italic\">\/\/Range Sum Segment Tree<\/span>\n<span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">St<\/span> <span style=\"color: #555555\">{<\/span>\n    <span style=\"color: #006699; font-weight: bold\">private<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> st<span style=\"color: #555555\">[],<\/span> length<span style=\"color: #555555\">;<\/span>\n    \n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #CC00FF\">St<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> arr<span style=\"color: #555555\">[])<\/span> <span style=\"color: #555555\">{<\/span>\n        length <span style=\"color: #555555\">=<\/span> arr<span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">length<\/span><span style=\"color: #555555\">;<\/span>\n        st <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">new<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span><span style=\"color: #555555\">[<\/span>length <span style=\"color: #555555\">*<\/span> <span style=\"color: #FF6600\">4<\/span><span style=\"color: #555555\">];<\/span> <span style=\"color: #0099FF; font-style: italic\">\/\/maximum length of segment tree can be 4 times of original array<\/span>\n        build<span style=\"color: #555555\">(<\/span>arr<span style=\"color: #555555\">,<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">,<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">,<\/span> arr<span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">length<\/span> <span style=\"color: #555555\">-<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">build<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> arr<span style=\"color: #555555\">[],<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> nodeIdx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> curLow<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> curHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>curLow <span style=\"color: #555555\">==<\/span> curHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n            st<span style=\"color: #555555\">[<\/span>nodeIdx<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">=<\/span> arr<span style=\"color: #555555\">[<\/span>curLow<span style=\"color: #555555\">];<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #555555\">}<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> mid <span style=\"color: #555555\">=<\/span> curLow <span style=\"color: #555555\">+<\/span> <span style=\"color: #555555\">(<\/span>curHigh <span style=\"color: #555555\">-<\/span> curLow<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">\/<\/span> <span style=\"color: #FF6600\">2<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> left <span style=\"color: #555555\">=<\/span> nodeIdx <span style=\"color: #555555\">*<\/span> <span style=\"color: #FF6600\">2<\/span> <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> right <span style=\"color: #555555\">=<\/span> left <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">;<\/span>\n        build<span style=\"color: #555555\">(<\/span>arr<span style=\"color: #555555\">,<\/span> left<span style=\"color: #555555\">,<\/span> curLow<span style=\"color: #555555\">,<\/span> mid<span style=\"color: #555555\">);<\/span>\n        build<span style=\"color: #555555\">(<\/span>arr<span style=\"color: #555555\">,<\/span> right<span style=\"color: #555555\">,<\/span> mid <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">,<\/span> curHigh<span style=\"color: #555555\">);<\/span>\n        st<span style=\"color: #555555\">[<\/span>nodeIdx<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">=<\/span> st<span style=\"color: #555555\">[<\/span>left<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">+<\/span> st<span style=\"color: #555555\">[<\/span>right<span style=\"color: #555555\">];<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">pointUpdate<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> idx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> val<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        pointUpdate<span style=\"color: #555555\">(<\/span>idx<span style=\"color: #555555\">,<\/span> val<span style=\"color: #555555\">,<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">,<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">,<\/span> length <span style=\"color: #555555\">-<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">pointUpdate<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> arrIdx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> val<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> nodeIdx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> curLow<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> curHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>curLow <span style=\"color: #555555\">&gt;<\/span> arrIdx <span style=\"color: #555555\">||<\/span> curHigh <span style=\"color: #555555\">&lt;<\/span> arrIdx<span style=\"color: #555555\">)<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>curLow <span style=\"color: #555555\">==<\/span> curHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n            st<span style=\"color: #555555\">[<\/span>nodeIdx<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">=<\/span> val<span style=\"color: #555555\">;<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #555555\">}<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> mid <span style=\"color: #555555\">=<\/span> curLow <span style=\"color: #555555\">+<\/span> <span style=\"color: #555555\">(<\/span>curHigh <span style=\"color: #555555\">-<\/span> curLow<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">\/<\/span> <span style=\"color: #FF6600\">2<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> left <span style=\"color: #555555\">=<\/span> nodeIdx <span style=\"color: #555555\">*<\/span> <span style=\"color: #FF6600\">2<\/span> <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> right <span style=\"color: #555555\">=<\/span> left <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">;<\/span>\n        pointUpdate<span style=\"color: #555555\">(<\/span>arrIdx<span style=\"color: #555555\">,<\/span> val<span style=\"color: #555555\">,<\/span> left<span style=\"color: #555555\">,<\/span> curLow<span style=\"color: #555555\">,<\/span> mid<span style=\"color: #555555\">);<\/span>\n        pointUpdate<span style=\"color: #555555\">(<\/span>arrIdx<span style=\"color: #555555\">,<\/span> val<span style=\"color: #555555\">,<\/span> right<span style=\"color: #555555\">,<\/span> mid <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">,<\/span> curHigh<span style=\"color: #555555\">);<\/span>\n        st<span style=\"color: #555555\">[<\/span>nodeIdx<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">=<\/span> st<span style=\"color: #555555\">[<\/span>left<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">+<\/span> st<span style=\"color: #555555\">[<\/span>right<span style=\"color: #555555\">];<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">pointAdd<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> idx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> addVal<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        pointAdd<span style=\"color: #555555\">(<\/span>idx<span style=\"color: #555555\">,<\/span> addVal<span style=\"color: #555555\">,<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">,<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">,<\/span> length <span style=\"color: #555555\">-<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">pointAdd<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> arrIdx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> addVal<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> nodeIdx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> curLow<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> curHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>curLow <span style=\"color: #555555\">&gt;<\/span> arrIdx <span style=\"color: #555555\">||<\/span> curHigh <span style=\"color: #555555\">&lt;<\/span> arrIdx<span style=\"color: #555555\">)<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>curLow <span style=\"color: #555555\">==<\/span> curHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n            st<span style=\"color: #555555\">[<\/span>nodeIdx<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">+=<\/span> addVal<span style=\"color: #555555\">;<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #555555\">}<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> mid <span style=\"color: #555555\">=<\/span> curLow <span style=\"color: #555555\">+<\/span> <span style=\"color: #555555\">(<\/span>curHigh <span style=\"color: #555555\">-<\/span> curLow<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">\/<\/span> <span style=\"color: #FF6600\">2<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> left <span style=\"color: #555555\">=<\/span> nodeIdx <span style=\"color: #555555\">*<\/span> <span style=\"color: #FF6600\">2<\/span> <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> right <span style=\"color: #555555\">=<\/span> left <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">;<\/span>\n        pointAdd<span style=\"color: #555555\">(<\/span>arrIdx<span style=\"color: #555555\">,<\/span> addVal<span style=\"color: #555555\">,<\/span> left<span style=\"color: #555555\">,<\/span> curLow<span style=\"color: #555555\">,<\/span> mid<span style=\"color: #555555\">);<\/span>\n        pointAdd<span style=\"color: #555555\">(<\/span>arrIdx<span style=\"color: #555555\">,<\/span> addVal<span style=\"color: #555555\">,<\/span> right<span style=\"color: #555555\">,<\/span> mid <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">,<\/span> curHigh<span style=\"color: #555555\">);<\/span>\n        st<span style=\"color: #555555\">[<\/span>nodeIdx<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">=<\/span> st<span style=\"color: #555555\">[<\/span>left<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">+<\/span> st<span style=\"color: #555555\">[<\/span>right<span style=\"color: #555555\">];<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> <span style=\"color: #CC00FF\">rangeSum<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> low<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> high<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">return<\/span> <span style=\"color: #CC00FF\">rangeSum<\/span><span style=\"color: #555555\">(<\/span>low<span style=\"color: #555555\">,<\/span> high<span style=\"color: #555555\">,<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">,<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">,<\/span> length <span style=\"color: #555555\">-<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> <span style=\"color: #CC00FF\">rangeSum<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> queryLow<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> queryHigh<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> nodeIdx<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> curLow<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> curHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>curLow <span style=\"color: #555555\">&gt;<\/span> queryHigh <span style=\"color: #555555\">||<\/span> curHigh <span style=\"color: #555555\">&lt;<\/span> queryLow<span style=\"color: #555555\">)<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>curLow <span style=\"color: #555555\">&gt;=<\/span> queryLow <span style=\"color: #555555\">&amp;&amp;<\/span> curHigh <span style=\"color: #555555\">&lt;=<\/span> queryHigh<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n            <span style=\"color: #006699; font-weight: bold\">return<\/span> st<span style=\"color: #555555\">[<\/span>nodeIdx<span style=\"color: #555555\">];<\/span>\n        <span style=\"color: #555555\">}<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> mid <span style=\"color: #555555\">=<\/span> curLow <span style=\"color: #555555\">+<\/span> <span style=\"color: #555555\">(<\/span>curHigh <span style=\"color: #555555\">-<\/span> curLow<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">\/<\/span> <span style=\"color: #FF6600\">2<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> left <span style=\"color: #555555\">=<\/span> nodeIdx <span style=\"color: #555555\">*<\/span> <span style=\"color: #FF6600\">2<\/span> <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> right <span style=\"color: #555555\">=<\/span> left <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">return<\/span>\n            <span style=\"color: #CC00FF\">rangeSum<\/span><span style=\"color: #555555\">(<\/span>queryLow<span style=\"color: #555555\">,<\/span> queryHigh<span style=\"color: #555555\">,<\/span> left<span style=\"color: #555555\">,<\/span> curLow<span style=\"color: #555555\">,<\/span> mid<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">+<\/span>\n            rangeSum<span style=\"color: #555555\">(<\/span>queryLow<span style=\"color: #555555\">,<\/span> queryHigh<span style=\"color: #555555\">,<\/span> right<span style=\"color: #555555\">,<\/span> mid <span style=\"color: #555555\">+<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">,<\/span> curHigh<span style=\"color: #555555\">);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n<span style=\"color: #555555\">}<\/span>\n<\/pre><\/td><\/tr><\/table><\/div>\n<\/div>\n<\/div>\n\n\n\n<h5 class=\"wp-block-heading\">Lazy Propagation in Segment Tree<\/h5>\n\n\n\n<p>Lazy propagation technique is used when we want to perform <strong>range updates<\/strong> on the the values of the array in O(LogN) operations. <\/p>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p class=\"accordion-button tertiary collapsed accordion-title\">TODO: Node based Implementation of Lazy Propagation<\/p><div class=\"accordion-panel collapsed\">\n<p>Todo<\/p>\n<\/div>\n\n\n\n<p class=\"accordion-button tertiary collapsed accordion-title\">Todo: Array based implementation of Lazy Propagation<\/p><div class=\"accordion-panel collapsed\">\n<p>Todo<\/p>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<h4 class=\"wp-block-heading\">Fenwick Tree (Binary Indexed Tree \/ BIT)<\/h4>\n\n\n\n<ul>\n<li>Fenwick Tree, also called Binary Indexed Tree (BIT) are used to store information of ranges of arrays as well as perform operations on those ranges of the arrays.<\/li>\n\n\n\n<li>Fenwick trees work with the ranges where value of range can be deduced by subtracting two values of bigger ranges. I.e. if \\( f\\left(a,b\\right) \\) is value of range \\( a \\) to \\( b\\), and \\( f\\left(a,c\\right) \\) is value of range \\( a \\) to \\( c \\) then, the value of range b to c can be calculated based on the formula \\( f\\left(b,c\\right)=f\\left(a,c\\right)-f\\left(a,b\\right) \\)<\/li>\n\n\n\n<li>Common use of Fenwick tree is range sum queries with point updates on the array. However Range minimum\/maximum query (RMQ) can&#8217;t be implemented since information stored in ranges for these kind of queries don&#8217;t have subtractive nature.<\/li>\n\n\n\n<li>General implementation of Fenwick tree works with 1 based indexes, however slight modification can be made to make it work with 0 based indexes.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p class=\"accordion-button tertiary collapsed accordion-title\">Implementation of Fenwick tree for Range Sum Queries with point updates<\/p><div class=\"accordion-panel collapsed\">\n<p>Following implementation works with 0 based index queries<\/p>\n\n\n\n<!-- HTML generated using hilite.me --><div style=\"background: #f0f3f3; overflow:auto;width:auto;border:none;font-size:small;\"><table><tr><td><pre style=\"margin: 0; line-height: 125%\"> 1\n 2\n 3\n 4\n 5\n 6\n 7\n 8\n 9\n10\n11\n12\n13\n14\n15\n16\n17\n18\n19\n20\n21\n22\n23\n24\n25\n26\n27\n28\n29\n30\n31\n32\n33\n34\n35\n36\n37\n38\n39\n40\n41\n42\n43\n44<\/pre><\/td><td><pre style=\"margin: 0; line-height: 125%\"><span style=\"color: #0099FF; font-style: italic\">\/\/ BIT with 0 based index implementation<\/span>\n<span style=\"color: #006699; font-weight: bold\">class<\/span> <span style=\"color: #00AA88; font-weight: bold\">BIT<\/span> <span style=\"color: #555555\">{<\/span>\n    <span style=\"color: #006699; font-weight: bold\">private<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> bit<span style=\"color: #555555\">[];<\/span> <span style=\"color: #0099FF; font-style: italic\">\/\/store prefix sum<\/span>\n    <span style=\"color: #006699; font-weight: bold\">private<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> arr<span style=\"color: #555555\">[];<\/span> <span style=\"color: #0099FF; font-style: italic\">\/\/store actual array<\/span>\n    \n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #CC00FF\">BIT<\/span> <span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> arr<span style=\"color: #555555\">[])<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">this<\/span><span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">arr<\/span> <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">new<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span><span style=\"color: #555555\">[<\/span>arr<span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">length<\/span><span style=\"color: #555555\">];<\/span>\n        bit <span style=\"color: #555555\">=<\/span> <span style=\"color: #006699; font-weight: bold\">new<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span><span style=\"color: #555555\">[<\/span>arr<span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">length<\/span><span style=\"color: #555555\">];<\/span>\n        <span style=\"color: #006699; font-weight: bold\">for<\/span> <span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> i <span style=\"color: #555555\">=<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">;<\/span> i <span style=\"color: #555555\">&lt;<\/span> arr<span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">length<\/span><span style=\"color: #555555\">;<\/span> i<span style=\"color: #555555\">++)<\/span>\n            pointUpdate<span style=\"color: #555555\">(<\/span>i<span style=\"color: #555555\">,<\/span> arr<span style=\"color: #555555\">[<\/span>i<span style=\"color: #555555\">]);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">pointUpdate<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> i<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> newVal<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        pointAdd<span style=\"color: #555555\">(<\/span>i<span style=\"color: #555555\">,<\/span> newVal <span style=\"color: #555555\">-<\/span> arr<span style=\"color: #555555\">[<\/span>i<span style=\"color: #555555\">]);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">void<\/span> <span style=\"color: #CC00FF\">pointAdd<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> i<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> addVal<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">if<\/span> <span style=\"color: #555555\">(<\/span>i <span style=\"color: #555555\">&lt;<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">)<\/span> <span style=\"color: #006699; font-weight: bold\">return<\/span><span style=\"color: #555555\">;<\/span>\n        arr<span style=\"color: #555555\">[<\/span>i<span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">+=<\/span> addVal<span style=\"color: #555555\">;<\/span>\n        i<span style=\"color: #555555\">++;<\/span> <span style=\"color: #0099FF; font-style: italic\">\/\/internally convert to 1 based index to perform required calculations<\/span>\n        <span style=\"color: #006699; font-weight: bold\">while<\/span> <span style=\"color: #555555\">(<\/span>i <span style=\"color: #555555\">&lt;=<\/span> bit<span style=\"color: #555555\">.<\/span><span style=\"color: #330099\">length<\/span><span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n            bit<span style=\"color: #555555\">[<\/span>i <span style=\"color: #555555\">-<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">]<\/span> <span style=\"color: #555555\">+=<\/span> addVal<span style=\"color: #555555\">;<\/span>\n            i <span style=\"color: #555555\">+=<\/span> lowestBit<span style=\"color: #555555\">(<\/span>i<span style=\"color: #555555\">);<\/span>\n        <span style=\"color: #555555\">}<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> <span style=\"color: #CC00FF\">preffixSum<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> i<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        i<span style=\"color: #555555\">++;<\/span> <span style=\"color: #0099FF; font-style: italic\">\/\/internally convert to 1 based index to perform required calculations<\/span>\n        <span style=\"color: #007788; font-weight: bold\">int<\/span> sum <span style=\"color: #555555\">=<\/span> <span style=\"color: #FF6600\">0<\/span><span style=\"color: #555555\">;<\/span>\n        <span style=\"color: #006699; font-weight: bold\">while<\/span> <span style=\"color: #555555\">(<\/span>i <span style=\"color: #555555\">&gt;=<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n            sum <span style=\"color: #555555\">+=<\/span> bit<span style=\"color: #555555\">[<\/span>i <span style=\"color: #555555\">-<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">];<\/span>\n            i <span style=\"color: #555555\">-=<\/span> lowestBit<span style=\"color: #555555\">(<\/span>i<span style=\"color: #555555\">);<\/span>\n        <span style=\"color: #555555\">}<\/span>\n        <span style=\"color: #006699; font-weight: bold\">return<\/span> sum<span style=\"color: #555555\">;<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">public<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> <span style=\"color: #CC00FF\">rangeSum<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> low<span style=\"color: #555555\">,<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> high<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">return<\/span> <span style=\"color: #CC00FF\">preffixSum<\/span><span style=\"color: #555555\">(<\/span>high<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">-<\/span> preffixSum<span style=\"color: #555555\">(<\/span>low <span style=\"color: #555555\">-<\/span> <span style=\"color: #FF6600\">1<\/span><span style=\"color: #555555\">);<\/span>\n    <span style=\"color: #555555\">}<\/span>\n\n    <span style=\"color: #006699; font-weight: bold\">private<\/span> <span style=\"color: #007788; font-weight: bold\">int<\/span> <span style=\"color: #CC00FF\">lowestBit<\/span><span style=\"color: #555555\">(<\/span><span style=\"color: #007788; font-weight: bold\">int<\/span> n<span style=\"color: #555555\">)<\/span> <span style=\"color: #555555\">{<\/span>\n        <span style=\"color: #006699; font-weight: bold\">return<\/span> n <span style=\"color: #555555\">&amp;<\/span> <span style=\"color: #555555\">-<\/span>n<span style=\"color: #555555\">;<\/span>\n    <span style=\"color: #555555\">}<\/span>\n<span style=\"color: #555555\">}<\/span>\n<\/pre><\/td><\/tr><\/table><\/div>\n<\/div>\n\n\n\n<p>A nice <a href=\"https:\/\/www.youtube.com\/watch?v=kPaJfAUwViY\">tutorial<\/a> video on Fenwick Trees.<\/p>\n<\/div>\n\n\n\n<h3 class=\"wp-block-heading\">Sorted Set (Tree Set)<\/h3>\n\n\n\n<div class=\"wp-block-create-block-indent indenter\">\n<p>Maintains key -&gt; value pair sorted by keys<\/p>\n\n\n\n<p>supports operations like firtKey(), lastKey(), ceilingKey(), floorKey(), update\/put\/get<\/p>\n\n\n\n<p>usually implemented using red-black tree (TODO)<\/p>\n<\/div>\n\n\n\n<h3 class=\"wp-block-heading\">Dynamic Programming with multiple state variables<\/h3>\n\n\n\n<p>Note: This is NOT multi-dimentional DP<\/p>\n\n\n\n<p>In Multi-state DP problems, the solution of a problem in <mark>one state<\/mark> is derived from the solution of subproblem in <mark>another state<\/mark>. For eg, to find the maximum profit made by <mark>selling<\/mark> a stock at day \\( d \\) by trading stock can be derived by knowing the maximum avialable balance present after <mark>buying<\/mark> the stock in previous days, here buying and selling are two states of the problem.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Multi-State DP Problem<\/td><td>Solution<\/td><\/tr><tr><td><a href=\"https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock-iii\/description\/\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock-iii\/description\/\">123. Best Time to Buy and Sell Stock III<\/a><\/td><td><a href=\"https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock-iii\/submissions\/1106024662\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock-iii\/submissions\/1106024662\">Using 2-state DP<\/a><br><a href=\"https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock-iii\/submissions\/1106031383\">By partitioning array in two halfs<\/a><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Boyer Moore&#8217;s Majority Voting Algorithm<\/h3>\n\n\n\n<p>Boyer Moore&#8217;s Majority Voting algorithm is used to find the majority element. A majority element is an element in array which repeats more than half the length of the array.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Problem<\/td><td>Solution<\/td><\/tr><tr><td><a href=\"https:\/\/leetcode.com\/problems\/majority-element\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/majority-element\">Majority Element<\/a><\/td><td><a href=\"https:\/\/leetcode.com\/problems\/majority-element\/submissions\/1115159441?envType=study-plan-v2&amp;envId=top-interview-150\">O(1) space, O(n) time<\/a><\/td><\/tr><tr><td><a href=\"https:\/\/leetcode.com\/problems\/majority-element-ii\/description\/\">Majority Element II<\/a><\/td><td><a href=\"https:\/\/leetcode.com\/problems\/majority-element-ii\/submissions\/1115208277\/\">O(1) space, O(n) time<\/a><\/td><\/tr><\/tbody><\/table><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>Classification of Data structure Types of Data Strcutures with Related Algorithms: Array DS String Heap A complete binary tree data strcuture, where value of parent node &gt;= children node. The comparison of values can be based on any kind of comparator. Stack Priority Queue Graph Tree Trees are Acyclic connected Graph where any node of [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":1291,"comment_status":"open","ping_status":"closed","sticky":false,"template":"single_compact.php","format":"standard","meta":{"footnotes":""},"categories":[2,6],"tags":[],"_links":{"self":[{"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/posts\/1150"}],"collection":[{"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/comments?post=1150"}],"version-history":[{"count":192,"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/posts\/1150\/revisions"}],"predecessor-version":[{"id":1482,"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/posts\/1150\/revisions\/1482"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/media\/1291"}],"wp:attachment":[{"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/media?parent=1150"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/categories?post=1150"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/spacican.com\/notes\/wp-json\/wp\/v2\/tags?post=1150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}