<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Vinay Vashist on Medium]]></title>
        <description><![CDATA[Stories by Vinay Vashist on Medium]]></description>
        <link>https://medium.com/@itsvinayyay?source=rss-5eb3bc4989d3------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*AXk1Y_RHlr2-gufAmas8EA.jpeg</url>
            <title>Stories by Vinay Vashist on Medium</title>
            <link>https://medium.com/@itsvinayyay?source=rss-5eb3bc4989d3------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 04:39:37 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@itsvinayyay/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Array Important Questions in C++]]></title>
            <link>https://medium.com/@itsvinayyay/array-important-questions-in-c-220c1c8bc03?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/220c1c8bc03</guid>
            <category><![CDATA[cplusplus]]></category>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[c-programming]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Thu, 02 Nov 2023 09:22:19 GMT</pubDate>
            <atom:updated>2023-11-02T09:22:19.298Z</atom:updated>
            <content:encoded><![CDATA[<p>The blog covers the important questions from the array data structure. The questions have been selected from the Love Babbar sheet. The prime objective of this article is to cover all tricky and hard Array Questions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*f2LT1qfGEYK70l5EupGtwQ.png" /></figure><p>The question statements have been taken from GFG for more information visit the <a href="https://practice.geeksforgeeks.org/">geekforgeeks</a> website.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*R9c2z-LamZyjyheVfHrIUA.png" /></figure><h3>Question 1. Kadane’s Algorithm</h3><p>Given an array <strong>Arr[] </strong>of <strong>N</strong> integers. Find the contiguous sub-array(containing at least one number) that has the maximum sum and return its sum.</p><p><strong>Example 1:</strong></p><pre>Input:<br>N = 5<br>Arr[] = {1,2,3,-2,5}<br>Output:<br>9<br>Explanation:<br>Max subarray sum is 9<br>of elements (1, 2, 3, -2, 5) which <br>is a contiguous subarray.</pre><p><strong>Example 2:</strong></p><pre>Input:<br>N = 4<br>Arr[] = {-1,-2,-3,-4}<br>Output:<br>-1<br>Explanation:<br>Max subarray sum is -1 <br>of element (-1)</pre><h3>Solution:</h3><p>The approach is simple and straight i.e. to neglect (or make it zero) when the current sum of a sub-array becomes negative.</p><pre>class Solution{<br>    public:<br>    // arr: input array<br>    // n: size of array<br>    //Function to find the sum of contiguous subarray with maximum sum.<br>    long long maxSubarraySum(int arr[], int n){<br>        long long max_sum = INT_MIN;<br>        long long sum = 0;<br>        <br>        for(int i=0; i&lt;n; i++){<br>            sum+=arr[i];<br>            if(sum &gt; max_sum){<br>                max_sum = sum;<br>            }<br>            if(sum&lt;0){<br>                sum = 0;<br>            }<br>        }<br><br>        return  max_sum;<br>        <br>    }<br>};</pre><h3>Question 2: Minimise the maximum difference between heights or Minimize the Heights II</h3><p>Given an array <strong>arr[]</strong> denoting heights of <strong>N</strong> towers and a positive integer <strong>K.</strong></p><p>For <strong>each </strong>tower, you must perform <strong>exactly one</strong> of the following operations <strong>exactly once</strong>.</p><ul><li><strong>Increase </strong>the height of the tower by <strong>K</strong></li><li><strong>Decrease </strong>the height of the tower by <strong>K</strong></li></ul><p>Find out the <strong>minimum </strong>possible difference between the height of the shortest and tallest towers after you have modified each tower.</p><p>You can find a slight modification of the problem <a href="https://practice.geeksforgeeks.org/problems/minimize-the-heights-i/1/">here</a>.<br><strong>Note:</strong> Increasing or decreasing the height by K for each tower is compulsory. <strong>After</strong> the operation, the resultant array should <strong>not</strong> contain any <strong>negative integers</strong>.</p><p><strong>Example 1:</strong></p><pre>Input:<br>K = 2, N = 4<br>Arr[] = {1, 5, 8, 10}<br>Output:<br>5<br>Explanation:<br>The array can be modified as <br>{1+k, 5-k, 8-k, 10-k} = {3, 3, 6, 8}. <br>The difference between <br>the largest and the smallest is 8-3 = 5.</pre><p><strong>Example 2:</strong></p><pre>Input:<br>K = 3, N = 5<br>Arr[] = {3, 9, 12, 16, 20}<br>Output:<br>11<br>Explanation:<br>The array can be modified as<br>{3+k, 9+k, 12-k, 16-k, 20-k} -&gt; {6, 12, 9, 13, 17}. <br>The difference between <br>the largest and the smallest is 17-6 = 11.</pre><h3>Solution:</h3><h4>Simple Approach</h4><p>Subtracting k from the largest element, adding k to the smallest element, and subtraction of these two new smaller and larger elements can lead to a probable minimum difference.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jiDEEN-gCC3E0R1ZfVrNMA.png" /></figure><p>Therefore, maximizing the current element and minimizing the element after, and then checking their difference can cover all the possible solutions to the problem.</p><p><strong>Code=&gt;</strong></p><pre>class Solution<br>{<br>public:<br>  int getMinDiff(int arr[], int n, int k)<br>  {<br>    sort(arr, arr + n);<br><br>    int first_ele = arr[0] + k;<br>    int last_ele = arr[n-1] -k;<br>    int diff = arr[n-1] - arr[0];<br><br>    for(int i=0; i&lt;n; i++){<br>      int min_ele = min(first_ele, arr[i+1] - k);<br>      int max_ele = max(last_ele, arr[i] + k); <br>      if(min_ele &lt; 0){<br>        continue;<br>      }<br>      diff = min(diff, max_ele - min_ele);<br>    }<br><br>    return diff;<br>  }<br>};<br></pre><h4>Complex Approach</h4><p>Taking all possible elements along with their indices and proceeding with sliding window.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rUmM2Jtu5Oyi2hVuLcBRrQ.png" /></figure><pre>class Solution<br>{<br>public:<br>  int getMinDiff(int arr[], int n, int k)<br>  {<br>    vector&lt;pair&lt;int, int&gt;&gt; all_elements;<br><br>    for (int i = 0; i &lt; n; i++)<br>    {<br>      if ((arr[i] - k) &gt;= 0)<br>      {<br>        all_elements.push_back({arr[i] - k, i});<br>      }<br>      all_elements.push_back({arr[i] + k, i});<br>    }<br><br>    sort(all_elements.begin(), all_elements.end());<br><br>    int left = 0;<br>    int right = 0;<br>    int elements = 0;<br>    vector&lt;int&gt; visited(n, 0);<br><br>    while (elements &lt; n &amp;&amp; right &lt; all_elements.size())<br>    {<br>      if (visited[all_elements[right].second] == 0)<br>      {<br>        elements++;<br>      }<br>      visited[all_elements[right].second]++;<br>      right++;<br>    }<br><br>    int answer = all_elements[right - 1].first - all_elements[left].first;<br><br>    while (right &lt; all_elements.size())<br>    {<br>      if (visited[all_elements[left].second] == 1)<br>      {<br>        elements--;<br>      }<br>      visited[all_elements[left].second]--;<br>      left++;<br><br>      while (elements &lt; n &amp;&amp; right &lt; all_elements.size())<br>      {<br>        if (visited[all_elements[right].second] == 0)<br>        {<br>          elements++;<br>        }<br>        visited[all_elements[right].second]++;<br>        right++;<br>      }<br><br>      if(elements == n){<br>        answer = min(answer, all_elements[right-1].first - all_elements[left].first);<br>      }<br>      else{<br>        break;<br>      }<br>    }<br>    return answer;<br>  }<br>};</pre><h3>Question 3: Minimum number of jumps to reach the end of the array</h3><p>Given an array of <strong>N</strong> integers <strong>arr[], each</strong> element represents the <strong>maximum</strong> length of the jump that can be made forward from that element. This means if arr[i] = x, then we can jump any distance y such that y ≤ x.<br>Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is <strong>0</strong>, you cannot move through that element.</p><p><strong>Note: </strong>Return -1 if you can’t reach the end of the array.</p><p><strong>Example 1:</strong></p><pre>Input:<br>N = 11 <br>arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} <br>Output: 3 <br>Explanation: <br>First jump from 1st element to 2nd <br>element with value 3. Now, from here <br>we jump to 5th element with value 9, <br>and from here we will jump to the last.</pre><p><strong>Example 2:</strong></p><pre>Input :<br>N = 6<br>arr = {1, 4, 3, 2, 6, 7}<br>Output: 2 <br>Explanation: <br>First we jump from the 1st to 2nd element <br>and then jump to the last element.</pre><h3>Solution:</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gwlpYfJUgDXBK7eJAkBh0Q.png" /></figure><pre>class Solution{<br>  public:<br>    int minJumps(int arr[], int n){<br>        <br>        if(arr[0] == 0){<br>            return -1;<br>        }<br>        int jumps = 1;<br>        int steps = arr[0];<br>        int maxR = arr[0];<br><br>        for(int i=1; i&lt;n; i++){<br>          if(i==n-1){<br>            return jumps;<br>          }<br>          maxR = max(maxR, arr[i] + i);<br>          steps--;<br>          if(steps == 0){<br>            jumps++;<br>            if(i &gt;= maxR){<br>              return -1;<br>            }<br>            steps = maxR - i;<br>          }<br>        }<br>        return jumps;<br>    }<br>};</pre><h3>Question 4. Merge two Sorted Arrays without using extra space.</h3><p>Given two sorted arrays <strong>arr1[]</strong> and <strong>arr2[] </strong>of<strong> </strong>sizes <strong>n</strong> and <strong>m</strong> in non-decreasing order. Merge them in sorted order without using any extra space. Modify arr1 to contain the first N elements and modify arr2 to contain the last M elements.</p><p><strong>Example 1:</strong></p><pre>Input: <br>n = 4, arr1[] = [1 3 5 7] <br>m = 5, arr2[] = [0 2 6 8 9]<br>Output: <br>arr1[] = [0 1 2 3]<br>arr2[] = [5 6 7 8 9]<br>Explanation:<br>After merging the two <br>non-decreasing arrays, we get, <br>0 1 2 3 5 6 7 8 9.</pre><p><strong>Example 2:</strong></p><pre>Input: <br>n = 2, arr1[] = [10 12] <br>m = 3, arr2[] = [5 18 20]<br>Output: <br>arr1[] = [5 10]<br>arr2[] = [12 18 20]<br>Explanation:<br>After merging two sorted arrays <br>we get 5 10 12 18 20.</pre><h3>Solution.</h3><h4>Brute Force Approach</h4><p>The brute force approach can be thought of by just creating another array and simply filling it in sorted order from the two given arrays (like in Merge Sort) and the last step is to fill both the given arrays from this new array.</p><p>But the primary purpose of this problem (to not use extra space) will not be fulfilled.</p><pre>class Solution<br>{<br>public:<br>    // Function to merge the arrays.<br>    void merge(long long arr1[], long long arr2[], int n, int m)<br>    {<br>        int l = n+m;<br>        long long main_arr[l];<br>        int left = 0, right = 0, index = 0;<br>        while(left &lt; n &amp;&amp; right &lt; m){<br>            if(arr1[left] &lt;= arr2[right]){<br>                main_arr[index] = arr1[left];<br>                index++;<br>                left++;<br>            } else{<br>                main_arr[index] = arr2[right];<br>                index++;<br>                right++;<br>            }<br>        }<br>        while(left &lt; n){<br>            main_arr[index] = arr1[left];<br>            left++;<br>            index++;<br>        }<br><br>        while(right &lt; m){<br>            main_arr[index] = arr2[right];<br>            right++;<br>            index++;<br>        }<br><br><br>        for(int i=0; i&lt;l; i++){<br>            if(i &lt; n){<br>                arr1[i] = main_arr[i];<br>            }<br>            else<br>                arr2[i-n] = main_arr[i];<br>        }<br><br>    }<br>};</pre><h4>Optimal Solution</h4><p>The optimal solution is based on a pointer approach where one pointer will be pointing at the last of the first array and the second one will be at the start of the second array. Comparisons will be made and elements will be swapped if elements at the left pointer are bigger than the elements of the right pointer.</p><pre>class Solution{<br>    void Swap(long long &amp;x, long long &amp;y)<br>    {<br>        long long temp = x;<br>        x = y;<br>        y = temp;<br>    }<br><br>public:<br>    // Function to merge the arrays.<br>    void merge(long long arr1[], long long arr2[], int n, int m)<br>    {<br>        int pointer1 = n - 1;<br>        int pointer2 = 0;<br><br>        while (pointer1 &gt;= 0 &amp;&amp; pointer2 &lt; m)<br>        {<br>            if (arr1[pointer1] &gt; arr2[pointer2])<br>            {<br>                Swap(arr1[pointer1], arr2[pointer2]);<br>            }<br>            pointer1--;<br>            pointer2++;<br><br>        }<br><br>        sort(arr1, arr1 + n);<br>        sort(arr2, arr2 + m);<br>    }<br>};</pre><h3>Question 5. Next Permutation</h3><p>Implement the next permutation, which rearranges the list of numbers into Lexicographically next greater permutation of the list of numbers. If such an arrangement is not possible, it must be rearranged to the lowest possible order <em>i.e.</em> sorted in an ascending order. You are given an list of numbers <strong>arr[ ]</strong> of size <strong>N</strong>.</p><p><strong>Example 1:</strong></p><pre>Input: N = 6<br>arr = {1, 2, 3, 6, 5, 4}<br>Output: {1, 2, 4, 3, 5, 6}<br>Explaination: The next permutation of the <br>given array is {1, 2, 4, 3, 5, 6}.</pre><p><strong>Example 2:</strong></p><pre>Input: N = 3<br>arr = {3, 2, 1}<br>Output: {1, 2, 3}<br>Explaination: As arr[] is the last <br>permutation. So, the next permutation <br>is the lowest one.</pre><h3>Solution.</h3><p>The problem can be approached in three steps:</p><ol><li>Founding the break-point.</li><li>Swapping the breakpoint with the element just greater (not equal) than it.</li><li>Reversing (O(n)) or Sorting (O(nlogn)) the array after the swapped breakpoint location.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C1Iepus9C2aLS71bDt6ruA.png" /></figure><p>Code=&gt;</p><pre>class Solution{<br>public:<br>    void reverse_array(vector&lt;int&gt; &amp;arr, int index, int N){<br>        int low = index + 1;<br>        int high = N-1;<br><br>        while(low&lt;=high){<br>            swap(arr[low], arr[high]);<br>            low++;<br>            high--;<br>        }<br>    }<br><br><br><br>public:<br>    vector&lt;int&gt; nextPermutation(int N, vector&lt;int&gt; arr){<br>        int index = -1;<br>        for(int i=N-2; i&gt;=0; i--){<br>            if(arr[i] &lt; arr[i+1]){<br>                index = i;<br>                break;<br>            }<br>        }<br><br>        if(index == -1){<br>            reverse(arr.begin(), arr.end());<br>            return arr;<br>        }<br><br>        for(int i = N-1; i&gt;=0; i--){<br>            if(arr[i] &gt; arr[index]){<br>                swap(arr[index], arr[i]);<br>                break;<br>            }<br>        }<br>        reverse_array(arr, index, N);<br><br>        return arr;<br><br>    }<br>};</pre><h3>Question 6. Factorial of a Large Number</h3><p>Given an integer N, find its factorial. return a list of integers denoting the digits that make up the factorial of N.</p><p><strong>Example 1:</strong></p><pre>Input: N = 5<br>Output: 120<br>Explanation : 5! = 1*2*3*4*5 = 120</pre><p><strong>Example 2:</strong></p><pre>Input: N = 10<br>Output: 3628800<br>Explanation :<br>10! = 1*2*3*4*5*6*7*8*9*10 = 3628800</pre><h3>Solution.</h3><p>Approach to the problem.</p><ol><li>Storing the answer in a vector digit by digit.</li><li>Outer for-loop to multiply with number.</li><li>Inner for-loop to traverse in our vector.</li></ol><pre>class Solution {<br>public:<br>    vector&lt;int&gt; factorial(int N){<br>        vector&lt;int&gt; answer;<br>        answer.push_back(1);<br><br>        for(int i=2; i&lt;=N; i++){<br>            int carry = 0;<br><br>            for(int j = 0; j&lt;answer.size(); j++){<br>                int val = answer[j] * i + carry;<br>                answer[j] = val%10;<br>                carry = val/10;<br>            }<br><br>            while(carry &gt; 0){<br>                answer.push_back(carry%10);<br>                carry/=10;<br>            }<br>        }<br>        <br>        reverse(answer.begin(), answer.end());<br><br>        return answer;<br>    }<br>};</pre><h3>Question 7. Buy and Sell a Share at most twice</h3><p>In daily share trading, a buyer buys shares in the morning and sells them on the same day. If the trader is allowed to make at most 2 transactions in a day, the second transaction can only start after the first one is complete (Buy-&gt;sell-&gt;Buy-&gt;sell). The stock prices throughout the day are represented in the form of an array of <strong>prices</strong>.</p><p>Given an array <strong>price</strong> of size <strong>N</strong>, find out the <strong>maximum</strong> profit that a share trader could have made.</p><p><strong>Example 1:</strong></p><pre>Input:<br>6<br>10 22 5 75 65 80<br>Output:<br>87<br>Explanation:<br>Trader earns 87 as sum of 12, 75 <br>Buy at 10, sell at 22, <br>Buy at 5 and sell at 80</pre><p><strong>Example 2:</strong></p><pre>Input:<br>7<br>2 30 15 10 8 25 80<br>Output:<br>100<br>Explanation:</pre><pre>Trader earns 100 as sum of 28 and 72<br>Buy at price 2, sell at 30,<br>Buy at 8 and sell at 80</pre><h3>Solution.</h3><h4>Dynamic Programming approach!</h4><p>1. Create a DP array and traverse the given array from the right and then from the left side.</p><p>2. Note down the maximum profit till the current position while traversing from the right side (from the given array) in the DP array.</p><p>3. While traversing from the left side note down the maximum profit (this time the price[i] will be the selling price) along with the previous profit stored in the DP array (inside the DP array).</p><pre>int maxProfit(vector&lt;int&gt;&amp;price){<br>    int maxR = price[price.size() - 1];<br>    int minL = price[0];<br>    int n = price.size();<br>    vector&lt;int&gt; dp(n);<br><br>    for(int i = n-2; i&gt;=0; i--){<br>        if(maxR &lt; price[i]){<br>            maxR = price[i];<br>        }<br>        dp[i] = max(dp[i+1], maxR - price[i]);<br>    }<br><br>    for(int i=1; i&lt;n; i++){<br>        if(minL &gt; price[i]){<br>            minL = price[i];<br>        }<br>        dp[i] = max(dp[i-1], dp[i] + (price[i] - minL));<br>    }<br><br><br>    return dp[n-1];<br>}</pre><h3>Question 8. Trapping Rainwater problem</h3><p>Given an array <strong>arr[]</strong> of <strong>N</strong> non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season.</p><p><strong>Example 1:</strong></p><pre>Input:<br>N = 6<br>arr[] = {3,0,0,2,0,4}<br>Output:<br>10<br>Explanation:</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/482/0*jDH2PxERr9VUf2Ew.png" /></figure><p><strong>Example 2:</strong></p><pre>Input:<br>N = 4<br>arr[] = {7,4,0,9}<br>Output:<br>10<br>Explanation:<br>Water trapped by above <br>block of height 4 is 3 units and above <br>block of height 0 is 7 units. So, the <br>total unit of water trapped is 10 units.</pre><p><strong>Example 3:</strong></p><pre>Input:<br>N = 3<br>arr[] = {6,9,9}<br>Output:<br>0<br>Explanation:<br>No water will be trapped.</pre><h3>Solution.</h3><h4>Better Solution</h4><ol><li>Construct two arrays namely rightArr and leftArr, which contain the largest element up to the current position from the right and left side of the array respectively.</li><li>Take the minimum value from both arrays and subtract the value of the given array for a current position.</li></ol><p>Code=&gt;</p><pre>class Solution{<br><br>    // Function to find the trapped water between the blocks.<br>    public:<br>    long long trappingWater(int arr[], int n){<br>        vector&lt;long long&gt; leftArr(n);<br>        vector&lt;long long&gt; rightArr(n);<br><br>        leftArr[0] = arr[0];<br>        rightArr[n-1] = arr[n-1];<br><br>        for(int i=1; i&lt;n; i++){<br>            if(arr[i] &gt; leftArr[i-1]){<br>                leftArr[i] = arr[i];<br>            } else{<br>                leftArr[i] = leftArr[i-1];<br>            }<br>        }<br><br><br>        for(int i=n-2; i&gt;=0; i--){<br>            if(arr[i] &gt; rightArr[i+1]){<br>                rightArr[i] = arr[i];<br>            } else{<br>                rightArr[i] = rightArr[i+1];<br>            }<br>        }<br>        long long ans = 0;<br><br>        for(int i=0; i&lt;n; i++){<br>            ans+=min(leftArr[i], rightArr[i]) - arr[i];<br>        }<br><br>        return ans;<br>    }<br>};</pre><h4>Optimal Solution</h4><ol><li>Create two pointers at the end and start of the given array.</li><li>Based on the conditions check if the left element is greater than the right element, also check if the left element is greater than maximumL, and for the right element check if it is greater than maximumR, and if not add the current element in the answer.</li><li>Traverse till left≤right.</li></ol><p>Code=&gt;</p><pre>class Solution{<br><br>    // Function to find the trapped water between the blocks.<br>    public:<br>    long long trappingWater(int arr[], int n){<br>        long long answer = 0;<br>        int maximumL = INT_MIN;<br>        int maximumR = INT_MIN;<br>        int left = 0;<br>        int right = n-1;<br><br>        while(left &lt;= right){<br>            if(arr[left] &lt; arr[right]){<br>                if(arr[left] &gt; maximumL){<br>                    maximumL = arr[left];<br>                }<br>                else{<br>                    answer+=maximumL - arr[left];<br>                }<br>                left++;<br>            }<br><br>            else{<br>                //arr[left] &gt; arr[right]<br>                if(arr[right] &gt; maximumR){<br>                    maximumR= arr[right];<br>                }<br>                else{<br>                    answer+=maximumR - arr[right];<br>                }<br>                right--;<br>            }<br>        }<br><br>        return answer;<br>    }<br>};</pre><h3>Question 9. Median of two sorted arrays of different sizes.</h3><h3>Solution.</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rxwYReRxkTjrHEnzRMOYSA.png" /></figure><ol><li>Find the partitions for both arrays by the condition L1≤R2 and L2≤R1.</li><li>Find L1, L2, R1, R2 using Partitions. If no valid partition, assign min to L1 or L2 and max to R1 or R2.</li><li>Find the median for odd and even arrays accordingly.</li></ol><pre>//User function Template for C++<br><br>class Solution{<br>    public:<br>    double MedianOfArrays(vector&lt;int&gt; &amp;array1, vector&lt;int&gt; &amp;array2)<br>    {<br>        if(array2.size() &lt; array1.size()){<br>            return MedianOfArrays(array2, array1);<br>        }<br>        int n1 = array1.size();<br>        int n2 = array2.size();<br>        int low = 0;<br>        int high = n1;<br><br>        while (low &lt;= high)<br>        {<br><br>            int cut1 = (low + high) / 2;<br>            int cut2 = (n1 + n2 + 1)/2 - cut1;<br>            int left1 = INT_MIN;<br>            int left2 = INT_MIN;<br>            int right1 = INT_MAX;<br>            int right2 = INT_MAX;<br><br>            if (cut1 != 0)<br>            {<br>                left1 = array1[cut1 - 1];<br>            }<br>            if (cut2 != 0)<br>            {<br>                left2 = array2[cut2 - 1];<br>            }<br>            if (cut1 != n1)<br>            {<br>                right1 = array1[cut1];<br>            }<br>            if (cut2 != n2)<br>            {<br>                right2 = array2[cut2];<br>            }<br><br>            if (left1 &lt;= right2 &amp;&amp; left2 &lt;= right1)<br>            {<br>                if ((n1 + n2) % 2 == 0)<br>                {<br>                    double median = (max(left1, left2) + min(right1, right2)) / 2.0;<br>                    return median;<br>                }<br>                else{<br>                    double median = max(left1, left2);<br>                    return median;<br>                }<br>            }<br>            else if(left1 &gt; right2){<br>                high = cut1-1;<br>            }<br>            else{<br>                //left2 &gt; right1 <br>                low = cut1 + 1;<br>            }<br>        }<br>        return 0.0;<br>    }<br>};</pre><p>That’s all!💯</p><p>These are the main and important questions selected from the <a href="https://practice.geeksforgeeks.org/explore?page=1&amp;sprint=94ade6723438d94ecf0c00c3937dad55&amp;sortBy=submissions&amp;sprint_name=Love%20Babbar%20Sheet">Love Babbar DSA Sheet</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=220c1c8bc03" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Graphs Data Structure in C++]]></title>
            <link>https://medium.com/@itsvinayyay/graphs-data-structure-in-c-ab7b4205f41a?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/ab7b4205f41a</guid>
            <category><![CDATA[graph-data-structure]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[breadth-first-search]]></category>
            <category><![CDATA[c-programming]]></category>
            <category><![CDATA[depth-first-search]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Mon, 07 Aug 2023 15:47:46 GMT</pubDate>
            <atom:updated>2023-08-07T15:47:46.656Z</atom:updated>
            <content:encoded><![CDATA[<p>One of the most visualizing concepts in C++ is Graphs. Starting from BFS, and DFS and ending all the way up to solving complex graph questions takes time. The article covers all concepts of Graphs.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Apr_gmx4qlcBWZIVwzMjcw.png" /></figure><h3>Graphs??</h3><p>A Graph is a data structure that is a combination of nodes and edges. Nodes/Vertex stores and entities while edges are connections between two nodes.</p><h4>Types of Graphs</h4><p><strong>a. Directed and Undirected Graphs:-</strong> When in a graph all edges point from one node to another node. The graph created is known as the Directed Graph. On the other hand, when there’s a simple line between two nodes as an edge the graph constructed is known as an Undirected graph.</p><p><strong>b. Weighted Graph:-</strong> A graph in which every edge has a weight (a value of the connection between two nodes connected by that edge).</p><p><strong>c. Cyclic and Acyclic Graphs:-</strong> In the case of Directed Graphs if there’s a possibility of creating a path such that while traveling you end up on an already traveled node, the graph is Cyclic. And the opposite goes for the Acyclic graph.</p><h4>Some Terms</h4><p><strong>a. Degree (in case of Undirected Graph): </strong>Degree means how many edges are connected to a node in case of Undirected graph.</p><p><strong>b. InDegree and OutDegree(Directed Graph):</strong> Indegree means how many incoming edges are on a node in the case of a Directed graph. On the other hand, Outdegree means how many outgoing edges are from a Directed Graph node.</p><h3>Visualization??</h3><p>A graph can be created/represented/visualized with the help of either a 2D matrix or an adjacency list.</p><h4>Representation via 2D Matrix</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G9XgjHTaR2aWh4SGWzV5bw.png" /></figure><h4>Representation via adjacency list</h4><p>Adjacency list can be created by <strong>using vector&lt;vector&lt;int&gt;&gt; or using unordered_map&lt;int, list&lt;int&gt;&gt;</strong>. The representation is shown in the figure below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*REuC93WOQw_K5o_ALp599w.png" /></figure><h3>Graph Traversals</h3><h4>Breadth First Search (BFS)</h4><p>Breadth First search is a search algorithm used in tree data structures to <strong>search a node with a specific property</strong>. The algorithm <strong>starts with a root node</strong> and <strong>as moving deeper it records the data of the nodes</strong>, unlike <strong>the DFS algorithm which travels to the deepest node</strong> and <strong>then records the data of the nodes.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ygtEATSZxDITD4-ttwSDYA.png" /></figure><p>Data Structures needed to carry out the BFS algorithm are:</p><ol><li><strong>Queue </strong>(To store the child or connected nodes which still need to be explored).</li><li><strong>Unordered Map </strong>or <strong>vector </strong>(To find that a particular node is visited or not).</li></ol><p><strong>Steps to achieve algorithm:</strong></p><ol><li>Mark the first received node in the function as visited.</li><li>Add this node to the queue</li><li>Take out the front node from the queue in a front variable.</li><li>Clear this node from the queue.</li><li>Push this node to the answer vector.</li><li>Add its neighbor to the queue.</li></ol><p>The code for BFS is as follows=&gt;</p><pre>class Solution {<br><br>    void BFS(vector&lt;int&gt; adj[], vector&lt;int&gt; &amp;answer, unordered_map&lt;int, bool&gt; &amp;visited, int node){<br>        queue&lt;int&gt; q;<br>        q.push(node);<br>        visited[node] = true;<br><br><br>        while(!q.empty()){<br>            int front = q.front();<br>            q.pop();<br><br>            for(auto neighbours : adj[front]){<br>                if(!visited[neighbours]){<br>                    visited[neighbours] = true;<br>                    q.push(neighbours);<br>                    answer.push_back(neighbours);<br>                }<br>            }<br>        }<br>    }<br>  public:<br>    // Function to return Breadth First Traversal of given graph.<br>    vector&lt;int&gt; bfsOfGraph(int V, vector&lt;int&gt; adj[]) {<br>        vector&lt;int&gt; answer;<br>        unordered_map&lt;int, bool&gt; visited;<br><br><br>        for(int i=0; i&lt;V; i++){<br>            if(!visited[i]){<br>                BFS(adj, answer, visited, i);<br>            }<br>        }<br><br>        return answer;<br><br>    }<br>};</pre><h4>Depth First Search Algorithm</h4><p>Depth First Search is a searching or traversing algorithm <strong>used to traverse a tree or a graph</strong>. The algorithm <strong>starts with a root node given to it</strong> and prints/traverses/checks the elements <strong>by moving more profoundly in the tree/graph.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SittDvikcMyPPoscQ64FMQ.png" /></figure><p>The data structure needed to carry out the DFS algorithm is:</p><ol><li><strong>Unordered Map </strong>or <strong>vector </strong>(To find that a particular node is visited or not).</li></ol><p><strong>Steps to achieve algorithm:</strong></p><ol><li>Mark the first received node as visited.</li><li>Add this note to the answer vector.</li><li>Make a loop over the adjacency list, if a node is not visited call the DFS function recursively.</li></ol><p>The code for DFS is as follows</p><pre>class Solution {<br>  <br>    void DFS(vector&lt;int&gt; adj[], vector&lt;int&gt; &amp;answer, unordered_map&lt;int, bool&gt; &amp;visited, int node){<br>        visited[node] = 1;<br>        answer.push_back(node);<br><br><br><br>        for(auto neighbour : adj[node]){<br><br>            if(!visited[neighbour]){<br>                DFS(adj, answer, visited, neighbour);<br>            }<br>        }<br>    }<br><br><br><br><br>    <br>  public:<br>    // Function to return a list containing the DFS traversal of the graph.<br>    vector&lt;int&gt; dfsOfGraph(int V, vector&lt;int&gt; adj[]) {<br>        vector&lt;int&gt; answer;<br>        unordered_map&lt;int, bool&gt; visited;<br><br><br><br>        for(int i=0; i&lt;V; i++){<br>            if(!visited[i]){<br>                DFS(adj, answer, visited, i);<br>            }<br>        }<br><br><br>        return answer;<br>    }<br>};</pre><h3>Cycle Detection</h3><p>The cycle is an instance in a graph where during traversal the iterator can come back to an already visited point during its traversal.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Mj54ZT9SlBZp9eHoaw1AYQ.png" /></figure><p>Cycle Detection has many types and can be done by the two searching techniques mentioned above (BFS/DFS).</p><h4>Cycle Detection in Undirected Graph ➡️ using BFS</h4><p>Cycle Detection using BFS is simple and is<strong> just like BFS traversal</strong> but with an <strong>extra </strong><strong>if the condition needs to be there</strong> along <strong>with a different data structure</strong>.</p><p>The data structures needed to carry out Cycle detection using BFS are:</p><ol><li><strong>Unordered Map </strong>or <strong>vector </strong>(To find that a particular node is visited or not).</li><li><strong>Unordered Map </strong>or <strong>vector </strong>(To keep the record of the parent).</li><li><strong>Queue </strong>(To keep track of the unvisited nodes as the traversal goes on).</li></ol><p>The <strong>prime condition</strong> which clears <strong>that a cycle is present in the graph</strong> is that a <strong>neighbor of the node for which you are checking is marked true</strong> and <strong>is not the parent of the node</strong>.</p><p>if(visited[neighbor] == true &amp;&amp; neighbor != parent[node]) ⬅️ Cycle is present.</p><p><strong>Steps to achieve algorithm:</strong></p><ol><li>Mark the first coming node as visited.</li><li>Mark the parent of this node as -1.</li><li>Add this node to the queue.</li><li>Take out the front element from this queue and pop this element from the queue.</li><li>Iterate over the adjacency list for this front element.</li><li>Check for the cycle condition and return true if the cycle condition hits true, else mark the neighbor as visited, set its parent to the front node, And push this neighbor to the queue.</li></ol><p><strong>Code=&gt;</strong></p><pre>bool Cycle_Detection(vector&lt;int&gt; adj[], unordered_map&lt;int, bool&gt; &amp;visited, int node)<br>    {<br><br>        unordered_map&lt;int, int&gt; parent;<br>        parent[node] = -1;<br>        visited[node] = 1;<br>        queue&lt;int&gt; q;<br>        q.push(node);<br><br>        while (!q.empty())<br>        {<br>            int front = q.front();<br>            q.pop();<br><br>            for (auto neighbour : adj[front])<br>            {<br>                if (visited[neighbour] == true &amp;&amp; neighbour != parent[front])<br>                {<br>                    return true;//Cycle Detection condition<br>                }<br><br>                else if (!visited[neighbour])<br>                {<br>                    visited[neighbour] = 1;<br>                    q.push(neighbour);<br>                    parent[neighbour] = front;<br>                }<br>            }<br>        }<br><br>        return false;<br>    }<br><br>public:<br>    // Function to detect cycle in an undirected graph.<br>    bool isCycle(int V, vector&lt;int&gt; adj[])<br>    {<br>        unordered_map&lt;int, bool&gt; visited;<br><br>        for (int i = 0; i &lt; V; i++)<br>        {<br>            if (!visited[i])<br>            {<br>                bool ans = Cycle_Detection(adj, visited, i);<br>                if (ans == true)<br>                {<br>                    return true;<br>                }<br>            }<br>        }<br><br>        return false;<br>    }</pre><h4>Cycle Detection in Undirected Graph ➡️ using DFS</h4><p>Again cycle detection using DFS is just like DFS traversal, all you need is to take care of the cycle condition which is if(neighbor != parent) and add give the parent variable in DFS recursive function call.</p><p>The data structures needed to carry out Cycle detection using DFS are:</p><ol><li><strong>Unordered Map </strong>or <strong>vector </strong>(To find that a particular node is visited or not).</li></ol><p><strong>code=&gt;</strong></p><pre>class Solution {<br>  bool cyclicDFS(vector&lt;int&gt; adj[], unordered_map&lt;int, bool&gt; &amp;visited, int parent, int node){<br>        visited[node] = 1;<br><br><br><br>        for(auto it : adj[node]){<br>            if(!visited[it]){<br>                bool iscyclic = cyclicDFS(adj, visited, node, it);<br>                if(iscyclic){<br>                    return true;<br>                }<br>            }<br>            else if(it != parent){<br>                return true;<br>            }<br>        }<br>        return false;<br>    }<br><br><br><br><br>  public:<br>    // Function to detect cycle in an undirected graph.<br>    bool isCycle(int V, vector&lt;int&gt; adj[]) {<br>        unordered_map&lt;int, bool&gt; visited;<br><br><br>        for(int i=0; i&lt;V; i++){<br>            if(!visited[i]){<br>                bool ans = cyclicDFS(adj, visited, -1, i);<br>                if(ans==true){<br>                    return true;<br>                }<br>            }<br>        }<br><br>        return false;<br>    }<br>};</pre><blockquote><strong>Cycle Detection in Directed graphs is different from Cycle Detection in Undirected graphs why??</strong></blockquote><blockquote>Since, the previous concept to <em>detect cycle in Undirected graphs using DFS</em>, <strong>don’t involve the concept where one node points to another</strong>, therefore, <strong>it even records a cycle in cases when there’s none</strong>. Therefore, we need another approach to <em>detect cycles in a Directed Graph using DFS</em>.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rVIf0Jfkx7jP1XwywozUHQ.png" /></figure><h4>Cycle Detection in Directed Graph ➡️ using BFS</h4><p>Cycle Detection in Directed graphs using BFS is done using Kahn’s algorithm which is discussed later in this article under Topological Sort (Using BFS).</p><p>The detection of the cycle here is done by <strong>making use of the converse of the properties of Topological sort</strong> since we know that Topological sort can only be<strong> implemented in Directed Acyclic Graphs</strong> which means that calling Topological sort in Cyclic graph <strong>will give the wrong result</strong>. Thus, this can <strong>help us to detect Cycles</strong> in Directed graphs.</p><p><strong>Steps to achieve algorithm:</strong></p><ol><li>Store all the Indegrees of the elements in an Indegree vector.</li><li>Initialize the queue by pushing the elements in it whose in degree is zero.</li><li>Implement Kahns algorithm’s concept.</li></ol><pre>class Solution {<br>     public:<br>  bool isCyclic(int V, vector&lt;int&gt; adj[])<br>    {<br><br>        // Indegree Creation<br>        vector&lt;int&gt; Indegree(V);<br>        for (int i = 0; i &lt; V; i++)<br>        {<br>            for (auto it : adj[i])<br>            {<br>                Indegree[it]++;<br>            }<br>        }<br><br>        // Queue Initialization<br><br>    <br>         queue&lt;int&gt; q;<br><br>        for (int i = 0; i &lt; V; i++)<br>        {<br>            if (Indegree[i]==0)<br>            {<br>                q.push(i);<br>            }<br>        }<br><br>        // Kahn&#39;s Algorithm (Concept) Implementation<br>        int counts = 0;<br>        while (!q.empty())<br>        {<br>            int front = q.front();<br>            q.pop();<br><br>            counts++;<br><br>            for (auto neighbor : adj[front])<br>            {<br>                Indegree[neighbor]--;<br>                if (Indegree[neighbor] == 0)<br>                {<br>                    q.push(neighbor);<br>                }<br>            }<br>        }<br><br>        if (counts == V)<br>        {<br>            return false;<br>        }<br>        else<br>        {<br>            return true;<br>        }<br>    }<br>};</pre><h4>Cycle Detection in Directed Graph ➡️ using DFS</h4><p>Cycle Detection in Directed graphs is again similar to DFS traversal but since in directed graphs a node/vertex points to other nodes/vertex, the previous concept to <em>detect cycle in Undirected graphs</em> can’t be applied here.</p><p>The new approach <strong>records the recursive call for a particular node/vertex</strong> and stores it in unordered_map&lt;int, bool&gt; or vector&lt;bool&gt;. This <strong>keeps track of whether the node we are looking for is already in the recursive call</strong> and if it is already <strong>marked visited</strong> then <strong>the cycle is present there</strong>!</p><p>The data structures needed to carry out Cycle detection using BFS are:</p><ol><li><strong>Unordered Map </strong>or <strong>vector </strong>(To find that a particular node is visited or not).</li><li><strong>Unordered Map </strong>or <strong>vector </strong>(To keep the record for recursive calls).</li></ol><p><strong>code=&gt;</strong></p><pre>class Solution {<br><br>    bool cycleDFS(vector&lt;int&gt; adj[], vector&lt;bool&gt; &amp;dfs_visited, vector&lt;bool&gt; &amp;visited, int node){<br>        visited[node] = true;<br>        dfs_visited[node] = true;//marking the current node in recursive call.<br><br><br>        for(auto neighbor : adj[node]){<br>            if(!visited[neighbor]){<br>                bool ans = cycleDFS(adj, dfs_visited, visited, neighbor);<br>                if(ans){<br>                    return ans;<br>                }<br>            }<br>            else if(dfs_visited[neighbor]){<br>                return true;<br>            }<br>        }<br>        dfs_visited[node] = false;//removing the current node/vertex from recursive call.<br>        return false;<br><br>    }<br><br><br><br><br>  public:<br>    // Function to detect cycle in a directed graph.<br>    bool isCyclic(int V, vector&lt;int&gt; adj[]) {<br>        vector&lt;bool&gt; visited(V, false);<br>        vector&lt;bool&gt; dfs_visited(V, false);<br><br>        for(int i=0; i&lt;V; i++){<br>            if(!visited[i]){<br>                bool ans = cycleDFS(adj, dfs_visited, visited, i);<br>                if(ans){<br>                    return ans;<br>                }<br>            }<br>        }<br><br>        return false;<br>    }<br>};</pre><h3>Topological Sort</h3><p>Topological Sort <strong>is a Linear ordering of vertices/nodes</strong> for every edge u to v. In the sorting method, u always appears before v in that ordering.</p><p><strong>Topological sort can only be implemented in Directed Acyclic Graphs (DAG).</strong></p><blockquote><strong>Why?? only in DAGs??</strong></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*htnmIbbZrtzvQSQbw6B8Rw.png" /></figure><h4>Topological Sort using DFS</h4><p>The Main idea behind the algorithm to implement Topological sort using DFS is that <strong>while coming back from recursive calls</strong> for every node<strong> storing that particular node in a stack</strong> and reading the stack elements <strong>from top to bottom</strong> will give the <strong>Topological sort for a particular graph</strong>.</p><p>The data structures needed to carry out Topological Sort are:-</p><ol><li><strong>Unordered Map </strong>or <strong>vector </strong>(To find that a particular node is visited or not).</li><li><strong>Stack </strong>(To record the elements coming back from recursive call).</li></ol><p><strong>code=&gt;</strong></p><pre>class Solution<br>{<br> void DFS_topological(vector&lt;int&gt; adj[], unordered_map&lt;int, bool&gt; &amp;visited, stack&lt;int&gt; &amp;st, int node){<br>        visited[node] = 1;<br><br><br>        for(auto neighbor : adj[node]){<br>            if(!visited[neighbor]){<br>                DFS_topological(adj, visited, st, neighbor);<br>            }<br>        }<br>        st.push(node);//Pushing a node after all its connected elements are traversed.<br>        return;<br><br>    }<br><br><br><br><br> public:<br> //Function to return list containing vertices in Topological order. <br> vector&lt;int&gt; topoSort(int V, vector&lt;int&gt; adj[]) <br> {<br>     unordered_map&lt;int, bool&gt; visited;<br>        stack&lt;int&gt; st;<br><br>        for(int i=0; i&lt;V; i++){<br>            if(!visited[i]){<br>                DFS_topological(adj, visited, st, i);<br>            }<br>        }<br><br>        vector&lt;int&gt; ans;<br>        while(!st.empty()){<br>            ans.push_back(st.top());<br>            st.pop();<br>        }<br><br><br>        return ans;<br> }<br>};</pre><h4>Topological Sort using BFS (Kahn’s Algorithm)</h4><p>The main idea to implement the algorithm using BFS is by making use of an Indegree vector or array. <strong>Whenever the Indegree of a particular vertex or node becomes zero add it to the BFS queue</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EDJnnOkNmEZyWV2YzpkwqQ.png" /></figure><p><strong>Steps to Implement the Algorithm</strong></p><ol><li>Create an Indegree vector or array and record the Indegrees of all the elements in it.</li><li>Create a queue and add the elements whose indegrees are zero.</li><li>Run the BFS algorithm and push the front element of the queue into an answer vector while running the while loop.</li><li>Decrease the in-degree of the iterated element and check in the Indegree vector if its indegrees are zero, if yes push it to the queue.</li></ol><p><strong>code=&gt;</strong></p><pre>class Solution<br>{<br> public:<br> //Function to return list containing vertices in Topological order. <br> vector&lt;int&gt; topoSort(int V, vector&lt;int&gt; adj[]) <br> {<br>     vector&lt;int&gt; Answer;<br><br><br>        //Indegree Creation<br>        vector&lt;int&gt; Indegree(V);<br>        for(int i=0; i&lt;V; i++){<br>            for(auto it : adj[i]){<br>                Indegree[it]++;<br>            }<br>        }<br><br>        <br>        //Queue Initialization<br>        queue&lt;int&gt; q;<br><br>        for(int i=0; i&lt;V; i++){<br>            if(Indegree[i] == 0){<br>                q.push(i);<br>            }<br>        }<br><br><br><br>        while(!q.empty()){<br>            int front = q.front();<br>            q.pop();<br><br>            Answer.push_back(front);<br><br>            for(auto it : adj[front]){<br>                Indegree[it]--;<br>                if(Indegree[it] == 0){<br>                    q.push(it);<br>                }<br>            }<br>        }<br><br><br>        return Answer;<br><br> }<br>};</pre><h3>Shortest Path</h3><p>Shortest Path is a concept in Graphs <strong>that calculates the shortest path between two vertices/nodes</strong>. This shortest route can be calculated in both <strong>directed and Undirected graphs</strong> by using the <strong>concept of DFS and BFS traversing algorithms.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SmUhlPdgpaFZZpXzUi9v3g.png" /></figure><h4>Shortest Path in Undirected Graph</h4><p>The shortest path in the Undirected graph can be calculated using the BFS algorithm logic. <strong>We’ll be traversing all, the nodes by putting them in a queue and checking if the distance to reach them is the shortest or not</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gifQeMXtid_PjDXDd8Jyiw.png" /></figure><p><strong>code=&gt;</strong></p><pre>class Solution<br>{<br>public:<br>    vector&lt;int&gt; shortestPath(vector&lt;vector&lt;int&gt;&gt; &amp;edges, int N, int M, int src)<br>    {<br>        unordered_map&lt;int, list&lt;int&gt;&gt; adj;<br><br>        for (int i = 0; i &lt; edges.size(); i++)<br>        {<br>            int u = edges[i][0];<br>            int v = edges[i][1];<br><br>            adj[u].push_back(v);<br>            adj[v].push_back(u);<br>        }<br><br>        vector&lt;int&gt; distance(N, INT_MAX);<br><br>        queue&lt;int&gt; q;<br>        q.push(src);<br>        distance[src] = 0;<br><br>        while (!q.empty())<br>        {<br>            int front = q.front();<br>            q.pop();<br><br>            for (auto neighbor : adj[front])<br>            {<br>                if (distance[front] + 1 &lt; distance[neighbor]){<br>                    distance[neighbor] = distance[front] + 1;<br>                }<br>                q.push(neighbor);<br>            }<br>        }<br><br>        for(int i=0; i&lt;distance.size(); i++){<br>            if(distance[i] == INT_MAX){<br>                distance[i] = -1;<br>            }<br>        }<br><br>        return distance;<br>    }<br>};</pre><h4>Shortest Path in Directed Graphs</h4><p>In the Directed graph Shortest path is calculated using the concept of Topological Sort. Further, the topological sort is generated using the concept of DFS.</p><p><strong>code=&gt;</strong></p><pre>class Solution {<br>  void DFS_top(unordered_map&lt;int, list&lt;pair&lt;int,int&gt;&gt;&gt; &amp;adj, unordered_map&lt;int, bool&gt; &amp;visited, stack&lt;int&gt; &amp;st, int node){<br>        visited[node] = 1;<br><br>        for(auto neighbor : adj[node]){<br>            if(!visited[neighbor.first]){<br>                DFS_top(adj, visited, st, neighbor.first);<br>            }<br>        }<br>        st.push(node);<br>        return;<br>    }<br><br><br><br><br>  public:<br>     vector&lt;int&gt; shortestPath(int N,int M, vector&lt;vector&lt;int&gt;&gt;&amp; edges){<br>        unordered_map&lt;int, list&lt;pair&lt;int,int&gt;&gt;&gt; adj;<br>        unordered_map&lt;int, bool&gt; visited;<br>        stack&lt;int&gt; st;<br>        vector&lt;int&gt; distance(N, INT_MAX);<br><br><br>        for(int i=0; i&lt;edges.size(); i++){<br>            int u = edges[i][0];<br>            int v = edges[i][1];<br>            int w = edges[i][2];<br><br>            adj[u].push_back({v, w});<br>        }<br><br><br>        for(int i=0; i&lt;N; i++){<br>            if(!visited[i]){<br>                DFS_top(adj, visited, st, i);<br>            }<br>        }<br><br><br>        int src = 0;<br>        distance[src] = 0;<br><br>        while(!st.empty()){<br>            int top = st.top();<br>            st.pop();<br><br><br>            if(distance[top]!=INT_MAX){<br>                for(auto neighbor : adj[top]){<br>                    if(distance[top] + neighbor.second &lt; distance[neighbor.first]){<br>                        distance[neighbor.first] = distance[top] + neighbor.second;<br>                    }<br>                }<br>            }<br>        }<br><br><br>        for(int i=0; i&lt;distance.size(); i++){<br>            if(distance[i] == INT_MAX){<br>                distance[i] = -1;<br>            }<br>        }<br><br>        return distance;<br><br><br><br><br>    }<br>};</pre><h3>Dijkstra Algorithm</h3><p>Dijkstra Algorithm is used to find the shortest distance from a source node to all the other nodes. It is similar to <em>finding the shortest distance in an undirected graph</em> <strong>with no weights</strong>. Dijkstra&#39;s algorithm makes use of the weights of the edges to find the shortest distance between a pair of nodes.</p><p>The approach below is discussed by making <strong>use of a set to store the next minimum distance and the node corresponding to it.</strong></p><h4>Steps to achieve Dijkstra</h4><ol><li>Create a set of type set&lt;pair&lt;int, int&gt;&gt;.</li><li>Create a distance vector and initialize it with INT_MAX vector&lt;int&gt; distance(V, INT_MAX).</li><li>Initialize the distance for the source node as zero and give the source node a distance in the set</li></ol><p>st.insert({0, src}) and distance[src] = 0 like this.</p><p>4. Create a while loop till the set is empty and <strong>check if the distance of the current node</strong> + <strong>the distance to reach its neighboring node</strong> is smaller than <strong>the distance already prefilled in the distance vector</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4sTIl17p4vw2TsRTE_D79A.png" /></figure><p>5. If the condition is true then replace any other entry of the node corresponding to its distance in the set.</p><p>6. repeat the above steps.</p><p><strong>code=&gt;</strong></p><pre>class Solution<br>{<br> public:<br> //Function to find the shortest distance of all the vertices<br>    //from the source vertex S.<br>    vector &lt;int&gt; dijkstra(int V, vector&lt;vector&lt;int&gt;&gt; adj[], int src)<br>    {<br>        set&lt;pair&lt;int, int&gt;&gt; st; //(distance, node)<br>        vector&lt;int&gt; distance(V, INT_MAX);<br><br>        //Initailizations<br>        st.insert({0, src});<br>        distance[src] = 0;<br><br>        //Processing<br>        while(!st.empty()){<br>            auto top = *(st.begin());<br><br>            int current_distance = top.first;<br>            int current_node = top.second;<br>            st.erase(st.begin());<br><br>            for(auto neighbor : adj[current_node]){<br>                int node = neighbor[0];<br>                int weight = neighbor[1];<br><br>                if(current_distance + weight &lt; distance[node]){<br>                    if(distance[node] != INT_MAX){<br>                        st.erase({distance[node], node});<br>                    }<br>                    distance[node] = current_distance + weight;<br>                    st.insert({distance[node], node});<br>                }<br>            }<br>        }<br><br>        return distance;<br><br>    }<br>};</pre><h3>Prim’s Algorithm</h3><p>Prim’s algorithm is also one of the most important algorithms when it comes to the Graphs topic. The algorithm <strong>aims to find the Minimum Spanning Tree (MST) by making use of the weights on the edges of the graphs.</strong></p><h4>Minimum Spanning Tree??</h4><p>MST is <strong>obtained from an undirected graph</strong> and <strong>aims to connect or to reach all vertices/nodes</strong>, <strong>without any cycles</strong> and <strong>with the minimum weight obtained as the result of tree creation.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7t6pdneVphdn9l44xJkFnA.png" /></figure><h4>Steps to achieve Prim’s algorithm</h4><ol><li>Create three data structures as key, visited, and parent to store the distances, mark node visited, and track the parent of a node respectively.</li><li>Initialize the source node in key and parent data structure as:</li></ol><p>key[src] = 0 and parent[src] = -1.</p><p>3. Take the minimum distance out of all the vertices from the key data structure and mark its vertex as visited.</p><p>4. Traverse over all its neighboring nodes and check if the weight is smaller than their occurrence in the key data structure. If the condition is true update the key data structure for that node and track its parent as well.</p><p>5. Repeat the above steps.</p><p>6. Output the result as the sum of the weights of the edges or the key data structure itself.</p><p><strong>code=&gt;</strong></p><pre>class Solution<br>{<br> public:<br> //Function to find sum of weights of edges of the Minimum Spanning Tree.<br>    int spanningTree(int V, vector&lt;vector&lt;int&gt;&gt; adj[])<br>    {<br>        //Creations<br>        vector&lt;int&gt; key(V, INT_MAX);//To store distances<br>        vector&lt;bool&gt; visited(V, false);//To traverse nodes<br>        vector&lt;int&gt; parent(V, -1);//To track parent<br><br>        //Initializations<br>        int src = 0;<br>        key[src] = 0;<br>        parent[src] = -1;<br><br><br>        for(int i=0; i&lt;V; i++){<br><br>            //Take out the node with minimum distance;<br>            int u;<br>            int mini = INT_MAX;<br><br>            for(int j=0; j&lt;V; j++){<br>                if(visited[j]!=true &amp;&amp; key[j] &lt; mini){<br>                    u = j;<br>                    mini = key[j];<br>                }<br>            }<br>            //Mark the smallest taken out node as visited!<br><br>            visited[u] = 1;<br><br>            //Traverse over adjacent nodes<br><br>            for(auto neighbor : adj[u]){<br>                int v = neighbor[0];//Node<br>                int w = neighbor[1];//Weight<br><br><br>                if(visited[v] == false &amp;&amp; w &lt; key[v]){<br>                    key[v] = w;<br>                    parent[v] = u;<br>                }<br>            }<br>        }<br><br><br>        int answer = 0;<br><br>        for(int i=0; i&lt;key.size(); i++){<br>            if(key[i] != INT_MAX){<br>                answer+=key[i];<br>            }<br>        }<br><br>        return answer;<br>    }<br>};</pre><h3>Kruskal’s Algorithm</h3><p>Kruskal’s is another algorithm that is used to determine the Minimum Spanning Tree. The algorithm works in the following steps:</p><ol><li>Sort all the edges by weight of the graph.</li><li>Create an MST by taking out the smallest edge and discarding an edge if it forms a cycle.</li><li>Stop when all the vertices are covered.</li></ol><p>Kruskal’s algorithm uses the capability of Disjoint Sets in order to find the MST.</p><h4>Disjoint Set??</h4><p>Disjoint sets are the pair of sets that do not have the same elements. In such situations, only two operations can be performed.</p><ol><li>Union (Combines 2 elements from different sets)</li><li>Find Parent or Find Set (which tells the parent of a particular element).</li></ol><p>➡️ The union can be done <strong>by making use of rank and path compression</strong>. In which a <strong>parent of an element is made whose rank is higher</strong> and if the ranks of <strong>both the elements are the same then</strong>, one of the two is selected as a parent and the other as a child, followed<strong> by an increase in rank of the parent element.</strong></p><pre>void unionSet(int u, int v, vector&lt;int&gt; &amp;parent, vector&lt;int&gt; &amp;rank)<br>    {<br>        u = findParent(parent, u);<br>        v = findParent(parent, v);<br><br>        if (rank[u] &lt; rank[v])<br>        {<br>            parent[u] = v;<br>        }<br><br>        else if(rank[u] &gt; rank[v]){<br>            parent[v] = u;<br>        }<br><br>        else{<br>            //Rank is same<br>            parent[v] = u;<br>            rank[u]++; <br>        }<br>    }</pre><p>➡️ Find Parent is done by <strong>finding the parent of an element</strong> this is done by putting the base condition asparent[node] = node then the recursion stops. This is because initially, <strong>every element is its own parent at the time of initialization.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Qhv1RfAEf52ujZGKS-VVIg.png" /></figure><p><strong>Code=&gt;</strong></p><pre>class Solution<br>{<br>    void makeSet(vector&lt;int&gt; &amp;rank, vector&lt;int&gt; &amp;parent, int V)<br>    {<br>        for (int i = 0; i &lt; V; i++)<br>        {<br>            parent[i] = i;<br>            rank[i] = 0;<br>        }<br>    }<br><br>    int findParent(vector&lt;int&gt; &amp;parent, int node)<br>    {<br>        if (parent[node] == node)<br>        {<br>            return node;<br>        }<br><br>        return parent[node] = findParent(parent, parent[node]);<br>    }<br><br>    void unionSet(int u, int v, vector&lt;int&gt; &amp;parent, vector&lt;int&gt; &amp;rank)<br>    {<br>        u = findParent(parent, u);<br>        v = findParent(parent, v);<br><br>        if (rank[u] &lt; rank[v])<br>        {<br>            parent[u] = v;<br>        }<br><br>        else if(rank[u] &gt; rank[v]){<br>            parent[v] = u;<br>        }<br><br>        else{<br>            parent[v] = u;<br>            rank[u]++; <br>        }<br>    }<br><br>public:<br>    // Function to find sum of weights of edges of the Minimum Spanning Tree.<br>    int spanningTree(int V, vector&lt;vector&lt;int&gt;&gt; edges[])<br>    {<br><br>        vector&lt;pair&lt;int, pair&lt;int, int&gt;&gt;&gt; adj;<br><br>        for(int i=0; i&lt;V; i++){<br>            for(auto it : edges[i]){<br>                int u = i;<br>                int v = it[0];<br>                int wt = it[1];<br><br>                adj.push_back({wt, {u, v}});<br>            }<br>        }<br><br>        //Sorting by weight<br>        sort(adj.begin(), adj.end());<br><br>        <br>        vector&lt;int&gt; rank(V);<br>        vector&lt;int&gt; parent(V);<br>        makeSet(rank, parent, V);<br>        int totalwt = 0;<br><br>        for(auto it : adj){<br>            int u = findParent(parent, it.second.first);<br>            int v = findParent(parent, it.second.second);<br><br>            int wt = it.first;<br><br>            //Calculates Totalwt and makes sure no cyucle is formed<br>            if(u!=v){<br>                totalwt+=wt;<br>                unionSet(u, v, parent, rank);<br>            }<br>        }<br><br>        return totalwt;<br>    }<br>};</pre><h3>Bridge in a Graph</h3><p>Given a Graph of V vertices and E edges and another edge(c — d), the task is to find if the given edge is a Bridge<strong>.</strong> i.e., removing the edge disconnects the graph.</p><blockquote>A bridge in a graph is that edge <strong>which when removed makes the graph splits/disconnect into the maximum number of connected components.</strong></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0it1wU7gAg33bsUMauFXHw.png" /></figure><p><strong>Example 1:</strong></p><pre>Input:</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/341/0*f5ebdaNm3Wghb8ng.png" /></figure><pre>c = 1, d = 2<br>Output:<br>1<br>Explanation:<br>From the graph, we can clearly see that<br>blocking the edge 1-2 will result in <br>disconnection of the graph. So, it is <br>a Bridge and thus the Output 1.</pre><blockquote>The example is taken from GeekforGeeks.</blockquote><h4>Naive or Brute Force Approach</h4><p>The brute force approach can be thought of as <strong>disconnecting every edge and checking all the time</strong> whether the graph is split into components or not.</p><p>The time complexity in this approach will be O(E*(V+E)). Also, the space complexity will be O(V + E).</p><h4>Optimized Approach (Tarjan’s Algorithm)</h4><p>The optimized approach includes the concept of Tarjan’s algorithm <strong>where 3 data structures and 1 variable</strong> which are mentioned below are created to keep all information about a particular node.</p><p><strong>Data Structures needed:-</strong></p><ol><li>Disc Vector&lt;int&gt; =&gt; Data structure for storing the <strong>time when a node is visited for the first time.</strong></li><li>Low vector&lt;int&gt; =&gt; Data structure <strong>that stores the least possible time</strong> to locate the node other than from its parent.</li><li>Visited Unordered_map&lt;int, bool&gt; =&gt; Tracks if the <strong>particular node is visited or not.</strong></li><li>Parent int =&gt; Variable that keeps the<strong> track of parent</strong> of a particular node.</li></ol><p>➡️<strong>Algorithm</strong></p><ol><li>Mark the <strong>first node in the function as visited</strong>. Since it will be called recursively every node will be marked visited during traversal.</li><li>Update the <strong>low and disc of a particular node as a timer</strong> initially.</li><li>Traverse <strong>over the connected nodes</strong> of a node at a time.</li><li>When traversing if the <strong>iterator points to the parent</strong> of the current node <strong>continue the loop</strong>.</li><li>When traversing <strong>if a node is not visited call the function recursively</strong>.</li><li><strong>When coming back from recursion</strong> update the low[node] as low[node] = min(low[node], low[nbr]). To make changes in the low[node] too if the graph below it has any back edge.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-9CblYaw5j-L9vMmiB4KJw.png" /></figure><p>7. If low[nbr] &gt; disc[node] is true, <strong>this means that there’s a bridge. </strong>As the node does not have any other path to be reached.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zoWyhv3b5yuCZNWBuvY0Pw.png" /></figure><p>8.<strong> When traversing if a particular node is visited</strong> and is also not the parent of the node then, <strong>it is a case of back edge</strong> handling it by updating low[node] as low[node] = min(low[node], disc[nbr]).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*W4wCWiqaVCU9BseoAo8fPw.png" /></figure><p><strong>Code=&gt;</strong></p><pre>class Solution<br>{<br> void DFS_Bridge(vector&lt;int&gt; adj[], unordered_map&lt;int, bool&gt; &amp;visited, vector&lt;int&gt; &amp;disc, vector&lt;int&gt; &amp;low, int parent, int &amp;timer, int &amp;isBridge, int node, int c, int d){<br>        visited[node] = 1;<br><br>        low[node] = disc[node] = timer++;<br><br>        for(auto nbr : adj[node]){<br>            if(nbr == parent){<br>                continue;<br>            }<br>            if(!visited[nbr]){<br>                DFS_Bridge(adj, visited, disc, low, node, timer, isBridge, nbr, c, d);<br><br>                //If back-edge is present below or in the neighbour of the node<br>                low[node] = min(low[node], low[nbr]);<br><br>                //Finding Bridge<br>                if((low[nbr] &gt; disc[node]) &amp;&amp; ((c == nbr &amp;&amp; d == node) || (c == node) &amp;&amp; d == nbr)){<br>                    isBridge = 1;<br>                }<br>            }<br>            else{<br>                //Back Edge<br>                low[node] = min(low[node], disc[nbr]);<br>            }<br>        }<br>    }<br><br><br><br><br> public:<br>    //Function to find if the given edge is a bridge in graph.<br>    int isBridge(int V, vector&lt;int&gt; adj[], int c, int d) <br>    {<br>        unordered_map&lt;int, bool&gt; visited;<br>        vector&lt;int&gt; disc(V, 0);<br>        vector&lt;int&gt; low(V,0);<br>        int parent = -1;<br>        int timer = 0;<br>        int isBridge = 0;<br><br>        for(int i=0; i&lt;V; i++){<br>            if(!visited[i]){<br>                DFS_Bridge(adj, visited, disc, low, parent, timer, isBridge, i, c, d);<br>            }<br>        }<br><br>        return isBridge;<br><br><br>    }<br>};</pre><h3>Articulation Point</h3><p>Given an undirected connected graph with <strong>V </strong>vertices and adjacency list <strong>adj</strong>. You are required to find all the vertices removing which (and edges through it) disconnect the graph into 2 or more components.<br><strong>Note: </strong>Indexing is zero-based i.e. nodes numbering from (0 to V-1). There might be loops present in the graph.</p><p><strong>Example 1:</strong></p><pre>Input:</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/392/0*wK97-NVwrkdYUTWE.png" /></figure><pre>Output:{1,4}<br>Explanation: Removing the vertex 1 will<br>discconect the graph as-</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/346/0*VD2rmls1_T1aRrds.png" /></figure><pre>Removing the vertex 4 will disconnect the<br>graph as-</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/283/0*RNU_B6P7YdBg3VqZ.png" /></figure><blockquote>The question and example are taken from geekforgeeks.</blockquote><blockquote>The articulation point is similar to Bridge in a graph as in this we need to find a node on the removal of which the graph will be disconnected into several components.</blockquote><p>The articulation points can be found using Tarjan’s algorithm concept. Therefore, the algorithm to approach it is the same as that of the question <strong><em>Bridge in a Graph.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-8XtsHohU1SNu3ne3AP1pA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7KowE14VxvU0qCFdjJZ-Bg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*B9ttitV7SQ7aiw-4kfUOfw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mDTXCYyztX0VW9f0MMuxNQ.png" /></figure><p><strong>Code=&gt;</strong></p><pre>class Solution {<br>  void DFS_AP(vector&lt;int&gt; adj[], vector&lt;int&gt; &amp;disc, vector&lt;int&gt; &amp;low, vector&lt;bool&gt; &amp;ap, unordered_map&lt;int, bool&gt; &amp;visited, int parent, int node, int timer)<br>    {<br><br>        visited[node] = 1;<br><br>        low[node] = disc[node] = timer++;<br>        int child = 0;<br><br>        for(auto nbr : adj[node]){<br>            <br>            if(nbr == parent){<br>                continue;<br>            }<br><br>            if(!visited[nbr]){<br>                DFS_AP(adj, disc, low, ap, visited, node, nbr, timer);<br>                //If the lower graph or the children of the node got a<br>                //backedge then=&gt;<br>                low[node] = min(low[nbr], low[node]);<br><br>                //Checking if the node is AP or not<br>                if(low[nbr] &gt;= disc[node] &amp;&amp; parent != -1){<br>                    ap[node] = 1;<br>                }<br>                child++;<br>            }<br>            else{<br>                //BackEdge<br>                low[node] = min(low[node], disc[nbr]);<br>            }<br>        }<br><br>        if(parent == -1 &amp;&amp; child &gt; 1){<br>            ap[node] = 1; // For parent node<br>        }<br><br>    }<br><br>public:<br>    vector&lt;int&gt; articulationPoints(int V, vector&lt;int&gt; adj[])<br>    {<br><br>        // Creating and Initializing required Data Structures<br>        vector&lt;int&gt; disc(V, -1);<br>        vector&lt;int&gt; low(V, -1);<br>        int parent = -1;<br>        vector&lt;bool&gt; ap(V);<br>        unordered_map&lt;int, bool&gt; visited;<br>        int timer = 0;<br><br>        // DFS<br>        for (int i = 0; i &lt; V; i++)<br>        {<br>            if (!visited[i])<br>            {<br>                DFS_AP(adj, disc, low, ap, visited, parent, i, timer);<br>            }<br>        }<br><br>        vector&lt;int&gt; answer;<br><br>        for (int i = 0; i &lt; ap.size(); i++)<br>        {<br>            if (ap[i])<br>            {<br>                answer.push_back(i);<br>            }<br>        }<br>        if(answer.empty()){<br>            answer.push_back(-1);<br>        }<br><br>        return answer;<br>    }<br>};</pre><h3>Kosaraju’s Algorithm</h3><p>Kosaraju’s algorithm aims to find the <strong>Strongly Connected Components or SCCs </strong>in a graph. These SCCs are the <strong>subgraphs that are strongly connected to one another.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vinqhc5fKKoRR19giHVaqA.png" /></figure><p>The algorithm is carried out in 3 steps which are:</p><ol><li>Performing <strong>Topological Sort</strong> of the graph.</li><li>By <strong>Transposing</strong> the graph.</li><li>By performing the <strong>DFS</strong> on the transposed graph.</li></ol><p><strong>Code=&gt;</strong></p><pre>class Solution<br>{<br> <br>    void DFS_Top(vector&lt;vector&lt;int&gt;&gt; &amp;adj, stack&lt;int&gt; &amp;st, vector&lt;int&gt; &amp;visited, int node){<br>        visited[node] = 1;<br><br>        for(auto nbr : adj[node]){<br>            if(!visited[nbr]){<br>                DFS_Top(adj, st, visited, nbr);<br>            }<br>        }<br>        st.push(node);<br>        <br>    }<br><br><br>    void DFS(vector&lt;vector&lt;int&gt;&gt; &amp;adj, vector&lt;int&gt; &amp;visited, int node){<br>        visited[node] = 1;<br><br>        for(auto it : adj[node]){<br>            if(!visited[it]){<br>                DFS(adj, visited, it);<br>            }<br>        }<br>    }<br><br><br><br> public:<br> //Function to find number of strongly connected components in the graph.<br>    int kosaraju(int V, vector&lt;vector&lt;int&gt;&gt;&amp; adj)<br>    {<br><br>        stack&lt;int&gt; st;<br>        vector&lt;int&gt; visited(V, 0);<br><br><br>        for(int i=0; i&lt;V; i++){<br>            if(!visited[i]){<br>                DFS_Top(adj, st, visited, i);<br>            }<br>        }<br><br>        vector&lt;vector&lt;int&gt;&gt; transpose(V);<br><br><br>        //Transpose<br>        for(int i=0; i&lt;V; i++){<br>            visited[i] = 0;<br>            for(auto it : adj[i]){<br>                transpose[it].push_back(i);<br>            }<br>        }<br><br><br>        int counts = 0;<br><br>        while(!st.empty()){<br>            int front = st.top();<br>            st.pop();<br><br>            if(!visited[front]){<br>                counts++;<br>                DFS(transpose, visited, front);<br>            }<br>        }<br><br><br>        return counts;<br><br><br><br>    }<br>};</pre><h3>Bellman Ford Algorithm</h3><p>Bellman Ford Algorithm <strong>aims to find the shortest path between the vertices of a graph.</strong> The algorithm also <strong>works on negative weights,</strong> unlike the Dijkstra algorithm which works only on positive weights.</p><p>Though Bellman-Ford Algorithm works on negative weights <strong>it cannot work on negative weight cycles.</strong> Due to this, <strong>it can also be used to detect negative weight cycles from a graph.</strong></p><p><strong>Steps to achieve algorithm:</strong></p><ol><li>Check the condition for n-1 times.</li></ol><p>2. Check one more time and if the results are the same, then there is no negative weight cycle present in the graph.</p><p><strong>Code=&gt;</strong></p><pre>// User function Template for C++<br><br>class Solution {<br>  public:<br>    /*  Function to implement Bellman Ford<br>    *   edges: vector of vectors which represents the graph<br>    *   S: source vertex to start traversing graph with<br>    *   V: number of vertices<br>    */<br>    vector&lt;int&gt; bellman_ford(int V, vector&lt;vector&lt;int&gt;&gt; &amp;edges, int S)<br>    {<br>        vector&lt;int&gt; distance(V, 1e8);<br>        distance[S] = 0;<br><br>        for (int i = 0; i &lt; V; i++)<br>        {<br>            for (int j = 0; j &lt; edges.size(); j++)<br>            {<br>                int u = edges[j][0];<br>                int v = edges[j][1];<br>                int wt = edges[j][2];<br><br>                if (distance[u] != INT_MAX &amp;&amp; ((distance[u] + wt) &lt; distance[v]))<br>                {<br>                    distance[v] = distance[u] + wt;<br>                }<br>            }<br>        }<br><br>        bool flag = 0;<br><br>        for (int j = 0; j &lt; edges.size(); j++)<br>        {<br>            int u = edges[j][0];<br>            int v = edges[j][1];<br>            int wt = edges[j][2];<br><br>            if (distance[u] != INT_MAX &amp;&amp; ((distance[u] + wt) &lt; distance[v]))<br>            {<br>                flag = 1;<br>            }<br>        }<br><br>        if(flag == 1){<br>            vector&lt;int&gt; answer;<br>            answer.push_back(-1);<br>            return answer;<br>        }<br><br>        return distance;<br>    }<br>};</pre><h3>Summary at a Glance</h3><p>The summary of the whole article is as follows:</p><h4><strong>BFS</strong></h4><p>Breadth First Search is used to traverse the graph using a queue. Just iterate over the elements of the graph using a queue.</p><h4>DFS</h4><p>Depth First Is used to traverse the graph in a recursive manner. Just call the DFS function recursively. If a particular element is not visited.</p><h4>Cycle detection using BFS in an undirected graph</h4><p>Create one more data structure. Name it as a parent and store the parent of all the elements in it, just check the cycle condition while traversing in a BFS manner. The cycle condition is ➡️if(visited[neighbor] == true &amp;&amp; neighbor != parent[node]).</p><h4>Cycle detection using DFS in an undirected graph</h4><p>Recursively send the parent of the node in the function, again, and check the condition for the cycle i.e. if(neighbor != parent) &amp;&amp; visited[neighbor] == true. The condition checks all the nodes other than the parent, if visited then the cycle is present there.</p><h4>Cycle detection using BFS in a directed graph</h4><p>Cycle detection in a directed graph using BFS is done <strong>using the concept of Kahn&#39;s algorithm.</strong> Since Khan&#39;s algorithms work on <strong>directed acyclic graphs</strong> which means if it is used on cyclic graphs <strong>it will give wrong results.</strong> Thus making a <strong>check condition</strong> using the algorithm can tell us if the graph has a cycle or not.</p><h4>Cycle detection using DFS in a directed graph.</h4><p>Cycles can be detected in a directed graph using DFS <strong>by tracking the parent node.</strong> This can be done by marking the<strong> first received node (parent node) as true in a data structure (vector or array)</strong> and checking its neighbor (If marked in that DFS call then the cycle is present there). <strong>At the end un-marking the parent node when all its neighbor nodes are traversed.</strong></p><h4>Topological Sort using BFS</h4><p>Topological sort using BFS can be found using Kahn&#39;s algorithm in which, a vector or array (Indegree) needs to be created for all the nodes and<strong> the nodes whose degree is zero, are pushed in a queue</strong> and BFS traversal is carried out on that queue. <strong>Processing is done by decreasing the iterator node’s value from the Indegree data structure and if it gets zero, it is pushed in the queue again.</strong></p><h4>Topological Sort using DFS</h4><p>Topological sort using DFS is just like the DFS traversal the change is, on <strong>coming back from the recursive call the node needs to be pushed in a stack.</strong> That&#39;s all the stack will contain the topological sort of the nodes in the graph.</p><p>That’s all💯</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ab7b4205f41a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Flutter State Management using Inherited Widget — Flutter State Management Series #2]]></title>
            <link>https://medium.com/@itsvinayyay/flutter-state-management-using-inherited-widget-flutter-state-management-series-2-b921451d2530?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/b921451d2530</guid>
            <category><![CDATA[app-development]]></category>
            <category><![CDATA[flutter]]></category>
            <category><![CDATA[inheritedwidget]]></category>
            <category><![CDATA[state-management]]></category>
            <category><![CDATA[flutter-app-development]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Mon, 17 Jul 2023 03:47:07 GMT</pubDate>
            <atom:updated>2023-07-17T03:47:07.275Z</atom:updated>
            <content:encoded><![CDATA[<h3>Flutter State Management using Inherited Widget — Flutter State Management Series #2</h3><p>The second blog in the Flutter State Management series, in this one we’ll explore and approach State Management using Inherited Widget. The approach is a little more complicated than the previous one but kinda straightforward.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KjAWS7mkafirO7FiYr5RTg.png" /></figure><p>Before diving in fully let’s understand Inherited Widget in deep!</p><h3>Inherited Widget??</h3><p>In simpler words, an InheritedWidget in Flutter is a special type of widget that <strong>allows you to share data down the widget tree with all of its descendants.</strong> It&#39;s like a container that holds some data and <strong>passes it along to all the widgets that need access to that data</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7MQzdrDbMVa1_MjPBelgog.png" /></figure><blockquote>Imagine you have a family tree, where the root is the InheritedWidget and its children and grandchildren are the widgets that depend on the data provided by the InheritedWidget. When the data inside the InheritedWidget changes, all the widgets below it in the tree will be automatically updated with the new data.</blockquote><p>This is useful when you have data that needs to be <strong>accessed by multiple widgets in different parts of your app</strong>. Instead of passing the data manually from widget to widget, you can use an InheritedWidget to share the data and let the framework handle the updates automatically.</p><p>It simplifies the process of managing and sharing data across your app, making it more efficient and reducing the need for repetitive code.</p><p>In summary, an InheritedWidget is a way to share data down the widget tree so that multiple widgets can access and use that data without the need for manual data passing. It helps keep your code clean and makes it easier to manage and update shared data in your app.</p><h4><strong>Example of using an Inherited Widget</strong></h4><pre>class example extends InheritedWidget {<br>  final int count;<br>  final Function() increment;<br><br>  CounterProvider({<br>    required this.count,<br>    required this.increment,<br>    required Widget child,<br>  }) : super(child: child);<br><br>  static example of(BuildContext context) {<br>    return context.dependOnInheritedWidgetOfExactType&lt;example&gt;()!;<br>  }<br><br>  @override<br>  bool updateShouldNotify(covariant example oldWidget) {<br>    return count != oldWidget.count;<br>  }<br>}</pre><p><strong>➡️The </strong><strong>of method</strong></p><p>The of method is a static method defined inside the example class (replace example with the actual class name) that allows accessing the nearest ancestor widget of type example from a given BuildContext.</p><pre>static example of(BuildContext context) {<br>    return context.dependOnInheritedWidgetOfExactType&lt;example&gt;()!;<br>  }</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xa9pO0SJE-jI8vT-5KDPdQ.png" /></figure><p>Let’s break down how it works:</p><ol><li>The of method is marked as static, which means it <strong>can be called directly on the class itself without requiring an instance</strong> of the class.</li><li>It takes a BuildContext as a parameter. The BuildContext <strong>represents the location of a widget within the widget tree.</strong></li><li>Inside the of method, the context.dependOnInheritedWidgetOfExactType&lt;T&gt;() method is called.<strong> This method is provided by the Flutter framework</strong> and searches for the nearest ancestor widget of type T (in this case, example), starting from the given BuildContext.</li><li>The dependOnInheritedWidgetOfExactType&lt;T&gt;() method <strong>returns the found widget or </strong><strong>null if no matching widget is found</strong>. However, the ! operator is used to assert that the returned value is not null. This is done because the method is expected to find a widget of type example in this case, and the code assumes it will always be present.</li><li>Finally, the found widget is returned from the of method, <strong>allowing other parts of the code to access the properties or methods of the </strong><strong>example widget.</strong></li></ol><blockquote>By using the of method, you can conveniently retrieve the nearest ancestor widget of a specific type from any point in the widget tree without having to manually traverse the tree. It simplifies the process of accessing shared data or functionality provided by an InheritedWidget or any other type of widget.</blockquote><p><strong>➡️The </strong><strong>updateShouldNotifymethod</strong></p><p>The updateShouldNotify method is an overridden method in an InheritedWidget subclass, typically used to determine if the descendants of the widget need to be notified of changes. Let&#39;s break down the code:</p><ol><li>The updateShouldNotify method is <strong>called automatically by the Flutter</strong> framework when the InheritedWidget is rebuilt. It compares the properties of the <strong>current widget instance with the properties of the previous (old) widget instance.</strong></li><li>The covariant keyword is used to indicate that the overridden method has a <strong>covariant parameter type</strong>. It allows the overridden method to accept a more specific type (example) than the base class&#39;s method signature.</li><li>Inside the updateShouldNotify method, a <strong>comparison is made</strong> between the count property of the current widget instance and the count property of the previous (old) widget instance (oldWidget.count).</li><li>If the comparison evaluates to true, it means that the count property has changed, and the descendants of the InheritedWidget need to be notified of the change.</li><li>The method returns a boolean value <strong>indicating whether the descendants should be notified</strong> (true) or not (false).</li></ol><blockquote>In summary, the updateShouldNotify method is used to determine if changes in the properties of the InheritedWidget are significant and require the descendants of the widget to be rebuilt. In this case, the method compares the count property of the current widget instance with the count property of the previous widget instance, and if they differ, it returns true, indicating that the descendants should be notified of the change.</blockquote><h3>Pros and Cons of Using Inherited Widget</h3><h4>Advantages of using Inherited Widget</h4><ol><li><strong>Efficient Data Sharing: </strong>InheritedWidget provides an efficient way to share data <strong>across multiple widgets in the widget tree without the need for explicit data passing</strong>. It <strong>avoids the need to pass</strong> data through <strong>multiple levels of widgets manually.</strong></li><li><strong>Automatic Widget Updates: </strong>When the data inside an InheritedWidget changes, <strong>all the dependent widgets in the widget tree are automatically updated</strong>. This eliminates the need for manual tracking and updating of data across widgets.</li><li><strong>Encapsulation:</strong> InheritedWidget allows you to encapsulate related data and functionality within a single widget, <strong>making it easier to manage and organize your code</strong>. It promotes the separation of concerns and helps improve code maintainability.</li><li><strong>Global Accessibility:</strong> Once an InheritedWidget is placed at the root of the widget tree, its <strong>data can be accessed from any descendant widget in the tree</strong>. This provides global accessibility to the shared data without explicitly passing it around.</li></ol><h4>Disadvantages of using it</h4><ol><li>Limited Scope: The data shared by an InheritedWidget is limited to the widget subtree below it. <strong>If you need to share data across multiple independent widget trees or across different screens</strong>, InheritedWidget alone may not be sufficient, and <strong>you may need to explore other state management solutions.</strong></li><li>Complexity: Understanding and working with InheritedWidget <strong>can be more complex</strong> compared to other state management solutions, especially for beginners. It r<strong>equires a good understanding of the Flutter</strong> <strong>widget lifecycle</strong> and how data flows through the widget tree.</li><li>Potential Performance Impact: Using InheritedWidget <strong>for large</strong> <strong>and frequently changing data</strong> <strong>can potentially impact performance</strong>. Each widget in the widget tree that depends on the InheritedWidget will be rebuilt when the data changes, which can lead to unnecessary rebuilds and affect app performance. In such cases, more optimized state management approaches might be preferred.</li><li>Possible Data Coupling: As the data shared by an InheritedWidget is accessible by any descendant widget,<strong> there is a possibility of unintended coupling between unrelated widgets</strong>. Care should be taken to ensure proper encapsulation and avoid tightly coupling widgets based on shared data.</li></ol><h4>Inherited Widget is Immutable</h4><p>In simpler words, an immutable object is one <strong>that cannot be changed once it is created.</strong> It means that its properties or values cannot be modified or updated.</p><p>In the context of an InheritedWidget, it means that the data or properties it holds cannot be directly modified after the InheritedWidget is created. Once the InheritedWidget is instantiated with certain values, <strong>those values remain the same throughout the lifespan of the widget.</strong></p><p>However, it’s important to note that while the InheritedWidget itself is immutable, <strong>the data it holds can be changed indirectly</strong>. This is typically <strong>done by creating a new instance of the </strong><strong>InheritedWidget with updated data and replacing the old instance with the new one.</strong></p><p>The immutability of an InheritedWidget <strong>ensures that the shared data remains consistent</strong> and avoids unexpected changes that could potentially cause issues in the widget tree.</p><p>In summary, the immutability of an InheritedWidget means that once it is created, its properties and values cannot be directly modified.<strong> It helps maintain the integrity and consistency of shared data in the widget tree.</strong></p><h3>State Management approach</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ux7nlX-9SwdEBfHL9eRp6g.png" /></figure><h4>API Creation</h4><p>To explain the approach of State Management we’ll be developing an application that will call our custom API which is used to get the current date and time with a custom delay of 5 seconds.</p><p><strong>Code Explanation</strong></p><pre>class Api {<br>  String? DateandTime;<br><br>  Future&lt;String&gt; getDateandTime() {<br>    return Future.delayed(<br>      Duration(seconds: 5),<br>      () =&gt; DateTime.now().toIso8601String(),<br>    ).then((value) {<br>      DateandTime = value;<br>      return value;<br>    });<br>  }<br>}</pre><p>The explanation of the code is as follows:</p><ol><li>The Api class is defined with a single property called DateandTime, which is of type String? (nullable String). It represents a date and time value.</li><li>The getDateandTime method is defined within the Api class. It returns a Future&lt;String&gt;, <strong>which means it will provide a </strong><strong>String value asynchronously sometime in the future</strong>.</li><li>Inside the getDateandTime method, a Future is created using the Future.delayed constructor. This creates a delayed future that completes after the specified duration, which in this case is 5 seconds.</li><li>The delayed future’s callback is defined using a lambda function () =&gt; DateTime.now().toIso8601String(). This function retrieves the current date and time using DateTime.now() and converts it to an ISO 8601 string format using toIso8601String().</li><li>The then method is chained to the delayed future. It <strong>takes a callback function that will be executed when the future completes successfully</strong>. In this case, the callback sets the DateandTime property of the Api instance to the obtained value and returns the same value.</li><li>When the getDateandTime method is called and awaited, it will return a future that will eventually complete after the specified delay (5 seconds). Once the future completes, the then callback will be executed, updating the DateandTime property and returning the obtained value.</li></ol><h4>Inherited Widget Creation</h4><p>The Inherited widget is created just the same as the example above. Here we are using a uuid that tells whether the old widget is the same as the current one.</p><pre>class ApiProvider extends InheritedWidget {<br>  final Api api;<br>  final String uuid;<br><br>  ApiProvider({Key? key, required this.api, required Widget child})<br>      : uuid = const Uuid().v4(),<br>        super(<br>          key: key,<br>          child: child,<br>        );<br><br>  @override<br>  bool updateShouldNotify(covariant ApiProvider oldWidget) {<br>    // TODO: implement updateShouldNotify<br>    return uuid != oldWidget.uuid;<br>    throw UnimplementedError();<br>  }<br><br>  static ApiProvider of(BuildContext context) {<br>    return context.dependOnInheritedWidgetOfExactType&lt;ApiProvider&gt;()!;<br>  }<br>}</pre><h4>HomePage Creation</h4><p>Creating the basic design of the application and implementing the use of ApiProvider Inherited Widget.</p><pre>class HomePage extends StatefulWidget {<br>  HomePage({Key? key}) : super(key: key);<br><br>  @override<br>  State&lt;HomePage&gt; createState() =&gt; _HomePageState();<br>}<br><br>class _HomePageState extends State&lt;HomePage&gt; {<br>  ValueKey _textkey = const ValueKey&lt;String?&gt;(null);<br><br>  @override<br>  Widget build(BuildContext context) {<br>    return Scaffold(<br><br>      backgroundColor: Colors.purpleAccent,<br>      appBar: AppBar(<br>        title: Text(<br>          &quot;Date and Time API&quot;,<br>          style: TextStyle(color: Colors.black),<br>        ),<br>      ),<br>      body: GestureDetector(<br>        onTap: () async {<br>          final api = ApiProvider.of(context).api;<br>          final dateandtime = await api.getDateandTime();<br><br>          setState(() {<br>            _textkey = ValueKey(dateandtime);<br>          });<br>        },<br>        child: SizedBox.expand(<br>          child: Container(<br>            color: Colors.purple.shade300,<br>            child: DateTimeWidget(<br>              key: _textkey,<br>            ),<br>            <br>          ),<br>        ),<br>      ),<br>    );<br>  }<br>}</pre><h4>Creating DateTimeWidget</h4><p>Creating the Date and Time widget which displays the actual date and time in separate containers.</p><pre>class DateTimeWidget extends StatelessWidget {<br>  const DateTimeWidget({Key? key}) : super(key: key);<br><br>  @override<br>  Widget build(BuildContext context) {<br>    final api = ApiProvider.of(context).api;<br>    final dateTime =<br>        api.DateandTime != null ? DateTime.parse(api.DateandTime!) : null;<br>    final formattedDate = dateTime != null<br>        ? &#39;${dateTime.day}-${dateTime.month}-${dateTime.year}&#39;<br>        : &#39;&#39;;<br>    final formattedTime = dateTime != null<br>        ? &#39;${dateTime.hour}:${dateTime.minute}:${dateTime.second}&#39;<br>        : &#39;&#39;;<br><br>    return Column(<br>      mainAxisAlignment: MainAxisAlignment.spaceEvenly,<br>      children: [<br>        Container(<br>          height: 100,<br>          width: 250,<br>          decoration: BoxDecoration(<br>              color: Colors.purple,<br>              borderRadius: BorderRadius.circular(20),<br>              border: Border.all(width: 3.0, color: Colors.white)),<br>          child: Center(<br>              child: Text(<br>            formattedDate,<br>            style: TextStyle(<br>                color: Colors.white, fontSize: 26, fontWeight: FontWeight.w600),<br>          ),),<br>        ),<br>        Container(<br>          height: 100,<br>          width: 250,<br>          decoration: BoxDecoration(<br>              color: Colors.purple,<br>              borderRadius: BorderRadius.circular(20),<br>              border: Border.all(width: 3.0, color: Colors.white)),<br>          child: Center(<br>            child: Text(<br>              formattedTime,<br>              style: TextStyle(<br>                  color: Colors.white, fontSize: 26, fontWeight: FontWeight.w600),<br>            ),),<br>        ),<br>      ],<br>    );<br>  }<br>}</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jCmH-vACgF-t2_Q04SGPHQ.png" /></figure><p><strong>Whole Code=&gt;</strong></p><pre>import &#39;package:flutter/material.dart&#39;;<br>import &#39;package:uuid/uuid.dart&#39;;<br><br>void main() {<br>  runApp(const MyApp());<br>}<br><br>class MyApp extends StatelessWidget {<br>  const MyApp({super.key});<br><br>  // This widget is the root of your application.<br>  @override<br>  Widget build(BuildContext context) {<br>    return MaterialApp(<br>      debugShowCheckedModeBanner: false,<br>      title: &#39;Flutter Demo&#39;,<br>      theme: ThemeData(<br>          colorScheme: ColorScheme.fromSeed(seedColor: Colors.deepPurple),<br>          useMaterial3: true,<br>          appBarTheme: const AppBarTheme(<br>            color: Colors.white,<br>          )),<br>      home: ApiProvider(<br>        child: HomePage(),<br>        api: Api(),<br>      ),<br>    );<br>  }<br>}<br><br>class ApiProvider extends InheritedWidget {<br>  final Api api;<br>  final String uuid;<br><br>  ApiProvider({Key? key, required this.api, required Widget child})<br>      : uuid = const Uuid().v4(),<br>        super(<br>          key: key,<br>          child: child,<br>        );<br><br>  @override<br>  bool updateShouldNotify(covariant ApiProvider oldWidget) {<br>    // TODO: implement updateShouldNotify<br>    return uuid != oldWidget.uuid;<br>    throw UnimplementedError();<br>  }<br><br>  static ApiProvider of(BuildContext context) {<br>    return context.dependOnInheritedWidgetOfExactType&lt;ApiProvider&gt;()!;<br>  }<br>}<br><br>class HomePage extends StatefulWidget {<br>  HomePage({Key? key}) : super(key: key);<br><br>  @override<br>  State&lt;HomePage&gt; createState() =&gt; _HomePageState();<br>}<br><br>class _HomePageState extends State&lt;HomePage&gt; {<br>  ValueKey _textkey = const ValueKey&lt;String?&gt;(null);<br><br>  @override<br>  Widget build(BuildContext context) {<br>    return Scaffold(<br><br>      backgroundColor: Colors.purpleAccent,<br>      appBar: AppBar(<br>        title: Text(<br>          &quot;Date and Time API&quot;,<br>          style: TextStyle(color: Colors.black),<br>        ),<br>      ),<br>      body: GestureDetector(<br>        onTap: () async {<br>          final api = ApiProvider.of(context).api;<br>          final dateandtime = await api.getDateandTime();<br><br>          setState(() {<br>            _textkey = ValueKey(dateandtime);<br>          });<br>        },<br>        child: SizedBox.expand(<br>          child: Container(<br>            color: Colors.purple.shade300,<br>            child: DateTimeWidget(<br>              key: _textkey,<br>            ),<br>            // child: Text(&quot;Click me!&quot;),<br>          ),<br>        ),<br>      ),<br>    );<br>  }<br>}<br><br>// class DateTimeWidget extends StatelessWidget {<br>//   const DateTimeWidget({Key? key}) : super(key: key);<br>//<br>//   @override<br>//   Widget build(BuildContext context) {<br>//     final api = ApiProvider.of(context).api;<br>//     return Text(api.DateandTime ?? &quot;Tap on the screen to get date and time&quot;);<br>//   }<br>// }<br><br>class DateTimeWidget extends StatelessWidget {<br>  const DateTimeWidget({Key? key}) : super(key: key);<br><br>  @override<br>  Widget build(BuildContext context) {<br>    final api = ApiProvider.of(context).api;<br>    final dateTime =<br>        api.DateandTime != null ? DateTime.parse(api.DateandTime!) : null;<br>    final formattedDate = dateTime != null<br>        ? &#39;${dateTime.day}-${dateTime.month}-${dateTime.year}&#39;<br>        : &#39;&#39;;<br>    final formattedTime = dateTime != null<br>        ? &#39;${dateTime.hour}:${dateTime.minute}:${dateTime.second}&#39;<br>        : &#39;&#39;;<br><br>    return Column(<br>      mainAxisAlignment: MainAxisAlignment.spaceEvenly,<br>      children: [<br>        Container(<br>          height: 100,<br>          width: 250,<br>          decoration: BoxDecoration(<br>              color: Colors.purple,<br>              borderRadius: BorderRadius.circular(20),<br>              border: Border.all(width: 3.0, color: Colors.white)),<br>          child: Center(<br>              child: Text(<br>            formattedDate,<br>            style: TextStyle(<br>                color: Colors.white, fontSize: 26, fontWeight: FontWeight.w600),<br>          ),),<br>        ),<br>        Container(<br>          height: 100,<br>          width: 250,<br>          decoration: BoxDecoration(<br>              color: Colors.purple,<br>              borderRadius: BorderRadius.circular(20),<br>              border: Border.all(width: 3.0, color: Colors.white)),<br>          child: Center(<br>            child: Text(<br>              formattedTime,<br>              style: TextStyle(<br>                  color: Colors.white, fontSize: 26, fontWeight: FontWeight.w600),<br>            ),),<br>        ),<br>      ],<br>    );<br>  }<br>}<br><br>class Api {<br>  String? DateandTime;<br><br>  Future&lt;String&gt; getDateandTime() {<br>    return Future.delayed(<br>      Duration(seconds: 2),<br>      () =&gt; DateTime.now().toIso8601String(),<br>    ).then((value) {<br>      DateandTime = value;<br>      return value;<br>    });<br>  }<br>}</pre><p>Thanks!</p><p>That’s all💯</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b921451d2530" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Flutter State Management using NotifyListener (inBuilt) — Flutter State Management Series #1]]></title>
            <link>https://medium.com/@itsvinayyay/flutter-state-management-using-notifylistener-inbuilt-flutter-state-management-series-1-8729700e6e34?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/8729700e6e34</guid>
            <category><![CDATA[flutter-app-development]]></category>
            <category><![CDATA[dart]]></category>
            <category><![CDATA[state-management]]></category>
            <category><![CDATA[app-development]]></category>
            <category><![CDATA[flutter]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Fri, 30 Jun 2023 03:47:43 GMT</pubDate>
            <atom:updated>2023-06-30T04:43:34.822Z</atom:updated>
            <content:encoded><![CDATA[<h3>Flutter State Management using ValueNotifier (inBuilt) — Flutter State Management Series #1</h3><p>The first blog in the Flutter State Management series in which we’ll see to update the state of the application using the inbuilt ValueNotifier widget. The approach is simple, straightforward forward, and involves some in-between concepts.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OHNAP1iW3L5gT96_P-UtVw.png" /></figure><p><strong>State Management is the way to glue all the layers of an application together and share the resources within the app or through the database.</strong> The definition can be changed according to the use of State Management across an application.</p><p>The first or fundamental concept of State Management is to achieve the Singleton pattern.</p><h3>What is the Singleton pattern??</h3><p>The Singleton pattern is a design pattern that <strong>restricts the instantiation of a class</strong> to a single object and ensures that <strong>there is only one instance of the class throughout the application</strong>. It provides a <strong>global point of access</strong> to this single instance.</p><blockquote>Here’s an analogy: Let’s say you have a magical cookie jar that contains special cookies. You want everyone in your family to share the same cookies from that jar. So you create a rule that says there can only be one cookie jar in the entire house. Whenever someone wants a cookie, they get it from the same jar.</blockquote><blockquote>In software development,<strong> the Singleton pattern works in a similar way</strong>.<strong> It allows different parts of your code to access the same object, preventing multiple copies of that object from being created.</strong> This can be useful when you want to maintain shared data, resources, or a centralized functionality that needs to be consistent across your application.</blockquote><p>Key characteristics of the Singleton pattern include:</p><ol><li><strong>Single Instance:</strong> The Singleton pattern ensures that there is only one instance of the class created and used throughout the application.</li><li><strong>Global Access:</strong> The single instance is typically accessible from any part of the application, allowing easy and consistent access to its functionality and data.</li><li><strong>Private Constructor:</strong> The Singleton class usually has a private constructor, preventing direct instantiation of the class from outside. This restricts the creation of multiple instances.</li><li><strong>Static Instance:</strong> The Singleton class provides a static method or variable that returns the single instance of the class. This static method or variable allows access to the instance without creating a new one.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cfePG9r_zTYx79wx8khCkw.png" /></figure><h4>How to achieve the Singleton pattern for a class?</h4><p>To achieve the Singleton pattern varies according to different languages but in Dart, the approach is explained below:</p><pre>class ContactBook {<br>  ContactBook._sharedInstance();<br>  static final ContactBook _shared = ContactBook._sharedInstance();<br>  factory ContactBook() =&gt; _shared;<br><br>}</pre><p>The three lines in the above code <strong>make the ContactBook class to be in the Singleton pattern.</strong></p><p>Breaking down the code snippet as:</p><ol><li><strong>ContactBook._sharedInstance();</strong>: This line is invoking the <strong>private named constructo</strong>r _sharedInstance() of the ContactBook class. The constructor is defined with an underscore prefix, indicating that it is private and can only be <strong>accessed within the class</strong> itself.</li><li><strong>static final ContactBook _shared = ContactBook._sharedInstance();</strong>: This line declares a static final variable _shared of type ContactBook. It is assigned the result of invoking the private constructor _sharedInstance(). <strong>This line ensures that a single instance of </strong><strong>ContactBook is created</strong> and stored in the _shared variable.</li><li><strong>factory ContactBook() =&gt; _shared;</strong>: This line defines a factory constructor for the ContactBook class. <strong>A </strong>factory<strong> constructor is a special constructor that can return an instance of a class.</strong> In this case, the factory constructor is defined without any parameters.</li><li>Inside the factory constructor, it returns the shared instance stored in the _shared variable. This means that whenever you call, ContactBook() it will return the same instance ContactBook created in Step 2.</li></ol><p>By using a factory constructor in this way, you can ensure that all requests for creating an instance of ContactBook <strong>will return the same shared instance</strong>, maintaining the singleton behavior.</p><blockquote><strong>A simple State Management can be approached using the Singleton pattern and using the ValueNotifier widget.</strong></blockquote><h3>What is ValueNotifier??</h3><p>It is a simple container that holds a value and notifies its listeners whenever that value changes. The ValueNotifier class provides a straightforward mechanism for <strong>tracking changes to a value</strong> and <strong>notifying interested parts of your application when those changes occur.</strong> It can be particularly useful for updating the user interface in response to changes in data.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Q8Xoq1C1ujjy7u5fMeR_fQ.png" /></figure><p>Imagine you have a variable, let’s call it value, and you want to be notified whenever its value changes. This can be useful when you want to update parts of your application whenever a specific value changes.</p><p>Here’s how it works:</p><ol><li>You create a ValueNotifier object and provide an initial value to it.</li><li>You can<strong> access the current value</strong> of the ValueNotifier using the .value property.</li><li>Whenever <strong>you want to update the valu</strong>e, you assign a new value to the .value property of the ValueNotifier. This triggers a notification to all registered listeners.</li><li>Any code that has registered as a listener for the ValueNotifier will be <strong>notified of the value change</strong>.</li><li>When a listener is notified, <strong>it can respond by performing some action</strong>, such as updating the user interface or executing specific logic.</li></ol><p>Simple Code Snippet to understand ValueNotifier=&gt;</p><pre>void main() {<br>  // Create a ValueNotifier with an initial value of 0<br>  ValueNotifier&lt;int&gt; valueNotifier = ValueNotifier&lt;int&gt;(0);<br><br>  // Register a listener that will be notified of value changes<br>  valueNotifier.addListener(() {<br>    print(&#39;New value: ${valueNotifier.value}&#39;);<br>  });<br><br>  // Update the value<br>  valueNotifier.value = 10;<br>}</pre><p>A simple State Management approach using the Singleton pattern and Value Notifier is implemented in the application.</p><h4><a href="https://github.com/itsvinayyay">itsvinayyay — GitHub</a></h4><p><a href="https://github.com/itsvinayyay/ValueNotifier_SM1">GitHub - itsvinayyay/ValueNotifier_SM1: State Management using Value Notifier is discussed in this repository!</a></p><pre>import &#39;package:flutter/material.dart&#39;;<br>import &#39;package:uuid/uuid.dart&#39;;<br><br>void main() {<br>  runApp(MaterialApp(<br>    title: &quot;Flutter Demo&quot;,<br>    theme: ThemeData(<br>      primarySwatch: Colors.blue,<br>    ),<br>    debugShowCheckedModeBanner: false,<br>    home: const HomePage(),<br>    routes: {<br>      &quot;./NewContact&quot;: (context) =&gt; NewContactView(),<br>    },<br>  ));<br>}<br><br>class Contact {<br>  final String id;<br>  final String name;<br><br>  Contact({required this.name}) : id = const Uuid().v4();<br>}<br><br>class ContactBook extends ValueNotifier&lt;List&lt;Contact&gt;&gt; {<br>  ContactBook._sharedInstance() : super([]);<br><br>  static final ContactBook _shared = ContactBook._sharedInstance();<br><br>  factory ContactBook() =&gt; _shared;<br><br>  int get length =&gt; value.length;<br><br>  void add({required Contact contact}) {<br>    final contacts = value;<br>    contacts.add(contact);<br>    notifyListeners();<br>  }<br><br>  void remove({required Contact contact}) {<br>    final contacts = value;<br>    if(contacts.contains(contact)){<br>      contacts.remove(contact);<br>      notifyListeners();<br>    }<br>  }<br><br>  Contact? contact({required int atIndex}) =&gt;<br>      value.length &gt; atIndex ? value[atIndex] : null;<br>}<br><br>class HomePage extends StatelessWidget {<br>  const HomePage({Key? key}) : super(key: key);<br><br>  @override<br>  Widget build(BuildContext context) {<br>    return Scaffold(<br>      appBar: AppBar(<br>        title: Text(&quot;Home Page&quot;),<br>      ),<br>      backgroundColor: Colors.white,<br>      body: ValueListenableBuilder(<br>        valueListenable: ContactBook(),<br>        builder: (Contact, value, child){<br>          final contacts = value;<br>          return ListView.builder(<br>            itemCount: value.length,<br>            itemBuilder: (context, index) {<br>              final contact = contacts[index];<br>              return Dismissible(<br>                key: ValueKey(contact.id),<br>                onDismissed: (direction){<br>                  // contacts.remove(contact);<br>                  ContactBook().remove(contact: contact);<br>                },<br>                child: Material(<br>                  color: Colors.white,<br>                  elevation: 6.0,<br>                  child: ListTile(<br>                    title: Text(contact.name),<br>                  ),<br>                ),<br>              );<br>            },<br>          );<br>        },<br>      ),<br>      floatingActionButton: FloatingActionButton(<br>        onPressed: () {<br>          Navigator.of(context).pushNamed(&quot;./NewContact&quot;);<br>        },<br>        child: const Icon(Icons.add),<br>      ),<br>    );<br>  }<br>}<br><br>class NewContactView extends StatefulWidget {<br>  const NewContactView({Key? key}) : super(key: key);<br><br>  @override<br>  State&lt;NewContactView&gt; createState() =&gt; _NewContactViewState();<br>}<br><br>class _NewContactViewState extends State&lt;NewContactView&gt; {<br>  late final TextEditingController _controller;<br><br>  @override<br>  void initState() {<br>    // TODO: implement initState<br>    super.initState();<br>    _controller = TextEditingController();<br>  }<br><br>  @override<br>  void dispose() {<br>    // TODO: implement dispose<br>    super.dispose();<br>    _controller.dispose();<br>  }<br><br>  @override<br>  Widget build(BuildContext context) {<br>    return Scaffold(<br>      appBar: AppBar(<br>        title: Text(&quot;Add new Contact&quot;),<br>      ),<br>      body: Column(<br>        children: [<br>          TextField(<br>            controller: _controller,<br>            decoration: InputDecoration(<br>              hintText: &quot;Enter Name&quot;,<br>            ),<br>          ),<br>          ElevatedButton(<br>            onPressed: () {<br>              final contact = Contact(name: _controller.text);<br>              ContactBook().add(contact: contact);<br>              Navigator.of(context).pop();<br>            },<br>            child: Text(&quot;Click Me&quot;),<br>          ),<br>        ],<br>      ),<br>    );<br>  }<br>}</pre><p>Thanks</p><p>That’s all💯</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8729700e6e34" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[CRUD in Cloud-FireStore through Flutter (Dart)]]></title>
            <link>https://medium.com/@itsvinayyay/crud-in-cloud-firestore-through-flutter-dart-d20407a81e70?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/d20407a81e70</guid>
            <category><![CDATA[firestore]]></category>
            <category><![CDATA[flutter-app-development]]></category>
            <category><![CDATA[firebase]]></category>
            <category><![CDATA[flutter]]></category>
            <category><![CDATA[app-development]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Fri, 19 May 2023 03:32:30 GMT</pubDate>
            <atom:updated>2023-05-19T03:32:30.777Z</atom:updated>
            <content:encoded><![CDATA[<p>Create, read, Update, and Delete, or CRUD is the first step to play with a database. FireStore is one of the most potent no-SQL databases and to implement CRUD in it can be quite difficult. This article covers all methods used in Creating, reading, Updating, and Deleting data from Cloud-Firestore.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9tVXrRP0vzLdza1AYWrbTQ.png" /></figure><h3>Create</h3><p>Here <strong>consider that we have given a form</strong> with the fields Name, Age, and email, all we need to do is to store this data in cloud Firestore. This can be done by simply <strong>adding a <em>submit </em>button at the end</strong> of the form with the code given below in its <strong>onpressed</strong>.</p><pre>Map&lt;String, dynamic&gt; data = {<br>  &#39;name&#39;: &#39;John Doe&#39;,<br>  &#39;age&#39;: 25,<br>  &#39;email&#39;: &#39;johndoe@example.com&#39;,<br>};<br><br>await FirebaseFirestore.instance.collection(&#39;users&#39;).add(data);</pre><p>Here Firebase abstractly is doing the conversion of the dart code to JSON and then putting it into its document.</p><p>Or one can simply use the traditional way of storing the data as:</p><pre>final docUser = FirebaseFireStore.instance.document(&#39;Users&#39;).doc(&#39;id-here&#39;);<br>final json = {<br>  &#39;name&#39;: &#39;John Doe&#39;,<br>  &#39;age&#39;: 25,<br>  &#39;email&#39;: &#39;johndoe@example.com&#39;,<br>};<br><br>await docUser.set(json);</pre><p>Here the .doc method at the of docUser provides the custom id to the document.</p><h3>Read</h3><p>Read functionality can be divided broadly into two types one with a subscription and the other one without a subscription.</p><h4>Without Subscription</h4><pre>void getmessages() async{<br>  final data = await FirebaseFirestore.instance.collection(&#39;Users&#39;).getDocuments();<br>  for (var dataset in data.documents){<br>    print(dataset.data);<br>  }<br>}</pre><p>Here the function <strong>needs to be called every time</strong> the user needs to detect a change in the database. This can be used with a <a href="https://api.flutter.dev/flutter/widgets/FutureBuilder-class.html"><strong>Future builder</strong></a> which will show the changes to the application.</p><h4>With Subscription</h4><pre>void getmessages()async{<br>  await for (var snapshots in FirebaseFirestore.instance.collection(&#39;Users&#39;).snapshots()){<br>    for (var dataset in snapshots.documents){<br>    print(dataset.data);<br>    }<br>  }<br>}</pre><p>Here we have a stream that will <strong>notify us whenever a change is made</strong> to the cloud firestore database.</p><p>Here we’re just printing the stream into the <strong>Run console</strong> we don’t need to rebuild anything on the actual application screen whenever there’s a change.</p><p>If there’s a change every time and the user wants to see the actual changes on the device screen then the following code may help.</p><pre>class Product {<br>  late String image_url;<br>  late String description;<br>  late String product_name;<br>  late String product_price;<br>  late VoidCallback? ontap;<br><br>  Product({required this.image_url,<br>    required this.description,<br>    required this.product_name,<br>    this.ontap,<br>    required this.product_price});<br>}</pre><p>Here is the data structure that we want to retrieve from our cloud-firestore.</p><pre>class ProductService {<br>  final _firestore = FirebaseFirestore.instance.collection(&quot;Products&quot;);<br><br>  Stream&lt;List&lt;Product&gt;&gt; getProductsList() {<br>    return _firestore.snapshots().map((snapshot) {<br>      return snapshot.docs.map((doc) {<br>        return Product(<br>          image_url: doc[&#39;ImageURL&#39;],<br>          description: doc[&#39;Description&#39;],<br>          product_name: doc[&#39;Name&#39;],<br>          product_price: doc[&#39;Price&#39;],<br>        );<br>      }).toList();<br>    });<br>  }<br>}</pre><p>Here, we’re creating a stream that will <strong>return the list of products</strong> from the database. This stream will be <strong>passed into the </strong><a href="https://api.flutter.dev/flutter/widgets/StreamBuilder-class.html"><strong>Stream builder</strong></a> which listens to the stream whenever there&#39;s an update.</p><pre>class buildProduct_Carousel extends StatelessWidget {<br>  @override<br>  Widget build(BuildContext context) {<br>    return StreamBuilder&lt;List&lt;Product&gt;&gt;(<br>      stream: ProductService().getProductsList(),<br>      builder: (context, snapshot) {<br>        if (snapshot.hasData) {<br>          List&lt;Product&gt; Details = snapshot.data!;<br>          return PageView(<br>            scrollDirection: Axis.horizontal,<br>            physics: BouncingScrollPhysics(),<br>            children: [<br>              ...List.generate(<br>                Details.length,<br>                    (index) =&gt; buildShoe_Card(<br>                  image_url: Details[index].image_url,<br>                  description: Details[index].description,<br>                  Shoe_name: Details[index].product_name,<br>                  on_tap: () {},<br>                  Shoe_price: Details[index].product_price,<br>                ),<br>              ),<br>            ],<br>          );<br>        } else if (snapshot.hasError) {<br>          return Text(&quot;${snapshot.error}&quot;);<br>        }<br><br>        return Center(child: CircularProgressIndicator());<br>      },<br>    );</pre><h3>Update</h3><p>An update can be used to update a particular field in a document.</p><pre>docUser.update({<br>  &#39;name&#39; = &#39;Raghav&#39;,<br> });</pre><p>Always <strong>remember to use only update</strong> and not to use set <strong>as this will delete the whole structure</strong> in the cloud and just take only the argument provided.</p><h3>Delete</h3><p>The delete method is used along with the update as below:</p><pre>docUser.update({<br>  &#39;name&#39; = FieldValue.delete(),<br> });</pre><p>this will <strong>delete the name field from the selected document</strong>.</p><p>That’s all💯</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d20407a81e70" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Heaps Placement Questions]]></title>
            <link>https://medium.com/@itsvinayyay/heaps-placement-questions-ae45a51897ab?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/ae45a51897ab</guid>
            <category><![CDATA[cplusplus]]></category>
            <category><![CDATA[heap]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[placement]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Mon, 24 Apr 2023 03:46:53 GMT</pubDate>
            <atom:updated>2023-04-24T03:46:53.373Z</atom:updated>
            <content:encoded><![CDATA[<p>The basics of Heaps had been discussed in the last article and now some of the most straightforward questions based on the concept will be covered in this one.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OKOf9BDRqUGvZvgN7dOhww.png" /></figure><h3>Question 1: Kth Smallest element in an array.</h3><h4>Given an array <strong>arr[]</strong> and an integer <strong>K</strong> where K is smaller than the size of the array, the task is to find the <strong>Kth smallest</strong> element in the given array. It is given that all array elements are distinct.</h4><h4><strong>Note</strong>:- <strong>l</strong> and <strong>r</strong> denote the <strong>starting</strong> and <strong>ending</strong> index of the array.</h4><p><strong>Example 1:</strong></p><pre>Input:<br>N = 6<br>arr[] = 7 10 4 3 20 15<br>K = 3<br>Output : 7<br>Explanation :<br>3rd smallest element in the given <br>array is 7.</pre><h3>Solution:</h3><p>Method:</p><ol><li>Create a max heap and add the elements of the array till k.</li><li>Now add the rest of the elements only if the <strong>current element</strong> is smaller than the <strong>top element</strong> of the max heap.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*j2ez2FNgxUqNI0mmpCifww.png" /><figcaption>The kth Smallest element in an array</figcaption></figure><pre>class Solution{<br>    public:<br>    // arr : given array<br>    // l : starting index of the array i.e 0<br>    // r : ending index of the array i.e size-1<br>    // k : find kth smallest element and return using this function<br>    int kthSmallest(int arr[], int l, int r, int k) {<br>        priority_queue&lt;int&gt; pq;<br><br>        for(int i=l; i&lt;k; i++){<br>            pq.push(arr[i]);<br>        }<br><br><br>        for(int i=k; i&lt;=r; i++){<br>            if(arr[i]&lt;pq.top()){<br>                pq.pop();<br>                pq.push(arr[i]);<br>            }<br>        }<br><br>        return pq.top();<br>    }<br>};</pre><p>Question link➡️ <a href="https://practice.geeksforgeeks.org/problems/kth-smallest-element5635/1">https://practice.geeksforgeeks.org/problems/kth-smallest-element5635/1</a></p><h3>Question 2: Is Binary Tree a heap</h3><h4>Given a binary tree. The task is to check whether the given tree follows the <strong>max heap</strong> property or not.<br><strong>Note: </strong>Properties of a tree to be a max heap — Completeness and Value of node greater than or equal to its child.</h4><p><strong>Example 1:</strong></p><pre>Input:<br>      5<br>    /  \<br>   2    3<br>Output: 1<br>Explanation: The given tree follows max-heap property since 5,<br>is root and it is greater than both its children.</pre><h3>Solution:</h3><p>Method:</p><ol><li>Check for both Complete Binary Tree and MaxOrder properties in separate bool type functions.</li><li>In the CBT function, ensure that the index does not exceed the Total Count of the nodes.</li><li>In the MaxOrder property function, ensure that both the children of the roots are smaller.</li></ol><pre>struct Node {<br>    int data;<br>    Node *left;<br>    Node *right;<br><br>    Node(int val) {<br>        data = val;<br>        left = right = NULL;<br>    }<br>};<br><br>class Solution {<br>    int NodeCount(Node *tree){<br>        if(tree==NULL){<br>            return 0;<br>        }<br><br>        return NodeCount(tree-&gt;left) + NodeCount(tree-&gt;right) + 1;<br>    }<br><br>    bool isCBT(Node *tree, int index, int n){<br>        if(tree==NULL){<br>            return true;<br>        }<br>        else if(index &gt;= n){<br>            return false;<br>        }<br>        else{<br>            bool left = isCBT(tree-&gt;left, 2 * index + 1, n);<br>            bool right = isCBT(tree-&gt;right, 2 * index + 2, n);<br>            return left &amp;&amp; right; <br>        }<br>    }<br><br><br>    bool isMaxHeap(Node *root){<br>        if(root-&gt;left==NULL &amp;&amp; root-&gt;right==NULL){<br>            return true;<br>        }<br>        if(root-&gt;right == NULL){<br>            if(root-&gt;data &gt; root-&gt;left-&gt;data){<br>                return true;<br>            }<br>            return false;<br>        }<br>        else{<br>            if((root-&gt;data &gt; root-&gt;left-&gt;data) &amp;&amp; (root-&gt;data &gt; root-&gt;right-&gt;data) &amp;&amp; isMaxHeap(root-&gt;left) &amp; isMaxHeap(root-&gt;right)){<br>                return true;<br>            }<br>            return false;<br>        }<br>    }<br>  public:<br>    bool isHeap(struct Node* tree) {<br>        int n = NodeCount(tree);<br>        if(isCBT(tree, 0, n) &amp;&amp; isMaxHeap(tree)){<br>            return true;<br>        }<br>        return false;<br>    }<br>};<br><br></pre><p>Question link➡️ <a href="https://practice.geeksforgeeks.org/problems/is-binary-tree-heap/1">https://practice.geeksforgeeks.org/problems/is-binary-tree-heap/1</a></p><h3>Question 3: Merge two binaryMax Heaps</h3><p>Given two binary max heaps as arrays, merge the given heaps to form a new max heap.</p><p><strong>Example 1:</strong></p><pre>Input  : <br>n = 4 m = 3<br>a[] = {10, 5, 6, 2}, <br>b[] = {12, 7, 9}<br>Output : <br>{12, 10, 9, 2, 5, 7, 6}<br>Explanation :</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/327/0*Fqdl0tZumNF0HW4A.jpg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/232/0*I6fJ7p8HeYTCnlhD.jpg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/0*nrzHrNmmsZ3ltBdq.jpg" /></figure><h3>Solution:</h3><pre>class Solution<br>{<br>    void Heapify(vector&lt;int&gt; &amp;c, int index)<br>    {<br>        int largest = index;<br>        int left = 2 * index + 1;<br>        int right = 2 * index + 2;<br><br>        if (left &lt; c.size() &amp;&amp; c[left] &gt; c[largest])<br>        {<br>            largest = left;<br>        }<br>        if (right &lt; c.size() &amp;&amp; c[right] &gt; c[largest])<br>        {<br>            largest = right;<br>        }<br><br>        if (largest != index)<br>        {<br>            swap(c[largest], c[index]);<br>            Heapify(c, largest);<br>        }<br>    }<br><br>public:<br>    vector&lt;int&gt; mergeHeaps(vector&lt;int&gt; &amp;a, vector&lt;int&gt; &amp;b, int n, int m)<br>    {<br>        vector&lt;int&gt; c;<br>        for (int i = 0; i &lt; n; i++)<br>        {<br>            c.push_back(a[i]);<br>        }<br><br>        for (int i = 0; i &lt; m; i++)<br>        {<br>            c.push_back(b[i]);<br>        }<br><br>        for (int i = ((c.size() / 2) - 1); i &gt;=0 ; i--)<br>        {<br>            Heapify(c, i);<br>        }<br>        return c;<br>    }<br>};</pre><p>Question link➡️ <a href="https://practice.geeksforgeeks.org/problems/merge-two-binary-max-heap0144/1">https://practice.geeksforgeeks.org/problems/merge-two-binary-max-heap0144/1</a></p><h3>Question 4: Minimum Cost of Ropes</h3><h4>There are given <strong>N</strong> ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to the sum of their lengths. The task is to connect the ropes at a minimum cost. Given <strong>N</strong> size array <strong>arr[]</strong> contains the lengths of the ropes.</h4><p><strong>Example 1:</strong></p><pre>Input:<br>n = 4<br>arr[] = {4, 3, 2, 6}<br>Output: <br>29<br>Explanation:<br>We can connect the ropes in following ways.<br>1) First connect ropes of lengths 2 and 3.<br>Which makes the array {4, 5, 6}. Cost of<br>this operation 2+3 = 5. <br>2) Now connect ropes of lengths 4 and 5.<br>Which makes the array {9, 6}. Cost of<br>this operation 4+5 = 9.<br>3) Finally connect the two ropes and all<br>ropes have connected. Cost of this <br>operation 9+6 =15<br>Total cost for connecting all ropes is 5<br>+ 9 + 15 = 29. This is the optimized cost<br>for connecting ropes. <br>Other ways of connecting ropes would always <br>have same or more cost. For example, if we <br>connect 4 and 6 first (we get three rope of 3,<br>2 and 10), then connect 10 and 3 (we get<br>two rope of 13 and 2). Finally we<br>connect 13 and 2. Total cost in this way<br>is 10 + 13 + 15 = 38.</pre><h3>Solution:</h3><p>Approach:</p><ol><li>Just add the minimum 2 lengths of two ropes (which can be achieved by using a Min Heap).</li><li>Push the added value into the heap again and also store it in a variable.</li><li>At last, return that variable.</li></ol><pre>class Solution<br>{<br>    public:<br>    //Function to return the minimum cost of connecting the ropes.<br>    long long minCost(long long arr[], long long n) {<br>        priority_queue&lt;long long int, vector&lt;long long int&gt;, greater&lt;long long int&gt;&gt; pq;<br><br>        for(int i=0; i&lt;n; i++){<br>            pq.push(arr[i]);<br>        }<br>        int size = n;<br>        long long sum = 0;<br><br>        while(size&gt;1){<br>            long long int element1 = pq.top();<br>            pq.pop();<br>            long long int element2 = pq.top();<br>            pq.pop();<br>            long long int result = element1 + element2;<br>            sum+=result;<br>            pq.push(result);<br>            size--;<br>        }<br><br>        return sum;<br>    }<br>};</pre><p>Question link➡️ <a href="https://practice.geeksforgeeks.org/problems/minimum-cost-of-ropes-1587115620/1">https://practice.geeksforgeeks.org/problems/minimum-cost-of-ropes-1587115620/1</a></p><h3>Question 5: K-th Largest Sum Contiguous Subarray</h3><h4>You are given an array <strong>Arr</strong> of size <strong>N</strong>. You have to find the <strong>K</strong>-th <strong>largest</strong> sum of contiguous <strong>subarray</strong> within the array elements.</h4><p><strong>Example 1:</strong></p><pre>Input:<br>N = 3<br>K = 2<br>Arr = {3,2,1}<br>Output:<br>5<br>Explanation:<br>The different subarray sums we can get from the array<br>are = {6,5,3,2,1}. Where 5 is the 2nd largest.</pre><h3>Solution:</h3><ol><li>Record all sub-array sums into another vector.</li><li>Insert this vector into a Min-Heap and solve just like <strong>Question 1</strong>.</li></ol><pre>class Solution{<br>public:<br>    int kthLargest(vector&lt;int&gt; &amp;arr,int n,int K){<br>        vector&lt;int&gt; subarrays;<br><br>        for(int i=0; i&lt;n; i++){<br>            int sum = arr[i];<br>            subarrays.push_back(sum);<br>            for(int j=i+1; j&lt;n; j++){<br>                sum += arr[j];<br>                subarrays.push_back(sum);<br>            }<br>        }<br><br>        priority_queue&lt;int, vector&lt;int&gt;, greater&lt;int&gt;&gt; pq;<br><br><br>        for(int i=0; i&lt;K; i++){<br>            pq.push(subarrays[i]);<br>        }<br><br>        for(int i=K; i&lt;subarrays.size(); i++){<br>            if(subarrays[i]&gt;pq.top()){<br>                pq.pop();<br>                pq.push(subarrays[i]);<br>            }<br>        }<br><br>        return pq.top();<br>    }<br>};</pre><p>Question link➡️<a href="https://practice.geeksforgeeks.org/problems/k-th-largest-sum-contiguous-subarray/1">https://practice.geeksforgeeks.org/problems/k-th-largest-sum-contiguous-subarray/1</a></p><h3>Question 6: Merge K-Sorted Arrays</h3><h4>Given <strong>K</strong> sorted arrays arranged in the form of a matrix of size K*K. The task is to merge them into one sorted array.<br><strong>Example 1:</strong></h4><pre>Input:<br>K = 3<br>arr[][] = {{1,2,3},{4,5,6},{7,8,9}}<br>Output: 1 2 3 4 5 6 7 8 9<br>Explanation:Above test case has 3 sorted<br>arrays of size 3, 3, 3<br>arr[][] = [[1, 2, 3],[4, 5, 6], <br>[7, 8, 9]]<br>The merged list will be <br>[1, 2, 3, 4, 5, 6, 7, 8, 9].</pre><h3>Solution:</h3><p>Method:</p><ol><li>Create a datatype <strong>in order to segregate</strong> each data block of the vector-matrix given.</li><li>Create a <strong>Compare (operator type function)</strong> to store the datatype in the Minheap.</li><li>Now store the first element of the given vectors in the MinHeap. <strong>Iterate over the rows for this with the column value set to 0.</strong></li><li>Now <strong>add the top of the MinHeap</strong> into an Answer vector (to be returned). Further, pop that element from the MinHeap.</li><li>After that just, <strong>insert the next element of the same array</strong> (of which the <strong>first element is inserted into the answer vector</strong> through the MinHeap’s top) into the MinHeap, if present.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9tC2vown1Wo5PpznmAlq2A.png" /><figcaption>Merge K-Sorted Arrays</figcaption></figure><pre>class Node{<br>    public:<br>    int data;<br>    int col;<br>    int row;<br><br>    Node(int data, int i, int j){<br>        this-&gt;data = data;<br>        row = i;<br>        col = j;<br>    }<br>};<br><br>class compare{<br>    public:<br>    bool operator()(Node *a, Node *b){<br>        return a-&gt;data&gt;b-&gt;data;<br>    }<br>};<br><br><br><br>class Solution<br>{<br>    public:<br>    //Function to merge k sorted arrays.<br>    vector&lt;int&gt; mergeKArrays(vector&lt;vector&lt;int&gt;&gt; arr, int K)<br>    {<br>        priority_queue&lt;Node*, vector&lt;Node*&gt;, compare&gt; pq;<br><br>        for(int i=0; i&lt;K; i++){<br>            Node *temp = new Node(arr[i][0], i, 0);<br>            pq.push(temp);<br>        }<br><br>        vector&lt;int&gt; Answer;<br><br><br>        while(pq.size()&gt;0){<br>            Node *temp = pq.top();<br>            Answer.push_back(pq.top()-&gt;data);<br>            pq.pop();<br><br>            int sel_row = temp-&gt;row;<br>            int sel_col = temp-&gt;col;<br><br>            if(sel_col + 1&lt;arr[sel_row].size()){<br>                Node *next = new Node(arr[sel_row][sel_col + 1], sel_row, sel_col + 1);<br>                pq.push(next);<br>            }<br><br>        }<br><br>        return Answer;<br>    }<br>};</pre><p>Question link➡️<a href="https://practice.geeksforgeeks.org/problems/merge-k-sorted-arrays/1">https://practice.geeksforgeeks.org/problems/merge-k-sorted-arrays/1</a></p><h3>Question 7: Merge K-Sorted Linked Lists</h3><h4>Given <strong>K</strong> sorted linked lists of different sizes. The task is to merge them in such a way that after merging they will be a single sorted linked list.</h4><p><strong>Example 1:</strong></p><pre>Input:<br>K = 4<br>value = {{1,2,3},{4 5},{5 6},{7,8}}<br>Output: 1 2 3 4 5 5 6 7 8<br>Explanation:<br>The test case has 4 sorted linked <br>list of size 3, 2, 2, 2<br>1st    list     1 -&gt; 2-&gt; 3<br>2nd   list      4-&gt;5<br>3rd    list      5-&gt;6<br>4th    list      7-&gt;8<br>The merged list will be<br>1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;5-&gt;6-&gt;7-&gt;8.</pre><h3>Solution:</h3><p>Same like the previous one just use the Linked Lists concept.</p><pre>class Node<br>{<br>public:<br>    int data;<br>    Node *next;<br><br>    Node(int val)<br>    {<br>        data = val;<br>        next = NULL;<br>    }<br>};<br><br>class compare{<br>    public:<br>    bool operator()(Node *a, Node *b){<br>        return a-&gt;data &gt; b-&gt;data;<br>    }<br>};<br><br>class Solution<br>{<br>public:<br>    // Function to merge K sorted linked list.<br>    Node *mergeKLists(Node *arr[], int K)<br>    {<br>        priority_queue&lt;Node*, vector&lt;Node*&gt;, compare&gt; pq;<br><br><br>        for(int i=0; i&lt;K; i++){<br>            Node *temp = arr[i];<br>            pq.push(temp);<br>        }<br>        Node *result = new Node(0);<br>        Node *iterator = result;<br><br>        while(!pq.empty()){<br>            Node *temp = pq.top();<br>            iterator-&gt;next = pq.top();<br>            pq.pop();<br><br>            if(temp-&gt;next!=NULL){<br>                pq.push(temp-&gt;next);<br>            }<br>            iterator = iterator-&gt;next;<br>        }<br><br>        return result-&gt;next;<br>    }<br>};</pre><p>Question link➡️ <a href="https://practice.geeksforgeeks.org/problems/merge-k-sorted-linked-lists/1">https://practice.geeksforgeeks.org/problems/merge-k-sorted-linked-lists/1</a></p><h3>Question 8: <strong>Smallest range in K lists</strong></h3><h4>Given <strong>K</strong> sorted lists of integers, <strong>KSortedArray[]</strong> of size <strong>N</strong> each. The task is to find the smallest range that includes at least one element from each of the <strong>K</strong> lists. If more than one such range is found, return the first such range found.</h4><p><strong>Example 1:</strong></p><pre>Input:<br>N = 5, K = 3<br>KSortedArray[][] = {{1 3 5 7 9},<br>                    {0 2 4 6 8},<br>                    {2 3 5 7 11}}<br>Output: 1 2<br>Explanation: K = 3<br>A:[1 3 5 7 9]<br>B:[0 2 4 6 8]<br>C:[2 3 5 7 11]<br>Smallest range is formed by number 1<br>present in first list and 2 is present<br>in both 2nd and 3rd list.</pre><h3>Solution:</h3><ol><li>The question is similar to Question No. 6, but just takes care of the minimum and maximum values which serve as the Starting and Ending points of the range.</li><li>The minimum element will get updated at the top of the Min Heap. On the other hand, the Max element will be initialized as the maximum of the first column of the 2x2 matrix. The Min element will also be initialized as the minimum element among the first column elements.</li></ol><pre>for(int i=0; i&lt;k; i++){<br>            Node *temp = new Node(arr[i][0], i, 0);<br>            max_element = max(max_element, temp-&gt;data);<br>            min_element = min(min_element, temp-&gt;data);<br><br>            pq.push(temp);<br>        }</pre><pre>Node *temp = pq.top();<br>            pq.pop();<br>            min_element = temp-&gt;data;</pre><p>3. Subsequently, the Max element will get updated as the maximum value next to the element at the top of the min heap.</p><pre>if((temp-&gt;cols + 1) &lt; n){<br>                Node *next = new Node(arr[temp-&gt;rows][temp-&gt;cols + 1], temp-&gt;rows, temp-&gt;cols + 1);<br>                max_element = max(max_element, arr[temp-&gt;rows][temp-&gt;cols + 1]);<br>                pq.push(next);<br>            }</pre><p>4. In between also compare the minimum range which needs to be returned.</p><pre>if(max_element - min_element &lt; end - start){<br>                start = min_element;<br>                end = max_element;<br>            }</pre><pre>class Node{<br>    public:<br>    int data;<br>    int cols;<br>    int rows;<br><br>    Node(int data, int i, int j){<br>        this-&gt;data = data;<br>        rows = i;<br>        cols = j;<br>    }<br>};<br><br>class compare{<br>    public:<br>    bool operator()(Node *a, Node *b){<br>        return a-&gt;data &gt; b-&gt;data;<br>    }<br>};<br><br>class Solution{<br>    public:<br>    pair&lt;int,int&gt; findSmallestRange(int arr[][N], int n, int k)<br>    {<br>        priority_queue&lt;Node*, vector&lt;Node*&gt;, compare&gt; pq;<br>        int max_element = INT_MIN;<br>        int min_element = INT_MAX;<br>        pair&lt;int, int&gt; Answer;<br><br><br>        for(int i=0; i&lt;k; i++){<br>            Node *temp = new Node(arr[i][0], i, 0);<br>            max_element = max(max_element, temp-&gt;data);<br>            min_element = min(min_element, temp-&gt;data);<br><br>            pq.push(temp);<br>        }<br><br>        int start = min_element, end = max_element;<br><br><br>        while(!pq.empty()){<br><br>            Node *temp = pq.top();<br>            pq.pop();<br>            min_element = temp-&gt;data;<br><br>            if(max_element - min_element &lt; end - start){<br>                start = min_element;<br>                end = max_element;<br>            }<br>            if((temp-&gt;cols + 1) &lt; n){<br>                Node *next = new Node(arr[temp-&gt;rows][temp-&gt;cols + 1], temp-&gt;rows, temp-&gt;cols + 1);<br>                max_element = max(max_element, arr[temp-&gt;rows][temp-&gt;cols + 1]);<br>                pq.push(next);<br>            }<br>            else{<br>                break;<br>            }<br>        }<br>        Answer = make_pair(start, end);<br>        return Answer;<br>    }<br>};</pre><p>Question link➡️ <a href="https://practice.geeksforgeeks.org/problems/find-smallest-range-containing-elements-from-k-lists/1">https://practice.geeksforgeeks.org/problems/find-smallest-range-containing-elements-from-k-lists/1</a></p><p>For detailed explainations➡️</p><ol><li><a href="https://youtu.be/_9F2VgZcvdw">https://youtu.be/_9F2VgZcvdw</a></li><li><a href="https://youtu.be/eccAKrmffh8">https://youtu.be/eccAKrmffh8</a></li><li><a href="https://youtu.be/RrxpTWqj97A">https://youtu.be/RrxpTWqj97A</a></li></ol><p>That’s all 💯</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ae45a51897ab" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[HashMaps in C++]]></title>
            <link>https://medium.com/@itsvinayyay/hashmaps-in-c-f9da8651dcff?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/f9da8651dcff</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[hashmap]]></category>
            <category><![CDATA[hashing]]></category>
            <category><![CDATA[cplusplus]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Fri, 14 Apr 2023 11:27:49 GMT</pubDate>
            <atom:updated>2023-04-14T11:27:49.749Z</atom:updated>
            <content:encoded><![CDATA[<p>HashMaps or Hashing is a data structure that stores values as a key-value pair. It uses HashTable to map the values in the form of indexes, these HashTable indexes can be used to store values later.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HOopQMBONtsQ1_NJiEQ7WQ.png" /></figure><h3>Insertion</h3><p>Insertion takes O(LogN) time in the case of a<em> map</em> and <em>unorderd_map </em>takes O(N) time.</p><p><strong>unordered_map&lt;string, int&gt; map;</strong></p><p>Three ways to insert an element into a Hashmap are:</p><ol><li>By making a Pair</li></ol><pre>Pair&lt;string, int&gt; p = make_pair(“entry”, 3); <br>map.insert(p);</pre><p>2. By making a pair (method 2)</p><pre>Pair&lt;string, int&gt; p2(&quot;insert&quot;, 2);<br>map.insert(p2);</pre><p>3. By direct insertion</p><pre>map[&quot;insert&quot;] = 5;</pre><p>Note: There’s always only one entry corresponding to a particular key. And if there are 2 collision happens (discussed later).</p><h3>Searching</h3><p>Searching in a HashMap can be done in the following ways:</p><ol><li>Direct search</li></ol><pre> cout &lt;&lt; map[&quot;insert&quot;] &lt;&lt; endl;</pre><p><strong>Output:</strong></p><p>2</p><p>2. Using <em>at </em>function</p><pre>cout &lt;&lt; map.at(&quot;entry&quot;) &lt;&lt; endl;</pre><p><strong>Output:</strong></p><p>3</p><h4>Difference between <em>Direct search and using the ‘at’ function</em></h4><p>When directly searched and the element is not present in the HashMap, <strong>a new count is created for the value</strong> but when searched with the ‘at<em>’ </em>function <strong>it displays the ‘<em>key not found’</em></strong><em>.</em></p><h3>Deletion</h3><pre>map.erase(&quot;insert&quot;);</pre><h3>Iteration</h3><p>Iteration in a HashMap can be done by two of the following methods.</p><p><strong>Method 1.</strong> By defining the iterator.</p><pre>unordered_map&lt;string, int&gt; :: iterator it = m.begin();<br>while(it!=m.end()){<br>  cout&lt;&lt;it-&gt;first&lt;&lt;it-&gt;second&lt;&lt;endl;<br>}</pre><p><strong>Method 2.</strong> By using an auto operator.</p><pre>for(auto i:m){<br>cout&lt;&lt;i-&gt;first&lt;&lt;i-&gt;second&lt;&lt;endl;<br>}</pre><h3>Bucket Array</h3><p>The value when inserted into a HashMap is stored in a Bucket. The value in the Bucket is stored using the key-to-value conversion done by the HashCode function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EXVN31VLLZPlKC7jOZKIHA.png" /></figure><p>A bucket array combines Linked Lists and arrays, where every first element is the head of the Linked List in a particular array location. <strong>In order to increase the efficiency</strong> while searching, inserting, and deleting, <strong>the main aim is to weaken or reduce the number of Nodes</strong> formed in linked Lists this can be <strong>achieved by designing a suitable HashCode</strong>.</p><h3>HashCode</h3><p>HashCode is used <strong>to compute indexes of the keys given</strong> and therefore, is used to <strong>map elements into a HashTable</strong>, and further the mapped indexes are<strong> used to store elements into a Bucket array.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vxb7zJJsrlviVWTlVZR56A.png" /></figure><h3>Collision Case</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*69ZWIhrYGmhbxIFgOgjbyg.png" /></figure><h3>Collision Handling</h3><p>A collision can be handled by using two methods, these are:</p><ol><li>Separate chaining or Open Hashing</li><li>Open Addressing or Closed Hashing</li></ol><h4>Separate Chaining</h4><p>Separate chaining is a method in which<strong> if two or more elements land into the same slot of an array</strong>, then a <strong>linked list is created</strong> <strong>at that location</strong> of the array in order to store the elements.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aWtEa1tWURQS9VhYkDdy1g.png" /></figure><p>In order to search an element in separate chaining the linked list is linearly traversed(if two or more similar elements are present in an array).</p><p><strong>Advantages</strong></p><ol><li>Useful when the number of insertions and deletions of elements is uncertain.</li><li>No need to add more space to Hash Table as more nodes can be created.</li><li>Simple to implement.</li></ol><p><strong>Disadvantages</strong></p><ol><li>Links use extra space.</li><li>Some space in the Hash Table is wasted as it never gets used.</li><li>Also, if the length of Linked lists is increased by a significant amount, the time complexity for inserting, deletion, and searching will also get increased.</li><li>Cache performance is less as compared to Open Addressing.</li></ol><h4>Open Addressing</h4><p>Open Addressing is also a solution to the collision problem, but unlike Separate chaining, the elements are stored in the same Hash Table. This can be done by assigning other indexes to similar elements.</p><p>Hi(a) = h(a) + Fi(a)</p><p>This assignment of indexes to two similar elements can have multiple ways to do so.</p><ol><li>Linear Probing</li><li>Quadratic Probing</li></ol><p><strong>Linear Probing</strong></p><p>In this type of probing similar elements are stored adjacent to each other.</p><p>value of F(i) = i.</p><p>For more information: <a href="https://www.geeksforgeeks.org/open-addressing-collision-handling-technique-in-hashing/#:~:text=of%20Open%20Addressing%3A-,1.%20Linear%20Probing%3A%C2%A0,-In%20linear%20probing">https://www.geeksforgeeks.org/open-addressing-collision-handling-technique-in-hashing/#:~:text=of%20Open%20Addressing%3A-,1.%20Linear%20Probing%3A%C2%A0,-In%20linear%20probing</a></p><p><strong>Quadratic Probing</strong></p><p>In this, similar elements are usually stored at a distance.</p><p>value of of F(i) = i²</p><p>For more information: <a href="https://www.geeksforgeeks.org/open-addressing-collision-handling-technique-in-hashing/#:~:text=2.%20Quadratic%20Probing%C2%A0">https://www.geeksforgeeks.org/open-addressing-collision-handling-technique-in-hashing/#:~:text=2.%20Quadratic%20Probing%C2%A0</a></p><h3>Complexity Analysis</h3><p>Complexity analysis for the two types of collision prevention techniques is as follows.</p><h4>Separate chaining</h4><p>Time complexity is O(1) as</p><p>Let&#39;s assume n= no. of entries in a map, b = boxes available.</p><p>Therefore, the number of entries in the box = n/b, this is also known as load factor. And it is always ensured to be less than 0.7.</p><h4>Open Addressing</h4><p>Time complexity for insertion is O(k) or O(1), {if n&gt;&gt;k}</p><p>where<em> n = Total number of words </em>and<em> k = word length.</em></p><p>For more information➡️ <a href="https://www.youtube.com/watch?v=7mUKGHznpfg&amp;pp=ygUSaGFzaG1hcHMgY29kZSBoZWxw">https://www.youtube.com/watch?v=7mUKGHznpfg&amp;pp=ygUSaGFzaG1hcHMgY29kZSBoZWxw</a></p><p>That’s all! 💯</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f9da8651dcff" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Heaps in C++]]></title>
            <link>https://medium.com/@itsvinayyay/heaps-in-c-ded6084eaea7?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/ded6084eaea7</guid>
            <category><![CDATA[heapsort]]></category>
            <category><![CDATA[cplusplus]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[heap]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Mon, 13 Mar 2023 04:24:45 GMT</pubDate>
            <atom:updated>2023-04-13T14:30:05.006Z</atom:updated>
            <content:encoded><![CDATA[<p>Heaps are one of the essential concepts in placement drives and also in Competitive programming. Other than that it also, helps to understand basic implementation on the development side.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rI_Q8umU5hsiyiT9eq-6cQ.png" /></figure><p>Heaps are mainly used in essential algorithms such as Dijkstra’s, Heap Sort, etc. It also helps in implementing priority queues.</p><p>Heaps involves the following sub-topics.</p><ol><li>Understanding Heaps</li><li>Heap Class Creation</li><li>Heap Insertion</li><li>Heap Deletion</li><li>Heapify Algorithm</li><li>Heap Sort</li></ol><h3>Understanding Heaps</h3><p>Heaps are nothing but a <strong>complete</strong> <strong>binary tree</strong> that comes with a heap order property namely,</p><ol><li>Max Heap</li><li>Min Heap</li></ol><h4>Complete Binary Tree</h4><p>A complete Binary tree can be seen as a typical Binary tree but with two exceptions (listed below).</p><ol><li>The entry-level needs to be completely filled (at least two nodes/child) except the last level.</li><li>Nodes need to be added only from the left-hand side.</li></ol><h4>Max Heap</h4><p>Max heap is the type of heap in which every root node is greater than its children.</p><h4>Min Heap</h4><p>Min heap is another type of heap in which every single node is smaller than its children.</p><h4>Some Formulae to note</h4><p>Taking ‘i’ as a node&#39;s index or current position in a heap.</p><ol><li>To find the<strong> Left child </strong>of the current node =&gt; <strong>2*i </strong>(for 1 base indexing) <strong>[2*i + 1(for 0 base indexing)]</strong>.</li><li>To find the <strong>Right child</strong> of the current node =&gt; <strong>2*i + 1</strong> (for 1 base indexing) <strong>[2*i + 2 (for 0 base indexing)]</strong>.</li><li>To find the parent of the current node =&gt; <strong>i/2</strong>.</li></ol><h3>Heap Class Creation</h3><p>A heap class can be created like the code below:</p><pre>class heap<br>{<br>public:<br>    int arr[100];<br>    int size;<br><br>    heap()<br>    {<br>        arr[0] = -1;//Taking 1 base indexing<br>        size = 0;<br>    }<br>}</pre><h3>Insertion in Heap</h3><p>Insertion in a heap can be performed in 2 steps.</p><ol><li>Add the number to be added to the array.</li><li>Assign its correct position in a heap.</li></ol><p>The implementation can be understood in the code below.</p><pre>void Insert(int val)<br>    {<br>        // 1st Step done!<br>        size += 1;<br>        int index = size;<br>        arr[index] = val;<br><br>        // 2nd Step<br>        while (index &gt; 1)<br>        {<br>            int parent = index / 2;//For 1 base indexing.<br>            if (arr[parent] &lt; arr[index])<br>            {<br>                swap(arr[parent], arr[index]);<br>                index = parent;<br>            }<br>            else<br>            {<br>                return;<br>            }<br>        }<br>    }</pre><h3>Deletion in Heap</h3><p>Deletion can be done by the following steps.</p><ol><li>Assign the last value to the root node.</li><li>Decrease the size of the heap.</li><li>Assign the correct position of the new root node.</li></ol><pre>void deleteinheap()<br>    {<br>        if (size == 0)<br>        {<br>            cout &lt;&lt; &quot;Nothing to delete!&quot; &lt;&lt; endl;<br>            return;<br>        }<br><br>        // STEP 1 Changing the root node with the last node<br>        arr[1] = arr[size];<br>        // STEP 2 Deleting root node;<br>        size--;<br>        // STEP 3 Assigning correct position to first/Root node<br>        int i = 1;<br>        while (i &lt; size)<br>        {<br>            int leftIndex = 2 * i;<br>            int rightIndex = 2 * i + 1;<br><br>            if (leftIndex &lt; size &amp;&amp; arr[leftIndex] &gt; arr[i])<br>            {<br>                swap(arr[leftIndex], arr[i]);<br>                i = leftIndex;<br>            }<br>            else if (rightIndex &lt; size &amp;&amp; arr[rightIndex] &gt; arr[i])<br>            {<br>                swap(arr[rightIndex], arr[i]);<br>                i = rightIndex;<br>            }<br>            else<br>            {<br>                return;<br>            }<br>        }<br>    }</pre><h3>Heapify Algorithm</h3><p>Heapify is used to create a heap data structure from a Binary Search Tree. The heap created can be a Min or a Max heap.</p><h4>Leaf Nodes</h4><p>Complete Binary exhibits a special property where the leaf nodes can be found from n/2+1 till nth index (For 1-based indexing). Consider the image below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Oe241aLsw4FYA7Eob-bTrQ.png" /></figure><p>Since Leaf nodes can already be considered a heap. Therefore, we just need to look at the nodes that are not heaps. These are from 1 to n/2 (1-based indexing).</p><p>Below is the code for the Heapify algorithm.</p><pre>void heapify(int arr[], int n, int index)<br>{<br>    int largest = index;<br>    int left = 2 * index;<br>    int right = 2 * index + 1; // 1-based indexing<br><br>    if (left &lt; n &amp;&amp; arr[largest] &lt; arr[left])<br>    {<br>        largest = left;<br>    }<br>    if (right &lt; n &amp;&amp; arr[largest] &lt; arr[right])<br>    {<br>        largest = right;<br>    }<br>    if (largest != index)<br>    {<br>        swap(arr[largest], arr[index]);<br>        heapify(arr, n, largest);<br>    }<br>}</pre><p>Its implementation in the <strong>main</strong> function is as follows.</p><pre>int main(int argc, char const *argv[])<br>{<br>    int n = 5;<br>    int arr[6] = {-1,54, 53, 55, 52, 50};<br>    for(int i=n/2; i&gt;0; i--){<br>        heapify(arr, n, i);//1-based indexing<br>    }<br><br><br>    for(int i=1; i&lt;=n; i++){<br>        cout&lt;&lt;arr[i]&lt;&lt;&quot; &quot;;<br>    }cout&lt;&lt;endl;<br>    return 0;<br>}</pre><h3>HeapSort</h3><p>HeapSort is used to sort the heap when the smallest or the largest value is needed instantly.</p><p>HeapSort can be performed using the two steps given below:</p><ol><li>Swap the first and last elements of the heap. And delete the last node by decrementing the size.</li><li>Assign the correct position to the first node.</li></ol><p>The code for HeapSort is given below:</p><pre>void heapsort(int arr[], int size)<br>{<br><br>    while (size &gt; 1)<br>    { // step 1<br>        swap(arr[1], arr[size]);<br>        size--;<br><br>        // Step 2<br>        heapify(arr, size, 1);<br>    }<br>}<br><br><br>int main(int argc, char const *argv[])<br>{<br>    int n = 5;<br>    int arr[6] = {-1 ,54, 53, 55, 52, 50};<br>    //Heap Creation<br>    for(int i=n/2; i&gt;0; i--){<br>        heapify(arr, n, i);<br>    }<br><br>    heapsort(arr, n);<br>    for(int i=1; i&lt;=n; i++){<br>        cout&lt;&lt;arr[i]&lt;&lt;&quot; &quot;;<br>    }cout&lt;&lt;endl;<br><br>    return 0;<br>}</pre><p>The time complexity for HeapSort is O(NLogN).</p><p>For a more detailed explanation ➡️<a href="https://youtu.be/NKJnHewiGdc">https://youtu.be/NKJnHewiGdc</a></p><p>And That’s all💯.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ded6084eaea7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Binary Search Challenges!]]></title>
            <link>https://medium.com/@itsvinayyay/binary-search-challenges-61c782366a5?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/61c782366a5</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[c-plus-plus-language]]></category>
            <category><![CDATA[binary-search]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Wed, 01 Feb 2023 15:45:16 GMT</pubDate>
            <atom:updated>2023-02-01T15:45:51.391Z</atom:updated>
            <content:encoded><![CDATA[<p>The traditional Binary Search algorithms have many uses, a few of which are discussed below in the form of challenges.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*W8ZpwW6Vm3gLd-xJlOvrFQ.png" /></figure><h3>Question 1. Largest Minimum Distance along a Straight Line.</h3><h4>Given an array with n elements that represent n positions along a straight line. Find K elements such that the minimum distance between any 2 elements is the maximum possible.</h4><h3>Solution.</h3><p>Applying Binary Search and checking with the mid element whether the pairs chosen are feasible or not. <strong>Feasibility can be checked if the difference is greater than equal to mid.</strong></p><pre>#include&lt;iostream&gt;<br>#include&lt;algorithm&gt;<br>#include&lt;climits&gt;<br>using namespace std;<br><br>bool isfeasible(int arr[], int mid, int n, int k){<br>    int difference = arr[0], elements = 1;<br><br>    for(int i=1; i&lt;n; i++){<br>        if(arr[i] - difference&gt;=mid){<br>            difference = arr[i];<br>            elements++;<br>            if(elements==k){<br>                return true;<br>            }<br>        }<br>    }<br><br>    return false;<br>}<br><br><br>int LargestMindist(int arr[], int n, int k){<br>    int result = -1;<br>    sort(arr, arr+n);<br>    int start = arr[0], end = arr[n-1];<br><br>    while(start&lt;end){<br>        int mid = (start+end)/2;<br><br>        if(isfeasible(arr, mid, n, k)){<br>            result = max(result, mid);<br>            start = mid+1;<br>        } else{<br>            end = mid;<br>        }<br>    }<br>    return result;<br>}<br><br>int main(int argc, char const *argv[])<br>{<br>    int arr[] = {1,2,8,4,9};<br>    cout&lt;&lt;LargestMindist(arr, 5, 3)&lt;&lt;endl;<br>    return 0;<br>}</pre><h3>Question 2. Allocate the Minimum Number of pages.</h3><h4>All the books have to be divided among m students, consecutively. Allocate the pages in such a way that the maximum number of pages allocated to a student is minimum.</h4><h3>Solution.</h3><pre>#include&lt;iostream&gt;<br>#include&lt;climits&gt;<br>using namespace std;<br><br>bool isFeasible(int arr[], int n, int students, int Minimum_Value){<br>    int StudentsReqd = 1; int sum = 0;<br><br>    for(int i=0;i&lt;n; i++){<br>        if(arr[i]&gt;Minimum_Value){<br>            return false;<br>        }<br>        else if(arr[i] + sum &gt; Minimum_Value){<br>            StudentsReqd++;<br>            sum = arr[i];<br>            if(StudentsReqd&gt;students){<br>                return false;<br>            }<br>        }<br>        else{<br>            sum+=arr[i];<br>        }<br>    }<br>    return true;<br>}<br><br><br>int Minalloc(int arr[], int n, int students){<br>    int sum = 0;<br>    for(int i=0; i&lt;n; i++){<br>        sum+=arr[i];<br>    }<br><br>    int start = 0, end = sum, result = INT_MAX;<br>    while(start&lt;=end){<br>        int mid = (start+end)/2;<br>        if(isFeasible(arr, n, students, mid)){<br>            result = min(mid, result);<br>            end = mid-1;<br>        } else{<br>            start = mid+1;<br>        }<br>    }<br><br>    return result;<br>}<br><br>int main(int argc, char const *argv[])<br>{<br>    int arr[] = {12, 34, 67, 90};<br>    cout&lt;&lt;Minalloc(arr, 4, 2)&lt;&lt;endl;<br>    return 0;<br>}</pre><h3>Question 3. Painter’s Partition Problem</h3><h4>A painter paints 1 unit of the board in 1 unit of time &amp; each painter will paint consecutive boards. Find the minimum time that will be required to paint all the boards.</h4><h3>Solution.</h3><p>Same as the previous one but the stub function only returns the numbers of painters. <strong>Take the maximum board size in the start variable in order to make it more efficient.</strong></p><pre>#include&lt;iostream&gt;<br>using namespace std;<br><br>int ReqdPainters(int boards[], int n, int limit, int Painters){<br>    int sum = 0;<br>    int reqdpainters = 1;<br>    for(int i=0; i&lt;n; i++){<br>        sum+=boards[i];<br>        if(sum&gt;limit){<br>            reqdpainters++;<br>            sum = boards[i];<br>        }<br>    }<br><br>    return reqdpainters;<br>}<br><br>int PaintersPartition(int boards[], int n, int Painters){<br>    int maxboard = -1;<br>    int TotalLength = 0;<br>    for(int i=0; i&lt;n; i++){<br>        TotalLength+=boards[i];<br>        maxboard = max(maxboard, boards[i]);<br>    }<br><br>    int start = maxboard, end = TotalLength;<br><br>    while(start&lt;end){<br>        int mid = (start+end)/2;<br>        <br>        if(ReqdPainters(boards, n, mid, Painters)&lt;=Painters){<br>            end = mid;<br>        }<br>        else{<br>            start = mid+1;<br>        }<br>    }<br>    return start;<br>}<br><br><br>int main(int argc, char const *argv[])<br>{<br>    int arr[] = {10,20,30,40};<br>    cout&lt;&lt;PaintersPartition(arr, 4, 2)&lt;&lt;endl;<br>    return 0;<br>}<br><br></pre><h3>Question 4. Search in Rotated Array.</h3><h4>An array has been given which is rotated from a pivot point. We need to search for an element X with a complexity less than that Linear search.</h4><h3>Solution.</h3><p>Check the condition if the<strong> starting value is smaller than mid or not</strong> and <strong>accordingly check that the key exists in the range between them</strong>.</p><pre>#include&lt;iostream&gt;<br>using namespace std;<br><br>int SearchinRotatedArray(int arr[], int start, int end, int key){<br>    if(start&gt;end){<br>        return -1;<br>    }<br>    int mid = (start+end)/2;<br><br>    if(arr[mid] == key){<br>        return mid;<br>    }<br><br>    else if(arr[start]&lt;=arr[mid]){<br>        if(key&gt;=arr[start] &amp;&amp; key&lt;arr[mid]){<br>            return SearchinRotatedArray(arr, start, mid-1, key);<br>        }<br>        else{<br>            return SearchinRotatedArray(arr, mid+1, end, key);<br>        }<br>    }<br><br>    else{<br>        //arr[start]&gt;arr[mid]<br>        if(key&gt;arr[mid] &amp;&amp; key&lt;arr[end]){<br>            return SearchinRotatedArray(arr, mid+1, end, key);<br>        }<br>        else{<br>            return SearchinRotatedArray(arr, start, mid-1, key);<br>        }<br>    }<br>}<br><br>int main(int argc, char const *argv[])<br>{<br>    int arr[] = {30,40,50,10,20};<br>    cout&lt;&lt;SearchinRotatedArray(arr, 0, 4, 40)&lt;&lt;endl;<br>    return 0;<br>}</pre><h3>Question 5. Find Peak Element.</h3><h3>Solution.</h3><p>Just take care of the corner cases here, i.e. when mid is at last and when it is at first.</p><pre>#include&lt;iostream&gt;<br>using namespace std;<br><br>int FindPeak(int arr[], int start, int end, int n){<br>    if(start&gt;end){<br>        return -1;<br>    }<br><br>    int mid = (start+end)/2;<br><br>    if((mid==0 || arr[mid]&gt;arr[mid-1]) &amp;&amp; (mid==n-1 || arr[mid]&gt;arr[mid+1])){<br>        return mid;<br>    }<br><br>    else if(mid &gt; 0 &amp;&amp; arr[mid]&lt;arr[mid-1]){<br>        return FindPeak(arr, start, mid-1, n);<br>    }<br><br>    else{<br>        //arr[mid]&lt;arr[mid+1] &amp;&amp; mid&lt;n-1<br>        return FindPeak(arr, mid+1, end, n);<br>    }<br>}<br><br>int main(int argc, char const *argv[])<br>{<br>    int arr[] = {1,3,4,5,6,10};<br>    cout&lt;&lt;FindPeak(arr, 0, 5, 6)&lt;&lt;endl;<br>    return 0;<br>}</pre><p>That’s all!💯</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=61c782366a5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Catalan Numbers (Binary Search Trees)]]></title>
            <link>https://medium.com/@itsvinayyay/catalan-numbers-binary-search-tress-95afee0299e7?source=rss-5eb3bc4989d3------2</link>
            <guid isPermaLink="false">https://medium.com/p/95afee0299e7</guid>
            <category><![CDATA[c-plus-plus-language]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[catalan-number]]></category>
            <category><![CDATA[binary-search-tree]]></category>
            <category><![CDATA[binary-tree]]></category>
            <dc:creator><![CDATA[Vinay Vashist]]></dc:creator>
            <pubDate>Fri, 20 Jan 2023 03:46:25 GMT</pubDate>
            <atom:updated>2023-02-25T06:38:58.499Z</atom:updated>
            <content:encoded><![CDATA[<p>Catalan numbers are the natural numbers encountered in various counting problems and often involve recursively defined objects.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WUFlCrnUoCWpqKk-aDy7CQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/763/1*aAzgAu_o65z9zjze7UmYOA.png" /></figure><h3>➡️C(n) = Sigma{C(i) C(n-i)}, i=0 to i=n-1</h3><p><strong>Here C(0) and C(1) are already pre-defined and are equal to 1.</strong></p><p>Subsequently, C(2) can be defined as:</p><h3>🔖C(2) = C(0)C(1) + C(1)C(0) = 2</h3><h3>and, 🔖C(3) = C(0)C(2) + C(1)C(1) + C(2)C(0) = 5</h3><p>By looking at the sequence the following standard pattern can be generated as:</p><h3>🌟C(n) = C(0)C(n-1) + C(1)C(n-2) + C(2)C(n-3) +…..+C(n-1)C(0)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*675x9vvg6u7ZtFj-QmHD-Q.png" /></figure><p>Code to find out the Catalan of a particular number:</p><pre>#include&lt;iostream&gt;<br>using namespace std;<br>int catalan(int n){<br>    if(n==1 || n==0){<br>        return 1;<br>    }<br>    cout&lt;&lt;&quot;call for catalan = &quot;&lt;&lt;n&lt;&lt;endl;<br>    int res = 0;<br>    for(int i=0; i&lt;n; i++){<br>        res+= catalan(i)*catalan(n-i-1);<br>        cout&lt;&lt;&quot;Added &quot;&lt;&lt;i&lt;&lt;&quot; and &quot;&lt;&lt;n-i-1&lt;&lt;endl;<br>    }<br><br>    return res;<br>}<br><br><br>int main()<br>{<br>    cout&lt;&lt;&quot;Final Answer: &quot;&lt;&lt;catalan(3)&lt;&lt;endl;<br>    return 0;<br>}</pre><p>Code’s output🔥</p><p>call for Catalan = 3<br>call for Catalan = 2<br>Added 0 and 1<br>Added 1 and 0<br>Added 0 and 2<br>Added 1 and 1<br>call for Catalan = 2<br>Added 0 and 1<br>Added 1 and 0<br>Added 2 and 0<br>Final Answer: 5</p><h3>Possible No. of BSTs (One of the applications of Catalan numbers)</h3><p>Here since we know the possible number of BSTs for <strong>1 node is 1</strong>. Similarly, for <strong>2 nodes, it is 2,</strong> and subsequently, for <strong>3 nodes it is 5.</strong></p><p>This can also be viewed as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wBIDfTNWz-UbkL40eHjm8A.png" /></figure><p>Since Node 3 involves 3 terms:</p><h3>C(3) = C(0)C(2) + C(1)C(1) + C(2)C(0) = 5</h3><p>For C(0)C(2) (term 1), suppose the configuration of nodes addition is like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Dl3vCF5TLmzOe9tv5KtfkQ.png" /></figure><p>While for term 2,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9YXxnF5Yuij8W7o55QuGzg.png" /></figure><p>and for term 3,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vv0_km80qWoxezCfU9-t6A.png" /></figure><p><strong>Note that here the node for three is attached at the leaf and not at the root.</strong></p><p>Therefore, the tree can have the following 5 configurations as under</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TU612Wgp-uTI5cj3EMfnDQ.png" /></figure><h3>Code to print the BSTs for a given number of nodes</h3><pre>//Catalan Numbers<br>#include&lt;iostream&gt;<br>#include&lt;vector&gt;<br>using namespace std;<br><br>class Node{<br>    public:<br>    int data;<br>    Node *left;<br>    Node *right;<br><br>    Node(int val){<br>        data = val;<br>        left = NULL;<br>        right = NULL;<br>    }<br>};<br><br>vector&lt;Node*&gt; NumberofBSTs(int start, int end){<br><br>    <br>    vector&lt;Node*&gt; Trees;<br>    if(start&gt;end){<br>        Trees.push_back(NULL);<br>        return Trees;<br>    }<br>    for(int i=start; i&lt;=end; i++){<br>        vector&lt;Node*&gt; LeftSub = NumberofBSTs(start, i-1);<br>        vector&lt;Node*&gt; RightSub = NumberofBSTs(i+1, end);<br><br><br>        for(int j=0; j&lt;LeftSub.size(); j++){<br>            Node *leftn = LeftSub[j];<br>            for(int k = 0; k&lt;RightSub.size(); k++){<br>                Node *rightn = RightSub[k];<br><br>                Node *node = new Node(i);<br>                node-&gt;left = leftn;<br>                node-&gt;right = rightn;<br>                Trees.push_back(node);<br>            }<br>        }<br>    }<br><br>    return Trees;<br>}<br><br>void Preorder(Node *root){<br>    if(root==NULL){<br>        return;<br>    }<br><br>    cout&lt;&lt;root-&gt;data&lt;&lt;&quot;-&gt;&quot;;<br>    Preorder(root-&gt;left);<br>    Preorder(root-&gt;right);<br>}<br><br>int main(int argc, char const *argv[])<br>{<br>    vector&lt;Node*&gt; Totaltrees = NumberofBSTs(1,3);<br><br>    for(int i=0; i&lt;Totaltrees.size(); i++){<br>        cout&lt;&lt;i+1&lt;&lt;&quot; : &quot;;<br>        Preorder(Totaltrees[i]);<br>        cout&lt;&lt;&quot;NULL&quot;&lt;&lt;endl;<br><br>    }<br>    <br>    return 0;<br>}</pre><p>Video Link🔥 <a href="https://www.youtube.com/watch?v=1ZAotQGnbi4&amp;list=PLfqMhTWNBTe0b2nM6JHVCnAkhQRGiZMSJ&amp;index=112">https://www.youtube.com/watch?v=1ZAotQGnbi4&amp;list=PLfqMhTWNBTe0b2nM6JHVCnAkhQRGiZMSJ&amp;index=112</a></p><p>And that’s all!💯</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=95afee0299e7" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>