<?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 SOURABH GURAV on Medium]]></title>
        <description><![CDATA[Stories by SOURABH GURAV on Medium]]></description>
        <link>https://medium.com/@Sourabh_Gurav?source=rss-e55c50b0ff9d------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*JSwTgRzJ_YUWUdig3MjB6w.png</url>
            <title>Stories by SOURABH GURAV on Medium</title>
            <link>https://medium.com/@Sourabh_Gurav?source=rss-e55c50b0ff9d------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 09:40:58 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@Sourabh_Gurav/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[“Yeahhh ! Sign in with Google ! ”: But What Actually Happens When You Click That Easy Button ?]]></title>
            <link>https://medium.com/@Sourabh_Gurav/yeahhh-sign-in-with-google-but-what-actually-happens-when-you-click-that-easy-button-762ea16e2acc?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/762ea16e2acc</guid>
            <category><![CDATA[google-auth]]></category>
            <category><![CDATA[google-cloud-platform]]></category>
            <category><![CDATA[authentication]]></category>
            <category><![CDATA[google-console]]></category>
            <category><![CDATA[cloud-secuirty]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Mon, 02 Nov 2026 15:52:36 GMT</pubDate>
            <atom:updated>2026-11-02T15:52:36.684Z</atom:updated>
            <content:encoded><![CDATA[<p><em>A step-by-step look at OAuth 2.0, OpenID Connect and PKCE, with Django examples</em></p><h3>Introduction</h3><p>Lets say you land on a new website, see <strong>“Sign in with Google”</strong>, click it, pick your account, and you’re in. You didn’t fill in a form or invent a password.</p><p>It’s quick and easy, which is why most of us prefer it. But a lot happens in those few seconds. Your browser, the website’s backend and Google pass messages back and forth, and each message is protected so attackers can’t hijack your login.</p><p>This post walks through the whole flow one step at a time, with backend code like in a Django website for each part.</p><h4>The scenario</h4><p>You want to sign up on a website (we’ll call it <strong>yourapp.com</strong>, and say it’s built with Django). You don’t want to type out your details or make up another password, so you click <strong>Sign in with Google</strong>.</p><h4>The three actors</h4><ul><li><strong>You (the browser)</strong> carry messages between the other two.</li><li><strong>The website’s backend (Django)</strong> wants to know who you are.</li><li><strong>Google</strong> knows who you are and can vouch for you.</li></ul><p>Under the hood, this is <strong>OAuth 2.0</strong> (for authorization) plus <strong>OpenID Connect (OIDC)</strong> (for identity), protected by <strong>PKCE</strong>. Let’s go through each step.</p><h3>Step 1: You click the Google button</h3><p>When you click <strong>Sign in with Google</strong>, your browser sends a request to the website’s own backend first, for example GET /accounts/google/login/. It does <strong>not</strong> go straight to Google. Django backend needs to do some setup before it sends you anywhere.</p><h3>Step 2: Django creates two security values (state and PKCE)</h3><p>Before redirecting you, Django generates two random secrets and saves them in your <strong>server-side session</strong>.</p><h4>2a. state: protection against CSRF</h4><ul><li>state is a long random string.</li><li>Django sends it to Google, and Google sends it back unchanged at the end.</li><li>When you come back, Django checks that the returned state matches the one it saved.</li></ul><p><strong>Why it matters:</strong> this stops <strong>Cross-Site Request Forgery (CSRF)</strong>. Without it, an attacker could trick your browser into finishing <em>their</em> login on your session. The state also ties the callback to the login attempt that started it.</p><h4>2b. PKCE: protection for the authorization code</h4><p>PKCE (Proof Key for Code Exchange, pronounced “pixy”) makes sure that <strong>only the app that started the login can finish it</strong>.</p><ol><li>Django creates a high-entropy random secret called the <strong>code_verifier</strong>, 43 to 128 URL-safe characters long:</li></ol><pre>code_verifier = &quot;xK9...43-to-128-random-url-safe-chars..</pre><p>2. Django hashes it to create a <strong>non-secret</strong> value called the <strong>code_challenge</strong>:</p><pre>code_challenge = BASE64URL( SHA256(code_verifier) )</pre><p>3. This is the <strong>S256</strong> method, which is the recommended one. (The other method, plain, sends the verifier unhashed and should be avoided.)</p><p><strong>4. The </strong><strong>code_challenge goes to Google. The </strong><strong>code_verifier stays secret in Django’s session.</strong></p><p>Later, when Django trades the code for tokens, it reveals the code_verifier. Google hashes it and compares the result with the code_challenge it saved earlier. <strong>If they don’t match, Google rejects the request.</strong> So even if an attacker steals the authorization code, it’s useless without the verifier.</p><h4>2c. (Bonus) nonce: protection for the ID token</h4><p>Because this is OpenID Connect, it’s also good practice to send a <strong>nonce</strong>. Google copies it into the ID token, and Django checks it later. This blocks replay of an old ID token.</p><pre>#Code: generating the values<br># accounts/views.py<br>import base64<br>import hashlib<br>import secrets<br>from urllib.parse import urlencode<br><br>from django.conf import settings<br>from django.shortcuts import redirect<br><br>GOOGLE_AUTH_URL = &quot;https://accounts.google.com/o/oauth2/v2/auth&quot;<br><br><br>def _make_pkce_pair():<br>    code_verifier = secrets.token_urlsafe(64)  # ~86 URL-safe chars<br>    digest = hashlib.sha256(code_verifier.encode(&quot;ascii&quot;)).digest()<br>    code_challenge = base64.urlsafe_b64encode(digest).rstrip(b&quot;=&quot;).decode(&quot;ascii&quot;)<br>    return code_verifier, code_challenge<br><br><br>def google_login(request):<br>    state = secrets.token_urlsafe(32)<br>    nonce = secrets.token_urlsafe(32)<br>    code_verifier, code_challenge = _make_pkce_pair()<br><br>    # Secrets stay on the server, in the session<br>    request.session[&quot;oauth_state&quot;] = state<br>    request.session[&quot;oauth_nonce&quot;] = nonce<br>    request.session[&quot;pkce_code_verifier&quot;] = code_verifier<br><br>    params = {<br>        &quot;client_id&quot;: settings.GOOGLE_CLIENT_ID,<br>        &quot;redirect_uri&quot;: settings.GOOGLE_REDIRECT_URI,<br>        &quot;response_type&quot;: &quot;code&quot;,<br>        &quot;scope&quot;: &quot;openid email profile&quot;,<br>        &quot;state&quot;: state,<br>        &quot;nonce&quot;: nonce,<br>        &quot;code_challenge&quot;: code_challenge,<br>        &quot;code_challenge_method&quot;: &quot;S256&quot;,<br>        # Optional, see the table in Step 3:<br>        # &quot;access_type&quot;: &quot;offline&quot;,<br>        # &quot;prompt&quot;: &quot;consent&quot;,<br>    }<br>    return redirect(f&quot;{GOOGLE_AUTH_URL}?{urlencode(params)}&quot;)</pre><p><strong>Note:</strong> Django saves the session after the view returns, so the stored values are there when you come back.</p><h3>Step 3: Your browser is redirected to Google</h3><p>Django replies with a redirect, and your browser goes to Google’s login and consent page at a URL like this (line breaks added for readability):</p><pre>https://accounts.google.com/o/oauth2/v2/auth<br>  ?client_id=1234567890-abcdefg.apps.googleusercontent.com<br>  &amp;redirect_uri=https%3A%2F%2Fyourapp.com%2Faccounts%2Fgoogle%2Flogin%2Fcallback%2F<br>  &amp;response_type=code<br>  &amp;scope=openid%20email%20profile<br>  &amp;state=9f8c1a2b7d6e4f5a<br>  &amp;nonce=n-0S6_WzA2Mj<br>  &amp;code_challenge=E9Melhoa2OwvFrEMTJguCHaoeK1t8URWbuGJSstw-cM<br>  &amp;code_challenge_method=S256<br>  &amp;access_type=offline<br>  &amp;prompt=consent</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kGyrgxFpt2-Y4Bb2r044vA.png" /></figure><h4>What is not in the URL</h4><ul><li><strong>No </strong><strong>code_verifier.</strong> It never leaves Django until the server-to-server exchange in Step 6.</li><li><strong>No client secret.</strong> It’s never sent through the browser.</li></ul><h3>Step 4: You log in to Google and give consent</h3><p>You’re now on Google’s own page, so:</p><ul><li><strong>The website never sees your Google password.</strong> You type it only into Google.</li><li>If you’re already signed in to Google, you might just pick an account.</li><li>Google shows what the app wants (name, email, profile picture), and you click <strong>Continue</strong> or <strong>Allow</strong>.</li></ul><p>Google then creates a one-time <strong>authorization code</strong> and links it to the code_challenge it received in Step 3.</p><h3>Step 5: Google sends you back to the website</h3><p>Google redirects your browser to the redirect_uri, adding a few values to the URL:</p><pre>https://yourapp.com/accounts/google/login/callback/<br>  ?state=9f8c1a2b7d6e4f5a<br>  &amp;code=4%2F0AX4XfWj...<br>  &amp;scope=email+profile+openid<br>  &amp;authuser=0<br>  &amp;prompt=consent</pre><ul><li><strong>code</strong> is the one-time, short-lived authorization code. It isn’t a token yet; it’s more like a claim ticket.</li><li><strong>state</strong> is the same value Django sent in Step 3, returned unchanged.</li><li><strong>No </strong><strong>code_verifier.</strong> Google never had it. Django will use the copy in its session.</li></ul><blockquote><em>If you click </em><strong><em>Cancel</em></strong><em> on Google’s screen, the callback comes back with </em><em>?error=access_denied instead of a </em><em>code. Your callback should handle that too.</em></blockquote><h3>Step 6: Django checks state and exchanges the code for tokens</h3><p>This step happens <strong>after</strong> the browser arrives at the callback URL. In the callback view, Django:</p><ol><li><strong>Reads</strong> code and state from the query string.</li><li><strong>Compares </strong><strong>state</strong> with the value stored in the session. <strong>If they differ, it rejects the request</strong> (possible CSRF).</li><li><strong>Gets the </strong><strong>code_verifier</strong> it saved when the login began.</li><li><strong>Makes a server-to-server HTTPS POST</strong> to Google’s token endpoint, https://oauth2.googleapis.com/token, sending:</li></ol><ul><li>the code</li><li>the code_verifier (PKCE proof)</li><li>its client_id and client_secret (a backend like Django is a “confidential client”, so it authenticates itself as well)</li><li>the same redirect_uri</li></ul><p>5. <strong>Google checks everything:</strong> the code is valid, unused and not expired; SHA256(code_verifier) matches the stored code_challenge; and the client credentials and redirect_uri are correct.</p><p>6. If everything checks out, Google returns <strong>tokens</strong>:</p><ul><li><strong>id_token</strong>: a signed JWT that says who you are (this is the OpenID Connect part)</li><li><strong>access_token</strong>: lets the app call Google APIs for you</li><li><strong>refresh_token</strong>: only if you asked for access_type=offline</li></ul><p><strong>7. Django removes</strong> the one-time state and code_verifier from the session so they can’t be reused.</p><p>The authorization code works <strong>only once</strong> and expires quickly.</p><pre># accounts/views.py (continued)<br>import requests<br>from django.http import HttpResponseBadRequest<br><br>GOOGLE_TOKEN_URL = &quot;https://oauth2.googleapis.com/token&quot;<br><br><br>def google_callback(request):<br>    # User cancelled or Google returned an error<br>    if &quot;error&quot; in request.GET:<br>        return redirect(&quot;/login/?error=&quot; + request.GET[&quot;error&quot;])<br><br>    # 1. Check state (CSRF protection); pop() also clears it<br>    returned_state = request.GET.get(&quot;state&quot;, &quot;&quot;)<br>    expected_state = request.session.pop(&quot;oauth_state&quot;, None)<br>    if not expected_state or not secrets.compare_digest(returned_state, expected_state):<br>        return HttpResponseBadRequest(&quot;Invalid state&quot;)<br><br>    # 2. Get the stored PKCE verifier (single-use)<br>    code_verifier = request.session.pop(&quot;pkce_code_verifier&quot;, None)<br>    code = request.GET.get(&quot;code&quot;)<br>    if not code or not code_verifier:<br>        return HttpResponseBadRequest(&quot;Missing code or verifier&quot;)<br><br>    # 3. Server-to-server exchange: the browser never sees this<br>    response = requests.post(<br>        GOOGLE_TOKEN_URL,<br>        data={<br>            &quot;grant_type&quot;: &quot;authorization_code&quot;,<br>            &quot;code&quot;: code,<br>            &quot;code_verifier&quot;: code_verifier,<br>            &quot;client_id&quot;: settings.GOOGLE_CLIENT_ID,<br>            &quot;client_secret&quot;: settings.GOOGLE_CLIENT_SECRET,<br>            &quot;redirect_uri&quot;: settings.GOOGLE_REDIRECT_URI,<br>        },<br>        timeout=10,<br>    )<br>    if response.status_code != 200:<br>        return redirect(&quot;/login/?error=token_exchange_failed&quot;)<br><br>    tokens = response.json()  # id_token, access_token, maybe refresh_token<br>    return handle_google_login(request, tokens)</pre><h3>Step 7: Django turns “Google says it’s you” into a real login</h3><p>Django now has tokens, but you aren’t logged in to yourapp.com yet. This final step turns Google’s word into a local Django session.</p><p>Google’s guidance is to verify the ID token on the server, then create a session from its claims.</p><h4>What this step does</h4><ol><li>Verify the ID token. Check that:</li></ol><ul><li>Google signed it (signature checked against Google’s public keys)</li><li>it was issued for your app (aud equals your client_id)</li><li>it came from Google (iss is accounts.google.com or <a href="https://accounts.google.com)/">https://accounts.google.com)</a></li><li>it hasn’t expired (exp)</li><li>the nonce matches the one you sent in Step 3</li></ul><p>2. Read the user’s claims: sub, email, email_verified, name, given_name, family_name, picture.</p><p>3. Find or create the Django user. Match the Google account to an existing user, or create one on first login. This is how you “sign up” without filling in a form.</p><p>4. Log the user in with Django’s login(), which sets the session cookie.</p><p>5. Optionally store OAuth tokens, if your app needs to call Google APIs later.</p><p>6. Redirect the user to the dashboard, home page or the page they originally wanted.</p><h4>What the ID token contains</h4><p>Once verified, the decoded claims look something like this:</p><pre>{<br>  &quot;iss&quot;: &quot;https://accounts.google.com&quot;,<br>  &quot;azp&quot;: &quot;1234567890-abcdefg.apps.googleusercontent.com&quot;,<br>  &quot;aud&quot;: &quot;1234567890-abcdefg.apps.googleusercontent.com&quot;,<br>  &quot;sub&quot;: &quot;110169484474386276334&quot;,<br>  &quot;email&quot;: &quot;sourabh@example.com&quot;,<br>  &quot;email_verified&quot;: true,<br>  &quot;name&quot;: &quot;Sourabh Gurav&quot;,<br>  &quot;given_name&quot;: &quot;Sourabh&quot;,<br>  &quot;family_name&quot;: &quot;Gurav&quot;,<br>  &quot;picture&quot;: &quot;https://lh3.googleusercontent.com/...&quot;,<br>  &quot;nonce&quot;: &quot;n-0S6_WzA2Mj&quot;,<br>  &quot;iat&quot;: 1790000000,<br>  &quot;exp&quot;: 1790003600<br>}</pre><p><strong>Use </strong><strong>sub, not </strong><strong>email, as the permanent account key.</strong> sub is Google’s stable, unique ID for the account and never changes. An email address can change or be reused.</p><p>Code: verifying the token and logging in</p><pre># accounts/views.py (continued)<br>from django.contrib.auth import login<br>from django.contrib.auth.models import User<br>from django.db import transaction<br>from google.auth.transport import requests as google_requests<br>from google.oauth2 import id_token<br><br>from accounts.models import GoogleAccount  # links a Django user to a Google `sub`<br><br>GOOGLE_ISSUERS = {&quot;accounts.google.com&quot;, &quot;https://accounts.google.com&quot;}<br><br><br>def handle_google_login(request, tokens):<br>    # 1. Verify the ID token: signature, aud and exp (recent google-auth also checks iss)<br>    try:<br>        claims = id_token.verify_oauth2_token(<br>            tokens.get(&quot;id_token&quot;),<br>            google_requests.Request(),<br>            settings.GOOGLE_CLIENT_ID,<br>        )<br>    except ValueError:<br>        return redirect(&quot;/login/?error=invalid_google_token&quot;)<br><br>    # Explicit issuer check (cheap insurance)<br>    if claims.get(&quot;iss&quot;) not in GOOGLE_ISSUERS:<br>        return redirect(&quot;/login/?error=invalid_issuer&quot;)<br><br>    # Nonce check: the token must belong to *this* login attempt<br>    expected_nonce = request.session.pop(&quot;oauth_nonce&quot;, None)<br>    if not expected_nonce or claims.get(&quot;nonce&quot;) != expected_nonce:<br>        return redirect(&quot;/login/?error=invalid_nonce&quot;)<br><br>    if not claims.get(&quot;email_verified&quot;, False):<br>        return redirect(&quot;/login/?error=email_not_verified&quot;)<br><br>    # 2. Read claims<br>    google_sub = claims[&quot;sub&quot;]<br>    email = claims[&quot;email&quot;]<br><br>    # 3. Find or create the local user<br>    with transaction.atomic():<br>        google_account = (<br>            GoogleAccount.objects.select_related(&quot;user&quot;)<br>            .filter(google_sub=google_sub)<br>            .first()<br>        )<br>        if google_account:<br>            user = google_account.user<br>        else:<br>            user = User.objects.create(<br>                username=f&quot;google_{google_sub}&quot;,<br>                email=email,<br>                first_name=claims.get(&quot;given_name&quot;, &quot;&quot;),<br>                last_name=claims.get(&quot;family_name&quot;, &quot;&quot;),<br>            )<br>            user.set_unusable_password()  # this user signs in only via Google<br>            user.save()<br>            google_account = GoogleAccount.objects.create(<br>                user=user,<br>                google_sub=google_sub,<br>                email=email,<br>                picture=claims.get(&quot;picture&quot;, &quot;&quot;),<br>            )<br><br>        # 5. Optional: keep a refresh token for later Google API calls.<br>        # Store it in the database (encrypted at rest), not in the session.<br>        if tokens.get(&quot;refresh_token&quot;):<br>            google_account.refresh_token = tokens[&quot;refresh_token&quot;]<br>            google_account.save(update_fields=[&quot;refresh_token&quot;])<br><br>    # 4. Start the Django session (also rotates the session key)<br>    login(request, user, backend=&quot;django.contrib.auth.backends.ModelBackend&quot;)<br><br>    # 6. Send them on their way<br>    return redirect(&quot;dashboard&quot;)</pre><h4>Why verification matters</h4><p>The id_token is a <strong>signed JWT</strong>. Verifying it confirms that:</p><ul><li><strong>Google</strong> signed it, not an attacker</li><li>it was issued <strong>for your app</strong>, not for some other site</li><li>it <strong>hasn’t expired</strong></li><li>it came from <strong>Google’s issuer</strong></li></ul><p>Google’s Python helper verify_oauth2_token() checks the signature, aud and exp. Recent versions of google-auth also check iss, and the explicit check above is a cheap extra safeguard. If you only allow users from a specific Google Workspace domain, also check the hd (hosted domain) claim.</p><h3>Step 8: You’re in</h3><p>Your browser now holds a normal <strong>Django session cookie</strong>, and you land on the dashboard. On later visits, Django recognizes the cookie. Google isn’t involved again until the session expires or you log out.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*boUb-dAkrCHfMTYuSua5iw.png" /></figure><p>After Step 7, the user has a normal Django session. Django may also keep Google tokens, but <strong>only if it needs to call Google APIs</strong>. For plain “Sign in with Google”, you often don’t need to store them at all.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=762ea16e2acc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Maximum Matrix Sum]]></title>
            <link>https://medium.com/@Sourabh_Gurav/maximum-matrix-sum-027ea555e115?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/027ea555e115</guid>
            <category><![CDATA[matrix]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[leetcode-medium]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Mon, 05 Jan 2026 18:04:58 GMT</pubDate>
            <atom:updated>2026-01-05T18:04:58.837Z</atom:updated>
            <content:encoded><![CDATA[<p>This problem might seem intimidating though its really super intuitive if you really understand the problem in and out. What the problem states is that you have been given a n*n matrix. You can chose any bordering adjacent cells and multiply both the elements of the matrix by -1 effectively reversing the signs of the elements.</p><p>You can continue doing this operation as many times as you want but the condition has to be satisfied. The two selected elements must be adjacent.</p><p>In this way we have to maximize the sum of those all numbers in the matrix.</p><p>What we can observe is that we can reverse signs of all negative numbers as we are allowed to do the above operation n number of times. So if there are even number of negative numbers we can effectively make all positives. But if the negative numbers are odd, we have one negative number remaining even if we apply as many number of times the above operation as possible. So we make sure we choose the minimum value number from the matrix so that our sum of numbers from the matrix is maximized.</p><p>The catch is if number of negative numbers is even we can just return sum of absolute values all numbers. But if we have odd number of negative numbers we have to subtract twice the value of the minimum absolute value number. You subtract <strong>2 × smallest_abs_value</strong> because you counted it once as <strong>positive</strong>, but it must end up <strong>negative</strong>, and flipping from +x to −x costs <strong>2x</strong>.</p><pre>class Solution(object):<br>    def maxMatrixSum(self, matrix):<br>        &quot;&quot;&quot;<br>        :type matrix: List[List[int]]<br>        :rtype: int<br>        &quot;&quot;&quot;<br>        ab_sum  = 0<br>        negatives = 0<br>        min_ab_val = float(&quot;inf&quot;)<br>        for r in range(len(matrix)):<br>            for c in range(len(matrix[0])):<br>                val = matrix[r][c]<br>                ab_sum += abs(val)<br>                if val &lt; 0:<br>                    negatives += 1<br>                min_ab_val = min(min_ab_val, abs(val))<br>        <br>        return ab_sum if negatives % 2 == 0 else ab_sum - 2*min_ab_val</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=027ea555e115" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Pascal’s Triangle]]></title>
            <link>https://medium.com/@Sourabh_Gurav/pascals-triangle-9241d519d64c?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/9241d519d64c</guid>
            <category><![CDATA[pascal-triangle]]></category>
            <category><![CDATA[leetcode-medium]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Sun, 04 Jan 2026 15:35:10 GMT</pubDate>
            <atom:updated>2026-01-04T15:35:10.804Z</atom:updated>
            <content:encoded><![CDATA[<p>This is one of those problems that demand seeing the pattern and building the most simplist solution on it. If you miss seeing the pattern you would probably have a little hard time arriving onto the solution.</p><p>The question wants us to build an array where the i th element (which would be an array) is the i th row of the Pascal’s Triangle.</p><p>The objective is to generate a two-dimensional array where the element at index i corresponds to the i-th row of Pascal’s Triangle. Every row begins and ends with the value `1`.</p><p>The intermediate elements of the current row are derived from the previous row; specifically, the value at index `j` in the current row is calculated as the sum of the elements at indices `j` and `j-1` in the immediately preceding row.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*jVSBGt4JxvghPvDy.png" /></figure><pre>class Solution:<br>    def generate(self, numRows: int) -&gt; List[List[int]]:<br>        # Handle edge case immediately<br>        if numRows == 0:<br>            return []<br>        <br>        res = [[1]]<br>        <br>        for i in range(numRows - 1):<br>            prev_row = res[-1]<br>            new_row = [1]<br>            <br>            for j in range(1, len(prev_row)):<br>                new_row.append(prev_row[j-1] + prev_row[j])<br>            <br>            new_row.append(1)<br>            res.append(new_row)<br>            <br>        return res</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9241d519d64c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Four Divisors]]></title>
            <link>https://medium.com/@Sourabh_Gurav/four-divisors-149c744c8117?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/149c744c8117</guid>
            <category><![CDATA[math]]></category>
            <category><![CDATA[biweekly]]></category>
            <category><![CDATA[leetcode-medium]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Sun, 04 Jan 2026 06:42:48 GMT</pubDate>
            <atom:updated>2026-01-04T06:42:48.413Z</atom:updated>
            <content:encoded><![CDATA[<p>This is one of the straightforward questions one can ask. First you check the constraints and realise that it can be solved with a brute force approach. But a little twist but still a brute force.</p><p>Constraints:</p><ul><li>1 &lt;= nums.length &lt;= 104</li><li>1 &lt;= nums[i] &lt;= 105</li></ul><p>Here in the question you are asked to find out sum of divisors for all numbers in the “nums” array that have exactly 4 divisors.</p><p>Obvious thing you can do is iterate over all numbers , find out which ones have divisors equal to 4 and sum only those divisors for that number and finally return the grand total of divisors.</p><p>But the different approach is we only check divisors for a number starting from 1 to square root of that number. The reason is :</p><p>For any divisor of a number <em>n ,</em> it has<em> </em>a “partner” that it multiplies with to be equal to <em>n</em>. If <em>i </em>is a divisor of <em>n </em>, then there must be another integer <em>j </em>such that: <em>i</em>×<em>j</em>=<em>n</em></p><p>Now, imagine <em>i </em>starts small (1,2,3…) and increases. Its partner <em>j </em>starts huge (<em>n</em>,<em>n</em>/2,<em>n</em>/3…) and decreases. There is a specific point where these two numbers meet. That meeting point is the square root.</p><ul><li>If one divisor is smaller than the square root, its partner must be larger than the square root.</li><li>If one divisor is larger than the square root, you have already found its smaller partner earlier in the loop.</li></ul><p>Example with <em>n</em>=100 :</p><ul><li>The square root of 100 is 10</li><li>Let’s look at the factor pairs:</li><li>2×<strong>50</strong>=100 (Found 2, we know 50 exists)</li><li>4×<strong>25</strong>=100 (Found 4, we know 25 exists)</li><li>5×<strong>20</strong>=100 (Found 5, we know 20 exists)</li><li>10×10=100 (The perfect square pair)</li></ul><p>If we keep looping past 10,</p><ul><li>Next we would find 20, But we already know 20 exists because we found 5 earlier!</li><li>Next we would find 25, But we already know 25 exists because we found 4 earlier !</li></ul><p>Therefore, once you pass the square root (10), you are just finding the “partners” of divisors you have already seen. You aren’t finding any <em>new</em> divisors.</p><p>So we check the divisors for each number and make sure we do not caclculate same divisors like 10 and 10 as 10 * 10 is 100 but we consider 10 once. We check if the partner is different from i that is i*j = n and i !=j.</p><p>We also make sure we import math and use ‘isqrt’ function since using “**0.5” might return float number close to the actual answer but not exact square root answer .</p><p>For example: square root of 49 is​ 7.0 and 49**0.5 might result in 6.999999999999999 due to floating point limitations.</p><pre>import math<br>class Solution:<br>    def sumFourDivisors(self, nums: List[int]) -&gt; int:<br>        def FourDivisorsum(num):<br>            n = math.isqrt(num) <br><br>            count = 0<br>            res = 0<br>            for i in range(1,n+1):<br>                if num%i == 0:<br>                    res += i<br>                    count += 1<br>                    if i != num//i:<br>                        res += (num//i)<br>                        count += 1<br>                if count &gt; 4:<br>                    return 0<br>            return res if count == 4 else 0<br>        <br>        res  = 0<br>        for num in nums:<br>            res += FourDivisorsum(num)<br>        return res</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=149c744c8117" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Plus One: First Problem of the New Year 2026]]></title>
            <link>https://medium.com/@Sourabh_Gurav/plus-one-first-problem-of-the-new-year-2026-988e9674c386?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/988e9674c386</guid>
            <category><![CDATA[simulation]]></category>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[leetcode-easy]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Sat, 03 Jan 2026 05:58:38 GMT</pubDate>
            <atom:updated>2026-01-03T05:58:38.668Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>Question: </strong>we have been given an array that represents the integer without any leading zeros. The number formed by the digits (elements) of the ‘digits’ array is actually from most significant to least significant in left-to-right order.</p><p>We have to add one to the number that is formed and return the digits of that resulting number in form of array where each element is its digits from most significant to least significant in left-to-right order.</p><p>Here the constraints are:</p><p><strong>1. there can be 100 elements at the most or atleast 1 element in array</strong></p><p><strong>2. Elements of the array can be any digits from 0 - 9 without any leading 0.</strong></p><p>What I observed is that we always have to add 1 to the least significant number that is the rightmost digitof the number formed. If the addition results in number greater than 9 we have to carry forward that “addition” to the next number (Basic addition maths).</p><p>We follow the same rule iterating backwards from the rightmost element digit to the leftmost digit and also keep updating the current digit in that place, but we stop and return the digits as soon as the addition results in value less than 9 because there nothing to carry forward and hence no changes would be applied to digits from here.</p><p>We solve this by simulating standard addition from right to left. Starting with an initial carry of, we iterate through the digits from the least significant digit (the end) to the most significant digit (the start). In each step, we add the carry to the current digit.</p><p>If the result is less than 10, we update the digit and immediately return the array, as no further carry propagation is needed. If the result is 10 or greater, we set the current digit to 0 (using modulo), keep the carry as 1, and continue moving left. If we finish the loop and still have a carry remaining, we insert it at the beginning of the list.</p><pre>class Solution:<br>    def plusOne(self, digits: List[int]) -&gt; List[int]:<br>        n = len(digits)<br>        addition = 1<br>        for i in range(n-1,-1,-1):<br>            value = digits[i] + addition<br>            if value &lt; 9:<br>                digits[i] = value<br>                return digits<br>            else:<br>                digits[i] = value % 10<br>                addition = value // 10<br>        if addition:<br>            digits = [addition] + digits<br>        return digits</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=988e9674c386" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Count Covered Buildings]]></title>
            <link>https://medium.com/@Sourabh_Gurav/count-covered-buildings-dd3d2790aae1?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/dd3d2790aae1</guid>
            <category><![CDATA[leetcode-medium]]></category>
            <category><![CDATA[cartesian-coordinates]]></category>
            <category><![CDATA[hashmap]]></category>
            <category><![CDATA[geometry]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Thu, 11 Dec 2025 16:02:13 GMT</pubDate>
            <atom:updated>2025-12-11T16:02:13.879Z</atom:updated>
            <content:encoded><![CDATA[<p>The intuition………….</p><p>Solving leetcode problems, once a while I realized that recognizing patterns is so important. We all are good at coding , at least now with vibe coding. But what remains crucial is having a eye for patterns and ideas and possibilities.</p><p>This problem taught me that. Here the problem asks you to count how many buildings are <strong>completely surrounded</strong> by other buildings.</p><p>Think of it like standing in a formation of people. You are “covered” only if you have people protecting you on <strong>all four sides</strong>.</p><h3>The Rules for Being “Covered”</h3><p>For a building at coordinates (x, y) to be counted, it must satisfy <strong>two conditions simultaneously</strong>:</p><ol><li><strong>Vertical Sandwich:</strong> There must be at least one building <strong>directly above</strong> it and at least one <strong>directly below</strong> it (on the same vertical line).</li><li><strong>Horizontal Sandwich:</strong> There must be at least one building <strong>directly to the left</strong> and at least one <strong>directly to the right</strong> (on the same horizontal line).</li><li>If a building is missing a neighbor on <strong>any</strong> of these four sides (Top, Bottom, Left, or Right), it is <strong>not</strong> covered.</li></ol><p>Here is the breakdown of why the solution uses grouping and focuses on the Min/Max coordinates.</p><pre>class Solution:<br>    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -&gt; int:<br><br>        xPoint = {} # x: [min_y, max_y]<br>        yPoint = {} # y: [min_x, max_x]<br>        for x, y in buildings:<br>            if x not in xPoint:<br>                xPoint[x] = [float(&#39;inf&#39;), -float(&#39;inf&#39;)]<br>            if y not in yPoint:<br>                yPoint[y] = [float(&#39;inf&#39;), -float(&#39;inf&#39;)]<br>            xPoint[x][0] = min(xPoint[x][0], y)<br>            xPoint[x][1] = max(xPoint[x][1], y)<br>            yPoint[y][0] = min(yPoint[y][0], x)<br>            yPoint[y][1] = max(yPoint[y][1], x)<br>        ans = 0<br>        for x, y in buildings:<br>            if y in xPoint[x] or x in yPoint[y]:<br>                continue<br>            ans += 1<br>        return ans</pre><h3>1. The Geometric Intuition</h3><p>Imagine the buildings as points on a grid.</p><ul><li><strong>Grouping by X:</strong> We isolate the y coordinates of points that lie on same vertical line parallel to Y-axis. This isolates all buildings that sit on the same <strong>vertical line</strong> (same column).</li><li><strong>Grouping by Y:</strong> Similarly we isolate all x coordinates that lie of same horizontal line. This isolates all buildings that sit on the same <strong>horizontal line</strong> (same row).</li></ul><p>We group them because a building can only be “covered” vertically by neighbors in the same column, and horizontally by neighbors in the same row. Comparing a building at x=1 with a building at x=100 is irrelevant for determining if it is covered vertically.</p><h3>2. Why Only Min and Max? (The “Sandwich” Logic)</h3><p>To understand if a building is “covered” (inside), it is easier to check the opposite: <strong>Is the building on the edge? </strong>On any given line (row or column), the buildings that are <strong>not</strong> covered are the ones at the very ends of the line.</p><ul><li>The building with the <strong>lowest coordinate</strong> (Min) is the bottom/left-most edge.</li><li>The building with the <strong>highest coordinate</strong> (Max) is the top/right-most edge.</li><li>Any building that is <strong>strictly between</strong> the Min and the Max is “covered” or “sandwiched” by the outer ones.</li><li>By taking into consideration only maximum and minimum of the points that we group, we are actually forming a net or a border which helps us to filter the points which are inside of it (covered).</li></ul><h4>Visual Example</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LFW7AsD2g_HacNlequFivQ.png" /></figure><p>The gray and black line actually group the points into X line and Y line respectively. Only the points that are on edge forming the end points of the lines form a border and all point which are inside this border contribute to covered building.</p><ul><li>If you are the min (smallest coordinate), you have no neighbor on one side.</li><li>If you are the max (largest coordinate), you have no neighbor on the other side.</li><li>If you are neither, you are safely in the middle !</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dd3d2790aae1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Why I Chose GraphQL for My Milk Logistics Web Application(And You Should Too)]]></title>
            <link>https://medium.com/@Sourabh_Gurav/why-i-chose-graphql-for-my-milk-logistics-web-application-and-you-should-too-efca83815dd2?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/efca83815dd2</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[strawberry]]></category>
            <category><![CDATA[graphql]]></category>
            <category><![CDATA[milk-collection-software]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Wed, 29 Oct 2025 16:55:47 GMT</pubDate>
            <atom:updated>2025-10-29T16:55:47.580Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hznkU5Y1Z1GEvzbWb6IkRg.png" /></figure><h3>The “Why” Behind the Switch ?</h3><blockquote>Hello readers, glad you are interested to know why I designed my backend in GraphQL !</blockquote><p>So let me paint you a picture: It’s 12:00 AM, I am working on a project for milk collection center which involves many sequential processes that should be saved and tracked down and I’m staring at my Django REST API that powers my milk logistics platform. We’ve got farmers delivering milk, collection centers testing quality, tankers transporting batches, and processing plants receiving shipments. I had to relate and create an inter-related models into my database. And my API? I kept on tangling as the mess of endpoints kept increasing with the requirement.</p><p>That’s when I decided to go for GraphQL with Django Strawberry. I had little idea of its implementation. But let me tell you, it’s been a game-changer.</p><h3>1. The Over-fetching Nightmare:</h3><p>Before GraphQL:</p><pre># REST endpoint: /api/milk-lots/123/<br>{<br>  &quot;id&quot;: 123,<br>  &quot;volume_l&quot;: 1000,<br>  &quot;fat_percent&quot;: 3.8,<br>  &quot;protein_percent&quot;: 3.2,<br>  &quot;lactose_percent&quot;: 4.7,<br>  &quot;total_solids&quot;: 12.5,<br>  &quot;snf&quot;: 8.7,<br>  &quot;urea_nitrogen&quot;: 15.2,<br>  &quot;bacterial_count&quot;: 12000,<br>  &quot;added_water_percent&quot;: 0.0,<br>  &quot;supplier&quot;: {...},  # 15 more fields<br>  &quot;tester&quot;: {...},    # 12 more fields<br>  &quot;bill&quot;: {...}       # 20 more fields<br>}</pre><p>Imagine if had a mobile app that only needed volume_l, fat_percent, and supplier.name. But REST was sending me 48 fields ! Massive ! That&#39;s like ordering a coffee and getting the entire café delivered to your table.</p><p>After GraphQL:</p><pre># Query you write for what you want<br>query {<br>  milkLot(id: 123) {<br>    volumeL<br>    fatPercent<br>    supplier {<br>      name<br>    }<br>  }<br>}</pre><pre># Response: Only what I asked for!<br>{<br>  &quot;data&quot;: {<br>    &quot;milkLot&quot;: {<br>      &quot;volumeL&quot;: 1000,<br>      &quot;fatPercent&quot;: 3.8,<br>      &quot;supplier&quot;: {<br>        &quot;name&quot;: &quot;Green Valley Dairy&quot;<br>      }<br>    }<br>  }<br>}</pre><p>Result: More than 50% of unnecessary data is stopped from delivering, this reduction in unnecessary data transfer could lead to lower bandwidth consumption and faster response times, improving user experience especially on mobile or limited networks.</p><h3>2. The N+1 Problem That Was Killing Us:</h3><p>REST Approach:</p><pre># 1. Get milk lots<br>GET /api/milk-lots/?bill_id=456<br><br># 2. For each milk lot, get supplier details<br>GET /api/suppliers/101/<br>GET /api/suppliers/102/<br>GET /api/suppliers/103/<br># ...and so on<br><br># 3. Then get tester details for each<br>GET /api/employees/201/<br>GET /api/employees/202/<br># ...you get the picture</pre><p>This was like sending 10 separate couriers to deliver one package to your neighbour.</p><p>GraphQL Solution:</p><pre># strawberry_schema.py<br>@strawberry.django.type(models.MilkLot)<br>class MilkLotType:<br>    id: int<br>    volume_l: float<br>    fat_percent: float<br>    supplier: &quot;SupplierType&quot;<br>    tester: Optional[&quot;EmployeeType&quot;]<br>    <br>    @strawberry.field<br>    def milk_lots_by_bill(self, info: Info, bill_id: int) -&gt; List[MilkLotType]:<br>        return models.MilkLot.objects.filter(bill_id=bill_id).select_related(<br>            &quot;supplier&quot;, &quot;tester&quot;<br>        )</pre><p>But GraphQL allows a client to request all the nested, related data it needs with a single query, which the backend efficiently resolves — often resulting in just one optimized database hit, saving me cost of requesting data through multiple API requests !</p><h3>3. Frontend Developers will stop asking for API fixes:</h3><p>Before GraphQL:</p><p>You definitely must have faced this as a backend developer !</p><p>Frontend Dev: “Hey, I need the collection route name for the milk transfer screen.”<br>Me: “Sure, let me create a new endpoint or add it to three existing ones. Give me 2 days.”</p><p>After GraphQL:<br>Frontend Dev: “No worries, I’ll just add route { name } to my query.&quot;<br>Me: 1 sec, Done !</p><h3>4. Real-time Updates Without the Headache:</h3><p>When a milk tanker arrives at a processing plant, multiple systems need to know:</p><ul><li>Quality lab: “Is the sample ready for testing?”</li><li>Billing: “Update the payment status”</li><li>Inventory: “Add to stock levels”</li></ul><p>With REST, this meant 3 separate API calls. With GraphQL:</p><pre>@strawberry.type<br>class Mutation:<br>    @strawberry.mutation<br>    def update_milk_transfer_status(<br>        self,<br>        info: Info,<br>        transfer_id: int,<br>        status: str<br>    ) -&gt; MilkTransferType:<br>        transfer = MilkTransfer.objects.get(id=transfer_id)<br>        transfer.status = status<br>        transfer.save()<br>        <br>        # All related data gets updated automatically<br>        return transfer</pre><p>So one mutation in GraphQL like a single push that sets off a chain reaction — similar to dominoes falling. When you update one piece of data, it automatically triggers updates to all related downstream data, keeping everything in sync without needing multiple separate operations. This streamlined process helps maintain data consistency and integrity across your application effortlessly.</p><p>Instead of manually handling each connected update, that one mutation cascades the necessary changes, making your code cleaner and your app more reliable — it’s like a well-coordinated domino effect but with positive outcomes that simplify complex data interactions.</p><h3>5. The Pythonic Way with Strawberry :</h3><p>I’m a Django developer, not a JavaScript expert. Strawberry made GraphQL feel right at home:</p><pre>import strawberry<br>from typing import List, Optional<br><br>@strawberry.type<br>class SupplierType:<br>    id: int<br>    name: str<br>    phone: str<br>    <br>    @strawberry.field<br>    def active_milk_lots(self) -&gt; List[&quot;MilkLotType&quot;]:<br>        return self.milk_lots.filter(status=&quot;ACTIVE&quot;)<br><br>@strawberry.type<br>class Query:<br>    suppliers: List[SupplierType] = strawberry.django.field()<br>    milk_lots_by_bill: List[MilkLotType] = strawberry.django.field()<br>    <br>    @strawberry.field<br>    def supplier_by_phone(self, phone: str) -&gt; Optional[SupplierType]:<br>        return Supplier.objects.filter(phone=phone).first()</pre><p>See? It’s just Python classes with type hints. Though I know that the learning curve felt like climbing Everest in flip-flops for the first week. But once it clicked, everything became simpler:</p><p><strong>Before: 27 REST endpoints to manage<br>After: 1 GraphQL endpoint that does everything</strong></p><p><strong>Before: Documentation scattered across 5 different places<br>After: Auto-generated GraphQL playground with built-in docs</strong></p><p><strong>Before: Versioning headaches (v1, v2, v3…)<br>After: Add fields without breaking existing queries.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cMk1304DmBChE1qVV3O0uA.png" /></figure><p>Also as I progress in adding more features and models, while the mobile application is build. GraphQL will surely allow multiple advantages over RESTAPI in :</p><ul><li><strong>Faster mobile apps (smaller payloads = quicker loads)</strong></li><li><strong>Better battery life (less data processing)</strong></li><li><strong>Happy developers (frontend and backend working in harmony)</strong></li><li><strong>Future-proof API (evolve without breaking changes)</strong></li></ul><p>The best part? When our field officers scan a milk can QR code, they now see everything in one view: supplier details, last test results, payment status, and collection route. All from one GraphQL query.</p><p>So if you’re building something complex with interconnected data (logistics, e-commerce, analytics), do yourself a favor and give GraphQL a shot. Your future self will thank you.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-CjfpW6zB6QDlv1ifC7awA.png" /></figure><p><em>Still thirsty for more? wait till I share my repo code where I break down our complete milk logistics schema and the product.</em></p><p>What about you? Have you tried GraphQL in your Django projects? War stories and success stories both welcome in the comments!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=efca83815dd2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Minimum Deletions to Make String K-Special]]></title>
            <link>https://medium.com/@Sourabh_Gurav/minimum-deletions-to-make-string-k-special-0267c06b69f4?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/0267c06b69f4</guid>
            <category><![CDATA[sorting]]></category>
            <category><![CDATA[hashmap]]></category>
            <category><![CDATA[string]]></category>
            <category><![CDATA[counting]]></category>
            <category><![CDATA[greedy-algorithms]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Sat, 21 Jun 2025 16:27:04 GMT</pubDate>
            <atom:updated>2025-06-21T16:30:09.698Z</atom:updated>
            <content:encoded><![CDATA[<p>Todays leetcode problem dated 21st June 2025, is interestingly simple for a medium problem but maybe not intuitive because I always try to come up with optimized solution. This makes me overlook the most obvious solution that is the brute force.</p><p>So here, you’re given a string word and an integer k.</p><p>You can <strong>delete</strong> characters from the string so that for <strong>any two characters </strong><strong>i and </strong><strong>j</strong>, the absolute difference in their <strong>frequencies</strong> is at most k. Here we have to minimize the characters so that after deletion the difference in the frequency of the characters is always less than or equal to the given integer k.</p><p>That is, we have to get all the character frequencies closer to one another. Such that the distance (frequency) between the furthest and nearest character is within k units.</p><p>In the solution, we try to make each character’s frequency the <strong>“baseline”</strong>. That is, we assume the current character to be the nearest and then calculate the distance to other characters. If any character has a distance (frequency) less than the baseline frequency, we delete that character frequency. If the distance is more than k, we delete only excess character frequencies and keep a note of it for the baseline frequency.</p><p>Case 1: If another character has less frequency than baseline → Delete it fully</p><p>Case 2: If another character has more frequency than baseline + k → Delete excess chars</p><p>We’ll iterate through each character’s frequency and calculate how many deletions are needed to make <strong>all other characters’ frequencies</strong> within the range [baseline, baseline + k].</p><p>Imagine a number line with frequencies. We plot each character’s frequencies on it and then try to calculate how far other characters are from a particular character. We do these calculations to get the number of deletions for each character considered as a baseline. We then decide whether to delete a character if it’s less than the frequency of the current character, or just delete the number of excess frequencies if it’s more than the frequency of the current character + k.</p><pre>class Solution(object):<br>    def minimumDeletions(self, word, k):<br>        &quot;&quot;&quot;<br>        :type word: str<br>        :type k: int<br>        :rtype: int<br>        &quot;&quot;&quot;<br>        from collections import defaultdict<br>        D = defaultdict(int)<br>        for char in word:<br>            D[char] += 1<br>        #we can have maximum deletions = len(words) but we have to find minimum deletions        <br>        total_del = len(word) <br>        #consider each character frequency as base start frequency<br>        for char in D:<br>            total = 0<br>            for remaining_char in D:<br>#check whether other character frequencies are less than base or more than range [base frequency + k]<br>                if D[remaining_char] &lt; D[char]:<br>                    total += D[remaining_char]<br>                elif D[char] + k &lt; D[remaining_char]:<br>                    total += (D[remaining_char] - k - D[char])<br>            total_del = min(total_del, total)<br>        return total_del</pre><h3>Complexity</h3><ul><li><strong>Time Complexity: </strong>Counting frequencies: <strong>O(n). </strong>Comparing each pair of characters: <strong>O(m²),</strong> where m is the number of unique characters (at most 26). So overall: <strong>O(n + m²)</strong></li><li><strong>Space Complexity</strong>: <strong>O(m)</strong> to store frequency map (at most 26 entries for lowercase English letters)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=0267c06b69f4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How I Solved the “Count Subarrays With Fixed Bounds” Problem]]></title>
            <link>https://medium.com/@Sourabh_Gurav/how-i-solved-the-count-subarrays-with-fixed-bounds-problem-942c41cae406?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/942c41cae406</guid>
            <category><![CDATA[leetcode-hard]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[monotonic-queue]]></category>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[sliding-window-algorithm]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Sat, 26 Apr 2025 06:42:37 GMT</pubDate>
            <atom:updated>2025-04-26T06:42:37.701Z</atom:updated>
            <content:encoded><![CDATA[<p>The problem was very easy to understand at first glance.<br> We are given an array nums, and two integers minK and maxK.<br> We need to <strong>count the number of subarrays</strong> (contiguous parts of the array) where:</p><ul><li>The minimum value of the subarray is exactly minK.</li><li>The maximum value of the subarray is exactly maxK.</li><li>All elements of the subarray must lie <strong>within</strong> the range [minK, maxK] (inclusive).</li></ul><h3>My Thought Process</h3><p>Initially, I thought:<br> Maybe we can <strong>group continuous segments</strong> of the array where every number lies within [minK, maxK].<br> This made sense because any number outside that range would immediately break the validity of the subarray.</p><p>However, the question was:<br> <strong>After identifying such a segment, how do we efficiently count valid subarrays?</strong></p><p>Here’s the idea I eventually figured out:</p><p>As we scan through the array, <strong>track</strong> the most recent indices where minK and maxK were seen. Also <strong>track</strong> the most recent index where a “bad” number appeared (i.e., a number outside [minK, maxK]). For every element, if both minK and maxK have been seen <strong>after</strong> the last &quot;bad&quot; number, we can form new valid subarrays ending at the current index. The number of such subarrays is determined by how far the earliest of last_min and last_max is from last_bad.</p><p>In short:</p><p>If last_min and last_max are valid (not -1), the number of new subarrays is min(last_min, last_max) - last_bad. Otherwise, no valid subarray ends at the current index.</p><pre>class Solution:<br>    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -&gt; int:<br>        count = 0<br>        last_min = last_max = last_bad = -1<br>        <br>        for i, num in enumerate(nums):<br>            if num &lt; minK or num &gt; maxK:<br>                last_bad = i<br>                last_min = last_max = -1<br>                continue<br>            <br>            if num == minK:<br>                last_min = i<br>            if num == maxK:<br>                last_max = i<br>            <br>            if last_min != -1 and last_max != -1:<br>                count += max(0, min(last_min, last_max) - last_bad)<br>        <br>        return count</pre><h3>Explanation</h3><ul><li>last_min keeps track of the last index where nums[i] == minK.</li><li>last_max keeps track of the last index where nums[i] == maxK.</li><li>last_bad keeps track of the last index where nums[i] was outside [minK, maxK].</li></ul><p>At each step:</p><ul><li>If the current number is bad (out of range), we reset last_min and last_max because no valid subarray can cross a bad number.</li><li>Otherwise, we update last_min and/or last_max if we see minK or maxK.</li><li>If both last_min and last_max are valid, we calculate how many valid subarrays end at the current index.</li></ul><p>This way, we process the array in <strong>one pass</strong> (O(n) time), making the solution efficient and elegant!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=942c41cae406" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Design a Number Container System]]></title>
            <link>https://medium.com/@Sourabh_Gurav/design-a-number-container-system-bee557dd04c9?source=rss-e55c50b0ff9d------2</link>
            <guid isPermaLink="false">https://medium.com/p/bee557dd04c9</guid>
            <category><![CDATA[hashmap]]></category>
            <category><![CDATA[dictionaries-in-python]]></category>
            <category><![CDATA[hash]]></category>
            <category><![CDATA[object-oriented-program]]></category>
            <category><![CDATA[heap]]></category>
            <dc:creator><![CDATA[SOURABH GURAV]]></dc:creator>
            <pubDate>Sat, 08 Feb 2025 08:19:22 GMT</pubDate>
            <atom:updated>2025-02-08T08:19:22.815Z</atom:updated>
            <content:encoded><![CDATA[<h4>LeetCode 2349</h4><p>Today’s a Saturday, and I woke up to solve this problem. Let me tell you what this problem is! You have to implement a class which has some functions (methods) to implement. The methods are “change” and “find”. What “change” does is that it lets you store a ‘number’ at the ‘index’. If an index already has a number, it replaces it with the current latest number. ‘find’ on the other hand returns the smallest index amongst all the indexes which have the given number. If the number is not present it returns -1.</p><p>I did think of using a list since it asks us to store numbers at specific index, but we do not have an idea about the largest index for us to decide and initialize an empty list of specific length.</p><p>Also, it might not be efficient to return the smallest index which stores a specific number.</p><p>But when it comes to returning smallest value efficiently, we rely on heap data structure. Heap pops and returns a smallest value efficiently in log(n) complexity. We therefore ‘utilize a dictionary which has number as the key and a heap data structure as a value which stores the indices which have that number.</p><p>But the problem here we might encounter is what if the number at a specific index is changed, we have to remove that index value from the heap which can be expensive. To tackle this, we will initialize another dictionary that has index as the key and number as the value. This number value is the latest current number at the index key.</p><p>At this point we know that we are going to implement a heap data structure (using list) in a dictionary to store group of indices as a ‘value’ to a specific key ‘number’. When implementing “find”, we need to return the smallest index which has the given number, we have the heap list of given indices, we can pop from the heap which gives the smallest value. But the catch is, does this index now has the given number? because as we process the input the number at that index must have been replaced by another different number. To check whether the number at that the popped index is still the same and not changed we refer another dictionary which I mentioned earlier that stores only current &amp; latest number at that index</p><ul><li>-&gt; Dictionary storing latest current number at specific index = {index: latest number at that index}</li><li>-&gt; Dictionary storing indices that have a given number → {Number: heapify[indices that have Number] }</li></ul><p>Hence, we go on popping the indices from the heap until it is confirmed that the number at the popped index is the same that is the index of the number we are asked to find.</p><pre>class NumberContainers:<br>    import heapq<br><br>    def __init__(self):<br>        self.container = {}<br>        self.index_place = {}<br><br>        <br><br>    def change(self, index: int, number: int) -&gt; None:<br>        if number not in self.container:<br>            self.container[number] = []<br>            heapq.heappush(self.container[number],index)<br>            <br>        else:<br>            heapq.heappush(self.container[number],index)<br>        self.index_place[index] = number<br>        <br>        <br>    def find(self, number: int) -&gt; int:<br>        if number not in self.container:<br>            return -1<br>        while len(self.container[number]) !=0:<br>            index = heapq.heappop(self.container[number])<br>            if self.index_place[index] == number:<br>                heapq.heappush(self.container[number], index)<br>                return index<br>        return -1<br><br>        <br><br><br># Your NumberContainers object will be instantiated and called as such:<br># obj = NumberContainers()<br># obj.change(index,number)<br># param_2 = obj.find(number)</pre><h3>Time Complexity Analysis:</h3><h4>change (index, number)</h4><ul><li>Insertion into a dictionary (self.index_place[index] = number) is <strong>O(1)</strong>.</li><li>heapq.heappush(self.container[number], index) runs in <strong>O(log N)</strong>, where <strong>N</strong> is the number of elements in the heap for number.</li><li>Overall, <strong>O(log N)</strong>.</li></ul><h4>find(number)</h4><ul><li>Checking if number not in self.container is <strong>O(1)</strong>.</li><li>The while loop repeatedly pops from the heap (heapq.heappop), which is <strong>O(log N)</strong> per operation.</li><li>In the worst case, we keep popping invalid indices until we find a valid one or exhaust the heap.</li><li>If most elements are outdated, the loop may run multiple times, leading to a worst-case <strong>O(N log N)</strong> complexity.</li><li>On average, if most elements are valid, it is closer to <strong>O(log N)</strong>.</li></ul><h3>Final Complexity Summary</h3><ul><li><strong>change</strong> → <strong>O(log N)</strong></li><li><strong>find</strong> → Worst case <strong>O(N log N)</strong>, average case <strong>O(log N)</strong>.</li></ul><p>I am here to answer any questions regarding the solution, let me know if any a deeper breakdown is needed !</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bee557dd04c9" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>