<?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 Ken on Medium]]></title>
        <description><![CDATA[Stories by Ken on Medium]]></description>
        <link>https://medium.com/@indy0214_19547?source=rss-826581f1758b------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*QimrkO9bSIy3uSpBx5PbJQ.jpeg</url>
            <title>Stories by Ken on Medium</title>
            <link>https://medium.com/@indy0214_19547?source=rss-826581f1758b------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 03:27:18 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@indy0214_19547/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[String to Integer(ATOI) — LeetCode 8]]></title>
            <link>https://medium.com/@indy0214_19547/string-to-integer-atoi-leetcode-8-40f5ee1d71b1?source=rss-826581f1758b------2</link>
            <guid isPermaLink="false">https://medium.com/p/40f5ee1d71b1</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Ken]]></dc:creator>
            <pubDate>Sun, 31 May 2026 15:14:50 GMT</pubDate>
            <atom:updated>2026-05-31T15:14:50.462Z</atom:updated>
            <content:encoded><![CDATA[<h3>Solution Video Link</h3><h3><a href="https://youtu.be/X8fROypQSog">⭐️ 8. String to Integer(ATOI) video is available from here</a></h3><p><strong>You can understand my solution with visualization and I have more +450 videos for technical interviews.</strong></p><p><strong>■ Subscribe URL</strong> <a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><p>Subscribers: 30,398</p><p>Thank you for your support!</p><h3>Approach</h3><p>The problem statement already provides hints for the algorithm, so there’s not much to explain. We will just follow the steps.</p><h3>Problem Requirements</h3><p>We need to implement a function that converts a string to a 32-bit signed integer with the following requirements:</p><ol><li><strong>Skip leading whitespace characters</strong></li><li><strong>Handle optional signs (+ or -)</strong></li><li><strong>Read and convert digits</strong></li><li><strong>Apply sign and return</strong></li></ol><h3>Algorithm Overview</h3><p><strong>Python</strong></p><pre>class Solution:<br>    def myAtoi(self, s: str) -&gt; int:<br>        if not s:<br>            return 0<br>        <br>        # Constants for 32-bit signed integer range<br>        INT_MAX = 2**31 - 1<br>        INT_MIN = -2**31<br>        <br>        i = 0<br>        n = len(s)<br>        <br>        # Step 1: Skip leading whitespace<br>        while i &lt; n and s[i] == &#39; &#39;:<br>            i += 1<br>        <br>        # Check if we&#39;ve reached the end<br>        if i == n:<br>            return 0<br>        <br>        # Step 2: Check for sign<br>        sign = 1<br>        if s[i] == &#39;+&#39;:<br>            i += 1<br>        elif s[i] == &#39;-&#39;:<br>            sign = -1<br>            i += 1<br>        <br>        # Step 3: Read digits and convert<br>        res = 0<br>        while i &lt; n and s[i].isdigit():<br>            digit = int(s[i])<br>            res = res * 10 + digit<br>            <br>            if sign * res &lt;= INT_MIN:<br>                return INT_MIN<br>            if sign * res &gt;= INT_MAX:<br>                return INT_MAX<br>            <br>            i += 1<br>        <br>        # Step 4: Apply sign and return<br>        return res * sign</pre><p><strong>JavaScript</strong></p><pre>/**<br> * @param {string} s<br> * @return {number}<br> */<br>var myAtoi = function(s) {<br>    if (!s) return 0;<br>    <br>    // Constants for 32-bit signed integer range<br>    const INT_MAX = 2**31 - 1;<br>    const INT_MIN = -(2**31);<br>    <br>    let i = 0;<br>    const n = s.length;<br>    <br>    // Step 1: Skip leading whitespace<br>    while (i &lt; n &amp;&amp; s[i] === &#39; &#39;) {<br>        i++;<br>    }<br>    <br>    // Check if we&#39;ve reached the end<br>    if (i === n) return 0;<br>    <br>    // Step 2: Check for sign<br>    let sign = 1;<br>    if (s[i] === &#39;+&#39;) {<br>        i++;<br>    } else if (s[i] === &#39;-&#39;) {<br>        sign = -1;<br>        i++;<br>    }<br>    <br>    // Step 3: Read digits and convert<br>    let res = 0;<br>    while (i &lt; n &amp;&amp; s[i] &gt;= &#39;0&#39; &amp;&amp; s[i] &lt;= &#39;9&#39;) {<br>        const digit = parseInt(s[i]);<br>        res = res * 10 + digit;<br>        <br>        if (sign * res &lt;= INT_MIN) {<br>            return INT_MIN;<br>        }<br>        if (sign * res &gt;= INT_MAX) {<br>            return INT_MAX;<br>        }<br>        <br>        i++;<br>    }<br>    <br>    // Step 4: Apply sign and return<br>    return res * sign;    <br>};</pre><p><strong>Java</strong></p><pre>class Solution {<br>    public int myAtoi(String s) {<br>        if (s == null || s.length() == 0) {<br>            return 0;<br>        }<br>        <br>        // Constants for 32-bit signed integer range<br>        final int INT_MAX = Integer.MAX_VALUE;<br>        final int INT_MIN = Integer.MIN_VALUE;<br>        <br>        int i = 0;<br>        int n = s.length();<br>        <br>        // Step 1: Skip leading whitespace<br>        while (i &lt; n &amp;&amp; s.charAt(i) == &#39; &#39;) {<br>            i++;<br>        }<br>        <br>        // Check if we&#39;ve reached the end<br>        if (i == n) {<br>            return 0;<br>        }<br>        <br>        // Step 2: Check for sign<br>        int sign = 1;<br>        if (s.charAt(i) == &#39;+&#39;) {<br>            i++;<br>        } else if (s.charAt(i) == &#39;-&#39;) {<br>            sign = -1;<br>            i++;<br>        }<br>        <br>        // Step 3: Read digits and convert<br>        long res = 0;<br>        while (i &lt; n &amp;&amp; Character.isDigit(s.charAt(i))) {<br>            int digit = s.charAt(i) - &#39;0&#39;;<br>            res = res * 10 + digit;<br>            <br>            if (sign * res &lt;= INT_MIN) {<br>                return INT_MIN;<br>            }<br>            if (sign * res &gt;= INT_MAX) {<br>                return INT_MAX;<br>            }<br>            <br>            i++;<br>        }<br>        <br>        // Step 4: Apply sign and return<br>        return (int)(res * sign);        <br>    }<br>}</pre><p><strong>C++</strong></p><pre>class Solution {<br>public:<br>    int myAtoi(string s) {<br>        if (s.empty()) {<br>            return 0;<br>        }<br>        <br>        // Use standard library constants<br>        const long long MAX_INT = INT_MAX;<br>        const long long MIN_INT = INT_MIN;<br>        <br>        int i = 0;<br>        int n = s.length();<br>        <br>        // Step 1: Skip leading whitespace<br>        while (i &lt; n &amp;&amp; s[i] == &#39; &#39;) {<br>            i++;<br>        }<br>        <br>        // Check if we&#39;ve reached the end<br>        if (i == n) {<br>            return 0;<br>        }<br>        <br>        // Step 2: Check for sign<br>        int sign = 1;<br>        if (s[i] == &#39;+&#39;) {<br>            i++;<br>        } else if (s[i] == &#39;-&#39;) {<br>            sign = -1;<br>            i++;<br>        }<br>        <br>        // Step 3: Read digits and convert<br>        long long res = 0;<br>        while (i &lt; n &amp;&amp; isdigit(s[i])) {<br>            int digit = s[i] - &#39;0&#39;;<br>            res = res * 10 + digit;<br>            <br>            if (sign * res &lt;= INT_MIN) {<br>                return INT_MIN;<br>            }<br>            if (sign * res &gt;= INT_MAX) {<br>                return INT_MAX;<br>            }<br>            <br>            i++;<br>        }<br>        <br>        // Step 4: Apply sign and return<br>        return static_cast&lt;int&gt;(res * sign);     <br>    }<br>};</pre><h3>Step by Step Breakdown</h3><h3>Step 1: Skip Leading Whitespace</h3><pre>while i &lt; n and s[i] == &#39; &#39;:<br>    i += 1</pre><p><strong>Logic:</strong></p><ul><li>Ignore all leading whitespace characters (spaces)</li><li>Advance the index i to the first non-whitespace character</li><li><strong>Time Complexity</strong>: O(k) where k is the number of leading whitespace characters</li></ul><h3>Step 2: Handle Signs</h3><pre>sign = 1<br>if s[i] == &#39;+&#39;:<br>    i += 1<br>elif s[i] == &#39;-&#39;:<br>    sign = -1<br>    i += 1</pre><p><strong>Logic:</strong></p><ul><li>Default to positive (sign = 1)</li><li>If + or - is found, set the sign and advance the index</li><li>Only the first sign is valid (&quot;+-2&quot; is invalid)</li></ul><p><strong>Key Points:</strong></p><ul><li>If no sign is present, proceed to the next step</li><li>Only advance the index when a sign is found</li></ul><h3>Step 3: Read and Convert Digits</h3><pre>res = 0<br>while i &lt; n and s[i].isdigit():<br>    digit = int(s[i])<br>    res = res * 10 + digit<br>    <br>    if sign * res &lt;= INT_MIN:<br>        return INT_MIN<br>    if sign * res &gt;= INT_MAX:<br>        return INT_MAX<br>    <br>    i += 1</pre><p><strong>Logic:</strong></p><ul><li>Continue reading digits and build the integer</li><li>Use res = res * 10 + digit to multiply by 10 for the next digit place and add the new digit</li><li>Check for overflow after each digit processing</li></ul><p><strong>Number Construction Example:</strong></p><pre>For &quot;1234&quot;:<br>res = 0<br>&#39;1&#39;: res = 0 * 10 + 1 = 1<br>&#39;2&#39;: res = 1 * 10 + 2 = 12<br>&#39;3&#39;: res = 12 * 10 + 3 = 123<br>&#39;4&#39;: res = 123 * 10 + 4 = 1234</pre><h3>Step 4: Apply Sign and Return Result</h3><pre>return res * sign</pre><p><strong>Logic:</strong></p><ul><li>Apply the sign to the final result</li><li>Overflow checks are already completed at this point</li></ul><h3>Overflow Handling Details</h3><p>The core of this algorithm is <strong>efficient overflow detection</strong>.</p><h3>Basic Approach</h3><pre>if sign * res &lt;= INT_MIN:<br>    return INT_MIN<br>if sign * res &gt;= INT_MAX:<br>    return INT_MAX</pre><p><strong>Why This Method Works Well:</strong></p><ol><li><strong>Real-time Detection</strong>: Check for overflow while processing each digit</li><li><strong>Simple Conditions</strong>: No complex pre-calculations needed</li><li><strong>Early Termination</strong>: Return immediately when overflow is detected</li></ol><h3>Concrete Examples</h3><p><strong>Positive Number Overflow:</strong></p><pre>&quot;2147483648&quot; (INT_MAX + 1)<br>When res = 2147483648:<br>sign * res = 1 * 2147483648 = 2147483648 &gt;= INT_MAX<br>→ Return INT_MAX (2147483647)</pre><p><strong>Negative Number Overflow:</strong></p><pre>&quot;-2147483649&quot; (INT_MIN - 1)<br>When res = 2147483649:<br>sign * res = -1 * 2147483649 = -2147483649 &lt;= INT_MIN<br>→ Return INT_MIN (-2147483648)</pre><h3>Edge Case Handling</h3><h3>1. Empty String or Whitespace Only</h3><pre>if not s:<br>    return 0</pre><pre>if i == n:  # Only whitespace<br>    return 0</pre><h3>2. Invalid Format</h3><pre># Stop processing when non-digit character is encountered<br>while i &lt; n and s[i].isdigit():<br>    # Process digits</pre><p><strong>Examples:</strong></p><ul><li>&quot;words and 987&quot; → 0 (non-digit at start)</li><li>&quot;4193 with words&quot; → 4193 (stop at non-digit)</li></ul><h3>3. Sign Only</h3><pre>&quot;+&quot; → 0<br>&quot;-&quot; → 0</pre><p>How I Studied LeetCode as a Beginner (That Actually Worked)</p><h3><a href="https://youtu.be/bU_dXCOWHls">⭐️ How to Use LeetCode Effectively video is available from here</a></h3><h3>Key Takeaways</h3><p>Important design principles learned from this atoi algorithm:</p><ol><li><strong>Step-by-Step Processing</strong>: Break complex problems into smaller steps</li><li><strong>Edge Case Consideration</strong>: Account for various input patterns</li><li><strong>Efficient Overflow Detection</strong>: Real-time detection rather than pre-checking</li><li><strong>Single-Pass Processing</strong>: Achieve O(n) time complexity with one string traversal</li></ol><p>This algorithm demonstrates fundamental patterns in string processing and is applicable to many similar problems. The state management and boundary condition handling are particularly important concepts that appear in many algorithmic challenges.</p><h3>Conclusion</h3><p>The atoi implementation showcases how seemingly simple problems can involve sophisticated design considerations. The real-time overflow detection technique and systematic approach to edge case handling make this solution both efficient and robust. Understanding these principles will help you tackle similar string processing and numerical conversion problems with confidence.</p><h3>Complexity</h3><ul><li>Time complexity: O(n)</li><li>Space complexity: O(1)</li></ul><p>Thank you for reading my post. ⭐️ Please upvote it and don’t forget to subscribe to my channel!</p><p>⭐️ Subscribe URL <a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><h3>⭐️ Next Question</h3><h3><a href="https://youtu.be/CijisxopxqM">⭐️ Palindrome Number video is available from here</a></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=40f5ee1d71b1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Reverse Integer — LeetCode 7]]></title>
            <link>https://medium.com/@indy0214_19547/reverse-integer-leetcode-7-b0bc267be2f7?source=rss-826581f1758b------2</link>
            <guid isPermaLink="false">https://medium.com/p/b0bc267be2f7</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Ken]]></dc:creator>
            <pubDate>Tue, 26 May 2026 16:46:19 GMT</pubDate>
            <atom:updated>2026-05-26T16:46:19.488Z</atom:updated>
            <content:encoded><![CDATA[<h3>Intuition</h3><p>Convert input to string or use remainders.</p><h3><a href="https://youtu.be/Y_NCKgC3BiM">⭐️ 7. Reverse Integer video is available from here</a></h3><p><strong>You can understand my solution with visualization and I have more +450 videos for technical interviews.</strong></p><p><strong>■ Subscribe URL</strong> <a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><p>Subscribers: 30,293</p><p>Thank you for your support!</p><h3>Approach</h3><p>This question doesn’t allow us to use 64-bit integer, so the first two solution are wrong but I think it’s good to have multiple solutions for real interview. I’ll show you three ways to solve this question.</p><h3>Solution 1 — Convert to String</h3><p><strong>We may use 64 bit integers.</strong></p><p>Simply, if we convert input number to string, we can reverse the string number then convert it to integer again.</p><pre>Input: x = 123</pre><p>Convert to string.</p><pre>123 → &quot;123&quot;</pre><p>Then reverse &quot;123&quot;.</p><pre>&quot;123&quot; → &quot;321&quot;</pre><p>Then convert it to integer again.</p><pre>&quot;321&quot; → 321</pre><pre>return 321</pre><p>Be careful! We have also negative case. In that case, start reversing the string from index 1, not index 0.</p><p>Easy! 😄</p><p>Let’s see a solution codes and step by step algorithm!</p><p>⭐️ I recently created a video on how I’ve been using LeetCode to learn.</p><h3><a href="https://youtu.be/bU_dXCOWHls">How To Use LeetCode effectively video is available from here</a></h3><p><strong>Python</strong></p><pre>class Solution:<br>    def reverse(self, x: int) -&gt; int:<br>        res = 0<br>        if x &lt; 0:<br>            res = int(str(x)[1:][::-1]) * -1<br>        else:<br>            res = int(str(x)[::-1])<br>        <br>        if res &gt; 2 ** 31 - 1 or res &lt; -2 ** 31:<br>            return 0<br>        <br>        return res</pre><p><strong>JavaScript</strong></p><pre>var reverse = function(x) {<br>    let res = 0;<br>    if (x &lt; 0) {<br>        res = parseInt(String(x).slice(1).split(&#39;&#39;).reverse().join(&#39;&#39;)) * -1;<br>    } else {<br>        res = parseInt(String(x).split(&#39;&#39;).reverse().join(&#39;&#39;));<br>    <br>    if (res &gt; Math.pow(2, 31) - 1 || res &lt; -Math.pow(2, 31)) {<br>        return 0;<br>    }<br><br>    return res;    <br>};</pre><p><strong>Java</strong></p><pre>class Solution {<br>    public int reverse(int x) {<br>        int res = 0;<br>        boolean isNegative = x &lt; 0;<br>        String strX = String.valueOf(Math.abs(x));<br>        StringBuilder sb = new StringBuilder(strX).reverse();<br>        <br>        try {<br>            res = Integer.parseInt(sb.toString());<br>        } catch (NumberFormatException e) {<br>            return 0;<br>        }<br>        <br>        return isNegative ? -res : res;       <br>    }<br>}</pre><h3>Step by Step Algorithm</h3><p><strong>1. Initialize the result variable </strong><strong>res:</strong></p><pre>res = 0</pre><p>We start by initializing the variable res to store the reversed integer.</p><p><strong>2. Check if the input number </strong><strong>x is negative:</strong></p><pre>if x &lt; 0:</pre><p>We check if the given integer x is negative.</p><p><strong>3. Reverse the digits of the integer:</strong></p><pre>res = int(str(x)[1:][::-1]) * -1</pre><p>If x is negative, we convert it to a string, remove the negative sign (str(x)[1:]), reverse the string ([::-1]), convert it back to an integer, and then multiply by -1 to keep the sign negative.</p><p><strong>4. Handle positive integers:</strong></p><pre>else:<br>    res = int(str(x)[::-1])</pre><p>If x is positive, we simply convert it to a string, reverse the string, and then convert it back to an integer.</p><p><strong>5. Check for overflow:</strong></p><pre>if res &gt; 2 ** 31 - 1 or res &lt; -2 ** 31:<br>    return 0</pre><p>We check if the reversed integer res is within the range of a 32-bit signed integer. If it exceeds this range, we return 0 to indicate overflow.</p><p><strong>6. Return the reversed integer:</strong></p><pre>return res</pre><p>Finally, we return the reversed integer.</p><p>Overall, the code efficiently reverses the digits of the given integer while handling negative numbers and checking for overflow. It demonstrates a concise approach to solve the problem.</p><h3>Solution 2 — Using Remainder</h3><p><strong>We may use 64 bit integers.</strong></p><p>Let me use the same input.</p><pre>Input: x = 123</pre><p>In the end, we want to return 321, so how we can move 3 to the first position?</p><p>My strategy is to use remainder divided by 10.</p><pre>123 % 10 = 3</pre><p>We can get 3 easily and add 3 to result variable (= res).</p><pre>res = 3</pre><p>But the next question is “How can we get 2 from 123?&quot;</p><p>My answer is to divide 123 by 10 so that we can get 12 for the next process. This time not remainder, we use the answer.</p><pre>123 // 10 = 12<br>x = 12</pre><p>We will get remainder of:</p><pre>12 % 10 = 2</pre><p>The next problem is now res = 3 and we got 2. We want to create 32 right? Because in the end we want to return 321. How can we create 32 with 3 and 2?</p><p>My answer is to multiply 10 with res, then add remainder (= 2) to it.</p><blockquote><em>⭐️ </em><strong><em>Key Formula</em></strong></blockquote><blockquote><em>res = (res * 10) + (x % 10)</em></blockquote><pre>res = (3 * 10) + (12 % 10)<br>    = 32</pre><p>We got 32. Next, we want 1 to create 321, so divide 12 by 10.</p><pre>12 // 10 = 1<br>x = 1</pre><p>Then we use the same formula above.</p><pre>res = (res * 10) + (x % 10)<br>res = (32 * 10) + (1 % 10)<br>    = 321</pre><pre>x(= 1) // 10 = 0</pre><p>When we reach 0, we finish iteration.</p><pre>return 321</pre><p>Of course, we handle negative case, but I believe you can understand it easily if you see the solution codes. Just convert a negative to a positive, reverse numbers, then convert the positive to a negative before we return output.</p><p><strong>Python</strong></p><pre>class Solution:<br>    def reverse(self, x: int) -&gt; int:<br>        is_negative = False<br><br>        if x &lt; 0:<br>            is_negative = True<br>            x *= -1<br>        <br>        res = 0<br>        while x &gt; 0:<br>            res = (res * 10) + (x % 10)<br>            x //= 10<br>        <br>        if res &gt; 2 ** 31 - 1:<br>            return 0<br>        <br>        return res * -1 if is_negative else res</pre><p><strong>JavaScript</strong></p><pre>var reverse = function(x) {<br>    let isNegative = false;<br><br>    if (x &lt; 0) {<br>        isNegative = true;<br>        x *= -1;<br>    }<br>    <br>    let res = 0;<br>    while (x &gt; 0) {<br>        res = (res * 10) + (x % 10);<br>        x = Math.floor(x / 10);<br>    }<br>    <br>    if (res &gt; Math.pow(2, 31) - 1) {<br>        return 0;<br>    }<br>    <br>    return isNegative ? -res : res;    <br>};</pre><p><strong>Java</strong></p><pre>class Solution {<br>    public int reverse(int x) {<br>        int reversed = 0;<br>        while (x != 0) {<br>            int digit = x % 10;<br>            x /= 10;<br>            if (reversed &gt; Integer.MAX_VALUE / 10 || (reversed == Integer.MAX_VALUE / 10 &amp;&amp; digit &gt; 7)) return 0;<br>            if (reversed &lt; Integer.MIN_VALUE / 10 || (reversed == Integer.MIN_VALUE / 10 &amp;&amp; digit &lt; -8)) return 0;<br>            reversed = reversed * 10 + digit;<br>        }<br>        return reversed;       <br>    }<br>}</pre><h3>Step by Step Algorithm</h3><p><strong>1. Initialize a boolean variable to track negativity:</strong></p><pre>is_negative = False</pre><p>We initialize a boolean variable is_negative to keep track of whether the input integer x is negative.</p><p><strong>2. Check if the input number </strong><strong>x is negative:</strong></p><pre>if x &lt; 0:<br>    is_negative = True<br>    x *= -1</pre><p>If the input integer x is negative, we set is_negative to True and make x positive by multiplying it by -1.</p><p><strong>3. Reverse the digits of the integer:</strong></p><pre>res = 0<br>while x &gt; 0:<br>    res = (res * 10) + (x % 10)<br>    x //= 10</pre><p>We initialize a variable res to store the reversed integer. Inside the while loop, we repeatedly extract the last digit of x using the modulo operator %, add it to the current value of res multiplied by 10, and then update x by removing its last digit using integer division //.</p><p><strong>4. Check for integer overflow:</strong></p><pre>if res &gt; 2 ** 31 - 1:<br>    return 0</pre><p>We check if the reversed integer res exceeds the range of a 32-bit signed integer. If it does, we return 0 to indicate integer overflow.</p><p><strong>5. Return the reversed integer:</strong></p><pre>return res * -1 if is_negative else res</pre><p>If the original input integer x was negative, we return the reversed integer with a negative sign. Otherwise, we return the reversed integer as is.</p><p>The code efficiently reverses the digits of the given integer while handling negative numbers and checking for integer overflow. It demonstrates a concise approach to solve the problem.</p><h3>Solution 3 — Avoid 64-bit Integer</h3><p>To avoid 64 bit integer, let me modify solution 2. We use almost the same logic. Just we check the current res before we create the next digit with res.</p><p><strong>Python</strong></p><pre>class Solution:<br>    def reverse(self, x: int) -&gt; int:<br>        is_negative = False<br>        if x &lt; 0:<br>            is_negative = True<br>            x *= -1<br><br>        res = 0<br>        while x &gt; 0:<br>            digit = x % 10<br>            x //= 10<br>            if (res &gt; (2 ** 31 - 1) // 10) or (res == (2 ** 31 - 1) // 10 and digit &gt; 7):<br>                return 0<br>            res = (res * 10) + digit<br><br>        return -res if is_negative else res</pre><p><strong>JavaScript</strong></p><pre>var reverse = function(x) {<br>    let isNegative = false;<br>    if (x &lt; 0) {<br>        isNegative = true;<br>        x = -x;<br>    }<br><br>    let res = 0;<br>    while (x &gt; 0) {<br>        let digit = x % 10;<br>        x = Math.floor(x / 10);<br>        if (res &gt; Math.floor((2 ** 31 - 1) / 10) || (res === Math.floor((2 ** 31 - 1) / 10) &amp;&amp; digit &gt; 7)) {<br>            return 0;<br>        }<br>        res = (res * 10) + digit;<br>    }<br><br>    return isNegative ? -res : res;    <br>};</pre><p><strong>Java</strong></p><pre>class Solution {<br>    public int reverse(int x) {<br>        boolean isNegative = false;<br>        if (x &lt; 0) {<br>            isNegative = true;<br>            x = -x;<br>        }<br><br>        int res = 0;<br>        while (x &gt; 0) {<br>            int digit = x % 10;<br>            x /= 10;<br>            if (res &gt; (Integer.MAX_VALUE - digit) / 10) {<br>                return 0;<br>            }<br>            res = (res * 10) + digit;<br>        }<br><br>        return isNegative ? -res : res;        <br>    }<br>}</pre><p>Thank you for reading my post. Please upvote it and don’t forget to subscribe to my channel!</p><p>⭐️ Subscribe URL <a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><p>⭐️ Related Question — Palindrome Number #9</p><h3><a href="https://youtu.be/CijisxopxqM">⭐️ Palindrome Number video is available from here</a></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b0bc267be2f7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Zigzag Conversion — LeetCode 6]]></title>
            <link>https://medium.com/@indy0214_19547/zigzag-conversion-leetcode-6-5c4fa69822cf?source=rss-826581f1758b------2</link>
            <guid isPermaLink="false">https://medium.com/p/5c4fa69822cf</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Ken]]></dc:creator>
            <pubDate>Mon, 25 May 2026 15:13:35 GMT</pubDate>
            <atom:updated>2026-05-25T15:13:35.612Z</atom:updated>
            <content:encoded><![CDATA[<h3>Intuition</h3><p>We can move up and down with 1 and -1</p><h3>Solution Video Link</h3><h3><a href="https://youtu.be/fxhPxvBAvD0">⭐️ Zigzag Conversion video is avaliable from here</a></h3><p>You can understand my solution with visualization and I have more +450 videos for technical interviews.</p><p><strong>■ Subscribe URL</strong> <a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><p>Subscribers: 30,280</p><p>Thank you for your support!</p><h3>Approach</h3><p>Let’s think about this example.</p><pre>s = &quot;abcdefghi&quot;, numRows = 4</pre><p>In this case, we put the characters of s like this.</p><pre>1 a     g → ag<br>2 b   f h → bfh<br>3 c e   i → cei<br>4 d       → d</pre><pre>return &quot;agbfhceid&quot;</pre><h3>What we should do?</h3><h3><em>⭐️ Points</em></h3><ul><li>Put characters on zigzag path</li><li>Create strings horizontally</li></ul><h3>Put characters on zigzag path</h3><p>Seems like tough because we move diagonally but it’s very simple.</p><pre>s = &quot;abcdefghi&quot;, numRows = 4</pre><p>In this case</p><pre>&quot;abcdefghi&quot;<br> 123432123 (= row)</pre><p>All we have to do is that we just move up and down. <strong>More precisely, if we reach </strong><strong>numsRows - 1, we move up next time and if we reach the first row, we move down next time.</strong></p><p>We will creat direction variable to handle moving direction. When we move down, the variable has 1. On the other hand, when we move up, the variable has -1.</p><h3>Create strings horizontally</h3><p>Now we have an array like this.</p><pre>1 a     g<br>2 b   f h<br>3 c e   i<br>4 d</pre><p>All we have to do is just to concatenate all characters in the same row. But there is a point here.</p><blockquote><em>⭐️ Points</em></blockquote><blockquote><em>Use 2d array instead of 1d array</em></blockquote><p><strong>Why?</strong></p><p>That’s because if we use 1d array(of course we can solve the question), we have to concatenate all characters in the same row when we add a new character which is O(n). We will repeat the process length of s times, so that is O(n²). n is the length of the string s.</p><p>To avoid O(n²), we use 2d array so that we just append a new character to the last position of a target row which is O(1).</p><p><strong>This enables us to keep O(n) time instead of O(n²).</strong></p><p>I put Python code of O(n²) below.</p><p>Easy!😄 Let’s see solution codes and step by step algorithm!</p><h3>Complexity</h3><ul><li><strong>Time complexity:</strong> O(n) — n is the length of the string s</li><li><strong>Space complexity:</strong> O(n)</li></ul><h3>Solution Code</h3><p><strong>Python</strong></p><pre>class Solution:<br>    def convert(self, s: str, numRows: int) -&gt; str:<br>        if numRows == 1 or numRows &gt;= len(s):<br>            return s<br><br>        idx, d = 0, 1<br>        rows = [[] for _ in range(numRows)]<br><br>        for char in s:<br>            rows[idx].append(char)<br>            if idx == 0:<br>                d = 1<br>            elif idx == numRows - 1:<br>                d = -1<br>            idx += d<br><br>        for i in range(numRows):<br>            rows[i] = &#39;&#39;.join(rows[i])<br><br>        return &#39;&#39;.join(rows) </pre><p><strong>JavaScript</strong></p><pre>var convert = function(s, numRows) {<br>    if (numRows === 1 || numRows &gt;= s.length) {<br>        return s;<br>    }<br><br>    let idx = 0, d = 1;<br>    const rows = new Array(numRows).fill().map(() =&gt; []);<br><br>    for (const char of s) {<br>        rows[idx].push(char);<br>        if (idx === 0) {<br>            d = 1;<br>        } else if (idx === numRows - 1) {<br>            d = -1;<br>        }<br>        idx += d;<br>    }<br><br>    for (let i = 0; i &lt; numRows; i++) {<br>        rows[i] = rows[i].join(&#39;&#39;);<br>    }<br><br>    return rows.join(&#39;&#39;);    <br>};</pre><p><strong>Java</strong></p><pre>class Solution {<br>    public String convert(String s, int numRows) {<br>       if (numRows == 1 || numRows &gt;= s.length()) {<br>            return s;<br>        }<br><br>        int idx = 0, d = 1;<br>        List&lt;Character&gt;[] rows = new ArrayList[numRows];<br>        for (int i = 0; i &lt; numRows; i++) {<br>            rows[i] = new ArrayList&lt;&gt;();<br>        }<br><br>        for (char c : s.toCharArray()) {<br>            rows[idx].add(c);<br>            if (idx == 0) {<br>                d = 1;<br>            } else if (idx == numRows - 1) {<br>                d = -1;<br>            }<br>            idx += d;<br>        }<br><br>        StringBuilder result = new StringBuilder();<br>        for (List&lt;Character&gt; row : rows) {<br>            for (char c : row) {<br>                result.append(c);<br>            }<br>        }<br><br>        return result.toString();        <br>    }<br>}</pre><p><strong>C++</strong></p><pre>class Solution {<br>public:<br>    string convert(string s, int numRows) {<br>        if (numRows == 1 || numRows &gt;= s.length()) {<br>            return s;<br>        }<br><br>        int idx = 0, d = 1;<br>        vector&lt;vector&lt;char&gt;&gt; rows(numRows);<br><br>        for (char c : s) {<br>            rows[idx].push_back(c);<br>            if (idx == 0) {<br>                d = 1;<br>            } else if (idx == numRows - 1) {<br>                d = -1;<br>            }<br>            idx += d;<br>        }<br><br>        string result;<br>        for (const auto&amp; row : rows) {<br>            for (char c : row) {<br>                result += c;<br>            }<br>        }<br><br>        return result;        <br>    }<br>};</pre><h3>Step by Step Algorithm</h3><p><strong>1. Check Special Cases</strong></p><p>If numRows is 1 or greater than or equal to the length of the input string s, it means that the ZigZag pattern will be the same as the input string. In such cases, just return the input string s as it is.</p><pre>if numRows == 1 or numRows &gt;= len(s):<br>    return s</pre><p><strong>2. Initialization</strong></p><p>Initialize idx to keep track of the current row index, starting from 0, and d as the direction of traversal (1 for downward, -1 for upward). Create a list of numRows empty lists to represent the rows of the ZigZag pattern.</p><pre>idx, d = 0, 1<br>rows = [[] for row in range(numRows)]</pre><p><strong>3. Traverse through the String</strong></p><p>Iterate through each character char in the input string s. Append the current character to the row indicated by the idx. Update the direction d based on the current position (idx). Update the current row index idx according to the direction d.</p><pre>for char in s:<br>    rows[idx].append(char)<br>    if idx == 0:<br>        d = 1<br>    elif idx == numRows - 1:<br>        d = -1<br>    idx += d</pre><p><strong>4. Join Rows</strong></p><p>Iterate through each row in rows. Join the characters in each row to form strings. Update each row in rows with the joined string.</p><pre>for i in range(numRows):<br>    rows[i] = &#39;&#39;.join(rows[i])</pre><p><strong>5. Join Rows into Result String</strong></p><p>Join all the rows together to form the final ZigZag pattern.</p><pre>return &#39;&#39;.join(rows)</pre><h3>Next Question</h3><h3><a href="https://youtu.be/Y_NCKgC3BiM">⭐️ Reverse Integer video is avaliable from here</a></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5c4fa69822cf" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Longest Palindromic Substring — LeetCode 5]]></title>
            <link>https://medium.com/@indy0214_19547/longest-palindromic-substring-86b89469534f?source=rss-826581f1758b------2</link>
            <guid isPermaLink="false">https://medium.com/p/86b89469534f</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Ken]]></dc:creator>
            <pubDate>Sun, 24 May 2026 16:27:24 GMT</pubDate>
            <atom:updated>2026-05-24T16:48:05.098Z</atom:updated>
            <content:encoded><![CDATA[<h3>Intuition</h3><p>Using two pointers</p><h3>Solution Video Link</h3><h3><a href="https://youtu.be/aMH1eomKCmE">⭐️ 5. Longest Palindromic Substring video is available from here</a></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nYFUDuV49M485fbnftd-BQ.jpeg" /></figure><p><strong>You can understand my solution with visualization and I have more +450 videos for technical interviews.</strong></p><p><strong>■ Subscribe URL</strong> <a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><p>Subscribers: 30,264</p><p>Thank you for your support!</p><h3>Approach</h3><h3>How we think about a solution</h3><p>First of all, Manacher’s Algorithm solves this question with O(n) time. But in real interviews, nobody will come up with such a solution, so I think O(n^2) time is enough to pass the interviews.</p><p>If interviewers ask you about a solution with O(n). just leave the room. lol</p><p>Seriously from here, first of all, we need to understand Palindromic Substring.</p><p>When I think about a solution, I usually start with the small and simple input, because it’s easy to understand and find a solution. But this time let’s start with a big input.</p><pre>Input: &quot;xkarqzghhgfedcbabcdefgzdekx&quot;</pre><p><strong>■ Question</strong></p><p>How did you find longest palindromic substring?</p><p>I believe you choose one character, then expand the range to left and right at the same time. If you find longest palindromic substring directly, you are not a human. lol</p><p>Actually, that is main idea of my solution today. But problem is that we don’t know where to start. That’s why we need to shift start point one by one.</p><p>⭐️ <strong>Points</strong></p><p>We need to shift a start point one by one to check longest palindromic substring.</p><p><strong>What is the start point?</strong></p><p>Since palindromic substring is like a mirror from some character, it’s good idea to consider current index as a center of palindromic substring and expand left and right at the same time.</p><p>For example,</p><pre>Input = &quot;abcba&quot;</pre><p>If we start from c, then</p><pre>&quot;ab&quot; &quot;c&quot; &quot;ba&quot;<br>      i</pre><pre>i = curerent index</pre><p>“ab” and “ba” is a mirror when “c” is center.</p><p>Let’s see one by one.</p><pre>Input = &quot;abcba&quot;</pre><p>We use left and right pointers. The both pointers start from index i but let me start from next to index i to make my explanation short. A single character is definitely a palindrome which is length of 1.</p><pre>i = 0</pre><pre>&quot;abcba&quot;<br>lir<br> <br>Check left(= out of bounds) and right(= &quot;b&quot;)<br>max_length = 1 (= &quot;a&quot;)</pre><pre>i = 1</pre><pre>&quot;abcba&quot;<br> lir</pre><pre>Check left(= &quot;a&quot;) and right(= &quot;c&quot;)<br>max_length = 1 (= &quot;a&quot; or &quot;b&quot;)</pre><pre>i = 2</pre><pre>&quot;abcba&quot;<br>  lir</pre><pre>l = 1<br>r = 3<br>Check left(= &quot;b&quot;) and right(= &quot;b&quot;) → &quot;bcb&quot; is a palindrome.😆</pre><pre>Let&#39;s expand the range!</pre><pre>&quot;abcba&quot;<br> l i r</pre><pre>l = 0<br>r = 4<br>Check left(= &quot;a&quot;) and right(= &quot;a&quot;) → &quot;abcba&quot; is a palindrome.😆<br>max_length = 5 (= &quot;abcba&quot;)</pre><pre> &quot;abcba&quot;<br> l  i  r</pre><pre>l = -1<br>r = 5<br>Now left and right are out of bounds, so we finish iteration.</pre><p>Let me skip the cases where we start from later “b” and “a”. We already found the max length. (of course solution code will check the later part)</p><p><strong>How do you calculate length of palindrome we found?</strong></p><p>From the example above, we found 5 as a max length. how do you calculate it? Simply</p><pre>right - left</pre><p>Right? So,</p><pre>right - left<br>5 - (-1)<br>= 6</pre><p>Wait? It’s longer than max length we found. The reason why this happens is because the two pointers stop at the next position of max length of palindrome.</p><pre>&quot;abcba&quot;<br> l i r</pre><p>When i = 2 left = 0 and right = 4, we found 5 as a max length, but we don&#39;t know 5 is the max length in the current iteration, so we try to move to the next place to find longer palindrome, even if we don&#39;t find it in the end.</p><p>That’s why, left and right pointer always overrun and stop at max length in current iteration + 1, so we need to subtract -1 from right - left.</p><pre>❌ right - left<br>🔴 right - left - 1</pre><p>But still you don’t get it because we have two pointers expanding at the same time? you think we should subtract -2?</p><p>This is calculation of index number, so index number usually starts from 0 not 1, so right - left includes -1 already. For example,</p><pre>&quot;aba&quot;<br> l r</pre><p>Actual length is 3, but if we calculate the length with index number, that should be 2(index 2 - index 0), so it&#39;s already including -1 compared with actual length. That&#39;s why when we have two pointers and calculate actual length, right - left - 1 works well.</p><p>Now you understand main idea of my solution, but I’m sure you will not pass all cases. Can you geuss why?</p><p>The answer is I explain the case where we have odd length of input string.</p><p>⭐️ <strong>Points</strong></p><p>We have to care about both odd length of input string and even length of input string</p><pre>Input: &quot;abbc&quot;</pre><p>Let’s see one by one. we can use the same idea. Let me write briefly.</p><pre>&quot;abbc&quot;<br>lir</pre><pre>max length = 1</pre><pre>&quot;abbc&quot;<br> lir</pre><pre>max length = 1</pre><pre>&quot;abbc&quot;<br>  lir</pre><pre>max length = 1</pre><pre>&quot;abbc&quot;<br>   lir</pre><pre>max length = 1</pre><pre>❌ Output: &quot;a&quot; or &quot;b&quot; or &quot;c&quot;</pre><p>Output should be</p><pre>🔴 Output: &quot;bb&quot;</pre><p><strong>Why this happens?</strong></p><p>Regarding odd length of input array, center position of palindrome is definitely on some charcter.</p><pre>&quot;abcba&quot;, center is &quot;c&quot;</pre><p>How about even length of input string</p><pre>&quot;abbc&quot;<br>Center of palindrome is &quot;b | b&quot;</pre><p>| is center of palindrome. Not on some character.</p><p><strong>So how can you avoid this?</strong></p><p>My idea to avoid this is we start left with current index and right with current index + 1, so we start interation as if we are coming from between the characters. Let me write only when index = 1.</p><pre>current index = 1</pre><pre>  lr<br>&quot;abbc&quot;<br>  i</pre><pre>We found palindrome &quot;bb&quot;</pre><pre> l  r<br>&quot;abbc&quot;<br>  i</pre><pre>Finish iteration.</pre><p>Then</p><pre>right - left - 1<br>3 - 0 - 1<br>= 2(= length of &quot;bb&quot;)</pre><p>We can use the same idea for both cases but start position is different, that’s why we call the same function twice in one iteration.</p><p>Let’s see a real algorithm!</p><h3>Algorithm Overview:</h3><ol><li>Initialize start and end variables to keep track of the starting and ending indices of the longest palindromic substring.</li><li>Iterate through each character of the input string s.</li><li>For each character, expand around it by calling the expand_around_center function with two different center possibilities: (i) the current character as the center (odd length palindrome), and (ii) the current character and the next character as the center (even length palindrome).</li><li>Compare the lengths of the two expanded palindromes and update start and end if a longer palindrome is found.</li><li>Finally, return the longest palindromic substring by slicing the input string s based on the start and end indices.</li></ol><h3>Complexity</h3><ul><li>Time complexity: O(n^2)</li></ul><p>“n” is the length of the input string “s.” This is because the code uses nested loops. The outer loop runs for each character in the string, and the inner loop, expand_around_center, can potentially run for the entire length of the string in the worst case, leading to a quadratic time complexity.</p><ul><li>Space complexity: O(1)</li></ul><p>the code uses a constant amount of extra space for variables like “start,” “end,” “left,” “right,” and function parameters. The space used does not depend on the size of the input string.</p><h3>Solution Code</h3><p><strong>Python</strong></p><pre>class Solution:<br>    def longestPalindrome(self, s: str) -&gt; str:<br>        if not s:<br>            return &quot;&quot;<br><br>        def expand_around_center(s: str, left: int, right: int):<br>            while left &gt;= 0 and right &lt; len(s) and s[left] == s[right]:<br>                left -= 1<br>                right += 1<br>            return right - left - 1<br><br><br>        start = 0<br>        end = 0<br><br>        for i in range(len(s)):<br>            odd = expand_around_center(s, i, i)<br>            even = expand_around_center(s, i, i + 1)<br>            max_len = max(odd, even)<br>            <br>            if max_len &gt; end - start:<br>                start = i - (max_len - 1) // 2<br>                end = i + max_len // 2<br>        <br>        return s[start:end+1]</pre><p><strong>JavaScript</strong></p><pre>/**<br> * @param {string} s<br> * @return {string}<br> */<br>var longestPalindrome = function(s) {<br>    if (!s) {<br>        return &quot;&quot;;<br>    }<br><br>    function expandAroundCenter(s, left, right) {<br>        while (left &gt;= 0 &amp;&amp; right &lt; s.length &amp;&amp; s[left] === s[right]) {<br>            left--;<br>            right++;<br>        }<br>        return right - left - 1;<br>    }<br><br>    let start = 0;<br>    let end = 0;<br><br>    for (let i = 0; i &lt; s.length; i++) {<br>        const odd = expandAroundCenter(s, i, i);<br>        const even = expandAroundCenter(s, i, i + 1);<br>        const max_len = Math.max(odd, even);<br><br>        if (max_len &gt; end - start) {<br>            start = i - Math.floor((max_len - 1) / 2);<br>            end = i + Math.floor(max_len / 2);<br>        }<br>    }<br><br>    return s.substring(start, end + 1);    <br>};</pre><p><strong>Java</strong></p><pre>class Solution {<br>    public String longestPalindrome(String s) {<br>        if (s == null || s.length() == 0) {<br>            return &quot;&quot;;<br>        }<br><br>        int start = 0;<br>        int end = 0;<br><br>        for (int i = 0; i &lt; s.length(); i++) {<br>            int odd = expandAroundCenter(s, i, i);<br>            int even = expandAroundCenter(s, i, i + 1);<br>            int max_len = Math.max(odd, even);<br><br>            if (max_len &gt; end - start) {<br>                start = i - (max_len - 1) / 2;<br>                end = i + max_len / 2;<br>            }<br>        }<br><br>        return s.substring(start, end + 1);        <br>    }<br><br>    private int expandAroundCenter(String s, int left, int right) {<br>        while (left &gt;= 0 &amp;&amp; right &lt; s.length() &amp;&amp; s.charAt(left) == s.charAt(right)) {<br>            left--;<br>            right++;<br>        }<br>        return right - left - 1;<br>    }    <br>}</pre><p><strong>C++</strong></p><pre>class Solution {<br>public:<br>    string longestPalindrome(string s) {<br>        if (s.empty()) {<br>            return &quot;&quot;;<br>        }<br><br>        int start = 0;<br>        int end = 0;<br><br>        for (int i = 0; i &lt; s.length(); i++) {<br>            int odd = expandAroundCenter(s, i, i);<br>            int even = expandAroundCenter(s, i, i + 1);<br>            int max_len = max(odd, even);<br><br>            if (max_len &gt; end - start) {<br>                start = i - (max_len - 1) / 2;<br>                end = i + max_len / 2;<br>            }<br>        }<br><br>        return s.substr(start, end - start + 1);        <br>    }<br><br>private:<br>    int expandAroundCenter(string s, int left, int right) {<br>        while (left &gt;= 0 &amp;&amp; right &lt; s.length() &amp;&amp; s[left] == s[right]) {<br>            left--;<br>            right++;<br>        }<br>        return right - left - 1;<br>    }    <br>};</pre><p>Let me explain this.</p><pre>if max_len &gt; end - start:<br>    start = i - (max_len - 1) // 2<br>    end = i + max_len // 2</pre><p>if statement means just when we find longer length.</p><p>Let’s use the same example again.</p><pre>Input = &quot;abcba&quot;</pre><p>When i = 2, we find 5 as a max length. Let&#39;s see what will happen.</p><pre>start = i(2) - (max_len(5) - 1) // 2<br>end = i(2) + max_len(5) // 2<br>↓<br>start = 2 - 2<br>end = 2 + 2<br>↓<br>start = 0<br>end = 4</pre><p><strong>Why -1?</strong></p><p>The -1 is used to calculate the length of the palindrome correctly based on whether it is of odd or even length.</p><p>Here, we try to get length of half palindrome except center chracters.</p><p>Regarding odd case, actually it works if we don’t subtract -1, because we have only one center chracter and we start from the character.</p><p>For example</p><pre>&quot;abcba&quot;<br>   ↑<br>Center of palindrome is &quot;c&quot;</pre><p>We will get length of “ab”</p><pre>no -1 case, 5 // 2 = 2<br>-1 case, 4 // 2 = 2</pre><p>The result is the same.</p><p>But regarding even case we start from between characters.</p><pre>&quot;abbc&quot;<br>Center of palindrome is &quot;bb&quot;</pre><p>We will get length of “”(empty = 0), because center character “bb” itself is whole length of palindrome.</p><pre>no -1 case, 2 // 2 = 1<br>-1 case, 1 // 2 = 0</pre><p>The result is different.</p><p>In this case, we have two center charcters, if we remove one character, we can create the same odd case situation from even situaiton, so that we can get correct length except center charcters.</p><p>In this case, i = 1, we get 2 as a max length.</p><pre>&quot;abbc&quot;</pre><pre>start = i(1) - (max_len(2) - 1) // 2<br>end = i(1) + max_len(2) // 2<br>↓<br>start = 1 - 0<br>end = 1 + 1<br>↓<br>start = 1<br>end = 2</pre><p>Looks good! 😆</p><p>Since the result is not affected by -1 in odd case, we subtract -1 both odd case and even case.</p><p>Thank you for reading my post. ⭐️ Please upvote it and don’t forget to subscribe to my channel!</p><p><strong>■ Subscribe URL</strong> <a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><p>⭐️ important topic of time complexity.</p><p><a href="https://youtu.be/K3MES6kEIMA">https://youtu.be/K3MES6kEIMA</a></p><h3>Next Question</h3><h3><a href="https://youtu.be/fxhPxvBAvD0">⭐️ LeetCode #6 ZigZag Conversion video is available from here</a></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=86b89469534f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Median of Two Sorted Arrays — LeetCode 4]]></title>
            <link>https://medium.com/@indy0214_19547/4-median-of-two-sorted-arrays-fd45fd4fa178?source=rss-826581f1758b------2</link>
            <guid isPermaLink="false">https://medium.com/p/fd45fd4fa178</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Ken]]></dc:creator>
            <pubDate>Sat, 09 May 2026 16:42:46 GMT</pubDate>
            <atom:updated>2026-05-09T16:43:08.400Z</atom:updated>
            <content:encoded><![CDATA[<h3>Intuition</h3><p>We divide each array into two parts — the left part (containing smaller numbers) and the right part (containing larger numbers) — to simulate a virtually sorted array.</p><h3><a href="https://youtu.be/xMBwzNvXmms">⭐️ 4. Median of Two Sorted Arrays video is available from here</a></h3><p><strong>You can understand my solution with visualization and I have more +450 videos for technical interviews. Check it out!!</strong></p><p><strong>■ Subscribe URL</strong> <a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><p>Subscribers: 26,227 Thank you for your support!</p><h3>Approach</h3><h3>Definition of the Median</h3><p>The <strong>median</strong> is “the middle value when a sorted array is split exactly in half.” If the number of elements is odd, the median is the middle element. If it’s even, the median is the average of the two middle elements.</p><p>For example:</p><pre>[1, 5, 8] → 5  <br>[1, 3, 5, 8] → 4 ( = (3 + 5) / 2 )</pre><p>The first idea that may come to mind is to <strong>merge the two arrays and extract the middle value</strong>. For example:</p><pre>class Solution:<br>    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -&gt; float:<br>        # Merge the two sorted arrays<br>        merged = sorted(nums1 + nums2)<br>        length = len(merged)<br>        <br>        # Check if the total length is even or odd<br>        if length % 2 == 0:<br>            # If even, return the average of the two middle elements<br>            return (merged[length // 2 - 1] + merged[length // 2]) / 2<br>        else:<br>            # If odd, return the middle element<br>            return merged[length // 2]</pre><p>This code does calculate the median. However, this approach has a time complexity of O((m+n)log(m+n)), which does <strong>not</strong> meet the O(log(m+n)) requirement. To achieve O(log(m+n)), as many may already know, we need to use <strong>binary search</strong>.</p><h3>Key to the Problem: Partition and Comparison</h3><p>The key to solving this problem efficiently is to <strong>“divide each array into left and right parts appropriately.”</strong></p><h3>Why Divide into Left and Right?</h3><p>The <strong>median</strong> is the “middle value when a sorted array is split exactly in half.” If the total number of elements is odd, it’s the one in the center. If even, it’s the average of the two center values.</p><p>Therefore, we can compute the median by finding the <strong>maximum of the left half</strong> or the <strong>average of the max of the left and the min of the right</strong>.</p><p>However, it’s not always the case that all elements of nums1 are smaller than those of nums2, or vice versa.</p><p>For example, if nums1 = [1, 2] and nums2 = [3, 4], you can simply append nums2 after nums1 to get [1, 2, 3, 4], which is sorted, and the median is 2.5.</p><p>However, in the case of nums1 = [1, 3, 8] and nums2 = [7, 9, 10, 11], if we try to merge the arrays directly and sort them, we get [1, 3, 7, 8, 9, 10, 11], where the value 7 from nums2 is smaller than 8 from nums1. This means we can&#39;t simply merge the two arrays as-is. Therefore, we divide each array into left and right parts — the left parts of nums1 and nums2 form the &quot;smaller group&quot;, and the right parts form the &quot;larger group&quot;. We calculate the partition in such a way that the entire combined array would be sorted.</p><p>Since actually merging and sorting the arrays would take more than O(log(m+n)) time, we simulate the sorted array using calculations instead.</p><p>If the maximum of the left part of nums1 (max_left1) is less than or equal to the minimum of the right part of nums2 (min_right2), and the maximum of the left part of nums2 (max_left2) is less than or equal to the minimum of the right part of nums1 (min_right1), then the combined array is virtually sorted. Our goal is to find such a partition using binary search.</p><p>For example:</p><p>These partitions are not correct, but please look at them just to get an idea of how the algorithm works.</p><pre>nums1 = [1, 3, | 8]<br>nums2 = [7 | 9, 10, 11]</pre><pre>max_left1 = 3<br>min_right1 = 8<br>max_left2 = 7<br>min_right2 = 9</pre><pre>if max_left1 &lt;= min_right2 and max_left2 &lt;= min_right1<br>= 3 &lt;= 9 and 7 &lt;= 8<br>= true → array is correctly partitioned</pre><p>You don’t need to compare the left and right within the same array (like max_left1 &lt;= min_right1), because both arrays are sorted individually based on what the question says. So the following conditions always hold:</p><pre>max_left1 &lt;= min_right1<br>max_left2 &lt;= min_right2</pre><h3>How to Determine Partitions</h3><p>The partition that determines the left and right sides is calculated using the binary search left and right.</p><pre>partition1 = (left + right) // 2<br>partition2 = (len1 + len2 + 1) // 2 - partition1</pre><pre>partition1: The number of elements on the left side of nums1<br>partition2: The number of elements on the left side of nums2<br>len1: The length of nums1<br>len2: The length of nums2</pre><p>Regarding partition2, since both partition1 and partition2 represent the total number of elements on the left side, they should sum up to half the length of the merged nums1 and nums2. This gives the following equation:</p><pre>partition1 + partition2 = (len1 + len2 + 1) // 2</pre><p>To calculate partition2, it would be:</p><pre>partition2 = (len1 + len2 + 1) // 2 - partition1</pre><p>What does the +1 mean?</p><p>When the total number of elements is even, the median is the average of the two central values. This means <strong>you add the left maximum value and the right minimum value, and then divide by 2.</strong></p><p>When the total number of elements is odd, the median is the single central value. <strong>By adding the central value to the left maximum value, the logic becomes consistent for both even and odd cases, simplifying the process.</strong></p><h3>How It Works</h3><pre>nums1 = [1, 3, 8]<br>nums2 = [7, 9, 10, 11]</pre><h3>Initialization</h3><pre>len1 = 3<br>len2 = 4<br>left = 0<br>right = 3  # len1</pre><h3>First Binary Search</h3><pre>part1 = 1 → (left + right) // 2<br>part2 = 3 → (len1 + len2 + 1) // 2 - partition1<br>max_left1 = 1<br>min_right1 = 3<br>max_left2 = 10<br>min_right2 = 11</pre><pre>part means partition</pre><pre>nums1 = [1 | 3, 8]<br>nums2 = [7, 9, 10 | 11]</pre><p>Check if we have correct partitions:</p><pre>if max_left1 &lt;= min_right2 and max_left2 &lt;= min_right1<br>= 1 &lt;= 11 and 10 &lt;= 3 → false</pre><p>We can’t create sorted array, because:</p><pre>This is virtual.</pre><pre>combine left sides<br>[1,7,9,10]</pre><pre>combine right sides<br>[3,8,11]</pre><pre>combine left and right<br>[1,7,9,10,3,8,11] → not sorted</pre><p>That’s why we will execute binary search again. But before that, we should narrow search range.</p><p>Since these two input arrays are sorted, the following conditions hold:</p><pre>max_left1 &lt;= min_right1<br>max_left2 &lt;= min_right2</pre><p>Therefore, we compare across the arrays as follows:</p><pre>if max_left1 &gt; min_right2</pre><p>If this condition is true, it means that the partition of nums1 has moved too far to the right. In other words, we need to search for smaller numbers, so we move the right pointer to:</p><pre>right = part1 - 1</pre><p>In the opposite case, we move the left pointer to:</p><pre>left = part1 + 1</pre><p>For this case:</p><pre>if max_left1 &gt; min_right2<br>= 1 &gt; 11<br>= false</pre><p>Since it’s false, we move:</p><pre>left = part1 + 1<br>= 2</pre><p>Now let’s proceed to the next binary search.</p><h3>Second Binary Search</h3><pre>part1 = 2<br>part2 = 2<br>max_left1 = 3<br>min_right1 = 8<br>max_left2 = 9<br>min_right2 = 10</pre><pre>nums1 = [1, 3 | 8]<br>nums2 = [7, 9 | 10, 11]</pre><p>Check if we put partitions correctly:</p><pre>if max_left1 &lt;= min_right2 and max_left2 &lt;= min_right1<br>= 3 &lt;= 10 and 9 &lt;= 8<br>= false, because [1,3,7,9] + [8,10,11] → not sorted</pre><p>Let’s narrow search range again.</p><pre>if max_left1 &gt; min_right2<br>= 3 &gt; 10<br>= false, left = 2 + 1 = 3</pre><h3>Third Binary Search</h3><pre>part1 = 3 → (left + right) // 2  <br>part2 = 1 → (len1 + len2 + 1) // 2 - partition1  <br>max_left1 = 8  <br>min_right1 = infinity  <br>max_left2 = 7  <br>min_right2 = 9</pre><pre>nums1 = [1, 3, 8 |]  <br>nums2 = [7 | 9, 10, 11]</pre><p>Let me explain about infinity. We&#39;ve already seen it twice, so some of you may already understand, but the algorithm checks the following condition:</p><pre>if max_left1 &lt;= min_right2 and max_left2 &lt;= min_right1</pre><p>In this case, there’s no number remaining on the right side of nums1. This means the key comparison is max_left1 &lt;= min_right2. As for the other comparison, max_left2 &lt;= min_right1, we want to ensure it doesn&#39;t cause a false result, so we make it always true. To do that, we set min_right1 to infinity, which is greater than any number. Since it&#39;s the right side of the partition, we use infinity, and when we reach the far left of a partition, we use -infinity.</p><p>Now, let’s return to the main point.</p><pre>if max_left1 &lt;= min_right2 and max_left2 &lt;= min_right1  <br>= 8 &lt;= 9 and 7 &lt;= infinity  <br>= true</pre><p>The condition is true. That means we&#39;ve found a valid partition that results in a sorted array.</p><pre>left: [1, 3, 7, 8]  <br>right: [9, 10, 11]  <br>= [1, 3, 7, 8, 9, 10, 11] → sorted</pre><p>We’ve finally found the correct partition point where the merged array would be sorted. The last point to cover is what we mentioned at the beginning:</p><blockquote><em>The median is the middle value when a sorted array is split exactly in half. If the total number of elements is odd, it’s the middle element. If it’s even, it’s the average of the two central elements.</em></blockquote><p>In this case, nums1 has a length of 3 and nums2 has a length of 4, making the total an odd number. So we just return the single middle value.</p><p>At the point where the partition gives us a sorted array:</p><pre>nums1 = [1, 3, 8 |]  <br>nums2 = [7 | 9, 10, 11]</pre><p>Do you remember why we added +1? In the case of an odd total number, we include the central value in the left half. Therefore, the median is the maximum of the two left sides: max_left1 and max_left2.</p><pre>return max(max_left1, max_left2) = max(8, 7)  <br>= 8</pre><p>Just for reference, if the total number of elements were even — for example, nums1 = [1, 2], nums2 = [3, 4] — the final partition would look like this:</p><pre>nums1 = [1, 2 |]  <br>nums2 = [| 3, 4]  <br>= [1, 2 | 3, 4]  <br>= 2.5 → (2 + 3) / 2  </pre><pre>max_left1 = 2  <br>min_right1 = inf  <br>max_left2 = -inf  <br>min_right2 = 3</pre><p>To get the median, we add the maximum of the two left values and the minimum of the two right values, then divide by 2.</p><pre>return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2  <br>= (max(2, -inf) + min(inf, 3)) / 2  <br>= (2 + 3) / 2  <br>= 2.5</pre><p>Looks good! 😆</p><p>Let’s see solution codes!</p><h3>How I Studied LeetCode as a Beginner (That Actually Worked)</h3><h3><a href="https://youtu.be/bU_dXCOWHls">⭐️ How to Use LeetCode Effectively video is available from here</a></h3><h3>Complexity</h3><p>Based on Python. Others might be different.</p><ul><li>Time complexity: O(log(min(m, n)))</li><li>Space complexity: O(1)</li></ul><h3>Code</h3><pre>class Solution:<br>    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -&gt; float:</pre><pre>        # Since one of the arrays can be significantly longer than<br>        # the other, we always perform binary search on the shorter<br>        # array to ensure that the time complexity remains<br>        # O(log(min(m, n))).<br>        if len(nums1) &gt; len(nums2):<br>            return self.findMedianSortedArrays(nums2, nums1)</pre><pre>        len1, len2 = len(nums1), len(nums2)<br>        left, right = 0, len1</pre><pre>        while left &lt;= right:<br>            part1 = (left + right) // 2<br>            part2 = (len1 + len2 + 1) // 2 - part1</pre><pre>            max_left1 = float(&#39;-inf&#39;) if part1 == 0 else nums1[part1 - 1]<br>            min_right1 = float(&#39;inf&#39;) if part1 == len1 else nums1[part1]<br>            max_left2 = float(&#39;-inf&#39;) if part2 == 0 else nums2[part2 - 1]<br>            min_right2 = float(&#39;inf&#39;) if part2 == len2 else nums2[part2]</pre><pre>            if max_left1 &lt;= min_right2 and max_left2 &lt;= min_right1:<br>                if (len1 + len2) % 2 == 0:<br>                    return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2<br>                else:<br>                    return max(max_left1, max_left2)<br>            elif max_left1 &gt; min_right2:<br>                right = part1 - 1<br>            else:<br>                left = part1 + 1</pre><pre>var findMedianSortedArrays = function(nums1, nums2) {<br>    if (nums1.length &gt; nums2.length) {<br>        return findMedianSortedArrays(nums2, nums1);<br>    }</pre><pre>    const len1 = nums1.length;<br>    const len2 = nums2.length;<br>    let left = 0, right = len1;</pre><pre>    while (left &lt;= right) {<br>        const part1 = Math.floor((left + right) / 2);<br>        const part2 = Math.floor((len1 + len2 + 1) / 2) - part1;</pre><pre>        const maxLeft1 = part1 === 0 ? -Infinity : nums1[part1 - 1];<br>        const minRight1 = part1 === len1 ? Infinity : nums1[part1];<br>        const maxLeft2 = part2 === 0 ? -Infinity : nums2[part2 - 1];<br>        const minRight2 = part2 === len2 ? Infinity : nums2[part2];</pre><pre>        if (maxLeft1 &lt;= minRight2 &amp;&amp; maxLeft2 &lt;= minRight1) {<br>            if ((len1 + len2) % 2 === 0) {<br>                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;<br>            } else {<br>                return Math.max(maxLeft1, maxLeft2);<br>            }<br>        } else if (maxLeft1 &gt; minRight2) {<br>            right = part1 - 1;<br>        } else {<br>            left = part1 + 1;<br>        }<br>    }    <br>};</pre><pre>class Solution {<br>    public double findMedianSortedArrays(int[] nums1, int[] nums2) {<br>        if (nums1.length &gt; nums2.length) {<br>            return findMedianSortedArrays(nums2, nums1);<br>        }</pre><pre>        int len1 = nums1.length, len2 = nums2.length;<br>        int left = 0, right = len1;</pre><pre>        while (left &lt;= right) {<br>            int part1 = (left + right) / 2;<br>            int part2 = (len1 + len2 + 1) / 2 - part1;</pre><pre>            int maxLeft1 = (part1 == 0) ? Integer.MIN_VALUE : nums1[part1 - 1];<br>            int minRight1 = (part1 == len1) ? Integer.MAX_VALUE : nums1[part1];<br>            int maxLeft2 = (part2 == 0) ? Integer.MIN_VALUE : nums2[part2 - 1];<br>            int minRight2 = (part2 == len2) ? Integer.MAX_VALUE : nums2[part2];</pre><pre>            if (maxLeft1 &lt;= minRight2 &amp;&amp; maxLeft2 &lt;= minRight1) {<br>                if ((len1 + len2) % 2 == 0) {<br>                    return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;<br>                } else {<br>                    return (double) Math.max(maxLeft1, maxLeft2);<br>                }<br>            } else if (maxLeft1 &gt; minRight2) {<br>                right = part1 - 1;<br>            } else {<br>                left = part1 + 1;<br>            }<br>        }<br>        return 0.0;        <br>    }<br>}</pre><pre>class Solution {<br>public:<br>    double findMedianSortedArrays(vector&lt;int&gt;&amp; nums1, vector&lt;int&gt;&amp; nums2) {<br>        if (nums1.size() &gt; nums2.size()) {<br>            return findMedianSortedArrays(nums2, nums1);<br>        }</pre><pre>        int len1 = nums1.size(), len2 = nums2.size();<br>        int left = 0, right = len1;</pre><pre>        while (left &lt;= right) {<br>            int part1 = (left + right) / 2;<br>            int part2 = (len1 + len2 + 1) / 2 - part1;</pre><pre>            int maxLeft1 = (part1 == 0) ? INT_MIN : nums1[part1 - 1];<br>            int minRight1 = (part1 == len1) ? INT_MAX : nums1[part1];<br>            int maxLeft2 = (part2 == 0) ? INT_MIN : nums2[part2 - 1];<br>            int minRight2 = (part2 == len2) ? INT_MAX : nums2[part2];</pre><pre>            if (maxLeft1 &lt;= minRight2 &amp;&amp; maxLeft2 &lt;= minRight1) {<br>                if ((len1 + len2) % 2 == 0) {<br>                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;<br>                } else {<br>                    return max(maxLeft1, maxLeft2);<br>                }<br>            } else if (maxLeft1 &gt; minRight2) {<br>                right = part1 - 1;<br>            } else {<br>                left = part1 + 1;<br>            }<br>        }</pre><pre>        return 0.0;        <br>    }<br>};</pre><h3>Step by Step Algorithm</h3><p><strong>1. Ensure nums1 is the smaller array:</strong></p><pre>if len(nums1) &gt; len(nums2):<br>    return self.findMedianSortedArrays(nums2, nums1)</pre><p>We always perform binary search on the <strong>shorter array</strong> to minimize the search space.</p><p><strong>2. Initialize variables:</strong></p><pre>len1, len2 = len(nums1), len(nums2)<br>left, right = 0, len1</pre><p><strong>3. Binary Search Loop on nums1:</strong></p><pre>while left &lt;= right:</pre><p>At each iteration:</p><p><strong>a. Partition both arrays:</strong></p><pre>part1 = (left + right) // 2<br>part2 = (len1 + len2 + 1) // 2 - part1</pre><ul><li>We divide the combined array into two halves such that the total number of elements in the left half is (len1 + len2 + 1) // 2.</li><li>part1 is the partition index in nums1, and part2 is in nums2.</li></ul><p><strong>b. Get max of left parts and min of right parts:</strong></p><pre>max_left1 = float(&#39;-inf&#39;) if part1 == 0 else nums1[part1 - 1]<br>min_right1 = float(&#39;inf&#39;) if part1 == len1 else nums1[part1]</pre><pre>max_left2 = float(&#39;-inf&#39;) if part2 == 0 else nums2[part2 - 1]<br>min_right2 = float(&#39;inf&#39;) if part2 == len2 else nums2[part2]</pre><p>These values define the current virtual “cut” in the combined array:</p><pre>[ ... max_left1 | min_right1 ... ]<br>[ ... max_left2 | min_right2 ... ]</pre><p><strong>c. Check if the partition is correct:</strong></p><pre>if max_left1 &lt;= min_right2 and max_left2 &lt;= min_right1:</pre><p>If so, you’ve found the correct partition.</p><ul><li><strong>If the total number of elements is even:</strong></li></ul><pre>return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2</pre><ul><li><strong>If odd:</strong></li></ul><pre>return max(max_left1, max_left2)</pre><p><strong>d. Adjust binary search range:</strong></p><p>If the partition is not correct, move the binary search range:</p><pre>elif max_left1 &gt; min_right2:<br>    right = part1 - 1<br>else:<br>    left = part1 + 1</pre><p>Thank you for reading my post.</p><p>⭐️ Please upvote it and don’t forget to subscribe to my channel!</p><p>⭐️ Subscribe URL <a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><h3>Next Question</h3><h3><a href="https://youtu.be/aMH1eomKCmE">⭐️ 5. Longest Palindromic Substring video is available from here</a></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fd45fd4fa178" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Longest Substring Without Repeating Characters — LeetCode 3]]></title>
            <link>https://medium.com/@indy0214_19547/longest-substring-without-repeating-characters-32092248b1a4?source=rss-826581f1758b------2</link>
            <guid isPermaLink="false">https://medium.com/p/32092248b1a4</guid>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Ken]]></dc:creator>
            <pubDate>Wed, 06 May 2026 06:14:45 GMT</pubDate>
            <atom:updated>2026-05-06T06:18:54.534Z</atom:updated>
            <content:encoded><![CDATA[<p>Solution Video Link</p><h3><a href="https://youtu.be/n4zCTMh03_M">⭐️ 3. Longest Substring Without Repeating Characters video is avaiable from here</a></h3><p><strong>It provides a visual explanation of the three solutions and I have more +450 videos for technical interviews including System Design. Check it out!!</strong></p><p><strong>■ Subscribe URL</strong><br><a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><p>Subscribers: 26,260<br>Thank you for your support!</p><h3>Approach</h3><p>We have two conditions to solve this question. The longest string should be</p><ul><li>Substring</li><li>Without repeating characters</li></ul><p>You just need to check that there are no repeated characters within a consecutive string of characters. To achieve this, you need to keep track of the characters currently forming the string. For this purpose, I considered three algorithms: one combining a sliding window and a set, and the second using a sliding window and a hash-based algorithm. The thrid is that the last position where each character was seen.</p><p>I’ll explain them one by one.</p><h3>Solution 1 — Sliding Window &amp; Set</h3><p>First of all, we create</p><pre>left = 0 <br>max_length = 0 (returned value)<br>char_set = set()</pre><p>left is pointer of sliding window.<br>max_length is a value we should return.<br>char_set is to keep current characters forming the longest string with the two conditions above.</p><p>We will iterate through all characters one by one and create right pointer of sliding window with for loop.</p><pre>for right in range(len(s)):</pre><p>Let’s begin!</p><pre>Input: s = &quot;abcabcbb&quot;</pre><pre>&quot;abcabcbb&quot;<br> r<br> l</pre><p>l is left of sliding window<br>r is right of sliding window</p><p>We found a. Every time we check char_set if we have the same character or not. In this case, we don&#39;t have a in char_set, so add a to char_set.</p><pre>char_set = {a}</pre><p>After that, we check max length.</p><pre>max_length = 0<br>current length = right - left + 1</pre><p>Why +1?</p><p>That’s because current length of string is 1 which is only a, so if we don&#39;t add 1, we will calculate 0(right) - 0(left) = 0 which is wrong answer.</p><p>This happens because the difference R - L represents the number of positions between the two indices, not the number of elements including both ends. To correctly count all characters from L to R, including both endpoints, we need to add +1. This ensures the length includes both the starting and ending characters.</p><p>Let’s go back to the main point.</p><pre>max_length = 1</pre><p>Next, only right pointer move next. I’ll speed up.</p><pre>&quot;abcabcbb&quot;<br> lr</pre><pre>Do we have &quot;b&quot;? → No<br>char_set = {a, b}</pre><pre>max_length = 2 (right(1) - left(0) + 1)</pre><p>Next, only right pointer move next.</p><pre>&quot;abcabcbb&quot;<br> l r</pre><pre>Do we have &quot;c&quot;? → No<br>char_set = {a,b,c}</pre><pre>max_length = 3 (right(2) - left(0) + 1)</pre><p>Next, only right pointer move next.</p><pre>&quot;abcabcbb&quot;<br> l  r</pre><pre>Do we have &quot;a&quot;? → Yes</pre><p>In this case, we have duplicate number a, so we can&#39;t continue to expand the string. That&#39;s why it&#39;s time to move left to the next. And we have important point.</p><p>⭐️ Points</p><p>When we move left to index 1, a at index 0 will be out of bounds, so we should remove a from char_set, so that we can keep unique characters forming the current string.</p><p>In this case, we use while loop, I&#39;ll explain why later.</p><pre>&quot;abcabcbb&quot;<br> l  r</pre><pre>- Do we have &quot;a&quot;? → Yes, remove &quot;a&quot; in char_set<br>char_set = {b,c}</pre><pre>- move left to the next<br>&quot;abcabcbb&quot;<br>  l r</pre><pre>- There is no &quot;a&quot; in char_set, we stop while looping.<br>- And add crreunt &quot;a&quot; to char_set<br>char_set = {b,c,a}</pre><pre>max_length = 3 (right(3) - left(1) + 1)</pre><p>Next, only right pointer move next.</p><pre>&quot;abcabcbb&quot;<br>  l  r</pre><pre>- Do we have &quot;b&quot;? → Yes, remove &quot;b&quot; in char_set<br>char_set = {c,a}</pre><pre>- move left to the next<br>&quot;abcabcbb&quot;<br>   l r</pre><pre>- There is no &quot;b&quot; in char_set, we stop while looping.<br>- And add crreunt &quot;b&quot; to char_set<br>char_set = {c,a,b}</pre><pre>max_length = 3 (right(4) - left(2) + 1)</pre><p>Next, only right pointer move next.</p><pre>&quot;abcabcbb&quot;<br>   l  r</pre><pre>- Do we have &quot;c&quot;? → Yes, remove &quot;c&quot; in char_set<br>char_set = {a,b}</pre><pre>- move left to the next<br>&quot;abcabcbb&quot;<br>    l r</pre><pre>- There is no &quot;c&quot; in char_set, we stop while looping.<br>- And add crreunt &quot;c&quot; to char_set<br>char_set = {a,b,c}</pre><pre>max_length = 3 (right(5) - left(3) + 1)</pre><p>Next, only right pointer move next.</p><pre>&quot;abcabcbb&quot;<br>    l  r</pre><pre>- Do we have &quot;b&quot;? → Yes, remove &quot;a&quot; in char_set</pre><p>Wait! Why do we have to remove a instead of b? That&#39;s because b is now duplicate character between left and right, so we have to remove chracters until we find b with left pointer.</p><p>⭐️ Points<br>Let’s look at the string deeply.</p><pre>&quot;abcb&quot;<br> l  r</pre><p>If we keep a in the string, we have to also keep the first b because a is outside of the first b in the string. If we want to remove the first b, we must remove a before we remove the first b. <strong>This is substring.</strong></p><p>In the end,</p><pre>&quot;abcb&quot;<br>   lr</pre><p>Let’s look at the process.</p><pre>&quot;abcabcbb&quot;<br>    l  r</pre><pre>- Do we have &quot;b&quot;? → Yes, remove &quot;a&quot; in char_set<br>char_set = {b,c}</pre><pre>- Move left to the next<br>&quot;abcabcbb&quot;<br>     l r</pre><pre>- Do we have &quot;b&quot;? → Yes, remove &quot;b&quot; in char_set<br>char_set = {c}</pre><pre>- Move left to the next<br>&quot;abcabcbb&quot;<br>      lr</pre><pre>- Do we have &quot;b&quot;? → No, now we stop while loop</pre><pre>- Add current &quot;b&quot; to char_set<br>- char_set = {c,b}</pre><pre>max_length = 3 &gt; (right(6) - left(5) + 1)</pre><p>I hope now you understand why we use while loop when remove charcters. <strong>There is an case where we remove multiple characters.</strong></p><p>I stop rest of explanation because we will repeat the same process.</p><pre>return 3</pre><p>As you can see, we keep char_set the same as the string between left and right when we add a current character to char_set. That&#39;s why we can check if current character is duplicate or not.</p><p>Easy😆!<br>Let’s see solution codes and step by step algorithm!</p><p>How I Studied LeetCode as a Beginner (That Actually Worked)</p><h3><a href="https://youtu.be/bU_dXCOWHls">⭐️ How to Use LeetCode Effectively video is available from here</a></h3><h3>Complexity</h3><ul><li>Time complexity: O(n)</li><li>Space complexity: O(1)</li></ul><p>Constraints say “s consists of English letters, digits, symbols and spaces”. I think we have fixed max size of characters consisting of the input string.</p><pre>class Solution:<br>    def lengthOfLongestSubstring(self, s: str) -&gt; int:<br>        left = max_length = 0<br>        char_set = set()<br>        <br>        for right in range(len(s)):<br>            while s[right] in char_set:<br>                char_set.remove(s[left])<br>                left += 1<br><br>            char_set.add(s[right])<br>            max_length = max(max_length, right - left + 1)<br>        <br>        return max_length</pre><pre>var lengthOfLongestSubstring = function(s) {<br>    let left = 0;<br>    let maxLength = 0;<br>    let charSet = new Set();<br><br>    for (let right = 0; right &lt; s.length; right++) {<br>        while (charSet.has(s[right])) {<br>            charSet.delete(s[left]);<br>            left++;<br>        }<br><br>        charSet.add(s[right]);<br>        maxLength = Math.max(maxLength, right - left + 1);<br>    }<br><br>    return maxLength;    <br>};</pre><pre>class Solution {<br>    public int lengthOfLongestSubstring(String s) {<br>        int left = 0;<br>        int maxLength = 0;<br>        HashSet&lt;Character&gt; charSet = new HashSet&lt;&gt;();<br><br>        for (int right = 0; right &lt; s.length(); right++) {<br>            while (charSet.contains(s.charAt(right))) {<br>                charSet.remove(s.charAt(left));<br>                left++;<br>            }<br><br>            charSet.add(s.charAt(right));<br>            maxLength = Math.max(maxLength, right - left + 1);<br>        }<br><br>        return maxLength;       <br>    }<br>}</pre><pre>class Solution {<br>public:<br>    int lengthOfLongestSubstring(string s) {<br>        int left = 0;<br>        int maxLength = 0;<br>        unordered_set&lt;char&gt; charSet;<br><br>        for (int right = 0; right &lt; s.length(); right++) {<br>            while (charSet.find(s[right]) != charSet.end()) {<br>                charSet.erase(s[left]);<br>                left++;<br>            }<br><br>            charSet.insert(s[right]);<br>            maxLength = max(maxLength, right - left + 1);<br>        }<br><br>        return maxLength;        <br>    }<br>};</pre><h3>Step by step algorithm</h3><ol><li><strong>Initialization:</strong></li></ol><pre>left = max_length = 0<br>char_set = set()</pre><ul><li>left: Marks the start of the current substring.</li><li>max_length: Tracks the length of the longest substring without repeating characters. Initialized to 0.</li><li>char_set: Keeps track of unique characters encountered so far, initialized as an empty set.</li></ul><p><strong>2. Iterating over the string characters:</strong></p><pre>for right in range(len(s)):</pre><ul><li>right: Represents the end of the current substring. It moves from 0 to the end of the string.</li></ul><p><strong>3. Checking for repeating characters:</strong></p><pre>while s[right] in char_set:<br>    char_set.remove(s[left])<br>    left += 1</pre><ul><li>This loop executes when the character at the ‘right’ index is already in the char_set, meaning we have encountered a repeating character.</li><li>It removes characters from the char_set and adjusts the &#39;left&#39; pointer until the current character at &#39;right&#39; is no longer in the char_set.</li></ul><p><strong>3. Updating </strong><strong>char_set and </strong><strong>max_length:</strong></p><pre>char_set.add(s[right])<br>max_length = max(max_length, right - left + 1)</pre><ul><li>Adds the current character to char_set.</li><li>Updates max_length.</li></ul><p><strong>4. Returning </strong><strong>max_length:</strong></p><pre>return max_length</pre><h3>Solution 2 — Sliding Window and Hashing</h3><p>In solution 2, we use almost the same idea as solution 1 with Slinding Window and Hashing. In Python, we use HashMap.</p><p>In HashMap, we keep each character as a key and frequency of the characters as a value.</p><p>Every time we find a character, add 1 frequency to HashMap. Since this question requires us to find the longest substring without repeating characters, so if we have more than 2 frequency of the current character, we add -1 to HashMap until we have 1 frequency of the current character and move left pointer to the next at the same time.</p><p>After that, this is the same as solution 1. Just compare max length</p><pre>max_length = max(max_length, right - left + 1)</pre><p>Easy😄！</p><p>Let’s see solution codes and step by step algorithm!</p><h3>Complexity</h3><ul><li>Time complexity: O(n)</li><li>Space complexity: O(1)</li></ul><p>Constraints say “s consists of English letters, digits, symbols and spaces”. I think we have fixed max size of characters consisting of the input string.</p><pre>class Solution:<br>    def lengthOfLongestSubstring(self, s: str) -&gt; int:<br><br>        max_length = left = 0<br>        count = {}<br><br>        for right, c in enumerate(s):<br>            count[c] = 1 + count.get(c, 0)<br>            while count[c] &gt; 1:<br>                count[s[left]] -= 1<br>                left += 1<br>        <br>            max_length = max(max_length, right - left + 1)<br><br>        return max_length</pre><pre>var lengthOfLongestSubstring = function(s) {<br>    let maxLength = 0;<br>    let left = 0;<br>    let count = {};<br><br>    for (let right = 0; right &lt; s.length; right++) {<br>        let c = s[right];<br>        count[c] = (count[c] || 0) + 1;<br>        <br>        while (count[c] &gt; 1) {<br>            count[s[left]] -= 1;<br>            left++;<br>        }<br>        <br>        maxLength = Math.max(maxLength, right - left + 1);<br>    }<br>    <br>    return maxLength;    <br>};</pre><pre>class Solution {<br>    public int lengthOfLongestSubstring(String s) {<br>        int maxLength = 0;<br>        int left = 0;<br>        Map&lt;Character, Integer&gt; count = new HashMap&lt;&gt;();<br><br>        for (int right = 0; right &lt; s.length(); right++) {<br>            char c = s.charAt(right);<br>            count.put(c, count.getOrDefault(c, 0) + 1);<br>            <br>            while (count.get(c) &gt; 1) {<br>                char leftChar = s.charAt(left);<br>                count.put(leftChar, count.get(leftChar) - 1);<br>                left++;<br>            }<br>            <br>            maxLength = Math.max(maxLength, right - left + 1);<br>        }<br>        <br>        return maxLength;       <br>    }<br>}</pre><pre>class Solution {<br>public:<br>    int lengthOfLongestSubstring(string s) {<br>        int maxLength = 0;<br>        int left = 0;<br>        unordered_map&lt;char, int&gt; count;<br><br>        for (int right = 0; right &lt; s.length(); right++) {<br>            char c = s[right];<br>            count[c] = count[c] + 1;<br>            <br>            while (count[c] &gt; 1) {<br>                char leftChar = s[left];<br>                count[leftChar] = count[leftChar] - 1;<br>                left++;<br>            }<br>            <br>            maxLength = max(maxLength, right - left + 1);<br>        }<br>        <br>        return maxLength;        <br>    }<br>};</pre><h3>Step by step algorithm</h3><ol><li><strong>Initialization:</strong></li></ol><pre>max_length = left = 0<br>count = {}</pre><p><strong>2. Iterating Over the String:</strong></p><pre>for right, c in enumerate(s):</pre><p><strong>3. Updating the Character Count:</strong></p><pre>count[c] = 1 + count.get(c, 0)</pre><p><strong>4. Adjusting the Left Pointer:</strong></p><pre>while count[c] &gt; 1:<br>    count[s[left]] -= 1<br>    left += 1</pre><p><strong>5. Updating the Maximum Length:</strong></p><pre>max_length = max(max_length, right - left + 1)</pre><p><strong>6. Returning the Result:</strong></p><pre>return max_length</pre><h3>Solution 3 — the last position where each character was seen</h3><p>In the solution 3, we also iterate through all characters one by one. That is right pointer.</p><p>We update left pointer with HashMap. In HashMap, we keep each character as a key and the last position where each character was seen as a value.</p><p>Do you remember this example in solution 1?</p><pre>&quot;abcb&quot;<br> l  r</pre><p>Let’s call HashMap last_seen.</p><p>In this case, last_seen should have this</p><pre>last_seen = {a:0, b:1, c:2}</pre><p>Now we find the second b at index 3. We update left pointer with:</p><pre>left = last_seen[b] + 1</pre><p>Then compare max length</p><pre>max_length = max(max_length, right - left + 1)</pre><p>Easy😄！</p><p>Let’s see solution codes and step by step algorithm!</p><h3>Complexity</h3><ul><li>Time complexity: O(n)</li><li>Space complexity: O(1)</li></ul><p>Constraints say “s consists of English letters, digits, symbols and spaces”. I think we have fixed max size of characters consisting of the input string.</p><pre>class Solution:<br>    def lengthOfLongestSubstring(self, s: str) -&gt; int:<br>        max_length = 0<br>        left = 0<br>        last_seen = {}<br><br>        for right, c in enumerate(s):<br>            if c in last_seen and last_seen[c] &gt;= left:<br>                left = last_seen[c] + 1<br>            <br>            max_length = max(max_length, right - left + 1)<br>            last_seen[c] = right<br><br>        return max_length</pre><pre>var lengthOfLongestSubstring = function(s) {<br>    let maxLength = 0;<br>    let left = 0;<br>    let lastSeen = {};<br><br>    for (let right = 0; right &lt; s.length; right++) {<br>        let c = s.charAt(right);<br>        if (c in lastSeen &amp;&amp; lastSeen[c] &gt;= left) {<br>            left = lastSeen[c] + 1;<br>        }<br>        maxLength = Math.max(maxLength, right - left + 1);<br>        lastSeen[c] = right;<br>    }<br><br>    return maxLength;     <br>};</pre><pre>class Solution {<br>    public int lengthOfLongestSubstring(String s) {<br>        int maxLength = 0;<br>        int left = 0;<br>        Map&lt;Character, Integer&gt; lastSeen = new HashMap&lt;&gt;();<br><br>        for (int right = 0; right &lt; s.length(); right++) {<br>            char c = s.charAt(right);<br>            if (lastSeen.containsKey(c) &amp;&amp; lastSeen.get(c) &gt;= left) {<br>                left = lastSeen.get(c) + 1;<br>            }<br>            maxLength = Math.max(maxLength, right - left + 1);<br>            lastSeen.put(c, right);<br>        }<br><br>        return maxLength;       <br>    }<br>}</pre><pre>class Solution {<br>public:<br>    int lengthOfLongestSubstring(string s) {<br>        int maxLength = 0;<br>        int left = 0;<br>        unordered_map&lt;char, int&gt; lastSeen;<br><br>        for (int right = 0; right &lt; s.length(); right++) {<br>            char c = s[right];<br>            if (lastSeen.find(c) != lastSeen.end() &amp;&amp; lastSeen[c] &gt;= left) {<br>                left = lastSeen[c] + 1;<br>            }<br>            maxLength = max(maxLength, right - left + 1);<br>            lastSeen[c] = right;<br>        }<br><br>        return maxLength;        <br>    }<br>};</pre><h3>Step by step algorithm</h3><ol><li><strong>Initialization:</strong></li></ol><pre>max_length = 0<br>left = 0<br>last_seen = {}</pre><p><strong>2. Iterating Over the String:</strong></p><pre>for right, c in enumerate(s):</pre><p><strong>3. Checking for Repeating Characters:</strong></p><pre>if c in last_seen and last_seen[c] &gt;= left:<br>    left = last_seen[c] + 1</pre><p><strong>4. Updating </strong><strong>max_length:</strong></p><pre>max_length = max(max_length, right - left + 1)</pre><p><strong>5. Updating </strong><strong>last_seen:</strong></p><pre>last_seen[c] = right</pre><p><strong>6. Returning the Result:</strong></p><pre>return max_length</pre><p>Thank you for reading my post. Please upvote it and don’t forget to subscribe to my channel!</p><p>⭐️ Subscribe URL<br><a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><h3>Next Question</h3><h3><a href="https://youtu.be/xMBwzNvXmms">⭐️ 4. Median of Two Sorted Arrays video is avaiable from here</a></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=32092248b1a4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Add Two Numbers — LeetCode 2]]></title>
            <link>https://medium.com/@indy0214_19547/intuition-a227d68b5414?source=rss-826581f1758b------2</link>
            <guid isPermaLink="false">https://medium.com/p/a227d68b5414</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Ken]]></dc:creator>
            <pubDate>Mon, 04 May 2026 02:01:51 GMT</pubDate>
            <atom:updated>2026-05-04T02:02:49.799Z</atom:updated>
            <content:encoded><![CDATA[<h3><a href="https://youtu.be/DFDTaCGlzTY">⭐️ Add Two number video is available from here</a></h3><p><strong>You can understand my solution with visualization and I have more +450 videos for technical interviews. Check it out!!</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*FVqhaI5rmS30dXqU.jpeg" /></figure><p><strong>■ Subscribe URL</strong><br><a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><p>Subscribers: 25,990<br>Thank you for your support!</p><h3>Approach</h3><p>This question is very simple. All we have to do is just to calculate node values from l1 and l2. Let&#39;s think about this case.</p><pre>Input: l1 = [2,4,3], l2 = [5,6]</pre><p>In the case, output should be</p><pre>[2,4,3]<br>[5,6]<br>-------<br>[7,0,4]</pre><p>We will implement simple algorithm and create a new LinkedList.</p><p>First of all, we create dummy node with value 0(you can put any number instead of 0).</p><pre>0 → None<br>d<br>r</pre><pre>d is dummy pointer<br>r is result pointer</pre><p>We copy dummy pointer and create result pointer. I’ll explain why we need result pointer later.</p><p>Basically, we calculate addition with values from l1 and l2 at the same index. Let&#39;s begin.</p><pre>[2,4,3]<br>[5,6]<br> ↑</pre><pre>2 + 5 = 7</pre><p>We got 7 as a total, so we create a new node with 7 and then connect it with node 0.</p><pre>0 → 7 → None<br>r   d</pre><p>We move dummy pointer to the next node(= 7) so that we can connect the next new node easily after 7.</p><p>Let’s calculate addition with the next values.</p><pre>[2,4,3]<br>[5,6]<br>   ↑</pre><pre>4 + 6 = 10</pre><p>We got 10. In that case, we want to put 0 for current digit. How can we put 0?</p><p>⭐️ Points</p><p>Simply, we use remainder divided by 10.</p><pre>total % 10</pre><p>For example,</p><pre>10 % 10 = 0<br>15 % 10 = 5<br>7 % 10 = 7</pre><p>You can use it when total is one digit. For example, previous digit 2 + 5 = 7</p><p>We have one more important thing. We have carry for a next digit, because total of current digit is 10. How can we calculate the carry?</p><p>⭐️ Points</p><p>Just divide total by 10, but this time we use // in Python.</p><pre>total // 10</pre><p>For example,</p><pre>8 // 10 = 0<br>18 // 10 = 1</pre><p>Now, we can get 0 for the current digit and carry 1 for the next digit, so we create a new node with 0 and then connect it with node 7 and move dummy pointer to node 0</p><pre>0 → 7 → 0 → None<br>r       d</pre><pre>carry = 1</pre><p>Next</p><pre>[2,4,3]<br>[5,6]<br>     ↑</pre><pre>3 + 0 + 1 = 4</pre><pre>0 comes after 6 in the second list<br>1 is carry</pre><p>Now, we can get 4 for the current digit and carry 0 for the next digit, so we create a new node with 4 and then connect it with node 0 and move dummy pointer to node 4</p><pre>0 → 7 → 0 → 4 → None<br>r           d</pre><pre>carry = 0</pre><p>We finish iteration. Problem here is that dummy pointer is at node 4 but we want to return 7 → 0 → 4, how can we return the whole new list?</p><p>⭐️ Points</p><p>Luckily, we have result pointer that is pointing to the first node 0. That is a reason why we copy dummy pointer and create result pointer at first.</p><p>We should return r.next(= node 7).</p><pre>return 7 → 0 → 4</pre><p>Let me add one more explanation. This is about conditions to continue calculating addition. To understand it, let’s add 7 to the second list after 6.</p><pre>0,0,1,1 (= carry)<br>[2,4,3]<br>[5,6,7]<br>--------<br>[7,0,1,1]</pre><p>In this case, 1 + 3 + 7 creates carry, so we should add node 1 at last. From this example, we have 3 conditions to continue calculating.</p><p>⭐️ Points</p><p>If list 1 has a value(= not null) or list 2 has a value(= not null) or we have a carry, then we continue to calculate addtion.</p><p>In the solution code, I use while instead of if.</p><p>Easy😄!<br>Let’s see solution codes and step by step algorithm!</p><p>How I Studied LeetCode as a Beginner (That Actually Worked)</p><h3><a href="https://youtu.be/bU_dXCOWHls">⭐️ How to Use LeetCode Effectively video is available from here</a></h3><h3>Solution Codes</h3><pre>class Solution:<br>    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -&gt; Optional[ListNode]:<br>        <br>        dummy = ListNode()<br>        res = dummy<br><br>        total = carry = 0<br><br>        while l1 or l2 or carry:<br>            total = carry<br><br>            if l1:<br>                total += l1.val<br>                l1 = l1.next<br>            if l2:<br>                total += l2.val<br>                l2 = l2.next<br>            <br>            num = total % 10<br>            carry = total // 10<br>            dummy.next = ListNode(num)<br>            dummy = dummy.next<br>        <br>        return res.next</pre><pre>var addTwoNumbers = function(l1, l2) {<br>    let dummy = new ListNode();<br>    let res = dummy;<br>    let total = 0, carry = 0;<br><br>    while (l1 || l2 || carry) {<br>        total = carry;<br><br>        if (l1) {<br>            total += l1.val;<br>            l1 = l1.next;<br>        }<br>        if (l2) {<br>            total += l2.val;<br>            l2 = l2.next;<br>        }<br><br>        let num = total % 10;<br>        carry = Math.floor(total / 10);<br>        dummy.next = new ListNode(num);<br>        dummy = dummy.next;<br>    }<br><br>    return res.next;    <br>};</pre><pre>class Solution {<br>    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {<br>        ListNode dummy = new ListNode();<br>        ListNode res = dummy;<br>        int total = 0, carry = 0;<br><br>        while (l1 != null || l2 != null || carry != 0) {<br>            total = carry;<br><br>            if (l1 != null) {<br>                total += l1.val;<br>                l1 = l1.next;<br>            }<br>            if (l2 != null) {<br>                total += l2.val;<br>                l2 = l2.next;<br>            }<br><br>            int num = total % 10;<br>            carry = total / 10;<br>            dummy.next = new ListNode(num);<br>            dummy = dummy.next;<br>        }<br><br>        return res.next;        <br>    }<br>}</pre><pre>class Solution {<br>public:<br>    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {<br>        ListNode* dummy = new ListNode();<br>        ListNode* res = dummy;<br>        int total = 0, carry = 0;<br><br>        while (l1 || l2 || carry) {<br>            total = carry;<br><br>            if (l1) {<br>                total += l1-&gt;val;<br>                l1 = l1-&gt;next;<br>            }<br>            if (l2) {<br>                total += l2-&gt;val;<br>                l2 = l2-&gt;next;<br>            }<br><br>            int num = total % 10;<br>            carry = total / 10;<br>            dummy-&gt;next = new ListNode(num);<br>            dummy = dummy-&gt;next;<br>        }<br><br>        ListNode* result = res-&gt;next;<br>        delete res;<br>        return result;         <br>    }<br>};</pre><h3>Step by step algorithm</h3><ol><li><strong>Initialization</strong>: Initialize a dummy node and a result pointer to the dummy node. Also, set total and carry variables to 0.</li></ol><pre>dummy = ListNode()<br>res = dummy<br>total = carry = 0</pre><ol><li><strong>Traversing Lists</strong>: Traverse through both linked lists (l1 and l2) until either of them or the carry has a value.</li></ol><pre>while l1 or l2 or carry:</pre><ol><li><strong>Calculating Sum</strong>: At each iteration, calculate the total sum of corresponding digits from l1, l2, and the carry.</li></ol><pre>total = carry<br>if l1:<br>    total += l1.val<br>    l1 = l1.next<br>if l2:<br>    total += l2.val<br>    l2 = l2.next</pre><ol><li><strong>Extracting Digit and Carry</strong>: Extract the digit by taking the modulo 10 of the total sum and update the carry for the next iteration by dividing the total sum by 10.</li></ol><pre>num = total % 10<br>carry = total // 10</pre><ol><li><strong>Creating New Node</strong>: Create a new ListNode with the extracted digit and attach it to the result linked list.</li></ol><pre>dummy.next = ListNode(num)<br>dummy = dummy.next</pre><ol><li><strong>Return Result</strong>: Finally, return the next node of the dummy node, which contains the head of the resultant linked list.</li></ol><pre>return res.next</pre><p>This algorithm effectively adds two numbers represented as linked lists, considering carryovers at each step.</p><h3>Complexity</h3><ul><li>Time complexity: O(n)<br>n is number of nodes in longer list l1 or l2.</li><li>Space complexity: O(n) or O(1)<br>If we count new list we create, that is O(n). If we don’t count, that is O(1)</li></ul><p>Thank you for reading my post. Please upvote it and don’t forget to subscribe to my channel!</p><p>⭐️ Subscribe URL<br><a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><h3>Next Question</h3><h3><a href="https://youtu.be/n4zCTMh03_M">⭐️ Longest Substring Without Repeating Characters video is available from here</a></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a227d68b5414" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[You Think Two Sum Is Easy? That’s Exactly the Problem.]]></title>
            <link>https://medium.com/@indy0214_19547/you-think-two-sum-is-easy-thats-exactly-the-problem-f6fdb030abb6?source=rss-826581f1758b------2</link>
            <guid isPermaLink="false">https://medium.com/p/f6fdb030abb6</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Ken]]></dc:creator>
            <pubDate>Sat, 02 May 2026 15:22:43 GMT</pubDate>
            <atom:updated>2026-05-02T15:22:43.809Z</atom:updated>
            <content:encoded><![CDATA[<h3><a href="https://youtu.be/WB2SZ3_QK28">⭐️ Two Sum video is available from here</a></h3><p>You Think Two Sum Is Easy? That’s Exactly the Problem.</p><p>Among the problems you encounter early on in LeetCode, Two Sum is probably one of the most well-known. At first glance, it looks extremely simple — so simple that many people are tempted to breeze past it. It’s common to think, “Is this even worth spending time on?” However, whether you take this problem seriously or not can significantly impact your growth as an engineer.</p><p>The real value of Two Sum is not in simply solving it, but in learning how to think. You might start with a straightforward approach, but what matters is how you refine it: identifying inefficiencies, reducing unnecessary work, and choosing better strategies. This process of iteration and improvement is a fundamental skill in algorithmic problem-solving, and once you develop it, you can apply it to a wide range of problems.</p><p>Two Sum is also deceptively dangerous because it’s easy to get “a correct answer” quickly. That often leads to a false sense of understanding. Many people can solve it, but far fewer can clearly explain <em>why</em> their solution is efficient, what alternatives exist, or how the time and space complexity differ between approaches. If you move on without fully understanding these aspects, you’re likely to get stuck when facing slightly more complex problems.</p><p>Another important point is that Two Sum is not an isolated problem. It serves as a foundation for many other problems you’ll encounter later. Variations involving more numbers, optimizations using data structures, and patterns that appear in array or subarray problems all build on the same core ideas. By deeply understanding Two Sum, you effectively lower the difficulty of many future problems.</p><p>From an interview perspective, Two Sum is frequently used — not because it’s hard, but because it clearly reveals your thought process. Interviewers are less interested in whether you can produce the answer and more focused on how you approach the problem. Can you identify better solutions? Do you consider time complexity? Can you articulate your reasoning? These are the qualities being evaluated.</p><p>Ultimately, Two Sum is a test of how deeply you can understand a simple problem. While solving difficult problems is important, your growth depends even more on how much insight you can extract from basic ones. Asking questions like “Are there alternative approaches?”, “Why is this optimal?”, and “How can this idea be applied elsewhere?” turns a simple exercise into a powerful learning opportunity.</p><p>If you’ve only “solved” Two Sum and moved on, it’s worth revisiting. The depth of your understanding here will directly influence your ability to tackle more advanced problems and strengthen your overall problem-solving skills.</p><h3><a href="https://youtu.be/WB2SZ3_QK28">⭐️ Two Sum video is available from here</a></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f6fdb030abb6" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Two Sum — LeetCode #1]]></title>
            <link>https://medium.com/@indy0214_19547/intuition-2ddcf50d881f?source=rss-826581f1758b------2</link>
            <guid isPermaLink="false">https://medium.com/p/2ddcf50d881f</guid>
            <category><![CDATA[two-sum]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Ken]]></dc:creator>
            <pubDate>Wed, 29 Apr 2026 14:37:26 GMT</pubDate>
            <atom:updated>2026-05-06T03:28:14.637Z</atom:updated>
            <content:encoded><![CDATA[<p>Use HashMap to keep numbers and their indices we found.</p><h3>Solution Video Link</h3><h3><a href="https://youtu.be/WB2SZ3_QK28">⭐️ Two Sum video is available from here</a></h3><p>Subscribers: 29,684<br>Thank you for your support!</p><h3>Approach</h3><p>If you check all possible pairs, we need two loops which is $$O(n²)$$.</p><pre>Input: nums = [2,7,11,15], target = 9</pre><p>All possible pairs are</p><pre>[2,2][2,7][2,11][2,15] = 4<br>[7,2][7,7][7,11][7,15] = 4<br>[11,2][11,7][11,11][11,15] = 4<br>[15,2][15,7][15,11][15,15] = 4</pre><pre>total 16 pairs</pre><p>And then, we need to find the right pair among them. They are including invalid pairs but at least we need to iterate input array 16 times which is 4^2. 4 is the length of input array.</p><p>Looping 16 times is not a big deal. But what if we have 100 or 1000 numbers as an input array. Do we loop 10000 or 1000000 times?</p><p>That’s why if we can improve the time complexity to $$O(n)$$, we will loop 100 or 1000 at most. It&#39;s much much much better right?</p><h3>How can we improve the time complexity?</h3><p>My answer is to use a memory to keep results of something my solution code has done.</p><p>⭐️ Points</p><p>Use a memory to keep data for something to improve time complexity.</p><p>In this case, HashMap is good data structure.</p><h3>What is data we should keep with HashMap?</h3><p>Let’s take a look at input array and target number.</p><pre>Input: nums = [2,7,11,15], target = 9</pre><p>In this case, if we subtract current number in input array from target number, we can get a number we need to create the target number.</p><p>For example,</p><pre>9 - 2 = 7</pre><p>7 is a number we need when current number is 2. So if we have 7 and index number of 7, we can create 9 with the current(= 2) number and 7.</p><p>From this example, what we should keep in HashMap is</p><p>⭐️ Points</p><p>Keep numbers(elements) as keys and index numbers as values in the input array.</p><p>Let’s iterate through one by one.</p><pre>Input: nums = [2,7,11,15], target = 9</pre><p>Let’s call the HashMap pair_idx.</p><pre>[2,7,11,15], target = 9<br>　　↑</pre><pre>pair_idx = {}</pre><p>We found 2. we need 7 to create 9, so check if we have 7 in pair_idx. But now pair_idx is empty, so just add current number and its index to pair_idx.</p><pre>pair_idx = {2: 0} </pre><pre>2 is current number<br>0 is index of 2</pre><p>Then move next.</p><pre>[2,7,11,15], target = 9<br>　　  ↑</pre><pre>pair_idx = {2: 0}</pre><p>We found 7, so we need 2. Check if we have 2 in pair_idx. And yes we have 2.</p><pre>return [0,1] or [1,0]</pre><p>The description says “You can return the answer in any order”.</p><p>We already found the answer but if we continue that</p><pre>pair_idx = {2: 0, 7: 1}<br>[2,7,11,15], target = 9<br>　　     ↑</pre><pre>We need 9 - 11 = -2 but no -2 in pair_idx, so<br>pair_idx = {2: 0, 7: 1, 11: 2}</pre><pre>pair_idx = {2: 0, 7: 1, 11: 2}<br>[2,7,11,15], target = 9<br>　　        ↑</pre><pre>We need 9 - 15 = -6 but no -6 in pair_idx, so<br>pair_idx = {2: 0, 7: 1, 11: 2, 15: 3}</pre><p>Easy!😄<br>Let’s see solution codes and step by step algorithm!</p><p>How I Studied LeetCode as a Beginner (That Actually Worked)</p><h3><a href="https://youtu.be/bU_dXCOWHls">⭐️ How to Use LeetCode Effectively video is available from here</a></h3><h3>Complexity</h3><ul><li>Time complexity: O(n)<br>n is number of elements in input array.</li><li>Space complexity: O(n)<br>n is number of elements in input array. In the worst case, we put all numbers in pair_idx.</li></ul><pre>class Solution:<br>    def twoSum(self, nums: List[int], target: int) -&gt; List[int]:<br>        pair_idx = {}<br><br>        for i, num in enumerate(nums):<br>            if target - num in pair_idx:<br>                return [i, pair_idx[target - num]]<br>            pair_idx[num] = i</pre><pre>var twoSum = function(nums, target) {<br>    const pairIdx = {};<br><br>    for (let i = 0; i &lt; nums.length; i++) {<br>        const num = nums[i];<br>        if (target - num in pairIdx) {<br>            return [i, pairIdx[target - num]];<br>        }<br>        pairIdx[num] = i;<br>    }    <br>};</pre><pre>class Solution {<br>    public int[] twoSum(int[] nums, int target) {<br>        Map&lt;Integer, Integer&gt; pairIdx = new HashMap&lt;&gt;();<br><br>        for (int i = 0; i &lt; nums.length; i++) {<br>            int num = nums[i];<br>            if (pairIdx.containsKey(target - num)) {<br>                return new int[] { i, pairIdx.get(target - num) };<br>            }<br>            pairIdx.put(num, i);<br>        }<br><br>        return new int[] {};        <br>    }<br>}</pre><pre>class Solution {<br>public:<br>    vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {<br>        unordered_map&lt;int, int&gt; pairIdx;<br><br>        for (int i = 0; i &lt; nums.size(); ++i) {<br>            int num = nums[i];<br>            if (pairIdx.find(target - num) != pairIdx.end()) {<br>                return {i, pairIdx[target - num]};<br>            }<br>            pairIdx[num] = i;<br>        }<br><br>        return {};        <br>    }<br>};</pre><p>In summary, this algorithm efficiently finds a pair of numbers in the nums list whose sum equals the target value. It does so by using a dictionary to store the indices of numbers encountered so far and checking for the existence of complementary numbers during the iteration.</p><p>Thank you for reading my post. Please upvote it and don’t forget to subscribe to my channel!</p><p>⭐️ Subscribe URL<br><a href="http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1">http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1</a></p><h3>Next Question</h3><h3><a href="https://youtu.be/DFDTaCGlzTY">⭐️ 2. Add Two Numbers is available from here</a></h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2ddcf50d881f" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>