SvenStack

🧩 Problem Description

LeetCode 7 - Reverse Integer
Given a signed 32-bit integer x, return x with its digits reversed.
If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], return 0.

Example:

1
2
3
4
5
6
7
8

Input: x = 123
Output: 321

Input: x = -123
Output: -321

Input: x = 120
Output: 21

💡 First Thought (Convert to String)

The simplest way is to convert the number to a string, reverse it, and parse it back.
However, this is not efficient and requires handling signs and overflow carefully.

⚙️ Optimized Approach — Math Manipulation

We can extract digits using modulo and build the reversed number step by step.

Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;

            // check overflow before multiplying
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7))
                return 0;
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8))
                return 0;

            rev = rev * 10 + pop;
        }
        return rev;
    }
}

⏱️ Complexity Analysis

🧠 Key Takeaways

• Always check overflow/underflow before multiplication.
• String reversal is simple but not optimal for integer manipulation.
• The mathematical approach avoids unnecessary conversions.

📘 Next Step: We’ll explore more number-based manipulation problems next.

🧩 Problem Description

LeetCode 6 - Zigzag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows, like this:

1
2
3

P   A   H   N
A P L S I I G
Y   I   R

Then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows.

Example:

1
2

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

💡 First Thought (Simulation)

We can simulate the zigzag process by writing characters row by row.
Keep track of the current row and the direction (down or up).

⚙️ Optimized Approach — Row Buckets

We maintain a list of StringBuilder objects, one for each row,
and iterate over the string while changing direction when we hit the top or bottom row.

Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) return s;

        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();

        int curRow = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows[curRow].append(c);
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }

        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) result.append(row);
        return result.toString();
    }
}

⏱️ Complexity Analysis

🧠 Key Takeaways

• Zigzag pattern can be simulated by tracking row direction.
• Great example of string traversal with controlled direction change.
• Easy to visualize and implement with StringBuilder[].

📘 Next Step: We’ll look into string pattern transformation problems in the next post.

🧩 Problem

LeetCode 287 - Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is only one repeated number but it could be repeated more than once.
Return the duplicate number. You must solve the problem without modifying the array and use only constant extra space (O(1) space).

Example:

1
2

Input: nums = [1,3,4,2,2]
Output: 2

💡 Idea

Treat the array as a linked list where the value at index i points to nums[i]. Because numbers are in [1, n], this mapping creates a cycle due to the duplicate. We can use Floyd’s Tortoise and Hare (cycle detection) algorithm to find the entrance to the cycle, which corresponds to the duplicate number.

Steps (Floyd’s algorithm):

1. Use two pointers tortoise and hare; move tortoise by one step and hare by two steps until they meet.
2. Reset one pointer to the start (index 0) and move both one step at a time; the meeting point is the duplicate (cycle start).

This approach does not modify the input and uses O(1) extra space.

🔢 Java Code (Floyd’s Tortoise and Hare)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int findDuplicate(int[] nums) {
        // Phase 1: find intersection point of two runners
        int tortoise = nums[0];
        int hare = nums[0];
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);
        
        // Phase 2: find entrance to the cycle
        tortoise = nums[0];
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }
        return hare;
    }
}

Alternative: Binary Search on Value (O(n log n), O(1) space)

Binary search on the value range [1, n]: count how many numbers <= mid. If count > mid, duplicate lies in left half; otherwise right half. This doesn’t modify the array and uses O(1) space but costs O(n log n) time.

⏱ Complexity Analysis

• Floyd’s algorithm:

  • Time: O(n)
  • Space: O(1)

• Binary search on value:

  • Time: O(n log n)
  • Space: O(1)

✍️ Summary

• Model the array as a functional graph and use cycle detection to locate the duplicate’s value.
• Floyd’s Tortoise and Hare gives O(n) time with constant space and doesn’t mutate the array — ideal for this problem.

🧩 Problem

LeetCode 31 - Next Permutation
Implement the next lexicographical permutation of the given integer array nums.
If such arrangement is not possible, rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be in-place and use only constant extra memory.

Example:

1
2
3
4
5
6
7
8

Input: nums = [1,2,3]
Output: [1,3,2]

Input: nums = [3,2,1]
Output: [1,2,3]

Input: nums = [1,1,5]
Output: [1,5,1]

💡 Idea

To get the next lexicographically larger permutation, we follow three steps:

1. Find the first decreasing element (pivot) from the right side where nums[i] < nums[i+1].
   If no such index exists, it means the array is in descending order → reverse it directly.

2. Find the smallest element greater than nums[i] to the right of it, say nums[j].

3. Swap nums[i] and nums[j], then reverse the subarray from i+1 to the end.
   This ensures the next immediate permutation is achieved.

💻 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }

        reverse(nums, i + 1, n - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }
}

🧠 Complexity

• Time: O(n) — One pass to find pivot, one to reverse.
• Space: O(1) — In-place manipulation.

🏁 Summary

The key insight is recognizing the first decreasing pair from the right and making the minimal change to reach the next permutation.
This elegant algorithm is widely used in combinatorial generation and backtracking problems.

🧩 Problem

LeetCode 75 - Sort Colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the colors red, white, and blue respectively.

You must solve this problem without using the library’s sort function.

Example:

1
2

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

💡 Idea

This is a Dutch National Flag problem, invented by Edsger Dijkstra.
We use three pointers to partition the array into three regions:

• 0 ... low-1: all 0s
• low ... mid-1: all 1s
• high+1 ... end: all 2s

We iterate using mid:

• If nums[mid] == 0: swap with low, increment both low and mid
• If nums[mid] == 1: just increment mid
• If nums[mid] == 2: swap with high, decrement high

This ensures a one-pass, in-place sorting solution.

💻 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low++, mid++);
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums, mid, high--);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

🧠 Complexity

• Time: O(n) — Single pass through the array
• Space: O(1) — In-place swaps only

🏁 Summary

This problem is a perfect example of in-place array manipulation using multiple pointers.
The Dutch National Flag algorithm is elegant, efficient, and a must-know for array partitioning problems.

🧩 Problem

LeetCode 169 - Majority Element
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times.
You may assume that the majority element always exists in the array.

Example:

1
2

Input: nums = [2,2,1,1,1,2,2]
Output: 2

💡 Idea

There are multiple approaches:

1. Sorting → The middle element is the majority.
2. HashMap counting → Count frequencies.
3. Boyer–Moore Majority Vote Algorithm → O(n) time, O(1) space (most optimal).

Boyer–Moore Explanation

We maintain a candidate and a count.

• If count is 0, set the current number as candidate.
• If the current number equals candidate, increment count; otherwise, decrement count.
  At the end, candidate is the majority element.

Example

1
2
3

nums = [2,2,1,1,1,2,2]
candidate=2, count=1
=> final candidate = 2

💻 Java Code

1
2
3
4
5
6
7
8
9
10

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0, candidate = 0;
        for (int num : nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

🧠 Complexity

• Time: O(n)
• Space: O(1)

🏁 Summary

The Boyer–Moore algorithm is elegant and efficient — it eliminates the need for extra storage by leveraging the majority element’s dominance in occurrence.

🧩 Problem

LeetCode 136 - Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with linear runtime complexity and use only constant extra space.

Example:

1
2

Input: nums = [4,1,2,1,2]
Output: 4

💡 Idea

This problem can be elegantly solved using the XOR (^) operation.
Key properties of XOR:

• a ^ a = 0
• a ^ 0 = a
• XOR is commutative and associative

Thus, when we XOR all numbers together, pairs cancel out, leaving only the unique number.

Example

1
2

nums = [4, 1, 2, 1, 2]
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4

💻 Java Code

1
2
3
4
5
6
7
8
9

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

🧠 Complexity

• Time: O(n) — iterate once through the array
• Space: O(1) — only one variable used

🏁 Summary

A perfect example of how bitwise operations simplify logic and improve efficiency.
The XOR trick is commonly used in array problems involving pairs and uniqueness detection.

🧩 Problem

LeetCode 72 - Edit Distance
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted:

• Insert a character
• Delete a character
• Replace a character

Example:

1
2
3
4
5
6

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

💡 Idea

This is a classic dynamic programming problem.
We define dp[i][j] as the minimum number of operations required to convert the first i characters of word1 into the first j characters of word2.

DP Transition

If the characters match (word1[i-1] == word2[j-1]):

1

dp[i][j] = dp[i-1][j-1]

Otherwise:

1
2
3
4
5

dp[i][j] = 1 + min(
    dp[i-1][j],   // delete
    dp[i][j-1],   // insert
    dp[i-1][j-1]  // replace
)

Base Cases

1
2

dp[0][j] = j  // need j insertions
dp[i][0] = i  // need i deletions

🧠 Complexity

• Time: O(m × n)
• Space: O(m × n)

💻 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = 1 + Math.min(dp[i - 1][j],
                                   Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
            }
        }
        return dp[m][n];
    }
}

🏁 Summary

This problem demonstrates how dynamic programming elegantly handles string transformations.
We systematically consider all operations (insert, delete, replace) and store intermediate results to build the final answer efficiently.

🧩 Problem Description

Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

If there is no common subsequence, return 0.

💬 Examples

Example 1

1
2
3

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace".

Example 2

1
2
3

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc".

Example 3

1
2
3

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: No common subsequence.

💡 Intuition

This is a classic dynamic programming problem.
Define dp[i][j] as the length of the longest common subsequence between text1[0..i) and text2[0..j).

Transitions:

• If text1[i-1] == text2[j-1], then dp[i][j] = dp[i-1][j-1] + 1.
• Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

We can implement this with a 2D DP table (size (m+1) × (n+1)) or optimize space to a 1D array by iterating rows and storing previous row values.

🔢 Java Code (2D DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

🔢 Java Code (1D DP - space optimized)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            int prev = 0; // dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        return dp[n];
    }
}

⏱ Complexity Analysis

• Time: O(m × n), where m and n are the lengths of text1 and text2.
• Space: O(m × n) for 2D DP, or O(n) for the optimized 1D DP.

✍️ Summary

• Use DP with dp[i][j] representing LCS length for prefixes.
• If characters match, extend dp[i-1][j-1]; otherwise take the max of neighboring states.
• Space optimization to 1D is possible by careful ordering.

Related problems: lc-583 (Delete Operation for Two Strings), lc-718 (Maximum Length of Repeated Subarray).

🧩 Problem Description

Given a string s, return the longest palindromic substring in s.

A palindrome is a string that reads the same backward as forward.

💬 Examples

Example 1

1
2
3

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2

1
2

Input: s = "cbbd"
Output: "bb"

💡 Intuition

We can solve this using Dynamic Programming or Expand Around Center.

🔹 Approach 1 — Expand Around Center

Every palindrome mirrors around its center.
There can be 2n - 1 centers (between characters and at characters).

Expand from each center until it’s no longer a palindrome.

🔢 Java Code (Expand Around Center)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandFromCenter(s, i, i);     // odd-length
            int len2 = expandFromCenter(s, i, i + 1); // even-length
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandFromCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

🔹 Approach 2 — Dynamic Programming

Let dp[i][j] mean whether substring s[i..j] is a palindrome.
Transition rule:

1

dp[i][j] = (s[i] == s[j]) && (j - i < 3 || dp[i + 1][j - 1])

🔢 Java Code (Dynamic Programming)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}

⏱ Complexity Analysis

✍️ Summary

• Expand around every center or use DP.
• Palindrome means symmetry around a center.
• Expand method is simpler and more space-efficient.

Related problems:

• lc-516 (Longest Palindromic Subsequence)
• lc-647 (Palindromic Substrings)