🚀 Day113 - LeetCode 27: Remove Element

🔍 Problem

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place.
Return the number of remaining elements. Order may change.

🧠 Approach

• Use two pointers
• fast scans array
• slow records valid element positions
• When nums[fast] != val, copy to nums[slow]

✅ Complexity

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

💻 Java Code

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

📝 Notes

• We don’t need an extra array
• Just overwrite values in-place
• slow pointer gives the new length

Keep grinding — one step closer every day! 💪🔥

LC-26 Remove Duplicates from Sorted Array

📌 Problem

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and return the new length. Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.

💬 Examples

Example 1

1
2

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

Example 2

1
2

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

💡 Intuition (Two Pointers)

Because the array is sorted, duplicates are adjacent. Use two pointers — slow and fast:

• slow tracks the position to write the next unique element (starts at 0).
• fast scans the array from 1 to end.
• When nums[fast] != nums[slow], increment slow and copy nums[fast] to nums[slow].

After the loop, the new length is slow + 1.

🔢 Java Code (Two Pointers)

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

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
}

⏱ Complexity Analysis

• Time: O(n) — single pass through the array.
• Space: O(1) — in-place, constant extra space.

✍️ Summary

• Use two pointers on a sorted array to overwrite duplicates.
• After processing, first k elements are the unique values where k = slow + 1.
• Very common in interviews — demonstrates in-place array manipulation and two-pointer technique.

🧩 Problem Description

Given an integer array nums and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Constraints:

• 4 <= nums.length <= 200
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

💡 Approach

This is a direct extension of the 3Sum problem.
We use sorting + two pointers:

1. Sort the array.
2. Use two nested loops for the first two numbers.
3. Apply the two-pointer method to find the remaining two numbers.
4. Skip duplicate values to avoid repeated quadruplets.

🧠 Key Insight

After fixing two indices i and j, we need to find two numbers whose sum equals target - nums[i] - nums[j].
This can be efficiently done with a two-pointer scan since the array is sorted.

🧮 Complexity

• Time Complexity: O(n³)
• Space Complexity: O(1) (excluding output list)

💻 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
32
33
34
35

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates

            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates

                long newTarget = (long)target - nums[i] - nums[j];
                int left = j + 1, right = n - 1;

                while (left < right) {
                    long sum = nums[left] + nums[right];
                    if (sum == newTarget) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < newTarget) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

🏁 Summary

• Sort → Fix two numbers → Use two pointers for the rest.
• Handle duplicates carefully.
• Similar to 3Sum, but one extra layer of iteration.

LC-16 3Sum Closest

📌 Problem

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers. You may assume that each input would have exactly one solution.

💬 Examples

Example 1

1
2
3

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2 (-1 + 2 + 1 = 2).

💡 Intuition

The problem is similar to the classic 3Sum, but instead of finding an exact match, we want the closest sum.
We can sort the array first, then use a two-pointer approach to efficiently explore possible triplets.

🔢 Java Code (Sorting + Two Pointers)

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

import java.util.*;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int closest = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < Math.abs(closest - target)) {
                    closest = sum;
                }
                if (sum < target) left++;
                else if (sum > target) right--;
                else return sum; // exact match
            }
        }
        return closest;
    }
}

⏱ Complexity Analysis

• Time: O(n²) — Sorting takes O(n log n), and two-pointer scanning for each element takes O(n²).
• Space: O(1) — In-place sorting, no extra space used.

✍️ Summary

• Sort the array to apply two-pointer logic.
• Track the closest sum as we move pointers.
• Efficient and intuitive extension of the 3Sum problem.

📌 Problem

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

💬 Examples

Example 1

1
2

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2

1
2

Input: strs = ["dog","racecar","car"]
Output: ""

Explanation: There is no common prefix among the input strings.

💡 Intuition

A common and simple approach is to start from the first string as the prefix, and then gradually shorten it while checking against other strings.
Stop when the prefix no longer matches.

🔢 Java Code (Vertical Scanning)

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

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }
}

⏱ Complexity Analysis

• Time: O(S) — S = total number of characters in all strings (each char checked at most once).
• Space: O(1) — no extra data structure used.

✍️ Summary

• Start with the first string as prefix and reduce it when mismatches occur.
• Efficient for small/medium input sizes.
• A clean and intuitive string problem that often appears early in interviews.

📌 Problem

Convert a Roman numeral to an integer. Input is guaranteed to be within the range corresponding to standard Roman numerals (typically 1..3999).

Roman numerals are represented by the symbols:
I(1), V(5), X(10), L(50), C(100), D(500), M(1000).
Some symbols may be placed before larger symbols to indicate subtraction, e.g., IV = 4, IX = 9.

💬 Examples

Example 1

1
2

Input: s = "III"
Output: 3

Example 2

1
2

Input: s = "IV"
Output: 4

Example 3

1
2

Input: s = "MCMXCIV"
Output: 1994

💡 Intuition (Greedy / Left-to-right)

Scan from left to right, adding values. If a smaller-value symbol appears before a larger one, subtract the smaller; otherwise add it. A simple approach: for each character, compare its value with the next character (if any) to decide add or subtract.

🔢 Java Code (Map + Greedy)

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

import java.util.*;

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);

        int n = s.length();
        int result = 0;
        for (int i = 0; i < n; i++) {
            int val = map.get(s.charAt(i));
            if (i + 1 < n && val < map.get(s.charAt(i + 1))) {
                result -= val;
            } else {
                result += val;
            }
        }
        return result;
    }
}

⏱ Complexity Analysis

• Time: O(n) — single pass over the string.
• Space: O(1) — constant-size map and a few variables.

✍️ Summary

• Use a mapping from Roman symbols to integers.
• Subtract when a smaller symbol precedes a larger one; otherwise add.
• Simple, linear-time solution ideal for interviews.

📌 Problem

Convert an integer to a Roman numeral. Input is guaranteed to be within the range 1 <= num <= 3999.

💬 Examples

Example 1

1
2

Input: num = 3
Output: "III"

Example 2

1
2
3

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3

1
2
3

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.

💡 Intuition (Greedy)

Use a greedy approach: repeatedly subtract the largest Roman value that does not exceed the current number and append its symbol. Predefine pairs of values and symbols in decreasing order (including subtractive forms like 900 -> “CM”).

🔢 Java Code (Greedy)

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

class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length && num > 0; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(symbols[i]);
            }
        }
        return sb.toString();
    }
}

⏱ Complexity Analysis

• Time: O(1) — bounded by a small constant (max ~15 symbol appends).
• Space: O(1) — output size is O(1) relative to input bounds.

✍️ Summary

• Predefine Roman symbols including subtractive pairs.
• Greedy subtraction + append produces correct Roman numeral efficiently.
• Java implementation above is simple and interview-friendly.

LC-10 Regular Expression Matching

📌 Problem

Implement regular expression matching with support for ‘.’ and ‘*’ where:

• ‘.’ Matches any single character.
• ‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

💬 Examples

Example 1

1
2

Input: s = "aa", p = "a"
Output: false

Example 2

1
2

Input: s = "aa", p = "a*"
Output: true

Example 3

1
2

Input: s = "ab", p = ".*"
Output: true

💡 Intuition & Brute Force

A naive recursive solution tries all possibilities for ‘*’ (match zero, one, multiple). This leads to exponential time in the worst case.

Key observation for DP: define dp[i][j] = whether s[0..i) matches p[0..j). Build up using smaller prefixes.

✅ Optimized Solution (Dynamic Programming)

Transitions:

1. If p[j-1] is a normal char or ‘.’, then:
   dp[i][j] = dp[i-1][j-1] && (p[j-1] == s[i-1] || p[j-1] == ‘.’)

2. If p[j-1] == ‘*’, it stands for zero or more of p[j-2]:

   • Zero occurrence: dp[i][j] = dp[i][j-2]
   • One or more: if p[j-2] matches s[i-1], dp[i][j] = dp[i-1][j]

Initialize dp[0][0] = true, and handle patterns like a*, ab that can match empty string.

🔢 Java Code (DP)

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
32

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        // Patterns like a*, a*b* can match empty string
        for (int j = 2; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char pc = p.charAt(j - 1);
                if (pc == '.' || pc == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pc == '*') {
                    // zero occurrence
                    dp[i][j] = dp[i][j - 2];
                    // one or more occurrence
                    char pprev = p.charAt(j - 2);
                    if (pprev == '.' || pprev == s.charAt(i - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}

⏱ Complexity Analysis

• Time: O(m × n) where m = s.length(), n = p.length().
• Space: O(m × n) for DP table.

✍️ Summary

• Use DP to avoid exponential recursion.
• Carefully handle ‘*’ by considering zero or multiple occurrences.
• Initialization for empty string vs pattern is important.

🧩 Problem Description

Given an integer x, return true if x is a palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

💬 Examples

Example 1

1
2

Input: x = 121
Output: true

Example 2

1
2
3

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-.

Example 3

1
2
3

Input: x = 10
Output: false
Explanation: Reads 01 from right to left.

💡 Intuition

Reversing the whole integer risks overflow. Instead, reverse only the second half of the number and compare it with the first half.
Edge cases:

• Negative numbers are not palindromes.
• Numbers ending with 0 are not palindromes unless the number is 0.

Stop when the reversed half is >= remaining half.

🔢 Java Code (Reverse Half)

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return x == rev || x == rev / 10;
    }
}

⏱ Complexity Analysis

• Time: O(log₁₀ n) — number of digits.
• Space: O(1) — constant extra space.

✍️ Summary

• Avoid full reversal to prevent overflow; reverse half instead.
• Handle negative numbers and trailing zeros explicitly.
• Simple, O(1) space solution suitable for interview settings.

🧩 Problem Description

LeetCode 8 - String to Integer (atoi)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The algorithm follows these steps:

1. Read and ignore leading whitespaces.
2. Check if the next character is + or - (determine the sign).
3. Read digits until a non-digit character or end of string.
4. Clamp the result within the 32-bit integer range.

Example:

1
2
3
4
5
6
7
8

Input: s = "42"
Output: 42

Input: s = "   -42"
Output: -42

Input: s = "4193 with words"
Output: 4193

💡 First Thought (Use Built-in Functions)

One might think of using Integer.parseInt() or similar methods,
but those cannot handle invalid formats and overflow gracefully.
We need to implement the parsing logic manually.

⚙️ Optimized Approach — Manual Parsing

We manually iterate through the string, handle spaces, sign, digits, and overflow.

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

public class Solution {
    public int myAtoi(String s) {
        int i = 0, n = s.length();
        while (i < n && s.charAt(i) == ' ') i++; // skip spaces

        int sign = 1;
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            sign = (s.charAt(i) == '-') ? -1 : 1;
            i++;
        }

        int result = 0;
        while (i < n && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';
            if (result > (Integer.MAX_VALUE - digit) / 10)
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            result = result * 10 + digit;
            i++;
        }

        return result * sign;
    }
}

⏱️ Complexity Analysis

🧠 Key Takeaways

• Manual parsing ensures robust handling of edge cases (overflow, invalid input).
• Remember to check integer boundaries before multiplication.
• Similar to C’s atoi() but safer for modern applications.

📘 Next Step: We’ll continue exploring string-to-number conversion problems next.