DEV Community: shine

[📝LeetCode #219] Contains Duplicate II

shine — Tue, 01 Jul 2025 03:56:16 +0000

🎀 The Problem

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example:

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

👩‍💻 My Answer

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            if (!map.containsKey(num)) {
                map.put(num, i);
                continue;
            }

            if (i - map.get(num) <= k)
                return true;
            else
                map.put(num, i);
        }

        return false;
    }
}

Pro & Con

✅ Runtime & Memory
🔺 Maybe there is a better one?

💋 Ideal Answer

Approach - "HashSet"

I read the solution post on LeetCode and found the HashSet approach, which was faster than my code. (Beats 98%)

Here is the code that I found on LeetCode.

New Code

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            if(i > k) set.remove(nums[i-k-1]); //remove element if its distance to nums[i] is not lesser than k
            if(!set.add(nums[i])) return true; //because all still existed elements is closer than k distance to the num[i], therefore if the add() return false, it means there's a same value element already existed within the distance k, therefore return true.
        }
        return false;
 }
}

I'm not 100% sure why the HashSet is faster than HashMap. (Both time and space complexity are O(N)). So, I asked in the comment section. If I get a reply, I will update here! Also, I'm thinking of writing a new post to compare the HashMap vs HashSet.

(Or if you know, please comment here!)

💡 What I Learned

I finally wrote decent, efficient code by myself for the first time to solve LeetCode.
Although I know how to use HashMap or HashSet, I still do not know that how operation is going on under the code;((((

[📝LeetCode #202] Happy Number

shine — Tue, 01 Jul 2025 03:55:58 +0000

🎀 The Problem

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.

Example:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

👩‍💻 My Answer

class Solution {
    public boolean isHappy(int n) {
        Set set = new HashSet();

        while (true) {
            int sum = 0;

            while (n != 0) {
                sum += (n % 10) * (n % 10);
                n = n / 10;
            }

            if (sum == 1)
                return true;

            if (!set.contains(sum))
                set.add(sum);
            else if (set.contains(sum))
                return false;

            n = sum;
        }
    }
}

Pro & Con

🔺 Runtime & Memory
✖️ Nested Loop (two while loops)

💋 Ideal Answer

Approach - "Fast and Slow Pointers"

When I was solving this, I could not come up with a HashSet system because I was not aware that the same remainder may come up (infinite cycle). Since my initial attempt was not working, I watched the YouTube video:
Nikhil Lohia's Happy Number (LeetCode 202)

BUT, the method introduced in Nikhil Lohia's video was not BEATING 100%. So, I watched the new video:
AlgoMasterIO's Happy Number (LeetCode 202)

This video introduced the two pointers: fast and slow. This algorithm is also used for the linked list problem but we can use this for the Happy Number problem.

New Code

class Solution {
    public boolean isHappy(int n) {

        int s = n,f = n; // slow , fast

        do{
            s = compute(s); // slow computes only once
            f = compute(compute(f)); // fast computes 2 times

            if(s == 1)return true; // if we found 1 then happy indeed !!!
        }while(s != f); // else at some point they will meet in the cycle

        return false;
    }

    private int compute (int n) {
        int sum = 0;

        while (n != 0) {
            sum += (n % 10) * (n % 10);
            n = n / 10;
        }
        return sum;
    }
}

💡 What I Learned

Java does not use ^ for power calculation. Instead of 10^2,
10*10
How to use fast and slow pointer
how to use do while instead of while

do {
CODE
} while (CONDITION)

[📝LeetCode #1] Two Sum

shine — Sun, 29 Jun 2025 04:40:55 +0000

🎀 The Problem

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

👩‍💻 My Answer

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int index = 0;

        while(index < nums.length){
            for (int i = index+1; i < nums.length; i++) {
                if (nums[i] == target - nums[index]) {
                    int[] output = new int[2];
                    output[0] = index;
                    output[1] = i;
                    return output;
                }
            }
            index++;
        }

        return null;
    }
}

Pro & Con

✖️ Runtime & Memory
✖️ Brute Force Code (nested loop)

💋 Ideal Answer

Approach - "Hash Table"

I read the solution on LeetCode and found that using a hash table is the fastest one for this.

New Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(target - nums[i]))
                map.put(nums[i], i);
            else
                return new int[] {map.get(target - nums[i]),i};
        }

        return null;
    }
}

💡 What I Learned

How I construct int[] in return line return new int[] {map.get(target - nums[i]),i};

[📝LeetCode #290] Word Pattern

shine — Thu, 26 Jun 2025 00:36:33 +0000

🎀 The Problem

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

👩‍💻 My Answer

class Solution {
    public boolean wordPattern(String pattern, String s) {
        HashMap map = new HashMap();
        int count = 0, wordcount = 0;
        String word = "";

        for (int i = 0; i < s.length(); i++) {
            char letter = s.charAt(i);

            if (count == pattern.length())
                return false;

            if (letter !=  ' ')
                word += letter;

            if (i == s.length() - 1 || word != "" && letter == ' ' ){
                char key = pattern.charAt(count);

                if (!map.containsKey(key))
                        if (!map.containsValue(word)) {
                            map.put(key, word);
                            wordcount++;
                        }
                        else
                            return false;
                else if (map.containsKey(key))
                    if (!map.get(key).equals(word))
                        return false;
                    else 
                        wordcount++;

                count++;
                word = "";
            }
        }

        if (wordcount != pattern.length())
            return false;

        return true;
    }
}

Pro & Con

✖️ Runtime & Memory

💋 Ideal Answer

Approach

Ok, I did not know there is a library that can split words by " " and store them into the String[]. This lack of knowledge costs me so many lines and runtime.

Here is my new code that BEATS 100%.

New Code

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");

        if (words.length != pattern.length())
            return false;

        HashMap map = new HashMap();

        for (int i = 0; i < words.length; i++) {
            char key = pattern.charAt(i);

            if (!map.containsKey(key) && !map.containsValue(words[i]))
                        map.put(key, words[i]);
            else if (map.containsKey(key) && map.get(key).equals(words[i]))
                continue;
            else
                return false;
        }

        return true;
    }
}

💡 What I Learned

How to separate the string by word and store them in a String[]. String[] words = STRING_NAME.split(" ");

[📝LeetCode #205] Isomorphic Strings

shine — Thu, 26 Jun 2025 00:36:13 +0000

🎀 The Problem

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

Example:

Input: s = "egg", t = "add"
Output: true

Explanation: The strings s and t can be made identical by:
Mapping 'e' to 'a'.
Mapping 'g' to 'd'.

👩‍💻 My Answer

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> map = new HashMap();

        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i)) && !map.containsValue(t.charAt(i)))
                map.put(s.charAt(i), t.charAt(i));
            else if (map.containsKey(s.charAt(i)) && map.get(s.charAt(i)) != t.charAt(i))
                return false;
            else if (!map.containsKey(s.charAt(i)) && map.containsValue(t.charAt(i)))
                return false;
        }

        return true;
    }
}

Pro & Con

✖️ Runtime & Memory

💋 Ideal Answer

Approach

I was not sure, and I am not sure why my code takes a long time, although I use a HashMap. My favorite YouTuber also suggested the HashMap. Nikhil Lohia's Isomorphic Strings (LeetCode 205)

In LeetCode, I found that the array method is faster than HashMap, so I would try with this array method.

New Code

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] slist = new int[256];
        int[] tlist = new int[256];

        for (int i = 0; i < s.length(); i++) {
            if (slist[s.charAt(i)] != tlist[t.charAt(i)])
                return false;

            slist[s.charAt(i)]=i+1;
            tlist[t.charAt(i)]=i+1;
        }

        return true;
    }
}

💡 What I Learned

Why int[256]? A char in Java is 16-bit, but standard ASCII characters only use 7 bits (0-127).

Extended ASCII uses 8 bits (0-255), so int[256] covers all possible ASCII characters.

i + 1 avoids ambiguity with default 0.

[📝LeetCode #242] Valid Anagram

shine — Mon, 23 Jun 2025 00:16:31 +0000

🎀 The Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example:

Input: s = "anagram", t = "nagaram"
Output: true

👩‍💻 My Answer

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;

        HashMap map = new HashMap();

        char counter = 0;
        int scount = 0, tcount = 0;

        while (counter < s.length()) {
            char letter = s.charAt(counter);

            if (!map.containsKey(letter)) {
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) == letter)
                        scount++;
                    if (t.charAt(i) == letter)
                        tcount++;
                }
            }

            if (scount != tcount)
                return false;
            else
                map.put(letter, scount);

            counter++;
        }

        return true;
    }
}

Pro & Con

✖️ Runtime & Memory

💋 Ideal Answer

Approach - "Array"

I watched the YouTube video and found that it's faster if I use int instead of a HashMap. Here is my array method.

New Code

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;

        int[] scount = new int[26];
        int[] tcount = new int[26];

        for (int i = 0; i < s.length(); i++) {
            scount[s.charAt(i)-'a']++;
            tcount[t.charAt(i)-'a']++;
        }

        for (int i = 0; i < 26; i++) {
            if (scount[i] != tcount[i])
                return false;
        }

        return true;
    }
}

This beats only 57%, so I was wondering what the ideal answer is. Then, I found the faster answer in LeetCode problem.

public class Solution {
    public boolean isAnagram(String s, String t) {
        int[] alphabet = new int[26];
        for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++;
        for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--;
        for (int i : alphabet) if (i != 0) return false;
        return true;
    }
}

💡 What I Learned

Use array instead of HashMap to make it faster.
int[] alphabet = new int[26];
I used to use two arrays for s and t. But use ONE instead.
If you find the letter in s, increment;t while the letter in t decreases the count in the array.

[📝LeetCode #383] Ransom Note

shine — Mon, 23 Jun 2025 00:16:13 +0000

🎀 The Problem

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example:

Input: ransomNote = "aa", magazine = "ab"
Output: false

👩‍💻 My Answer

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Integer, Integer> hash = new HashMap();

        for (int i = 0; i < magazine.length(); i++) {
            int letter = magazine.charAt(i);
            if (!hash.containsKey(letter))
                hash.put(letter, 1);
            else
                hash.replace(letter, hash.get(letter) + 1);
        }

        for (int j = 0; j < ransomNote.length(); j++) {
            int letter = ransomNote.charAt(j);

            if (!hash.containsKey(letter))
                return false;

            int value = hash.get(letter);

            if (value == 1)
                hash.remove(letter);
            else
                hash.replace(letter, value - 1);
        }

        return true;
    }
}

Pro & Con

✖️ Runtime & Memory
✖️ Too long

💋 Ideal Answer

Approach - "Two Pointer"

I watched the YouTube video to understand better and realized that there is a way to add the frequency without using if statement to check whether the same character has been added before.

TheAnalyticGuy's Leetcode 383 Ransom Note (Java)

New Code

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Integer, Integer> hash = new HashMap();

        for (int i = 0; i < magazine.length(); i++) {
            int letter = magazine.charAt(i);

            hash.put(letter, hash.getOrDefault(letter, 0) + 1);
        }

        for (int j = 0; j < ransomNote.length(); j++) {
            int letter = ransomNote.charAt(j);

            if (!hash.containsKey(letter))
                return false;

            int value = hash.get(letter);

            if (value == 1)
                hash.remove(letter);
            else
                hash.replace(letter, value - 1);
        }

        return true;
    }
}

It only beats 57.83%. I checked the other solutions on LeetCode, but I could not find a better (efficient) one than this using a HashMap.

💡 What I Learned

How to set the value in HashMap MAP_NAME.put(KEY_NAME, MAP_NAME.getOrDefault(KEY_NAME, 0) + 1);

[📝LeetCode #392] Is Subsequence

shine — Fri, 20 Jun 2025 22:51:32 +0000

🎀 The Problem

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example:

Input: s = "abc", t = "ahbgdc"
Output: true

👩‍💻 My Answer

class Solution {
    public boolean isSubsequence(String s, String t) {
        int current = 0;

        if (s.length() == 0)
            return true;

        for (int i = 0; i < t.length(); i++) {
            if (s.charAt(current) == t.charAt(i)) {
                current++;
            }

            if (current == s.length())
                return true;
        }

        return false;
    }
}

Pro & Con

✖️ Runtime & Memory

💋 Ideal Answer

Approach

I don't really find the better one in the LeetCode solution, but I just find that it is useful to set the return return current == s.length();.

New Code

class Solution {
    public boolean isSubsequence(String s, String t) {
        int current = 0;

        for (int i = 0; i < t.length() && current < s.length(); i++) {
            if (s.charAt(current) == t.charAt(i)) {
                current++;
            }
        }

        return current == s.length();
    }
}

This only beats 66% but I don't think there is a better version of this in Java.

💡 What I Learned

I started to code faster and gain more knowledge of the library.

[📝LeetCode #125] Valid Palindrome

shine — Fri, 20 Jun 2025 22:51:13 +0000

🎀 The Problem

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

👩‍💻 My Answer

class Solution {
    public boolean isPalindrome(String s) {

        s = s.toLowerCase();
        int i = 0;
        int j = s.length() - 1;

        while (i != j && i < s.length()) {

            while (48 > s.charAt(i) || (57 < s.charAt(i) && s.charAt(i) < 97) || s.charAt(i) > 122) {
                i++;

                if (i == s.length())
                    return true;
            }

            while (48 > s.charAt(j) || (57 < s.charAt(j) && s.charAt(j) < 97) || s.charAt(j) > 122) {
                j--;
            }

            if (s.charAt(j) != s.charAt(i))
                return false;

            i++;
            j--;
        }

        return true;
    }
}

Pro & Con

✖️ Runtime & Memory
✖️ Too long
✖️ Bit complicated (Hard to read)

💋 Ideal Answer

Approach

I read the solution post on LeetCode and realized there is a library to check if the char is a letter (Character.isLetterOrDigit())

New Code

class Solution {
    public boolean isPalindrome(String s) {

        s = s.toLowerCase();
        int i = 0;
        int j = s.length() - 1;

        while (i < j) {
            if (!Character.isLetterOrDigit(s.charAt(i))) {
                i++;
            } else if (!Character.isLetterOrDigit(s.charAt(j))) {
                j--;
            } else if (s.charAt(j) != s.charAt(i)) 
                return false;
            else {
                i++;
                j--;
            }
        }
        return true;
    }
}

It does not beat 100%, but this was the most efficient java solution that I found.

💡 What I Learned

How to detect if it's a letter or not
Character.isLetterOrDigit(CHAR_NAME)
How to make string to lower character
STRING_NAME.toLowerCase()

[📝LeetCode #14] Longest Common Prefix

shine — Thu, 12 Jun 2025 00:00:20 +0000

🎀 The 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 "".

Example:

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

👩‍💻 My Answer

class Solution {
    public String longestCommonPrefix(String[] strs) {

        if (strs.length < 2)
            return strs[0];

        String word = strs[0];
        String output = "";
        Boolean check = false;

        for (int i = 1; i < strs.length; i++) {
            String word2 = strs[i];

            if (i % 2 == 0) {
                check = true;
                word = "";
            }
            else if (i % 2 == 1) {
                check = false;
                output = "";
            }

            if (!check) {
                for (int j = 0; j < Math.min(word.length(), word2.length()); j++) {
                    if (word.charAt(j) == word2.charAt(j))
                        output += word.charAt(j);
                    else
                        break;
                }

            } else {
                for (int j = 0; j < Math.min(output.length(), word2.length()); j++) {
                    if (output.charAt(j) == word2.charAt(j))
                        word += output.charAt(j);
                    else
                        break;
                }
            }
        }

        if (!check)
            return output;
            return word;
    }
}

Pro & Con

✖️ Runtime & Memory (OMG it's so slow)
✖️ Too long
✖️ Bit complicated (Hard to read)

💋 Ideal Answer

Approach - "Two Pointer"

I read the solution post on LeetCode and found the two approaches. I will explain by using the example:

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

One approach is:
Set the prefix = first word, so "flower"
Compare the prefix("flower") and next word("flow")
If charAt differs, it substrings to that index (prefix.substring(0, index))

Another one is:
Set the prefix = first word, so "flower"
Use strs[i].indexOf(prefix) to see if strs[i] contains prefix or not.
If not, it reduces the last char of prefix (prefix.substring(0,prefix.length()-1))

I tried both and found that the second one is much faster(Beat 100%) than the first one (Beat 64%). The reason is the first one uses nested loop (SUPER inefficient) while the second one uses indexOf(), which is a highly optimized native method in java!

Here is the second method code:

New Code

class Solution {
    public String longestCommonPrefix(String[] strs) {
        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);
            }
        }

        return prefix;
    }
}

💡 What I Learned

Set the prefix = first word. (Learn a better algorithm)
Avoid nested loops at all costs!

[📝LeetCode #58] Length of Last Word

shine — Sat, 07 Jun 2025 07:08:05 +0000

🎀 The Problem

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

👩‍💻 My Answer

class Solution {
    public int lengthOfLastWord(String s) {
        boolean check = true;
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            char letter = s.charAt(i);
            if (check && letter != ' ')
                count++;
            else if  (!check && letter != ' ') {
                count = 1;
                check = true;
            }
            else
                check = false;
        }

        return count;
    }
}

Pro & Con

✅ Memory
✖️ Runtime

💋 Ideal Answer

Approach

I read the solution post on LeetCode and found it is better to iterate backward because we are looking for the LAST word.

New Code

class Solution {
    public int lengthOfLastWord(String s) {
        int count = 0;

        for (int i = s.length() - 1; i >= 0; i--) {
            char letter = s.charAt(i);
            if (letter != ' ') {
                count++;
            } else if  (count != 0 && letter == ' ')
                return count;
        }
        return count;
    }
}

💡 What I Learned

Iterate backward!!! If you only care about the LAST word, iterate backward! The direction of iteration matters!
ALSO! You don't need boolean to check. You can just use COUNTER (integer) of the letter. If its 0, then ' ' is just the one after the last word. If its more than 0, then ' ' is the one between the second last and last one!

[📝LeetCode #169] Majority Element

shine — Fri, 06 Jun 2025 04:26:23 +0000

🎀 The Problem

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:

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

👩‍💻 My Answer

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

Pro & Con

✅ Super short
🔺 Runtime & Memory
🔺 Not sure I can use Arrays.sort()

💋 Ideal (another) Answer

Approach - "Hash Table"

Tbh, I was quite satisfied with my Sorting method. It's only 2 lines and a unique approach. But I watched the YouTube video about this question.

It is the interview favorite question because it has many methods to solve, and the interviewers can prompt the interviewees to come up with more and more solutions.

Here is the link to the YouTube video that motivates me to learn other methods. I DO recommend watching this;))))
Nikhil Lohia's Merge Sorted Array Explanation

New Code

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap();
        int frequency = -1, i = 0, num = 0;

        if (nums.length == 1)
            return nums[0];

        while (frequecy == -1 || frequency < nums.length/2.0 && i < nums.length) {
            num = nums[i];

            if(!map.containsKey(num))
                map.put(num, 1);
            else {
                frequency = map.get(num)+1;
                map.replace(num, frequency);
            }
            i++;
        }

        return num;
    }
}

BUT it still beats 22% <<<<<< 100%. So, I found the 100% BEAT code in the solution on LeetCode. Here is the code:

class Solution {
    public int majorityElement(int[] nums) {
    int count=0, ret = 0;

    for (int num: nums) {
        if (count == 0) // if the number never appeared before
            ret = num;

        if (num != ret)
            count--;
        else
            count++;
    }

    return ret;
}
}

💡 What I Learned

How to use HashMap in java:

HashMap<Integer, Integer> map = new HashMap();
map.replace(KEY, NEW_VALUE);
map.containsKey(num);

How to categorize number type in java

3/2 -> 1
3/2.0 -> 1.5