<?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 Vikas Gogia on Medium]]></title>
        <description><![CDATA[Stories by Vikas Gogia on Medium]]></description>
        <link>https://medium.com/@vikasg_65078?source=rss-dc09473684e2------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*LFR4PjM15Sn8kE_ETe55vg.jpeg</url>
            <title>Stories by Vikas Gogia on Medium</title>
            <link>https://medium.com/@vikasg_65078?source=rss-dc09473684e2------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 03:27:55 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@vikasg_65078/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[Leetcode 2492. Minimum Score of a Path Between Two Cities]]></title>
            <link>https://medium.com/@vikasg_65078/leetcode-2492-minimum-score-of-a-path-between-two-cities-f11e3ea678df?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/f11e3ea678df</guid>
            <category><![CDATA[jobs]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[graph]]></category>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Sat, 04 Jul 2026 19:39:00 GMT</pubDate>
            <atom:updated>2026-07-04T19:39:00.059Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GRZQiwysEsAjp3FOe9H9fw.png" /><figcaption><a href="https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/description/">https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/</a></figcaption></figure><h3>1. Overview &amp; Problem Explanation</h3><p>You are given n cities numbered from 1 to n. These cities are connected by a series of bidirectional roads, where each road is represented as a triplet [u, v, distance]. This tells us we are working with a <strong>weighted, undirected graph</strong>.</p><p>Your goal is to find the <strong>minimum score</strong> of a path traveling from city 1 to city n. The problem guarantees that there is <em>at least one</em> valid path connecting city 1 and city n.</p><h4>What Does “Score of a Path” Actually Mean?</h4><p>This is where many developers get tripped up. The “score” of a path is <strong>not</strong> the sum of the road distances (which would make it a standard shortest-path problem). Instead, the score of a path is defined as the <strong>minimum weight of any edge encountered along that path.</strong></p><blockquote><em>⚠️ </em><strong><em>Crucial Rule:</em></strong><em> You are allowed to visit the same node or traverse the same edge </em><strong><em>multiple times</em></strong><em> within a single path.</em></blockquote><p>For example, imagine your path from city 1 to city 4 goes like this: <br>1 -&gt; 2 -&gt; 3 -&gt; 2 -&gt; 4. <br>If the road between city 2 and city 3 has a tiny weight of 4, that 4 becomes the minimum weight seen on the entire journey. Because you can freely detour back and forth across that cheap road and still finish your journey at city 4, the <em>entire path&#39;s score</em> drops down to 4.</p><h3>2. Crux of the Problem</h3><p>The “Aha!” moment of this problem lies entirely within that permission to traverse roads multiple times.</p><p>Because you can visit any edge multiple times, you don’t actually need to find a direct, lean path from 1 to n. In fact, <strong>any edge that belongs to the same connected component as city </strong>1<strong> and city </strong>n<strong> can be part of your path.</strong></p><h4>The Key Inference</h4><p>If city 1 and city n are in the same connected component, you can start at city 1, travel anywhere within that component to traverse the absolute smallest edge available in that entire network, turn back around, and eventually finish your journey at city n.</p><p>Therefore, the problem completely shifts:</p><ul><li><strong>Initial thought:</strong> “I need to find the optimal path from 1 to n.”</li><li><strong>The Reality:</strong> “I just need to find the absolute minimum edge weight inside the entire connected component containing city 1 and city n.”</li></ul><h4>Why Dijkstra’s Algorithm is Overkill</h4><p>When we see words like “minimum” and “path” in graph problems, our brains instantly scream <strong>Dijkstra’s Algorithm</strong>. However, Dijkstra’s is designed to minimize the <em>cumulative sum</em> of edge weights to find the shortest path. Since we are allowed unlimited backtracking and only care about a single global minimum edge in our connected component, traditional shortest-path tracking is completely unnecessary. We don’t care how far away an edge is; we only care if it’s reachable.</p><h3>3. Approaches Possible + Why This Approach?</h3><p>There are a few classic graph traversal strategies we could use to solve this:</p><ul><li><strong>Breadth-First Search (BFS) / Depth-First Search (DFS):</strong> We could kick off a standard traversal starting from city 1, explore every reachable node, and keep a running track of the smallest edge weight we encounter along the way.</li><li><strong>Disjoint Set Union (DSU):</strong> Also known as the Union-Find algorithm. This approach dynamically groups nodes into connected components while simultaneously tracking properties of those components.</li></ul><h3>4. Visual Representation</h3><p>Let’s visualize how the DSU processes edges and tracks the minimum weights of components. Imagine we have 4 cities and the following roads:</p><ul><li>[1, 2, 9]</li><li>[2, 3, 4]</li><li>[3, 4, 7]</li></ul><p>Initially, every node is its own separate component with a minimum weight of infty (INT_MAX).</p><pre>Initial State:<br>Node:         [1]        [2]        [3]        [4]<br>Parent:        1          2          3          4<br>Min Weight:    ∞          ∞          ∞          ∞</pre><p>Now, let’s process the edges one by one using unionBySize:</p><pre>Step 1: Process Road [1, 2, 9]<br>  - Merge 1 and 2. <br>  - Component Root: 1<br>  - minWeight[1] = min(∞, ∞, 9) -&gt; 9<br><br>Component Map:<br>     [1] (minWeight: 9)<br>      |<br>     [2]                  [3] (minWeight: ∞)    [4] (minWeight: ∞)<br>------------------------------------------------------------------<br>Step 2: Process Road [2, 3, 4]<br>  - Find root of 2 (which is 1). Find root of 3 (which is 3).<br>  - Merge component 1 and component 3.<br>  - Component Root: 1<br>  - minWeight[1] = min(minWeight[1], minWeight[3], 4) -&gt; min(9, ∞, 4) -&gt; 4<br><br>Component Map:<br>     [1] (minWeight: 4)<br>    /   \<br>  [2]   [3]               [4] (minWeight: ∞)<br>------------------------------------------------------------------<br>Step 3: Process Road [3, 4, 7]<br>  - Find root of 3 (which is 1). Find root of 4 (which is 4).<br>  - Merge component 1 and component 4.<br>  - Component Root: 1<br>  - minWeight[1] = min(minWeight[1], minWeight[4], 7) -&gt; min(4, ∞, 7) -&gt; 4<br><br>Component Map:<br>        [1] (minWeight: 4)<br>      /  |  \<br>    [2] [3] [4]</pre><p>When we call getMinEdge(1), the algorithm finds the ultimate parent of 1 (which is 1) and returns its tracked minWeight, which is 4.</p><h3>5. Clean Code</h3><pre>class DisjointSet {<br>private:<br>    // parent tracks the ultimate root/representative for each node.<br>    vector&lt;int&gt; parent;<br>    // size tracks the number of nodes inside a specific component to keep trees flat.<br>    vector&lt;int&gt; size;<br>    // minWeight continuously tracks the absolute minimum edge weight within a component.<br>    vector&lt;int&gt; minWeight;<br>public:<br>    // Constructor to initialize the tracking arrays<br>    DisjointSet(int n) {<br>        size.resize(n + 1, 1);<br>        parent.resize(n + 1);<br>        minWeight.resize(n + 1, INT_MAX);<br>        // Initially, every node is its own parent<br>        for(int i = 0; i &lt;= n; i++) {<br>            parent[i] = i;<br>        }<br>    }<br><br>    // Find function with Path Compression optimization<br>    int findUltimateParent(int node) {<br>        if (node == parent[node])<br>            return node;<br>        // Path compression: flattens the structure by pointing nodes directly to the root<br>        return parent[node] = findUltimateParent(parent[node]);<br>    }<br><br>    // Union by Size optimization with custom metadata tracking for minWeight<br>    void unionBySize(int u, int v, int w) {<br>        int up = findUltimateParent(u);<br>        int vp = findUltimateParent(v);<br>        // If they are already in the same component, just check if the current <br>        // edge weight &#39;w&#39; is smaller than our known minimum for this component.<br>        if(up == vp) {<br>            minWeight[up] = min(minWeight[up], w);<br>            return;<br>        }<br>        // Union by size: attach the smaller tree under the larger tree<br>        if(size[up] &lt; size[vp]) {<br>            parent[up] = vp;<br>            size[vp] += size[up];<br>            // Update the root&#39;s minWeight by comparing both components and the bridging edge<br>            minWeight[vp] = min({minWeight[vp], minWeight[up], w});<br>        }<br>        else {<br>            parent[vp] = up;<br>            size[up] += size[vp];<br>            minWeight[up] = min({minWeight[vp], minWeight[up], w});<br>        }<br>    }<br><br>    // Helper to fetch the minimum edge weight of the component containing &#39;node&#39;<br>    int getMinEdge(int node) {<br>        int root = findUltimateParent(node);<br>        return minWeight[root];<br>    }<br>};<br><br>class Solution {<br>public:<br>    int minScore(int n, vector&lt;vector&lt;int&gt;&gt;&amp; roads) {<br>        DisjointSet ds(n);<br>        // Process every road to construct our connected components<br>        for (const auto&amp; road : roads) {<br>            int u = road[0];<br>            int v = road[1];<br>            int weight = road[2];<br>            ds.unionBySize(u, v, weight);<br>        }<br>        // The problem guarantees that city 1 and city n are always connected.<br>        // Thus, we simply query the minimum edge within city 1&#39;s component.<br>        return ds.getMinEdge(1);<br>    }<br>};</pre><h3>6. Time and Space Complexity Analysis</h3><p>Time Complexity</p><ul><li>Time complexity: O(V + E * alpha(V)) ~ O(V + E)</li><li>Space complexity: O(V)</li></ul><p>where alpha(V) is Inverse Ackermann function which yields tiny results &lt;= 4 for even huge numbers. Therefore ~O(1).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f11e3ea678df" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 1143. Longest Common Subsequence]]></title>
            <link>https://medium.com/@vikasg_65078/1143-longest-common-subsequence-f0c4047d4360?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/f0c4047d4360</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Mon, 29 Jun 2026 01:33:10 GMT</pubDate>
            <atom:updated>2026-06-29T22:58:28.506Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*L5tcbQv6UUSeaGgmg38j2A.png" /><figcaption><a href="https://leetcode.com/problems/longest-common-subsequence/">https://leetcode.com/problems/longest-common-subsequence/</a></figcaption></figure><h3>1. The Problem</h3><p>Find the length of the longest subsequence present in two given strings, text1 and text2.</p><p>A <strong>subsequence</strong> is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, &quot;ace&quot; is a subsequence of &quot;abcde&quot;. A <em>common subsequence</em> is one that appears in both strings.</p><h3>2. Our Approach</h3><h3>The Brute Force Intuition (Recursion)</h3><p>Imagine standing at the end of both strings with two pointers, i (for text1) and j (for text2). We compare the characters at these positions:</p><ol><li><strong>If they match (</strong>text1[i] == text2[j]<strong>)</strong>: This character is definitely part of our longest common subsequence! We gain 1 point of length and move both pointers backward to evaluate the rest: <strong>F(i,j) = 1 + F(i-1, j-1)</strong></li><li><strong>If they don’t match</strong>: We have a choice to make. We either ignore the current character of text1 or ignore the current character of text2. We take the path that yields the maximum result: <strong>F(i,j) = max(F(i-1, j), F(i, j-1))</strong></li></ol><p>If either pointer drops below 0, it means we&#39;ve run out of characters, yielding a base length of 0.</p><p>While mathematically sound, raw recursion recalculates the same sub-problems repeatedly, leading to an exponential time complexity of O(2^(n1+n2)).</p><h3>The Optimization: Bottom-Up Dynamic Programming</h3><p>To solve this efficiently, we switch from a top-down recursive approach to a <strong>bottom-up iterative approach</strong> using a 2D table (dp).</p><p>To avoid dealing with messy negative indices or out-of-bounds errors for our base cases, we size our table to (n1 + 1) * (n2 + 1). In this setup:</p><ul><li>Row 0 represents an empty text1.</li><li>Column 0 represents an empty text2.</li><li>dp[i][j] stores the length of the LCS for the prefixes.</li></ul><h3>3. Visual Representation (Dry Run)</h3><p>Let’s trace how the DP table fills up using text1 = &quot;abc&quot; and text2 = &quot;ac&quot;.</p><h3>Step-by-Step Execution:</h3><ol><li><strong>Initialization</strong>: Initialize a 4 *3 grid entirely with 0s.</li><li><strong>Row 1 (</strong>i = 1<strong>, </strong>text1[0] = &#39;a&#39;<strong>)</strong>:</li></ol><pre>j = 1 (text2[0] = &#39;a&#39;): Match! =&gt; dp[1][1] = 1 + dp[0][0] = 1. <br>j = 2 (text2[1] = &#39;c&#39;): No match. =&gt; dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1.</pre><p>3. <strong>Row 2 (</strong>i = 2<strong>, </strong>text1[1] = &#39;b&#39;<strong>)</strong>:</p><pre>j = 1 (&#39;a&#39;): No match. =&gt; dp[2][1] = max(dp[1][1], dp[2][0]) = max(1, 0) = 1.<br>j = 2 (&#39;c&#39;): No match. =&gt; dp[2][2] = max(dp[1][2], dp[2][1]) = max(1, 1) = 1.</pre><p><strong>4. Row 3 (</strong>i = 3<strong>, </strong>text1[2] = &#39;c&#39;<strong>)</strong>:</p><pre>j = 1 (&#39;a&#39;): No match. =&gt; dp[3][1] = max(dp[2][1], dp[3][0]) = max(1, 0) = 1.<br>j = 2 (&#39;c&#39;): Match! =&gt; dp[3][2] = 1 + dp[2][1] = 1 + 1 = 2.</pre><h3>Final DP Table:</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VheTdNHTlzeL4x8aAIzSvQ.png" /></figure><p>The final answer sits safely at the bottom-right corner: dp[3][2] = 2.</p><h3>4. Code</h3><pre>class Solution {<br>public:<br>    int longestCommonSubsequence(string text1, string text2) {<br>        int n1 = text1.size(), n2 = text2.size();<br>        <br>        // dp[i][j] handles 1-based indexing where index 0 represents an empty string<br>        vector&lt;vector&lt;int&gt;&gt; dp(n1 + 1, vector&lt;int&gt;(n2 + 1, 0));<br><br>        // Fill the DP table iteratively<br>        for (int i = 1; i &lt;= n1; i++) {<br>            for (int j = 1; j &lt;= n2; j++) {<br>                if (text1[i - 1] == text2[j - 1]) {<br>                    // Character match: Look diagonally back and add 1<br>                    dp[i][j] = 1 + dp[i - 1][j - 1];<br>                } else {<br>                    // No match: Take the maximum from the top or left cell<br>                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);<br>                }<br>            }<br>        }<br><br>        // The bottom-right cell contains the length of the absolute LCS<br>        return dp[n1][n2];<br>    }<br>};</pre><h3>5. Analysis</h3><ul><li>Time complexity: O(n1 * n2)</li><li>Space complexity: O(n1 * n2)</li></ul><blockquote><strong><em>Pro-Tip (Space Optimization):</em></strong><em> Notice that when computing </em><em>dp[i][j], we only ever reference the </em>current<em> row </em><em>i and the </em>previous<em> row </em><em>i - 1. We could optimize the space complexity down to n2 by maintaining just two 1D rows (</em><em>prev and </em><em>curr) instead of an entire grid!</em></blockquote><p>Print LCS</p><pre>// Online C++ compiler to run C++ program online<br>#include &lt;iostream&gt;<br>#include &lt;vector&gt;<br>#include &lt;string&gt;<br><br>using namespace std;<br><br>int main() {<br>    string text1 = &quot;ac&quot;, text2 = &quot;ace&quot;;<br>    int n1 = text1.size(), n2 = text2.size();<br>        <br>    // dp[i][j] handles 1-based indexing where index 0 represents an empty string<br>    vector&lt;vector&lt;int&gt;&gt; dp(n1 + 1, vector&lt;int&gt;(n2 + 1, 0));<br><br>    // Fill the DP table iteratively<br>    for (int i = 1; i &lt;= n1; i++) {<br>        for (int j = 1; j &lt;= n2; j++) {<br>            if (text1[i - 1] == text2[j - 1]) {<br>                // Character match: Look diagonally back and add 1<br>                dp[i][j] = 1 + dp[i - 1][j - 1];<br>            } else {<br>                // No match: Take the maximum from the top or left cell<br>                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);<br>            }<br>        }<br>    }<br>        <br>        <br>    // What does the array look like?<br>    for(int i=0; i&lt;= n1; i++) {<br>        for(int j=0; j&lt;= n2; j++) {<br>            cout &lt;&lt; dp[i][j] &lt;&lt; &quot; &quot;;<br>        }<br>        cout &lt;&lt; endl;<br>    }<br>    <br>    cout &lt;&lt; endl &lt;&lt; endl;<br>    <br>    int i=n1, j=n2;<br>    while(i &gt;= 1 &amp;&amp; j &gt;= 1) {<br>        cout &lt;&lt; &quot;dp[&quot; &lt;&lt; i &lt;&lt; &quot;][&quot; &lt;&lt; j &lt;&lt; &quot;]: &quot; &lt;&lt; dp[i][j] &lt;&lt; endl;<br>        if(text1[i-1] == text2[j-1]) {<br>            i--, j--;<br>        } else {<br>            if(dp[i-1][j] &gt;= dp[i][j-1]) {<br>                i--;<br>            } else {<br>                j--;<br>            }<br>        }<br>    }<br><br>    return 0;<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f0c4047d4360" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 3020. Find the maximum number of elements in a subset]]></title>
            <link>https://medium.com/@vikasg_65078/leetcode-3020-find-the-maximum-number-of-elements-in-a-subset-643c87d9035c?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/643c87d9035c</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Sun, 28 Jun 2026 21:45:49 GMT</pubDate>
            <atom:updated>2026-06-29T00:39:09.037Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Viq-Ar1TA-TY1O_yi7eXyA.png" /><figcaption><a href="https://leetcode.com/problems/maximum-element-after-decreasing-and-rearranging/">https://leetcode.com/problems/maximum-element-after-decreasing-and-rearranging/</a></figcaption></figure><p>The problem asks us to find a <strong>subset</strong> (pick any element in any order) that forms a very specific <strong>symmetric pattern </strong>when sorted:</p><pre>x, x², x⁴, ..., x^k, ..., x⁴, x², x</pre><p>If you look closely, this is just a <strong>mountain array</strong> built on squares.</p><ul><li>Every element on the way “up” the mountain must appear <strong>at least twice</strong> (one for the left side, one for the right).</li><li>The element at the absolute peak (x^k) only needs to appear <strong>once</strong>.</li></ul><h3>The Trap 🪤</h3><p>A common instinct is to look at a number and try to find its square roots to see how deep the pattern goes. <strong>Don’t do this.</strong> It’s much easier to start from the smallest possible base (x) and keep squaring it (x to x² to x⁴) to see how high of a mountain you can build.</p><h3>The Game Plan</h3><p>To make this work seamlessly, we need three strategic moves:</p><ol><li><strong>Sort by Frequency:</strong> We use a std::map in C++ (red-black tree) because it automatically keeps our keys sorted. Starting from the smallest numbers ensures we build our mountains from the absolute foundation.</li><li><strong>The “Look-Ahead” Squaring:</strong> Instead of factoring, we just multiply x * x and check if the map has it.</li><li><strong>The “Burn After Reading” Rule:</strong> Once we process a number as a base, we set its frequency to 0. Why? Because if it couldn&#39;t form a bigger mountain starting from a smaller base, it certainly won&#39;t do better later. This eliminates redundant checks and infinite loops!</li></ol><h3>Walkthrough: A Visual Example</h3><p>Let’s trace the logic with an array: [2, 2, 4, 4, 16, 2, 4]</p><p>First, our frequency map looks like this:</p><ul><li>2: 3 times</li><li>4: 3 times</li><li>16: 1 time</li></ul><p>We start iterating from the smallest element, 2:</p><ul><li><strong>Step 1:</strong> Look at 2. Frequency is 3 ≥ 2. Excellent! We can use two 2s (one for each side of the mountain). cnt = 2. Move to 2^2 = 4.</li><li><strong>Step 2:</strong> Look at 4. Frequency is 3 ≥ 2. Perfect! We take two 4s. cnt = 4. Move to 4^2 = 16.</li><li><strong>Step 3:</strong> Look at 16. Frequency is exactly 1. This is our peak! We take the one 16. cnt = 5. Because we hit a frequency of 1, the mountain tops out here. We break.</li></ul><p>Our raw count is 5. Since the peak element doesn&#39;t need a pair, our final valid mountain length is 5 (representing the subset [2, 4, 16, 4, 2]).</p><h3>Turning Intuition into Elegant Code</h3><p>Here is how cleanly this translates into C++. Notice the specialized handle for the edge case of 1 (since 1^2 = 1 infinitely):</p><pre>typedef long long int ll;<br><br>class Solution {<br>public:<br>    int maximumLength(vector&lt;int&gt;&amp; nums) {<br>        // Step 1: Keep keys sorted automatically using an ordered map<br>        map&lt;int, int&gt; freq;<br>        int maxCnt = 1; // A single element is always a valid subset of length 1<br><br>        for(auto el : nums) freq[el]++;<br><br>        for(auto [el, f] : freq) {<br>            if (f == 0) continue; // Already processed in an earlier chain<br>            <br>            ll x = el;<br>            int cnt = 0;<br><br>            // Step 2: Keep squaring forward<br>            while(freq.find(x) != freq.end() &amp;&amp; freq[x] &gt; 0) {<br>                // Special edge case: 1 squared is always 1<br>                if(x == 1) {<br>                    cnt += freq[1]; <br>                    break;<br>                }<br>                // We found our peak element<br>                else if(freq[x] == 1) {<br>                    cnt++;<br>                    break;<br>                }<br>                // We have enough to keep building the slopes<br>                else if(freq[x] &gt;= 2) {<br>                    cnt += 2;<br>                }<br>                <br>                freq[x] = 0; // Burn after reading to optimize S.C./T.C.<br>                if(x &gt; 1e5) break; // Prevent integer overflow on the next square<br>                x = x * x;<br>            }<br><br>            // If the mountain ended perfectly on a paired slope, <br>            // we must subtract 1 because the peak only needs 1 element, not 2.<br>            if(cnt % 2 == 0) cnt--;<br>            maxCnt = max(maxCnt, cnt);<br>        }<br><br>        return maxCnt;<br>    }<br>};</pre><h3>Why This is Fast ⚡</h3><p>You might look at a nested while loop inside a for loop and worry about a O(N^2) time complexity.</p><p><strong>Don’t worry!</strong> Because we are squaring x every single time (x to x² to x⁴ to x⁸), the value grows exponentially. For any number up to 10⁹, the while loop will run a maximum of <strong>only 5 times</strong> (2 to 4 to 16 to 256 to 65536 to …).</p><p>Mathematically, the while loop runs in O(log(log(M))) time, which is practically O(1) constant time.</p><ul><li><strong>Time Complexity:</strong> O(N log N) due to the sorted map insertions.</li><li><strong>Space Complexity:</strong> O(N) to store the frequency map.</li></ul><h3>Wrapping Up</h3><p>By shifting our perspective from <em>finding roots</em> to <em>predicting squares</em>, we turned a daunting math problem into a straightforward simulation. The next time you see a pattern involving geometric progressions, remember: <strong>sometimes it’s much easier to look forward than it is to look back!</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=643c87d9035c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 2799 Count complete subarrays in an array]]></title>
            <link>https://medium.com/@vikasg_65078/leetcode-2799-count-complete-subarrays-in-an-array-36da52ebff4b?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/36da52ebff4b</guid>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Thu, 24 Apr 2025 22:42:21 GMT</pubDate>
            <atom:updated>2025-04-24T22:42:21.556Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b1zGm7wfqQSmifWwrxfRVg.png" /></figure><p>Brute force solution is to use set and explore all subarrays and check unique elements in all subarrays and compare it with the uniques in the original array.</p><pre>class Solution {<br>public:<br>    int countCompleteSubarrays(vector&lt;int&gt;&amp; nums) {<br>        set&lt;int&gt; s(begin(nums), end(nums));<br>        int len = nums.size(), unique = s.size(), cnt = 0;<br><br>        for(int i=0; i&lt; len; i++) {<br>            set&lt;int&gt; s2;<br>            for(int j=i; j&lt; len; j++) {<br>                s2.insert(nums[j]);<br>                if(unique == s2.size()) cnt++;<br>            }<br>        }<br>        return cnt;<br>    }<br>};</pre><ul><li>T.C. = O(n² log n)</li><li>S.C. = O(n)</li></ul><p>Can we optimize? Yes, sliding window approach can help bringing down the time complexity.</p><pre>class Solution {<br>public:<br>    int countCompleteSubarrays(vector&lt;int&gt;&amp; nums) {<br>        int unique = unordered_set&lt;int&gt;(begin(nums), end(nums)).size();<br>        unordered_map&lt;int, int&gt; freq;<br>        int left = 0, right = 0, cnt = 0, uniqueInWindow = 0, len = nums.size();<br><br>        while(right &lt; len) {<br>            int curr = nums[right];<br>            if (++freq[curr] == 1) uniqueInWindow++;<br><br>            while (uniqueInWindow == unique) {<br>                cnt += (len - right);<br>                if (--freq[nums[left++]] == 0) uniqueInWindow--;<br>            }<br>            right++;<br>        }<br><br>        return cnt;<br>    }<br>};</pre><ul><li>T.C. = O(n)</li><li>S.C. = O(n)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=36da52ebff4b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 2338 Count the number of ideal arrays]]></title>
            <link>https://medium.com/@vikasg_65078/leetcode-2338-count-the-number-of-ideal-arrays-7f2c5bd35b32?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/7f2c5bd35b32</guid>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Tue, 22 Apr 2025 23:07:38 GMT</pubDate>
            <atom:updated>2025-04-22T23:07:38.111Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4uOSW0RsCULnu5E_a6UuKQ.png" /></figure><p>I couldn’t completely solve the problem with combinatorics, but have tried the solution using recursion and memoization approach.</p><pre>// arr[i] % arr[i-1] == 0<br>// 1 &lt;= arr[i] &lt;= maxValue<br>// arr[i-1] &lt;= arr[i] --&gt; arr[i] - arr[i-1] &gt;= 0 --&gt; ascending order<br><br>typedef long long int ll;<br><br>class Solution {<br>    int MOD = 1e9 + 7;<br><br>    int idealArraysRec(int &amp;n, int &amp;maxValue, int idx, int prev, vector&lt;vector&lt;int&gt; &gt; &amp;dp) {<br>        if(idx == n) return 1;<br>        if(dp[prev][idx] != -1) return dp[prev][idx];<br><br>        ll cnt = 0;<br><br>        // place multiples of prev as the next value<br>        for(int i= prev; i&lt;= maxValue; i += prev) {<br>            cnt = (cnt + idealArraysRec(n, maxValue, idx+1, i, dp)) % MOD;<br>        }<br><br>        return dp[prev][idx] = cnt; // memoization<br>    }<br><br>public:<br>    int idealArrays(int n, int maxValue) {<br>        ll cnt = 0;<br>        vector&lt;vector&lt;int&gt; &gt; dp(maxValue+1, vector&lt;int&gt;(n+1, -1)); <br><br>        for(int i=1; i &lt;= maxValue; i++) {<br>            cnt = (cnt + idealArraysRec(n, maxValue, 1, i, dp)) % MOD;<br>        }<br><br>        return cnt;<br>    }<br>};</pre><ul><li>T.C. = O(n * maxValue * log(maxValue))</li><li>S.C. = O(n * maxValue)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7f2c5bd35b32" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 2145 Count the hidden sequences]]></title>
            <link>https://medium.com/@vikasg_65078/leetcode-2145-count-the-hidden-sequences-bd669f5cd0ff?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/bd669f5cd0ff</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[prefix-sum]]></category>
            <category><![CDATA[daily-coding-challenge]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Tue, 22 Apr 2025 00:29:05 GMT</pubDate>
            <atom:updated>2025-04-22T00:29:05.032Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-JNRP5eEXJ1BU2lepk2IGw.png" /></figure><p>The problem asks us to find the number of possible hidden sequences of length n+1 where all the values are in the range [lower, upper]. Moreover, sequence must follow the pattern:</p><p>seq[i] = seq[i-1] + diffs[i-1]</p><p>Our aim is just to figure out the max value and min value of the seq[0] such that all values must be in [lower, upper] range. By using the prefix sum approach, we figure out the min and max values of the sequence. Now, calculating minimum and maximum values for seq[0] is all about the following mathematical equation:</p><p>Since, seq[i] = seq[0] + prefixSum[i-1]<br>seq[0] + minPrefix &gt;= lower<br>seq[0] + maxPrefix &lt;= upper</p><p>And total sequences = maxSeq0 — minSeq0 + 1</p><pre>class Solution {<br>public:<br>    int numberOfArrays(vector&lt;int&gt;&amp; diffs, int lower, int upper) {<br>        long minPrefix = 0, maxPrefix = 0, sum = 0;<br><br>        // prefix sum<br>        for (int diff : diffs) {<br>            sum += diff;<br>            minPrefix = min(minPrefix, sum);<br>            maxPrefix = max(maxPrefix, sum);<br>        }<br><br>        long mini = lower - minPrefix;<br>        long maxi = upper - maxPrefix;<br><br>        return max(0L, maxi - mini + 1);<br>    }<br>};</pre><ul><li>T.C. = O(n)</li><li>S.C. = O(1)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bd669f5cd0ff" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 781 Rabbits in Forest]]></title>
            <link>https://medium.com/@vikasg_65078/leetcode-781-rabbits-in-forest-251e596db4d4?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/251e596db4d4</guid>
            <category><![CDATA[maps]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[leetcode-daily-challenge]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Sun, 20 Apr 2025 23:16:16 GMT</pubDate>
            <atom:updated>2025-04-21T02:11:44.540Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4wOPYAMf7S21OiCdFN9zMg.png" /></figure><p>The key insight is that if a rabbit reports seeing k other rabbits of the same color, it means there must be a group of (k + 1) rabbits of that specific color (the rabbit itself + the k others it saw). All rabbits within the same color group will report the same number k.</p><p>Our goal is to find the <em>minimum</em> total number of rabbits. This means we should try to group rabbits reporting the same number into as few distinct color groups as possible.</p><pre>class Solution {<br>public:<br>    int numRabbits(vector&lt;int&gt;&amp; answers) {<br>        unordered_map&lt;int, int&gt; umap; // unique numbers of rabbits seen<br>        int cnt = 0;<br><br>        for(auto ans : answers) {<br>            umap[ans]++;<br>        }<br><br>        for(auto kv : umap) {<br>            // v rabbits reporting k, we need ceil(v / (k + 1)) groups.<br>            int k = kv.first, v = kv.second;<br>            int groupSize = k + 1;<br>            int groups = (v + groupSize - 1) / groupSize; // ceiling division<br>            cnt += groups * groupSize;<br>        }<br><br>        return cnt;<br>    }<br>};</pre><ul><li>T.C. = O(n)</li><li>S.C. = O(u), where u is map size</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=251e596db4d4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Daily Problem 2285. Max total importance of roads: Jun 28, 2024]]></title>
            <link>https://medium.com/@vikasg_65078/leetcode-daily-problem-2285-max-total-importance-of-roads-jun-28-2024-38fb8c9bf477?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/38fb8c9bf477</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[leetcode-daily-challenge]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[graph]]></category>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Fri, 28 Jun 2024 13:53:27 GMT</pubDate>
            <atom:updated>2024-06-28T13:53:27.192Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gVxt7bVw4yLkhl12i423Kw.png" /></figure><p>Easy graph problem. Simply, count the degrees of each node and sort them to assign values in a greedy way such that we get the maximum importance of a road.</p><pre>#define ll long long int<br><br>class Solution {<br>public:<br>    long long maximumImportance(int n, vector&lt;vector&lt;int&gt;&gt;&amp; roads) {<br>        // n cities (0 to n-1)<br>        // assign value (1 to n) to each city<br>        // importance of a road/ edge = sum of 2 city values that we assigned<br>        // max importance<br><br>        vector&lt;ll&gt; degrees(n);<br><br>        // calculate degrees<br>        for(auto edge: roads) {<br>            degrees[edge[0]]++;<br>            degrees[edge[1]]++;<br>        }<br><br>        sort(degrees.begin(), degrees.end());<br><br>        ll val = 1, sum = 0;<br>        for(auto degree: degrees) {<br>            sum += (val * degree);<br>            val++;<br>        }<br><br>        return sum;<br>    }<br>};</pre><p>T.C. = O(nlogn)<br>S.C. = O(n)</p><p>Keep grinding, folks!</p><p>sakiV</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=38fb8c9bf477" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Daily Problem 1038. Binary Search Tree to Greater Sum Tree: Jun 25, 2024]]></title>
            <link>https://medium.com/@vikasg_65078/leetcode-daily-problem-1038-binary-search-tree-to-greater-sum-tree-jun-25-2024-4d8cc708ef51?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/4d8cc708ef51</guid>
            <category><![CDATA[recursion]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[binary-tree]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[leetcode-daily-challenge]]></category>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Tue, 25 Jun 2024 17:45:25 GMT</pubDate>
            <atom:updated>2024-06-25T17:45:25.955Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_injcM4wH2ARdfFU7O0M_Q.png" /></figure><p>Every node’s value is to be replaced with its own value and the sum of all the values greater than it. Since, it’s a BST, we need parent’s modified value and right subtree sum.</p><pre>class Solution {<br>    int gst(TreeNode* parent, TreeNode* root) {<br>        if(!root) return 0;<br><br>        int prevRootVal = root-&gt;val;<br><br>        int rightSubtreeSum = gst(parent, root-&gt;right);<br>        root-&gt;val += rightSubtreeSum + (parent ? parent-&gt;val : 0);<br><br>        int leftSubtreeSum = gst(root, root-&gt;left);<br><br>        return prevRootVal + rightSubtreeSum + leftSubtreeSum;<br>    }<br><br>public:<br>    TreeNode* bstToGst(TreeNode* root) {<br>        // sum of node-&gt;val + right subtree + parent sum<br>        // go to the right &amp; then come to the left --&gt; R N L<br><br>        gst(NULL, root);<br>        return root;<br>    }<br>};</pre><p>T.C. = O(n)<br>S.C. = O(n)</p><p>Keep grinding, folks!</p><p>sakiV</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4d8cc708ef51" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Daily Problem 1438.]]></title>
            <link>https://medium.com/@vikasg_65078/leetcode-daily-problem-1438-74b7a357388b?source=rss-dc09473684e2------2</link>
            <guid isPermaLink="false">https://medium.com/p/74b7a357388b</guid>
            <category><![CDATA[multiset]]></category>
            <category><![CDATA[sliding-window-algorithm]]></category>
            <category><![CDATA[leetcode-daily-challenge]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[dequeue]]></category>
            <dc:creator><![CDATA[Vikas Gogia]]></dc:creator>
            <pubDate>Sun, 23 Jun 2024 20:10:31 GMT</pubDate>
            <atom:updated>2024-06-23T20:10:31.231Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Daily Problem 1438. Longest continuous subarray with absolute diff less than or equal to limit: Jun 23, 2024</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sVu3_UFCUqtadtqSESk_wQ.png" /></figure><p>We are asked to return size of longest subarray such that max abs diff b/w 2 elements is &lt;= limit. Here, we can consider having max and min values in a subarray and try finding the difference between the max and min and check if that’s ≤ limit.</p><p>Brute force approach: Simple enough. Get all subarrays, check for max and min values, and calculate the max length where maxi — mini ≤ limit. This approach take T.C.= O(n²), S.C. = O(1)</p><pre>class Solution {<br><br>    // T.C. = O(n^2), S.C. = O(1)<br>    int bruteForce(vector&lt;int&gt;&amp; arr, int limit) {<br>        int n = arr.size(), len = 0;<br>        for(int i=0; i&lt; n; i++) {<br>            int maxi = INT_MIN, mini = INT_MAX;<br><br>            for(int j=i; j&lt; n; j++) {<br>                maxi = max(maxi, arr[j]);<br>                mini = min(mini, arr[j]);<br><br>                if(maxi - mini &lt;= limit) {<br>                    len = max(len, j-i+1);<br>                }<br>            }<br>        }<br>        return len;<br>    }<br><br>public:<br>    int longestSubarray(vector&lt;int&gt;&amp; arr, int limit) {<br>        <br>        return bruteForce(arr, limit);<br>    }<br>};</pre><p>Looking at the time constraints, we clearly know that this is going to give TLE. So, we use another approach here. We use a sliding window approach to get through this in less time. So, we expand until the max and min values are ≤ limit, and once maxi — mini &gt; limit, we start shrinking. Now the question is, how do we shrink and get the new or updated maxi and mini values for the subarray after shrinking?</p><p>We use an additional data structure for that. We use a multiset&lt;int&gt; which will store the elements in a sorted fashion and we can retrieve maxi and mini values after removal during shrinking.</p><p>to fetch minimum element from multiset -&gt; *ms.begin()<br>to fetch maximum element from multiset -&gt; *ms.rbegin()<br>to erase an element from multiset -&gt; *ms.erase(ms.find(element))</p><pre>class Solution {<br><br>    // T.C. = O(nlogn), S.C. = O(n)<br>    int betterApproach(vector&lt;int&gt;&amp; arr, int limit) {<br>        // sliding window<br>        int n = arr.size(), left = 0, right = 0, len = 0;<br>        multiset&lt;int&gt; sorted;<br><br>        while(right &lt; n) {<br>            // expand<br>            sorted.insert(arr[right]);<br>            int diff = *sorted.rbegin() - *sorted.begin();<br>            <br>            // shrink<br>            while(left &lt; n &amp;&amp; diff &gt; limit) {<br>                sorted.erase(sorted.find(arr[left++]));<br>                diff = *sorted.rbegin() - *sorted.begin();<br>            }<br>            <br>            len = max(len, (int)sorted.size());<br>            right++;<br>        }<br>        return len;<br>    }<br><br>public:<br><br>    int longestSubarray(vector&lt;int&gt;&amp; arr, int limit) {<br><br>        return betterApproach(arr, limit);<br>    }<br>};</pre><p>T.C. = O(n * logn)<br>S.C. = O(n)</p><p>This approach is accepted and pretty decent for interview questions. But, let’s think of how can we reduce this T.C. to O(n).</p><p>Let’s take an example:</p><p>[10, 1, 2, 4, 7, 2], limit = 5</p><p>let’s take a data structure for each max and min values:<br>maxi = [ ]<br>mini = [ ]</p><p>Step 1: 10, maxi = [10], mini = [10], 10–10 = 0, 0 ≤ 5 → len = 1</p><p>Step 2: 1, maxi = [10, 1], mini = [1, 10], → for mini, we don’t need 10 as 10 is at 0 index &amp; 1 is at index 1, so remove 10 from mini.<br>maxi = [10, 1], mini = [1]<br>now, 10–1 = 9 &gt; 5 → shrink → find left = min of index(maxi, mini) + 1<br>and remove elements with index &lt; left from mini &amp; maxi<br>maxi = [1], mini = [1]</p><p>Step 3: 2, maxi = [2], mini = [1, 2]</p><p>Step 4: 4, maxi = [4], mini = [1, 2, 4]</p><p>Step 5: 7, maxi = [7], mini = [1, 2, 4, 7]</p><p>Step 6: 2, maxi = [7, 2], mini = [1, 2, 2]</p><p>Here, we push every element at the back and want to get an ability to pop from front and back. So, we use deque data structure.</p><pre>class Solution {<br><br>public:<br><br>    // T.C. = O(n), S.C. = O(n)<br>    int longestSubarray(vector&lt;int&gt;&amp; arr, int limit) {<br><br>        deque&lt;int&gt; maxQ, minQ;<br>        int left = 0, right = 0, n = arr.size(), len = 0;<br><br>        while(right &lt; n) {<br>            // remove from maxQ deque until the back() &lt; currElement<br>            while(!maxQ.empty() &amp;&amp; arr[maxQ.back()] &lt; arr[right]) maxQ.pop_back();<br>            maxQ.push_back(right);<br><br>            // remove from minQ deque until the back() &gt; currElement<br>            while(!minQ.empty() &amp;&amp; arr[minQ.back()] &gt; arr[right]) minQ.pop_back();<br>            minQ.push_back(right);<br><br>            int diff = arr[maxQ.front()] - arr[minQ.front()];<br><br>            // shrink<br>            while(left &lt; right &amp;&amp; diff &gt; limit) {<br>                left = min(maxQ.front(), minQ.front()) + 1;<br><br>                // remove the elements from front of which index &lt; newLeft<br>                while(!maxQ.empty() &amp;&amp; maxQ.front() &lt; left) maxQ.pop_front();<br>                while(!minQ.empty() &amp;&amp; minQ.front() &lt; left) minQ.pop_front();<br><br>                diff = arr[maxQ.front()] - arr[minQ.front()];<br>            }<br><br>            len = max(len, right - left + 1);<br>            right++;<br>        }<br><br>        return len;<br>    }<br>};</pre><p>T.C. = O(n)<br>S.C. = O(n)</p><p>Keep grinding, folks!</p><p>sakiV</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=74b7a357388b" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>