<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom" xmlns:dc="http://purl.org/dc/elements/1.1/">
  <channel>
    <title>DEV Community: Aryan Subudhi</title>
    <description>The latest articles on DEV Community by Aryan Subudhi (@aryan_subudhi_01).</description>
    <link>https://dev.to/aryan_subudhi_01</link>
    <image>
      <url>https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F3949061%2Fcccd6479-33a2-4da7-be7e-f75607518d4d.png</url>
      <title>DEV Community: Aryan Subudhi</title>
      <link>https://dev.to/aryan_subudhi_01</link>
    </image>
    <atom:link rel="self" type="application/rss+xml" href="https://dev.to/feed/aryan_subudhi_01"/>
    <language>en</language>
    <item>
      <title>LeetCode Solution: 5. Longest Palindromic Substring</title>
      <dc:creator>Aryan Subudhi</dc:creator>
      <pubDate>Mon, 25 May 2026 17:54:40 +0000</pubDate>
      <link>https://dev.to/aryan_subudhi_01/leetcode-solution-5-longest-palindromic-substring-2jm4</link>
      <guid>https://dev.to/aryan_subudhi_01/leetcode-solution-5-longest-palindromic-substring-2jm4</guid>
      <description>&lt;h1&gt;
  
  
  5. Longest Palindromic Substring: Unraveling the Palindromic Puzzle 🧩
&lt;/h1&gt;

&lt;p&gt;Hey fellow coders! 👋 Today, we're diving into a LeetCode classic that often stumps beginners but reveals a really elegant pattern once you spot it: the Longest Palindromic Substring problem.&lt;/p&gt;

&lt;p&gt;Don't let the fancy name scare you! We'll break it down piece by piece, find an intuitive way to tackle it, and emerge victorious with a neat, efficient solution. Ready? Let's go!&lt;/p&gt;

&lt;h2&gt;
  
  
  📜 Problem Explanation
&lt;/h2&gt;

&lt;p&gt;The problem asks us to find the &lt;em&gt;longest palindromic substring&lt;/em&gt; within a given string &lt;code&gt;s&lt;/code&gt;.&lt;/p&gt;

&lt;p&gt;"Whoa, hold on!" you might say. "What's a palindrome? And what's a substring?" Great questions!&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;Palindrome&lt;/strong&gt;: A string that reads the same forwards and backward. Think words like "madam", "racecar", or even single letters like "a".&lt;/li&gt;
&lt;li&gt;  &lt;strong&gt;Substring&lt;/strong&gt;: A contiguous sequence of characters within a string. For "babad", "bab", "aba", "bad", "a" are all substrings. "bba" is &lt;em&gt;not&lt;/em&gt; a substring because the 'b's aren't contiguous in that order.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;So, our mission is to scan through the given string &lt;code&gt;s&lt;/code&gt;, find all possible substrings that are also palindromes, and then return the longest one among them.&lt;/p&gt;

&lt;p&gt;Let's look at the examples:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;Example 1: &lt;code&gt;s = "babad"&lt;/code&gt;&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;  Possible palindromic substrings: "b", "a", "b", "a", "d", "bab", "aba".&lt;/li&gt;
&lt;li&gt;  The longest ones are "bab" and "aba". Either is a valid answer.&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;  &lt;strong&gt;Example 2: &lt;code&gt;s = "cbbd"&lt;/code&gt;&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;  Possible palindromic substrings: "c", "b", "b", "d", "bb".&lt;/li&gt;
&lt;li&gt;  The longest is "bb".&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;p&gt;&lt;strong&gt;Constraints:&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  The string &lt;code&gt;s&lt;/code&gt; will have between 1 and 1000 characters.&lt;/li&gt;
&lt;li&gt;  It will only contain digits and English letters. No weird symbols to worry about!&lt;/li&gt;
&lt;/ul&gt;

&lt;h2&gt;
  
  
  🤔 Intuition: Don't Brute Force, Explore From the Middle!
&lt;/h2&gt;

&lt;p&gt;A common first thought for many string problems is: "Let's check every possible substring!"&lt;/p&gt;

&lt;p&gt;If you have a string of length &lt;code&gt;N&lt;/code&gt;:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt; There are &lt;code&gt;N * (N + 1) / 2&lt;/code&gt; possible substrings (e.g., for "abc", "a", "b", "c", "ab", "bc", "abc").&lt;/li&gt;
&lt;li&gt; For each substring, checking if it's a palindrome takes &lt;code&gt;O(length_of_substring)&lt;/code&gt; time.&lt;/li&gt;
&lt;li&gt; This quickly leads to an &lt;code&gt;O(N^3)&lt;/code&gt; solution, which for &lt;code&gt;N=1000&lt;/code&gt; is &lt;code&gt;1000^3 = 1,000,000,000&lt;/code&gt; operations – way too slow! 🐌&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;We need something smarter.&lt;/p&gt;

&lt;p&gt;What makes a palindrome special? It's symmetrical around its center!&lt;/p&gt;

&lt;p&gt;Consider "racecar":&lt;br&gt;
&lt;code&gt;r a c e c a r&lt;/code&gt;&lt;br&gt;
The &lt;code&gt;e&lt;/code&gt; is the center. Everything expands outwards equally.&lt;/p&gt;

&lt;p&gt;Consider "abba":&lt;br&gt;
&lt;code&gt;a b b a&lt;/code&gt;&lt;br&gt;
The "center" is &lt;em&gt;between&lt;/em&gt; the two &lt;code&gt;b&lt;/code&gt;s.&lt;/p&gt;

&lt;p&gt;This gives us a huge hint! Instead of picking two ends and checking inwards, what if we pick a &lt;em&gt;center&lt;/em&gt; and expand outwards?&lt;/p&gt;

&lt;p&gt;Every palindrome has a center:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;Odd-length palindromes&lt;/strong&gt;: A single character is the center (e.g., 'a' in "bab", 'e' in "racecar").&lt;/li&gt;
&lt;li&gt;  &lt;strong&gt;Even-length palindromes&lt;/strong&gt;: The "center" is the space between two identical characters (e.g., the space between the two 'b's in "bb", or "abba").&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;This means we can iterate through every possible "center" in our string and try to expand outwards to find the longest palindrome centered there. Since there are &lt;code&gt;N&lt;/code&gt; characters and &lt;code&gt;N-1&lt;/code&gt; spaces between characters, there are roughly &lt;code&gt;2N - 1&lt;/code&gt; potential centers.&lt;/p&gt;

&lt;h2&gt;
  
  
  🚀 Approach: Expand Around Center
&lt;/h2&gt;

&lt;p&gt;Our intuition leads us to a solid plan:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt; We'll maintain variables &lt;code&gt;start&lt;/code&gt; and &lt;code&gt;max_len&lt;/code&gt; to keep track of the beginning index and length of the longest palindrome we've found so far. Initialize &lt;code&gt;start = 0&lt;/code&gt; and &lt;code&gt;max_len = 1&lt;/code&gt; (a single character is always a palindrome).&lt;/li&gt;
&lt;li&gt; We'll iterate through each character in the string &lt;code&gt;s&lt;/code&gt; using an index &lt;code&gt;i&lt;/code&gt;. For each &lt;code&gt;i&lt;/code&gt;, we consider it as a potential center for a palindrome.&lt;/li&gt;
&lt;li&gt; Since palindromes can be odd or even length, we'll need to check &lt;em&gt;two&lt;/em&gt; types of expansions for each &lt;code&gt;i&lt;/code&gt;:

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;Odd length&lt;/strong&gt;: &lt;code&gt;i&lt;/code&gt; itself is the center. We'll try to expand outwards from &lt;code&gt;left = i&lt;/code&gt;, &lt;code&gt;right = i&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;  &lt;strong&gt;Even length&lt;/strong&gt;: The space &lt;em&gt;after&lt;/em&gt; &lt;code&gt;i&lt;/code&gt; is the center. We'll try to expand outwards from &lt;code&gt;left = i&lt;/code&gt;, &lt;code&gt;right = i + 1&lt;/code&gt;.&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;li&gt; To avoid repeating code, we'll create a helper function, let's call it &lt;code&gt;expandAroundCenter(s, left, right)&lt;/code&gt;. This function will take the string &lt;code&gt;s&lt;/code&gt; and two pointers, &lt;code&gt;left&lt;/code&gt; and &lt;code&gt;right&lt;/code&gt;, and expand them outwards as long as:

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;left&lt;/code&gt; is not less than 0 (we're within string bounds).&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;right&lt;/code&gt; is not greater than or equal to &lt;code&gt;len(s)&lt;/code&gt; (we're within string bounds).&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;s[left]&lt;/code&gt; is equal to &lt;code&gt;s[right]&lt;/code&gt; (the characters match, so it's still a palindrome).&lt;/li&gt;
&lt;li&gt;  Once these conditions are no longer met, the function returns the length of the palindrome found (which is &lt;code&gt;right - left - 1&lt;/code&gt;).&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;li&gt; In our main loop, after calling &lt;code&gt;expandAroundCenter&lt;/code&gt; for both odd and even cases, we'll compare the lengths of the palindromes found. If either is longer than our current &lt;code&gt;max_len&lt;/code&gt;, we update &lt;code&gt;max_len&lt;/code&gt; and calculate the new &lt;code&gt;start&lt;/code&gt; index. The &lt;code&gt;start&lt;/code&gt; index will be &lt;code&gt;i - (current_palindrome_length - 1) // 2&lt;/code&gt;. (This formula looks tricky, but it simply finds the leftmost character of the new longest palindrome given its length and its "center" &lt;code&gt;i&lt;/code&gt;).&lt;/li&gt;
&lt;li&gt; After checking all possible centers, we return the substring &lt;code&gt;s[start : start + max_len]&lt;/code&gt;.&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;Let's trace &lt;code&gt;s = "babad"&lt;/code&gt;:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  Initialize &lt;code&gt;start = 0&lt;/code&gt;, &lt;code&gt;max_len = 1&lt;/code&gt; (our initial "b")&lt;/li&gt;
&lt;li&gt;  &lt;strong&gt;i = 0 (char 'b')&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;expandAroundCenter(s, 0, 0)&lt;/code&gt; -&amp;gt; returns length 1 ("b")&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;expandAroundCenter(s, 0, 1)&lt;/code&gt; -&amp;gt; 'b' != 'a', returns length 0&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;  &lt;strong&gt;i = 1 (char 'a')&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;expandAroundCenter(s, 1, 1)&lt;/code&gt; -&amp;gt; returns length 1 ("a")&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;expandAroundCenter(s, 1, 2)&lt;/code&gt; -&amp;gt; 'a' == 'b' NO, returns length 0&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;expandAroundCenter(s, 0, 2)&lt;/code&gt; for center 'a': &lt;code&gt;s[0]&lt;/code&gt;=='b', &lt;code&gt;s[2]&lt;/code&gt;=='b'. &lt;code&gt;left&lt;/code&gt; becomes -1, &lt;code&gt;right&lt;/code&gt; becomes 3. Palindrome is "bab", length 3.

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;max_len&lt;/code&gt; = 3, &lt;code&gt;start&lt;/code&gt; = &lt;code&gt;1 - (3-1)//2&lt;/code&gt; = &lt;code&gt;1 - 1&lt;/code&gt; = 0. Current best: "bab".&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;/li&gt;

&lt;li&gt;  &lt;strong&gt;i = 2 (char 'b')&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;expandAroundCenter(s, 2, 2)&lt;/code&gt; -&amp;gt; returns length 1 ("b")&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;expandAroundCenter(s, 2, 3)&lt;/code&gt; -&amp;gt; 'b' != 'a', returns length 0&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;expandAroundCenter(s, 1, 3)&lt;/code&gt; for center 'b': &lt;code&gt;s[1]&lt;/code&gt;=='a', &lt;code&gt;s[3]&lt;/code&gt;=='a'. &lt;code&gt;left&lt;/code&gt; becomes 0, &lt;code&gt;right&lt;/code&gt; becomes 4. Palindrome is "aba", length 3.

&lt;ul&gt;
&lt;li&gt;  Length is 3, same as current &lt;code&gt;max_len&lt;/code&gt;. We don't need to update &lt;code&gt;start&lt;/code&gt; and &lt;code&gt;max_len&lt;/code&gt; if it's not strictly greater, but it's fine if we do (it would become "aba"). Let's say it updates to "aba".&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;/li&gt;

&lt;li&gt;  ... and so on.&lt;/li&gt;

&lt;/ul&gt;

&lt;p&gt;Finally, we return &lt;code&gt;s[start : start + max_len]&lt;/code&gt;.&lt;/p&gt;

&lt;h2&gt;
  
  
  💻 Code
&lt;/h2&gt;



&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight python"&gt;&lt;code&gt;&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Solution&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
    &lt;span class="k"&gt;def&lt;/span&gt; &lt;span class="nf"&gt;longestPalindrome&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;self&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nb"&gt;str&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;-&amp;gt;&lt;/span&gt; &lt;span class="nb"&gt;str&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
        &lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="ow"&gt;not&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
            &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="sh"&gt;""&lt;/span&gt;

        &lt;span class="c1"&gt;# Helper function to expand around a center
&lt;/span&gt;        &lt;span class="c1"&gt;# It takes the string s, and the left and right pointers
&lt;/span&gt;        &lt;span class="c1"&gt;# It expands outwards as long as characters match and stay within bounds
&lt;/span&gt;        &lt;span class="c1"&gt;# Returns the length of the palindrome found
&lt;/span&gt;        &lt;span class="k"&gt;def&lt;/span&gt; &lt;span class="nf"&gt;expandAroundCenter&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;left&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nb"&gt;int&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;right&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nb"&gt;int&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;-&amp;gt;&lt;/span&gt; &lt;span class="nb"&gt;int&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
            &lt;span class="k"&gt;while&lt;/span&gt; &lt;span class="n"&gt;left&lt;/span&gt; &lt;span class="o"&gt;&amp;gt;=&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt; &lt;span class="ow"&gt;and&lt;/span&gt; &lt;span class="n"&gt;right&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;&lt;/span&gt; &lt;span class="nf"&gt;len&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="ow"&gt;and&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;left&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;right&lt;/span&gt;&lt;span class="p"&gt;]:&lt;/span&gt;
                &lt;span class="n"&gt;left&lt;/span&gt; &lt;span class="o"&gt;-=&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;
                &lt;span class="n"&gt;right&lt;/span&gt; &lt;span class="o"&gt;+=&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;
            &lt;span class="c1"&gt;# After the loop, left and right are one step *past* the palindrome
&lt;/span&gt;            &lt;span class="c1"&gt;# So, the length is (right - 1) - (left + 1) + 1 = right - left - 1
&lt;/span&gt;            &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="n"&gt;right&lt;/span&gt; &lt;span class="o"&gt;-&lt;/span&gt; &lt;span class="n"&gt;left&lt;/span&gt; &lt;span class="o"&gt;-&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;

        &lt;span class="n"&gt;start_index&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;  &lt;span class="c1"&gt;# Stores the starting index of the longest palindrome
&lt;/span&gt;        &lt;span class="n"&gt;max_length&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;   &lt;span class="c1"&gt;# Stores the maximum length found so far
&lt;/span&gt;
        &lt;span class="c1"&gt;# Loop through each character to consider it as a center
&lt;/span&gt;        &lt;span class="k"&gt;for&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="ow"&gt;in&lt;/span&gt; &lt;span class="nf"&gt;range&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nf"&gt;len&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;)):&lt;/span&gt;
            &lt;span class="c1"&gt;# Case 1: Odd length palindrome (e.g., "aba", "racecar")
&lt;/span&gt;            &lt;span class="c1"&gt;# The current character s[i] is the center
&lt;/span&gt;            &lt;span class="n"&gt;len1&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="nf"&gt;expandAroundCenter&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;i&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;

            &lt;span class="c1"&gt;# Case 2: Even length palindrome (e.g., "abba", "bb")
&lt;/span&gt;            &lt;span class="c1"&gt;# The center is between s[i] and s[i+1]
&lt;/span&gt;            &lt;span class="n"&gt;len2&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="nf"&gt;expandAroundCenter&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;i&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;

            &lt;span class="c1"&gt;# Get the maximum length found from these two expansions
&lt;/span&gt;            &lt;span class="n"&gt;current_max_len&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="nf"&gt;max&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;len1&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;len2&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;

            &lt;span class="c1"&gt;# If this palindrome is longer than our current max_length
&lt;/span&gt;            &lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="n"&gt;current_max_len&lt;/span&gt; &lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;max_length&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
                &lt;span class="n"&gt;max_length&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;current_max_len&lt;/span&gt;
                &lt;span class="c1"&gt;# Calculate the new starting index for this longest palindrome
&lt;/span&gt;                &lt;span class="c1"&gt;# For an odd length palindrome, start = i - (length - 1) / 2
&lt;/span&gt;                &lt;span class="c1"&gt;# For an even length palindrome, start = i - (length / 2 - 1)
&lt;/span&gt;                &lt;span class="c1"&gt;# Both can be generalized as: i - (length - 1) // 2
&lt;/span&gt;                &lt;span class="n"&gt;start_index&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;-&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;max_length&lt;/span&gt; &lt;span class="o"&gt;-&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;//&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;

        &lt;span class="c1"&gt;# Return the substring from start_index with max_length
&lt;/span&gt;        &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;start_index&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="n"&gt;start_index&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="n"&gt;max_length&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt;

&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;h2&gt;
  
  
  ⏱️ Time &amp;amp; Space Complexity Analysis
&lt;/h2&gt;

&lt;p&gt;Let's break down how efficient our solution is:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;p&gt;&lt;strong&gt;Time Complexity: &lt;code&gt;O(N^2)&lt;/code&gt;&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  The main &lt;code&gt;for&lt;/code&gt; loop iterates &lt;code&gt;N&lt;/code&gt; times (once for each character in &lt;code&gt;s&lt;/code&gt;).&lt;/li&gt;
&lt;li&gt;  Inside the loop, we call &lt;code&gt;expandAroundCenter&lt;/code&gt; twice.&lt;/li&gt;
&lt;li&gt;  The &lt;code&gt;expandAroundCenter&lt;/code&gt; function, in the worst case (e.g., &lt;code&gt;s = "aaaaa"&lt;/code&gt;), might expand all the way to the boundaries of the string. This takes &lt;code&gt;O(N)&lt;/code&gt; time.&lt;/li&gt;
&lt;li&gt;  Therefore, the total time complexity is &lt;code&gt;N * O(N) = O(N^2)&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;  Given &lt;code&gt;N &amp;lt;= 1000&lt;/code&gt;, &lt;code&gt;N^2&lt;/code&gt; is &lt;code&gt;1,000,000&lt;/code&gt;, which is perfectly acceptable within typical time limits (usually around &lt;code&gt;10^8&lt;/code&gt; operations per second).&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;

&lt;p&gt;&lt;strong&gt;Space Complexity: &lt;code&gt;O(1)&lt;/code&gt;&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  We are only using a few constant variables (&lt;code&gt;start_index&lt;/code&gt;, &lt;code&gt;max_length&lt;/code&gt;, &lt;code&gt;i&lt;/code&gt;, &lt;code&gt;len1&lt;/code&gt;, &lt;code&gt;len2&lt;/code&gt;, &lt;code&gt;left&lt;/code&gt;, &lt;code&gt;right&lt;/code&gt;). We are not storing any data structures that grow with the input size &lt;code&gt;N&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;  The slicing &lt;code&gt;s[start_index : start_index + max_length]&lt;/code&gt; creates a new string, but this is part of the output, not auxiliary space used by the algorithm itself.&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;h2&gt;
  
  
  🌟 Key Takeaways
&lt;/h2&gt;

&lt;ol&gt;
&lt;li&gt; &lt;strong&gt;Don't Jump to Brute Force&lt;/strong&gt;: Always consider the constraints and think about whether a naive &lt;code&gt;O(N^3)&lt;/code&gt; or &lt;code&gt;O(N^2)&lt;/code&gt; approach will pass. Often, there's a more elegant pattern waiting to be discovered!&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;Palindromes and Symmetry&lt;/strong&gt;: The core idea for many palindrome problems revolves around their symmetrical nature. Thinking about "centers" is a powerful paradigm.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;Odd vs. Even Length&lt;/strong&gt;: Remember that palindromes can have either odd or even lengths, and your solution needs to account for both types of "centers."&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;Helper Functions&lt;/strong&gt;: Breaking down complex logic into smaller, reusable helper functions (like &lt;code&gt;expandAroundCenter&lt;/code&gt;) makes your code cleaner, more readable, and easier to debug.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;Smallest Palindrome is 1&lt;/strong&gt;: Don't forget that a single character is always a palindrome, which can be useful for initializing &lt;code&gt;max_length&lt;/code&gt;.&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;This problem is a fantastic introduction to dynamic programming and string algorithms, and mastering the "expand around center" technique will serve you well in many other coding challenges!&lt;/p&gt;

&lt;p&gt;Happy coding! ✨&lt;/p&gt;




&lt;h3&gt;
  
  
  Submission Details
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;Author Account&lt;/strong&gt;: aryan-subudhi&lt;/li&gt;
&lt;li&gt;  &lt;strong&gt;Publishing Time&lt;/strong&gt;: 2026-05-25 23:24:13&lt;/li&gt;
&lt;/ul&gt;

</description>
      <category>leetcode</category>
      <category>dsa</category>
      <category>programming</category>
      <category>tutorial</category>
    </item>
    <item>
      <title>LeetCode Solution: 1. Two Sum</title>
      <dc:creator>Aryan Subudhi</dc:creator>
      <pubDate>Mon, 25 May 2026 17:42:02 +0000</pubDate>
      <link>https://dev.to/aryan_subudhi_01/leetcode-solution-1-two-sum-1749</link>
      <guid>https://dev.to/aryan_subudhi_01/leetcode-solution-1-two-sum-1749</guid>
      <description>&lt;h1&gt;
  
  
  Cracking LeetCode 1: Two Sum - Your First Step into Algorithm Mastery!
&lt;/h1&gt;

&lt;p&gt;Hey everyone! 👋 aryan-subudhi here, ready to dive into what's often the very first problem many of us encounter on our LeetCode journey: &lt;strong&gt;Two Sum&lt;/strong&gt;. Don't let its "easy" tag fool you; this problem is a fantastic introduction to fundamental algorithmic thinking, data structures, and the crucial concept of time complexity. If you're just starting out, you're in for a treat!&lt;/p&gt;




&lt;h2&gt;
  
  
  2. Problem Explanation: The Mission, Should You Choose To Accept It!
&lt;/h2&gt;

&lt;p&gt;Imagine you're given a list of numbers, let's call it &lt;code&gt;nums&lt;/code&gt;, and a specific target number, &lt;code&gt;target&lt;/code&gt;. Your mission, should you choose to accept it, is to find &lt;em&gt;two different numbers&lt;/em&gt; within that &lt;code&gt;nums&lt;/code&gt; list that add up precisely to &lt;code&gt;target&lt;/code&gt;. Once you find them, you don't return the numbers themselves, but their &lt;em&gt;positions&lt;/em&gt; (indices) in the original list.&lt;/p&gt;

&lt;p&gt;&lt;strong&gt;Here's the lowdown:&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;Input&lt;/strong&gt;:

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;nums&lt;/code&gt;: An array (or list in Python) of integers.&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;target&lt;/code&gt;: A single integer.&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;  &lt;strong&gt;Output&lt;/strong&gt;:

&lt;ul&gt;
&lt;li&gt;  A list (or array) of two integers, representing the &lt;em&gt;indices&lt;/em&gt; of the two numbers that sum up to &lt;code&gt;target&lt;/code&gt;.&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;  &lt;strong&gt;Key Guarantees/Constraints&lt;/strong&gt;:

&lt;ul&gt;
&lt;li&gt;  There will always be &lt;em&gt;exactly one&lt;/em&gt; valid solution. No need to worry about multiple pairs or no pairs at all!&lt;/li&gt;
&lt;li&gt;  You can't use the same number twice (i.e., you need two distinct elements from the array).&lt;/li&gt;
&lt;li&gt;  The answer can be returned in any order (e.g., &lt;code&gt;[0, 1]&lt;/code&gt; or &lt;code&gt;[1, 0]&lt;/code&gt; are both fine).&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;p&gt;Let's look at an example to make it crystal clear:&lt;/p&gt;

&lt;p&gt;&lt;strong&gt;Example 1:&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;nums = [2, 7, 11, 15]&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;target = 9&lt;/code&gt;
&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;We need to find two numbers in &lt;code&gt;[2, 7, 11, 15]&lt;/code&gt; that sum to 9.&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;2 + 7 = 9&lt;/code&gt; Bingo!&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;2&lt;/code&gt; is at index &lt;code&gt;0&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;7&lt;/code&gt; is at index &lt;code&gt;1&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;  So, the output is &lt;code&gt;[0, 1]&lt;/code&gt;. Simple, right?&lt;/li&gt;
&lt;/ul&gt;




&lt;h2&gt;
  
  
  3. Intuition: Thinking Through the Problem (From Simple to Smart!)
&lt;/h2&gt;

&lt;p&gt;Okay, so we need to find two numbers. How would a human do it? You'd probably start picking numbers and seeing if their partners exist.&lt;/p&gt;

&lt;p&gt;&lt;strong&gt;The "Brute Force" Idea (Our First Thought):&lt;/strong&gt;&lt;/p&gt;

&lt;p&gt;Let's try every possible pair!&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt; Pick the first number (e.g., &lt;code&gt;2&lt;/code&gt;).&lt;/li&gt;
&lt;li&gt; Then, go through &lt;em&gt;all the other numbers&lt;/em&gt; to see if any of them, when added to &lt;code&gt;2&lt;/code&gt;, equal &lt;code&gt;target&lt;/code&gt; (which is &lt;code&gt;9&lt;/code&gt;).

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;2 + 7 = 9&lt;/code&gt; (Found it!)&lt;/li&gt;
&lt;li&gt;  If not, you'd continue: &lt;code&gt;2 + 11 = 13&lt;/code&gt; (No), &lt;code&gt;2 + 15 = 17&lt;/code&gt; (No).&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;li&gt; If you didn't find it with &lt;code&gt;2&lt;/code&gt;, you'd move to the next number, &lt;code&gt;7&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt; Then, you'd go through &lt;em&gt;all the numbers after &lt;code&gt;7&lt;/code&gt;&lt;/em&gt; (because &lt;code&gt;7 + 2&lt;/code&gt; is the same as &lt;code&gt;2 + 7&lt;/code&gt;, and we don't want to recheck or use the same element twice).

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;7 + 11 = 18&lt;/code&gt; (No)&lt;/li&gt;
&lt;li&gt;  &lt;code&gt;7 + 15 = 22&lt;/code&gt; (No)&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;li&gt; And so on...&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;This approach definitely works! You're guaranteed to find the pair because you check &lt;em&gt;every single combination&lt;/em&gt;.&lt;/p&gt;

&lt;p&gt;&lt;strong&gt;The Catch:&lt;/strong&gt; While correct, this isn't very efficient for large lists. If &lt;code&gt;nums&lt;/code&gt; has &lt;code&gt;N&lt;/code&gt; numbers, you're essentially doing &lt;code&gt;N&lt;/code&gt; checks for the first number, &lt;code&gt;N-1&lt;/code&gt; for the second, and so on. This looks like &lt;code&gt;N * N&lt;/code&gt; operations in the worst case, which we call &lt;strong&gt;O(N^2)&lt;/strong&gt; complexity. For &lt;code&gt;N = 10,000&lt;/code&gt;, &lt;code&gt;N^2&lt;/code&gt; is &lt;code&gt;100,000,000&lt;/code&gt; — that's a lot of operations! Our follow-up question specifically asks for something better than O(N^2).&lt;/p&gt;

&lt;p&gt;&lt;strong&gt;Towards a Smarter Idea:&lt;/strong&gt;&lt;/p&gt;

&lt;p&gt;Can we be faster? When we pick a number, say &lt;code&gt;num&lt;/code&gt;, we know what its "partner" or "complement" &lt;em&gt;should&lt;/em&gt; be to reach the &lt;code&gt;target&lt;/code&gt;.&lt;br&gt;
&lt;code&gt;complement = target - num&lt;/code&gt;&lt;/p&gt;

&lt;p&gt;Instead of searching through the &lt;em&gt;rest of the list&lt;/em&gt; for this &lt;code&gt;complement&lt;/code&gt; (which takes time), what if we could &lt;em&gt;instantly know&lt;/em&gt; if we've seen this &lt;code&gt;complement&lt;/code&gt; before? This is where a &lt;strong&gt;hash map&lt;/strong&gt; (or dictionary in Python) shines!&lt;/p&gt;




&lt;h2&gt;
  
  
  4. Approach: The Hash Map Magic! ✨
&lt;/h2&gt;

&lt;p&gt;The optimized approach uses a hash map (often called a dictionary in Python) to store numbers we've seen so far, along with their indices. This allows for &lt;em&gt;very fast&lt;/em&gt; lookups.&lt;/p&gt;

&lt;p&gt;Here's the game plan:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt; &lt;strong&gt;Initialize an empty hash map (dictionary)&lt;/strong&gt;: Let's call it &lt;code&gt;seen&lt;/code&gt;. This &lt;code&gt;seen&lt;/code&gt; map will store &lt;code&gt;(number: index)&lt;/code&gt; pairs.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;Iterate through the &lt;code&gt;nums&lt;/code&gt; array&lt;/strong&gt;: For each &lt;code&gt;num&lt;/code&gt; and its &lt;code&gt;index&lt;/code&gt; (let's call it &lt;code&gt;i&lt;/code&gt;):
a.  &lt;strong&gt;Calculate the &lt;code&gt;complement&lt;/code&gt;&lt;/strong&gt;: &lt;code&gt;complement = target - num&lt;/code&gt;. This is the number we &lt;em&gt;need&lt;/em&gt; to find to hit our &lt;code&gt;target&lt;/code&gt;.
b.  &lt;strong&gt;Check if &lt;code&gt;complement&lt;/code&gt; is in &lt;code&gt;seen&lt;/code&gt;&lt;/strong&gt;:
    *   If &lt;code&gt;complement&lt;/code&gt; &lt;em&gt;is&lt;/em&gt; in &lt;code&gt;seen&lt;/code&gt;, it means we've previously encountered the number that, when added to our current &lt;code&gt;num&lt;/code&gt;, gives us &lt;code&gt;target&lt;/code&gt;. We've found our pair!
    *   The index of the &lt;code&gt;complement&lt;/code&gt; is &lt;code&gt;seen[complement]&lt;/code&gt;, and the index of our current &lt;code&gt;num&lt;/code&gt; is &lt;code&gt;i&lt;/code&gt;. We return &lt;code&gt;[seen[complement], i]&lt;/code&gt;.
c.  &lt;strong&gt;If &lt;code&gt;complement&lt;/code&gt; is NOT in &lt;code&gt;seen&lt;/code&gt;&lt;/strong&gt;: This means our current &lt;code&gt;num&lt;/code&gt; doesn't complete a pair with any number we've seen &lt;em&gt;so far&lt;/em&gt;. So, we add our current &lt;code&gt;num&lt;/code&gt; and its &lt;code&gt;index&lt;/code&gt; (&lt;code&gt;i&lt;/code&gt;) to our &lt;code&gt;seen&lt;/code&gt; map: &lt;code&gt;seen[num] = i&lt;/code&gt;. This way, if a future number needs &lt;em&gt;this&lt;/em&gt; &lt;code&gt;num&lt;/code&gt; as its complement, it will find it quickly.&lt;/li&gt;
&lt;li&gt; Since the problem guarantees exactly one solution, we know our loop will always find a pair and return.&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;Let's trace &lt;code&gt;nums = [2, 7, 11, 15]&lt;/code&gt;, &lt;code&gt;target = 9&lt;/code&gt; with this approach:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;&lt;code&gt;seen = {}&lt;/code&gt;&lt;/strong&gt; (empty dictionary)&lt;/li&gt;
&lt;/ul&gt;

&lt;ol&gt;
&lt;li&gt;
&lt;p&gt;&lt;strong&gt;&lt;code&gt;i = 0&lt;/code&gt;, &lt;code&gt;num = 2&lt;/code&gt;&lt;/strong&gt;:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;complement = target - num = 9 - 2 = 7&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;  Is &lt;code&gt;7&lt;/code&gt; in &lt;code&gt;seen&lt;/code&gt;? No, &lt;code&gt;seen&lt;/code&gt; is empty.&lt;/li&gt;
&lt;li&gt;  Add &lt;code&gt;num&lt;/code&gt; to &lt;code&gt;seen&lt;/code&gt;: &lt;code&gt;seen = {2: 0}&lt;/code&gt;.&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;p&gt;&lt;strong&gt;&lt;code&gt;i = 1&lt;/code&gt;, &lt;code&gt;num = 7&lt;/code&gt;&lt;/strong&gt;:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;code&gt;complement = target - num = 9 - 7 = 2&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;  Is &lt;code&gt;2&lt;/code&gt; in &lt;code&gt;seen&lt;/code&gt;? YES! &lt;code&gt;seen[2]&lt;/code&gt; is &lt;code&gt;0&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;  We found our pair! The indices are &lt;code&gt;seen[2]&lt;/code&gt; (which is &lt;code&gt;0&lt;/code&gt;) and our current &lt;code&gt;i&lt;/code&gt; (which is &lt;code&gt;1&lt;/code&gt;).&lt;/li&gt;
&lt;li&gt;  &lt;strong&gt;Return &lt;code&gt;[0, 1]&lt;/code&gt;&lt;/strong&gt;.&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;And we're done! Notice how much faster that was than checking every single pair. We only made one pass through the list.&lt;/p&gt;




&lt;h2&gt;
  
  
  5. Code: The Solution in Action
&lt;/h2&gt;



&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight python"&gt;&lt;code&gt;&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Solution&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
    &lt;span class="k"&gt;def&lt;/span&gt; &lt;span class="nf"&gt;twoSum&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;self&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;nums&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;target&lt;/span&gt;&lt;span class="p"&gt;):&lt;/span&gt;
        &lt;span class="c1"&gt;# Initialize an empty hash map (dictionary in Python)
&lt;/span&gt;        &lt;span class="c1"&gt;# to store numbers we've seen and their indices.
&lt;/span&gt;        &lt;span class="n"&gt;seen&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="p"&gt;{}&lt;/span&gt; 

        &lt;span class="c1"&gt;# Iterate through the array `nums` with both index `i` and value `num`.
&lt;/span&gt;        &lt;span class="k"&gt;for&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;num&lt;/span&gt; &lt;span class="ow"&gt;in&lt;/span&gt; &lt;span class="nf"&gt;enumerate&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;nums&lt;/span&gt;&lt;span class="p"&gt;):&lt;/span&gt;
            &lt;span class="c1"&gt;# Calculate the complement needed to reach the target.
&lt;/span&gt;            &lt;span class="n"&gt;complement&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;target&lt;/span&gt; &lt;span class="o"&gt;-&lt;/span&gt; &lt;span class="n"&gt;num&lt;/span&gt;

            &lt;span class="c1"&gt;# Check if this complement already exists in our `seen` map.
&lt;/span&gt;            &lt;span class="c1"&gt;# If it does, we've found our pair!
&lt;/span&gt;            &lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="n"&gt;complement&lt;/span&gt; &lt;span class="ow"&gt;in&lt;/span&gt; &lt;span class="n"&gt;seen&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
                &lt;span class="c1"&gt;# Return the index of the complement (from `seen`) and the current index `i`.
&lt;/span&gt;                &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;seen&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;complement&lt;/span&gt;&lt;span class="p"&gt;],&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt;

            &lt;span class="c1"&gt;# If the complement wasn't found, store the current number and its index
&lt;/span&gt;            &lt;span class="c1"&gt;# in the `seen` map for future lookups.
&lt;/span&gt;            &lt;span class="n"&gt;seen&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;num&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt;

&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;






&lt;h2&gt;
  
  
  6. Time &amp;amp; Space Complexity Analysis: Getting Technical!
&lt;/h2&gt;

&lt;p&gt;Understanding how efficient your code is, is crucial for competitive programming and real-world applications.&lt;/p&gt;

&lt;h3&gt;
  
  
  &lt;strong&gt;Brute Force (Nested Loops) Approach:&lt;/strong&gt;
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;Time Complexity: O(N^2)&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;  We have two nested loops. The outer loop runs &lt;code&gt;N&lt;/code&gt; times (for each number). The inner loop runs up to &lt;code&gt;N&lt;/code&gt; times for each iteration of the outer loop. This results in approximately &lt;code&gt;N * N&lt;/code&gt; operations.&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;  &lt;strong&gt;Space Complexity: O(1)&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;  We don't use any additional data structures that grow with the input size, just a few variables.&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;h3&gt;
  
  
  &lt;strong&gt;Hash Map (Dictionary) Approach:&lt;/strong&gt;
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;Time Complexity: O(N)&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;  We iterate through the &lt;code&gt;nums&lt;/code&gt; array exactly once.&lt;/li&gt;
&lt;li&gt;  Inside the loop, calculating the &lt;code&gt;complement&lt;/code&gt; is O(1).&lt;/li&gt;
&lt;li&gt;  Checking if a key (&lt;code&gt;complement&lt;/code&gt;) exists in a hash map (dictionary) is, on average, O(1).&lt;/li&gt;
&lt;li&gt;  Adding a key-value pair (&lt;code&gt;num: i&lt;/code&gt;) to a hash map is, on average, O(1).&lt;/li&gt;
&lt;li&gt;  Since all operations inside the loop are constant time on average, the total time complexity is proportional to the number of elements &lt;code&gt;N&lt;/code&gt;, making it O(N). This is significantly better than O(N^2) for large inputs!&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;  &lt;strong&gt;Space Complexity: O(N)&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;  In the worst case, we might need to store all &lt;code&gt;N&lt;/code&gt; numbers and their indices in our &lt;code&gt;seen&lt;/code&gt; hash map before finding the pair (e.g., if the pair is the last two elements).&lt;/li&gt;
&lt;li&gt;  Therefore, the space used grows linearly with the input size &lt;code&gt;N&lt;/code&gt;.&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;p&gt;The hash map approach effectively &lt;strong&gt;trades space complexity (O(N)) for significantly improved time complexity (O(N))&lt;/strong&gt;. This is a very common and powerful optimization technique in algorithms!&lt;/p&gt;




&lt;h2&gt;
  
  
  7. Key Takeaways: What We Learned!
&lt;/h2&gt;

&lt;ol&gt;
&lt;li&gt; &lt;strong&gt;Don't Settle for Brute Force (Always!):&lt;/strong&gt; While often the easiest to think of, the most straightforward approach isn't always the most efficient. Always consider if there's a faster way.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;The Power of Hash Maps:&lt;/strong&gt; Hash maps (dictionaries) are your best friends for problems requiring fast lookups. They allow you to check for the existence of an element in (average) constant time, O(1), making algorithms much faster.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;The Complement Strategy:&lt;/strong&gt; Many "find a pair" problems can be simplified by thinking about what &lt;code&gt;complement&lt;/code&gt; you need for a given &lt;code&gt;num&lt;/code&gt; to reach the &lt;code&gt;target&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;Time-Space Trade-off:&lt;/strong&gt; Often, you can improve the time complexity of an algorithm by using extra space (like our hash map). This is a fundamental concept in algorithm design.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;Understanding &lt;code&gt;enumerate&lt;/code&gt;:&lt;/strong&gt; In Python, &lt;code&gt;enumerate(nums)&lt;/code&gt; is a neat way to get both the index (&lt;code&gt;i&lt;/code&gt;) and the value (&lt;code&gt;num&lt;/code&gt;) when iterating through a list.&lt;/li&gt;
&lt;/ol&gt;




&lt;h2&gt;
  
  
  8. Submission Details
&lt;/h2&gt;

&lt;p&gt;&lt;strong&gt;Author Account&lt;/strong&gt;: aryan-subudhi&lt;br&gt;
&lt;strong&gt;Publishing Time&lt;/strong&gt;: 2026-05-25 23:11:39&lt;br&gt;
&lt;strong&gt;Title&lt;/strong&gt;: 1. Two Sum&lt;/p&gt;




&lt;p&gt;That's it for Two Sum! I hope this deep dive was helpful and clarified why this seemingly simple problem is so foundational. Keep practicing, and happy coding! 🚀&lt;/p&gt;

</description>
      <category>leetcode</category>
      <category>dsa</category>
      <category>programming</category>
      <category>tutorial</category>
    </item>
    <item>
      <title>LeetCode Solution: 6. Zigzag Conversion</title>
      <dc:creator>Aryan Subudhi</dc:creator>
      <pubDate>Sun, 24 May 2026 13:03:49 +0000</pubDate>
      <link>https://dev.to/aryan_subudhi_01/leetcode-solution-6-zigzag-conversion-eln</link>
      <guid>https://dev.to/aryan_subudhi_01/leetcode-solution-6-zigzag-conversion-eln</guid>
      <description>&lt;h1&gt;
  
  
  Unraveling the Zigzag: A Beginner's Guide to LeetCode 6 (Zigzag Conversion)
&lt;/h1&gt;

&lt;p&gt;Hey LeetCoders and aspiring competitive programmers! aryan-subudhi here, ready to dive into another fascinating problem that looks tricky on the surface but unlocks a cool pattern-recognition skill. Today, we're tackling &lt;strong&gt;LeetCode Problem 6: Zigzag Conversion&lt;/strong&gt;. Get ready to bend your string into some interesting shapes!&lt;/p&gt;

&lt;h2&gt;
  
  
  Problem Explanation
&lt;/h2&gt;

&lt;p&gt;Imagine you're writing a message, but instead of straight lines, you write it in a zigzag pattern across a given number of rows. Once you've written it, you then read the message line by line, from left to right. Your task is to implement a function &lt;code&gt;convert&lt;/code&gt; that takes a string &lt;code&gt;s&lt;/code&gt; and an integer &lt;code&gt;numRows&lt;/code&gt; and returns the converted string.&lt;/p&gt;

&lt;p&gt;Let's look at an example. If our input string is &lt;code&gt;s = "PAYPALISHIRING"&lt;/code&gt; and &lt;code&gt;numRows = 3&lt;/code&gt;:&lt;/p&gt;

&lt;p&gt;We write it like this:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;P   A   H   N
A P L S I I G
Y   I   R
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Notice how &lt;code&gt;P&lt;/code&gt; is in row 0, &lt;code&gt;A&lt;/code&gt; in row 1, &lt;code&gt;Y&lt;/code&gt; in row 2, then we go back up with &lt;code&gt;P&lt;/code&gt; in row 1, &lt;code&gt;A&lt;/code&gt; in row 0, and so on. It forms a 'N' or 'Z' shape.&lt;/p&gt;

&lt;p&gt;Once written, we read it line by line:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;Row 0: &lt;code&gt;P&lt;/code&gt;, &lt;code&gt;A&lt;/code&gt;, &lt;code&gt;H&lt;/code&gt;, &lt;code&gt;N&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;Row 1: &lt;code&gt;A&lt;/code&gt;, &lt;code&gt;P&lt;/code&gt;, &lt;code&gt;L&lt;/code&gt;, &lt;code&gt;S&lt;/code&gt;, &lt;code&gt;I&lt;/code&gt;, &lt;code&gt;I&lt;/code&gt;, &lt;code&gt;G&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;Row 2: &lt;code&gt;Y&lt;/code&gt;, &lt;code&gt;I&lt;/code&gt;, &lt;code&gt;R&lt;/code&gt;
&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Concatenating these gives us: &lt;code&gt;"PAHNAPLSIIGYIR"&lt;/code&gt;. This is our expected output!&lt;/p&gt;

&lt;p&gt;Another example: &lt;code&gt;s = "PAYPALISHIRING"&lt;/code&gt;, &lt;code&gt;numRows = 4&lt;/code&gt;&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;P     I    N
A   L S  I G
Y A   H R
P     I
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Reading line by line:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;Row 0: &lt;code&gt;P&lt;/code&gt;, &lt;code&gt;I&lt;/code&gt;, &lt;code&gt;N&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;Row 1: &lt;code&gt;A&lt;/code&gt;, &lt;code&gt;L&lt;/code&gt;, &lt;code&gt;S&lt;/code&gt;, &lt;code&gt;I&lt;/code&gt;, &lt;code&gt;G&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;Row 2: &lt;code&gt;Y&lt;/code&gt;, &lt;code&gt;A&lt;/code&gt;, &lt;code&gt;H&lt;/code&gt;, &lt;code&gt;R&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;Row 3: &lt;code&gt;P&lt;/code&gt;, &lt;code&gt;I&lt;/code&gt;
&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Concatenating: &lt;code&gt;"PINALSIGYAHRPI"&lt;/code&gt;.&lt;/p&gt;

&lt;p&gt;&lt;strong&gt;Constraints:&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;The string length &lt;code&gt;s&lt;/code&gt; can be up to 1000 characters.&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;s&lt;/code&gt; consists of English letters (upper/lower-case), ',', and '.'.&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;numRows&lt;/code&gt; can be between 1 and 1000.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;An important edge case: if &lt;code&gt;numRows = 1&lt;/code&gt;, the zigzag pattern doesn't really form. The string remains unchanged. &lt;code&gt;convert("A", 1)&lt;/code&gt; should return &lt;code&gt;"A"&lt;/code&gt;.&lt;/p&gt;

&lt;h2&gt;
  
  
  Intuition
&lt;/h2&gt;

&lt;p&gt;At its core, this problem is about simulating the pattern. If we were doing this manually, we'd pick a character from the input string, place it in the correct row, then decide where the &lt;em&gt;next&lt;/em&gt; character goes. This suggests we need a way to keep track of:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt;Which row we're currently placing characters into.&lt;/li&gt;
&lt;li&gt;The direction we're moving (downwards or upwards).&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;The pattern repeats in cycles: go down from &lt;code&gt;row 0&lt;/code&gt; to &lt;code&gt;numRows - 1&lt;/code&gt;, then go up from &lt;code&gt;numRows - 2&lt;/code&gt; to &lt;code&gt;row 1&lt;/code&gt;, and then repeat. Notice that &lt;code&gt;row 0&lt;/code&gt; and &lt;code&gt;numRows - 1&lt;/code&gt; are only hit when going "down." The "up" phase skips these two rows to avoid double-counting or overshooting the pattern.&lt;/p&gt;

&lt;h2&gt;
  
  
  Approach: Simulating the Zigzag
&lt;/h2&gt;

&lt;p&gt;Let's formalize our intuition into a concrete algorithm:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt;&lt;p&gt;&lt;strong&gt;Handle the Edge Case:&lt;/strong&gt; If &lt;code&gt;numRows&lt;/code&gt; is 1, no zigzag conversion is needed. Simply return the original string &lt;code&gt;s&lt;/code&gt;.&lt;/p&gt;&lt;/li&gt;
&lt;li&gt;&lt;p&gt;&lt;strong&gt;Initialize Rows:&lt;/strong&gt; We need a way to store characters for each row. A list of lists (or list of strings/string builders) is perfect for this. Let's create &lt;code&gt;numRows&lt;/code&gt; empty lists. For example, &lt;code&gt;mat = [[] for _ in range(numRows)]&lt;/code&gt;.&lt;/p&gt;&lt;/li&gt;
&lt;li&gt;
&lt;p&gt;&lt;strong&gt;Traverse and Populate:&lt;/strong&gt; We'll iterate through the input string &lt;code&gt;s&lt;/code&gt; character by character. For each character, we need to append it to the correct row. The key is to manage our &lt;code&gt;current_row&lt;/code&gt; index and the &lt;code&gt;direction&lt;/code&gt;.&lt;/p&gt;

&lt;p&gt;The pattern can be seen as a series of "full columns" going down, followed by "diagonal segments" going up-right.&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;  &lt;strong&gt;Phase 1: Going Down:&lt;/strong&gt; We start at &lt;code&gt;row 0&lt;/code&gt; and append characters sequentially to &lt;code&gt;mat[0]&lt;/code&gt;, &lt;code&gt;mat[1]&lt;/code&gt;, ..., up to &lt;code&gt;mat[numRows - 1]&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;  &lt;strong&gt;Phase 2: Going Up-Right:&lt;/strong&gt; After reaching the bottom, we move "up and right." This means we append characters to &lt;code&gt;mat[numRows - 2]&lt;/code&gt;, &lt;code&gt;mat[numRows - 3]&lt;/code&gt;, ..., up to &lt;code&gt;mat[1]&lt;/code&gt;. We stop before &lt;code&gt;row 0&lt;/code&gt; because &lt;code&gt;row 0&lt;/code&gt; is the start of the next "down" phase. Similarly, &lt;code&gt;numRows - 1&lt;/code&gt; is only hit when going down.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;We repeat these two phases until all characters from &lt;code&gt;s&lt;/code&gt; are processed.&lt;/p&gt;
&lt;/li&gt;
&lt;li&gt;&lt;p&gt;&lt;strong&gt;Construct Result:&lt;/strong&gt; Once all characters have been placed into their respective row lists, concatenate all the lists (or strings) in &lt;code&gt;mat&lt;/code&gt; from &lt;code&gt;row 0&lt;/code&gt; to &lt;code&gt;numRows - 1&lt;/code&gt; to form the final result string.&lt;/p&gt;&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;Let's trace &lt;code&gt;s = "PAYPALISHIRING", numRows = 3&lt;/code&gt; with this approach:&lt;/p&gt;

&lt;p&gt;&lt;code&gt;mat = [[], [], []]&lt;/code&gt;&lt;br&gt;
&lt;code&gt;s_idx = 0&lt;/code&gt;&lt;/p&gt;

&lt;p&gt;&lt;strong&gt;Cycle 1:&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Down Phase:&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;s[0]&lt;/code&gt; ('P') -&amp;gt; &lt;code&gt;mat[0]&lt;/code&gt; -&amp;gt; &lt;code&gt;['P']&lt;/code&gt;, &lt;code&gt;s_idx = 1&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;s[1]&lt;/code&gt; ('A') -&amp;gt; &lt;code&gt;mat[1]&lt;/code&gt; -&amp;gt; &lt;code&gt;['A']&lt;/code&gt;, &lt;code&gt;s_idx = 2&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;s[2]&lt;/code&gt; ('Y') -&amp;gt; &lt;code&gt;mat[2]&lt;/code&gt; -&amp;gt; &lt;code&gt;['Y']&lt;/code&gt;, &lt;code&gt;s_idx = 3&lt;/code&gt; (Reached &lt;code&gt;numRows - 1&lt;/code&gt;)&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;

&lt;strong&gt;Up-Right Phase:&lt;/strong&gt; (&lt;code&gt;numRows - 2&lt;/code&gt; down to &lt;code&gt;1&lt;/code&gt; -&amp;gt; &lt;code&gt;3 - 2 = 1&lt;/code&gt; down to &lt;code&gt;1&lt;/code&gt;)

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;s[3]&lt;/code&gt; ('P') -&amp;gt; &lt;code&gt;mat[1]&lt;/code&gt; -&amp;gt; &lt;code&gt;['A', 'P']&lt;/code&gt;, &lt;code&gt;s_idx = 4&lt;/code&gt; (Reached &lt;code&gt;row 1&lt;/code&gt;)&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;p&gt;&lt;strong&gt;Cycle 2:&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Down Phase:&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;s[4]&lt;/code&gt; ('A') -&amp;gt; &lt;code&gt;mat[0]&lt;/code&gt; -&amp;gt; &lt;code&gt;['P', 'A']&lt;/code&gt;, &lt;code&gt;s_idx = 5&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;s[5]&lt;/code&gt; ('L') -&amp;gt; &lt;code&gt;mat[1]&lt;/code&gt; -&amp;gt; &lt;code&gt;['A', 'P', 'L']&lt;/code&gt;, &lt;code&gt;s_idx = 6&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;s[6]&lt;/code&gt; ('I') -&amp;gt; &lt;code&gt;mat[2]&lt;/code&gt; -&amp;gt; &lt;code&gt;['Y', 'I']&lt;/code&gt;, &lt;code&gt;s_idx = 7&lt;/code&gt;
&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;

&lt;strong&gt;Up-Right Phase:&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;s[7]&lt;/code&gt; ('S') -&amp;gt; &lt;code&gt;mat[1]&lt;/code&gt; -&amp;gt; &lt;code&gt;['A', 'P', 'L', 'S']&lt;/code&gt;, &lt;code&gt;s_idx = 8&lt;/code&gt;
&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;p&gt;&lt;strong&gt;Cycle 3:&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Down Phase:&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;s[8]&lt;/code&gt; ('H') -&amp;gt; &lt;code&gt;mat[0]&lt;/code&gt; -&amp;gt; &lt;code&gt;['P', 'A', 'H']&lt;/code&gt;, &lt;code&gt;s_idx = 9&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;s[9]&lt;/code&gt; ('I') -&amp;gt; &lt;code&gt;mat[1]&lt;/code&gt; -&amp;gt; &lt;code&gt;['A', 'P', 'L', 'S', 'I']&lt;/code&gt;, &lt;code&gt;s_idx = 10&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;s[10]&lt;/code&gt; ('R') -&amp;gt; &lt;code&gt;mat[2]&lt;/code&gt; -&amp;gt; &lt;code&gt;['Y', 'I', 'R']&lt;/code&gt;, &lt;code&gt;s_idx = 11&lt;/code&gt;
&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;li&gt;

&lt;strong&gt;Up-Right Phase:&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;s[11]&lt;/code&gt; ('I') -&amp;gt; &lt;code&gt;mat[1]&lt;/code&gt; -&amp;gt; &lt;code&gt;['A', 'P', 'L', 'S', 'I', 'I']&lt;/code&gt;, &lt;code&gt;s_idx = 12&lt;/code&gt;
&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;p&gt;&lt;strong&gt;Cycle 4:&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Down Phase:&lt;/strong&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;s[12]&lt;/code&gt; ('N') -&amp;gt; &lt;code&gt;mat[0]&lt;/code&gt; -&amp;gt; &lt;code&gt;['P', 'A', 'H', 'N']&lt;/code&gt;, &lt;code&gt;s_idx = 13&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;s[13]&lt;/code&gt; ('G') -&amp;gt; &lt;code&gt;mat[1]&lt;/code&gt; -&amp;gt; &lt;code&gt;['A', 'P', 'L', 'S', 'I', 'I', 'G']&lt;/code&gt;, &lt;code&gt;s_idx = 14&lt;/code&gt; (String &lt;code&gt;s&lt;/code&gt; exhausted)&lt;/li&gt;
&lt;/ul&gt;


&lt;/li&gt;

&lt;/ul&gt;

&lt;p&gt;Final &lt;code&gt;mat&lt;/code&gt;:&lt;br&gt;
&lt;code&gt;mat[0] = ['P', 'A', 'H', 'N']&lt;/code&gt;&lt;br&gt;
&lt;code&gt;mat[1] = ['A', 'P', 'L', 'S', 'I', 'I', 'G']&lt;/code&gt;&lt;br&gt;
&lt;code&gt;mat[2] = ['Y', 'I', 'R']&lt;/code&gt;&lt;/p&gt;

&lt;p&gt;Join them: "PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR". Perfect!&lt;/p&gt;

&lt;h2&gt;
  
  
  Code
&lt;/h2&gt;



&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight python"&gt;&lt;code&gt;&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Solution&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
    &lt;span class="k"&gt;def&lt;/span&gt; &lt;span class="nf"&gt;convert&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;self&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nb"&gt;str&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;numRows&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nb"&gt;int&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;-&amp;gt;&lt;/span&gt; &lt;span class="nb"&gt;str&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
        &lt;span class="c1"&gt;# Edge case: If there's only one row, no zigzag conversion needed.
&lt;/span&gt;        &lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="n"&gt;numRows&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
            &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;

        &lt;span class="c1"&gt;# Initialize numRows empty lists to represent each row.
&lt;/span&gt;        &lt;span class="c1"&gt;# Each list will store characters that belong to that row.
&lt;/span&gt;        &lt;span class="n"&gt;mat&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="p"&gt;[[]&lt;/span&gt; &lt;span class="k"&gt;for&lt;/span&gt; &lt;span class="n"&gt;_&lt;/span&gt; &lt;span class="ow"&gt;in&lt;/span&gt; &lt;span class="nf"&gt;range&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;numRows&lt;/span&gt;&lt;span class="p"&gt;)]&lt;/span&gt;

        &lt;span class="c1"&gt;# Pointer for the current character in the input string s.
&lt;/span&gt;        &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;
        &lt;span class="c1"&gt;# Length of the input string s.
&lt;/span&gt;        &lt;span class="n"&gt;n&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="nf"&gt;len&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;

        &lt;span class="c1"&gt;# Loop until all characters from the input string are processed.
&lt;/span&gt;        &lt;span class="k"&gt;while&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;&lt;/span&gt; &lt;span class="n"&gt;n&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
            &lt;span class="c1"&gt;# Phase 1: Go down (from row 0 to numRows - 1)
&lt;/span&gt;            &lt;span class="k"&gt;for&lt;/span&gt; &lt;span class="n"&gt;down&lt;/span&gt; &lt;span class="ow"&gt;in&lt;/span&gt; &lt;span class="nf"&gt;range&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;numRows&lt;/span&gt;&lt;span class="p"&gt;):&lt;/span&gt;
                &lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;&lt;/span&gt; &lt;span class="n"&gt;n&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="c1"&gt;# Check if there are still characters left in s
&lt;/span&gt;                    &lt;span class="n"&gt;mat&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;down&lt;/span&gt;&lt;span class="p"&gt;].&lt;/span&gt;&lt;span class="nf"&gt;append&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;i&lt;/span&gt;&lt;span class="p"&gt;])&lt;/span&gt;
                    &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;+=&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;

            &lt;span class="c1"&gt;# Phase 2: Go up-right (from numRows - 2 down to row 1)
&lt;/span&gt;            &lt;span class="c1"&gt;# We skip row 0 and numRows - 1 as they are handled exclusively by the 'down' phase
&lt;/span&gt;            &lt;span class="c1"&gt;# or will be the start/end of the next 'down' phase.
&lt;/span&gt;            &lt;span class="k"&gt;for&lt;/span&gt; &lt;span class="n"&gt;up&lt;/span&gt; &lt;span class="ow"&gt;in&lt;/span&gt; &lt;span class="nf"&gt;range&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;numRows&lt;/span&gt; &lt;span class="o"&gt;-&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="o"&gt;-&lt;/span&gt;&lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;):&lt;/span&gt;
                &lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;&lt;/span&gt; &lt;span class="n"&gt;n&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="c1"&gt;# Check if there are still characters left in s
&lt;/span&gt;                    &lt;span class="n"&gt;mat&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;up&lt;/span&gt;&lt;span class="p"&gt;].&lt;/span&gt;&lt;span class="nf"&gt;append&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;i&lt;/span&gt;&lt;span class="p"&gt;])&lt;/span&gt;
                    &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;+=&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;

        &lt;span class="c1"&gt;# After populating all rows, join the characters in each row
&lt;/span&gt;        &lt;span class="c1"&gt;# and then concatenate all rows to form the final result string.
&lt;/span&gt;        &lt;span class="n"&gt;result&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="p"&gt;[]&lt;/span&gt;
        &lt;span class="k"&gt;for&lt;/span&gt; &lt;span class="n"&gt;row&lt;/span&gt; &lt;span class="ow"&gt;in&lt;/span&gt; &lt;span class="n"&gt;mat&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt;
            &lt;span class="n"&gt;result&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nf"&gt;extend&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;row&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="c1"&gt;# Use extend for efficiency, then join once
&lt;/span&gt;
        &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="sh"&gt;""&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nf"&gt;join&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;result&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;

&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;h2&gt;
  
  
  Time &amp;amp; Space Complexity Analysis
&lt;/h2&gt;

&lt;p&gt;&lt;strong&gt;Time Complexity: O(N)&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;We iterate through the input string &lt;code&gt;s&lt;/code&gt; once using the &lt;code&gt;while i &amp;lt; n&lt;/code&gt; loop.&lt;/li&gt;
&lt;li&gt;Inside the loop, each character &lt;code&gt;s[i]&lt;/code&gt; is appended to a list in &lt;code&gt;mat&lt;/code&gt; exactly once.&lt;/li&gt;
&lt;li&gt;Finally, we iterate through the &lt;code&gt;mat&lt;/code&gt; (which collectively holds &lt;code&gt;N&lt;/code&gt; characters) to build the &lt;code&gt;result&lt;/code&gt; list and then join them into a string. The &lt;code&gt;extend&lt;/code&gt; and &lt;code&gt;join&lt;/code&gt; operations are proportional to the total number of characters, which is &lt;code&gt;N&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;Therefore, the overall time complexity is linear with respect to the length of the string &lt;code&gt;s&lt;/code&gt;.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;&lt;strong&gt;Space Complexity: O(N)&lt;/strong&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;We create &lt;code&gt;numRows&lt;/code&gt; lists in &lt;code&gt;mat&lt;/code&gt;. In the worst case (e.g., &lt;code&gt;numRows = N&lt;/code&gt;), each list holds one character. In general, all &lt;code&gt;N&lt;/code&gt; characters of the string &lt;code&gt;s&lt;/code&gt; are stored across these &lt;code&gt;numRows&lt;/code&gt; lists.&lt;/li&gt;
&lt;li&gt;The &lt;code&gt;result&lt;/code&gt; list also temporarily stores all &lt;code&gt;N&lt;/code&gt; characters before joining.&lt;/li&gt;
&lt;li&gt;Therefore, the space complexity is linear with respect to the length of the string &lt;code&gt;s&lt;/code&gt;.&lt;/li&gt;
&lt;/ul&gt;

&lt;h2&gt;
  
  
  Key Takeaways
&lt;/h2&gt;

&lt;ol&gt;
&lt;li&gt; &lt;strong&gt;Simulation Power:&lt;/strong&gt; Many string manipulation or pattern-based problems can be solved by directly simulating the process described. Break down the pattern into repeatable steps.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;State Management:&lt;/strong&gt; Keeping track of &lt;code&gt;current_row&lt;/code&gt; and &lt;code&gt;direction&lt;/code&gt; (or explicit phases like "down" and "up-right") is crucial for controlling the simulation.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;Edge Cases First:&lt;/strong&gt; Always consider simple edge cases like &lt;code&gt;numRows = 1&lt;/code&gt; early on. They often simplify your logic or prevent errors.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;List of Lists for Structure:&lt;/strong&gt; When dealing with grid-like or row-based structures, a list of lists (or 2D array) is a very natural and effective data structure.&lt;/li&gt;
&lt;li&gt; &lt;strong&gt;Concatenation Efficiency:&lt;/strong&gt; For building strings from many smaller pieces, appending to a list of characters/strings and then using &lt;code&gt;"".join(list)&lt;/code&gt; is generally more efficient in Python than repeated string concatenation (&lt;code&gt;+=&lt;/code&gt;).&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;Hope this breakdown helped you "unzigzag" this problem! Keep practicing, and you'll master these patterns in no time. Happy coding!&lt;/p&gt;

&lt;h2&gt;
  
  
  Submission Details
&lt;/h2&gt;

&lt;p&gt;Author Account: aryan-subudhi&lt;br&gt;
Publishing Time: 2026-05-24 18:33:26&lt;br&gt;
Title: Unraveling the Zigzag: A Beginner's Guide to LeetCode 6 (Zigzag Conversion)&lt;/p&gt;

</description>
      <category>leetcode</category>
      <category>dsa</category>
      <category>programming</category>
      <category>tutorial</category>
    </item>
  </channel>
</rss>
