Leetcode 112. Path Sum Java Solution

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Problem Solving Approach

• The objective of this problem is to check whether there is a path in the given binary tree from the root to a leaf node whose sum equals the given targetSum.
• Therefore, this code recursively explores paths in the given binary tree and checks if the path sum matches the targetSum.

Algorithm

1. Recursion:
   • The hasPathSum function is called recursively.
   • This function subtracts the value of the current node from targetSum and uses the result as the new targetSum.
2. Base Case:
   • At the start of the recursive call, it checks if the current node is null to determine if it has reached the end of the tree.
   • If it's null, the current path is not valid, so it returns false.
3. Leaf Node Check:
   • It checks if the current node is a leaf node, meaning it has no children.
   • If the current node is a leaf node, it checks if targetSum is equal to 0.
   • If targetSum is 0, it means that the current path's sum matches the targetSum, so it returns true.
4. Recursive Calls for Left and Right Subtrees:
   • If the current node is not a leaf node, it makes recursive calls to the left and right subtrees using the modified targetSum value.
5. Return Result:
   • If either the left or right subtree returns true, it means there exists a path in the current path that satisfies the targetSum, so it returns true.
   • Otherwise, it returns false.

Recursive Function Implementation Table

• Goal: https://leetcode.com/problems/path-sum/

• Base Case (Termination Conditions):

  if root == null
  return false
  
  if left == null && right == null <- after subtracting root.val from sum
  return sum == 0
  

• Is the previous step's result needed?: Yes

• Problem Splitting (Divide the Problem):

  sum -= root.val
  

• Combining Results:

  boolean left
  boolean right
  return left || right
  

• Recursive Calls and Changes Before Moving to the Next Step (Recursive Call):

  sum -= root.val
  

Github Link

https://github.com/eunhanlee/LeetCode_112_PathSum_Solution.git

Time Complexity: O(n), Space Complexity: O(h)

class Solution {

    /**
     * Checks if there is a path from the root to a leaf node in the given binary tree
     * with a sum equal to the target sum.
     *
     * @param root      The root node of the binary tree.
     * @param targetSum The target sum to be achieved.
     * @return Returns `true` if a path exists, `false` otherwise.
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        // Subtract the value of the current node from the target sum.
        targetSum -= root.val;

        // Check if the current node is a leaf node and if the target sum is 0.
        if (root.left == null && root.right == null) {
            return targetSum == 0;
        }

        // Recursively check the left and right subtrees.
        Boolean rightNode = hasPathSum(root.right, targetSum);
        Boolean leftNode = hasPathSum(root.left, targetSum);

        // Return `true` if there is a valid path in either the left or right subtree.
        return rightNode || leftNode;
    }
}

Time Complexity

• The time complexity of this code is O(n) because it visits all nodes in the tree exactly once, where n is the number of nodes in the tree.

Space Complexity

• Due to the recursive function calls, a call stack is built up, but it only requires space up to the height of the tree, so the space complexity is O(h), where h is the height of the tree.

LeetCode 2413. Smallest Even Multiple Java Solution

Problem

Smallest Even Multiple - LeetCode

Solution Approach

• The term "multiple of 2" indicates that the number must be even.
• The term "multiple of n" indicates that the number must be a multiple of n.
• This problem is about finding the smallest even multiple among the multiples of n.
• Initially, I attempted an algorithm where I iterated by incrementing n and returned it if it was even. However, I soon realized that the second multiple of n is always an even number.
• Therefore, the most efficient algorithm is as follows:
  • Check if n is even.
  • If n is even, return n.
  • If n is not even, then the next multiple will always be even.
  • Therefore, return n * 2.

Github Link

https://github.com/eunhanlee/LeetCode_2413_SmallestEvenMultiple_Solution.git

Time Complexity: O(1), Space Complexity: O(1)

public class Solution {
    /**
     * Finds the smallest even multiple of the given number.
     *
     * @param n The number for which the smallest even multiple needs to be found.
     * @return The smallest even multiple of the given number.
     */
    public int smallestEvenMultiple(int n) {
        if (n % 2 == 0) {
            return n;
        } else {
            return n * 2;
        }
    }
}

LeetCode 75. Sort Colors Java Solution

Problem

Sort Colors - LeetCode

Solution Approach

• This problem asks whether you can implement a sorting algorithm without using built-in sorting functions or methods.
• Since the input consists of only 0, 1, and 2, it is possible to solve it using a logic-based algorithm.
• Algorithm:
  • Iterate through all elements and count the occurrences of 0s, 1s, and 2s.
  • Fill the array with 0s, then 1s, and finally 2s based on their counts.
• The "Follow up" asks about the one-pass algorithm known as the Dutch National Flag algorithm, which specializes in sorting 0s and 1s.
• Alternatively, you can implement the Quick Sort algorithm.

References

What is Dutch National Flag algorithm

What is Quick Sort

Github Link

https://github.com/eunhanlee/LeetCode_75_SortColors_Solution.git

Logic Algorithm Time Complexity: O(n), Space Complexity: O(1)

/**
 * The Solution class provides a method to sort an array containing only 0, 1, and 2.
 */
public class Solution {

    /**
     * Sorts the given array using the counting technique. The array should contain only 0, 1, and 2.
     *
     * @param nums The array to be sorted.
     */
    public void sortColors(int[] nums) {
        int Zero = 0, One = 0, Two = 0; // Variables to count the occurrences of 0s, 1s, and 2s
        int idx = 0; // Index to track the position in the array

        // Count occurrences of 0s, 1s, and 2s
        for (int num : nums) {
            if (num == 0) Zero++;
            if (num == 1) One++;
            if (num == 2) Two++;
        }

        // Fill the array with 0s, then 1s, and finally 2s based on their counts
        for (int i = 0; i < Zero; i++) {
            nums[idx] = 0;
            idx++;
        }
        for (int i = 0; i < One; i++) {
            nums[idx] = 1;
            idx++;
        }
        for (int i = 0; i < Two; i++) {
            nums[idx] = 2;
            idx++;
        }
    }
}

Dutch National Flag Algorithm Time Complexity: O(n), Space Complexity: O(1)

public class Solution {
    /**
     * Sorts the given array containing only 0, 1, and 2 using the Dutch National Flag algorithm.
     *
     * @param nums The array to be sorted.
     */
    public void sortColors(int[] nums) {
        int low = 0;  // Pointer to 0
        int mid = 0;  // Pointer to 1
        int high = nums.length - 1;  // Pointer to 2

        while (mid <= high) {
            if (nums[mid] == 0) {
                // If the current element is 0, swap it with the element at the low pointer.
                swap(nums, low, mid);
                low++;  // Increment low pointer
                mid++;  // Increment mid pointer (since the swapped element is 1)
            } else if (nums[mid] == 1) {
                // If the current element is 1, move the mid pointer forward.
                mid++;
            } else if (nums[mid] == 2) {
                // If the current element is 2, swap it with the element at the high pointer.
                swap(nums, mid, high);
                high--;  // Decrement high pointer
                // Note: Here, the mid pointer is not incremented yet as the swapped element's value is uncertain.
            }
        }
    }

    /**
     * Swaps two elements in the array.
     *
     * @param nums The array containing the elements.
     * @param i    Index of the first element to be swapped.
     * @param j    Index of the second element to be swapped.
     */
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Quick Sort Time Complexity: O(n log n), Space Complexity: O()

public class Solution3 {
    /**
     * Sorts the given array using the Quick Sort algorithm.
     *
     * @param nums The array to be sorted.
     */
    public void sortColors(int[] nums) {
        quickSort(nums);
    }

    private static void quickSort(int[] input) {
        quickSortRecur(input, 0, input.length - 1);
    }

    /**
     * Recursively implements Quick Sort using the Lomuto partition scheme.
     * pivot: Rightmost element
     * Starting point for selected value (left): 0
     * Starting point for comparison value (right): 0
     *
     * @param input The array to be sorted.
     * @param left  Starting index of the array to be partitioned.
     * @param right Ending index of the array to be partitioned.
     */
    private static void quickSortRecur(int[] input, int left, int right) {
        // Quick Sort termination condition: array length is 1 or less
        if (left >= right) {
            return;
        }

        // Find the partition point using the Lomuto partition scheme
        int pivotPos = partition(input, left, right);

        // Recursively sort the left partition
        quickSortRecur(input, left, pivotPos - 1);
        // Recursively sort the right partition
        quickSortRecur(input, pivotPos + 1, right);
    }

    /**
     * Swaps the positions of two elements in an array.
     *
     * @param input The array containing the elements.
     * @param a     Index of the first element.
     * @param b     Index of the second element.
     */
    private static void swap(int[] input, int a, int b) {
        int temp = input[a];
        input[a] = input[b];
        input[b] = temp;
    }

    /**
     * Uses the Lomuto partition scheme to partition an array and returns the position of the pivot.
     *
     * @param input The array to be partitioned.
     * @param left  Starting index of the array to be partitioned.
     * @param right Ending index of the array to be partitioned.
     * @return The position of the pivot.

GFG Count the Substrings Java Solution

Problem

Problem_Link

Solution Approach

• Condition: Substrings with an equal number of uppercase and lowercase letters
• If the difference between the uppercase and lowercase letters at the starting and ending positions of a specific substring is the same, then that substring satisfies the condition.

Example: “AbaBBa”

• The total number of substrings for the given example is 21, and the number of substrings that meet the condition is 7.
• To calculate the uppercase-lowercase difference, we use +1 for uppercase and -1 for lowercase letters.
• The starting point has no uppercase-lowercase difference, so it is 0.

Index	None	0	1	2	3	4	5
Element	Start	A	b	a	B	B	a
Uppercase-Lowercase Difference	0	1	0	-1	0	1	0

Substrings with the same uppercase-lowercase difference are considered satisfying the condition.

Substring	Index	Uppercase-Lowercase Difference
Ab	None~2	0
aB	2~4	0
Ba	4~6	0
AbaB	None~4	0
baBB	1~5	0
aBBa	2~6	0
AbaBBa	1~5	1

• The first index is not included, and the last index is included. This is because the starting point is 0, and there is no index for it.

Time Complexity: O(n), Space Complexity: O(n)

import java.util.HashMap;
import java.util.Map;

public class BalancedSubstring {
    public static void main(String[] args) {
        String S = "AbaBBa";
        System.out.println(countSubstring(S));
    }

    public static int countSubstring(String S) {
        int n = S.length();
        int count = 0;
        int diff = 0;
        Map<Integer, Integer> diffMap = new HashMap<>();

        // Initialize diffMap with difference 0
        diffMap.put(0, 1);

        for (int i = 0; i < n; i++) {
            char c = S.charAt(i);

            // Update the uppercase-lowercase difference
            if (Character.isUpperCase(c)) {
                diff++;
            } else if (Character.isLowerCase(c)) {
                diff--;
            }

            // Increase count based on previously encountered difference
            // If the current difference was encountered before, it means there exists a substring with equal counts of uppercase and lowercase letters
            count += diffMap.getOrDefault(diff, 0);

            // Update the current difference and its count in the diffMap
            diffMap.put(diff, diffMap.getOrDefault(diff, 0) + 1);
        }

        return count;
    }
}

Explanation

1. First, initialize a diffMap HashMap. This map is used to store the difference between the counts of uppercase and lowercase letters. Since the initial difference is 0, we add (0, 1) to the map.
2. Use a for loop to iterate through the input string S. The loop runs from index 0 to one less than the length of the string.
3. Retrieve the character c at the current index and determine if it is uppercase or lowercase. If it's uppercase, increment the diff variable by 1; if it's lowercase, decrement diff by 1.
4. If the current difference diff has been encountered before, it means there exists a substring with an equal number of uppercase and lowercase letters. Therefore, add the count of such substrings to the count variable. If the difference hasn't been encountered before, use the getOrDefault method to retrieve 0.
5. Update the diffMap using the current difference diff. If diff already exists in the map, increment its count by 1; if not, add the new difference to the map with a count of 1.
6. After the for loop finishes, return the value stored in count. This value represents the number of substrings that meet the condition of having an equal number of uppercase and lowercase letters.

LeetCode 1672. Richest Customer Wealth Java Solution

Problem

Richest Customer Wealth - LeetCode

Approach

• This problem involves working with a 2D array to calculate the sum of values and optimize based on it.
• Initially, I straightforwardly stored the sum of all values in an array and then found the maximum value by iterating through that array. However, with better optimization, it's possible to directly find the maximum value without needing to store values in an array.
• Algorithm:
  • In the first loop, iterate through each array.
  • In the second loop, calculate the sum of values in each array.
  • After the second loop, compare the sum of values with the current maximum and update it if the sum is higher.
  • Return the stored maximum value.

Github Link

https://github.com/eunhanlee/LeetCode_1672_RichestCustomerWealth_Solution.git

Time Complexity: O(n), Space Complexity: O(1)

public class Solution {
    /**
     * Calculates the maximum wealth among customers.
     *
     * @param accounts 2D array representing customers and their account wealth
     * @return Maximum wealth among customers
     */
    public int maximumWealth(int[][] accounts) {
        int max = 0; // Initialize the maximum wealth as 0.

        for (int[] listOfWealth : accounts) {
            int tempSum = 0; // Initialize temporary sum for each customer.

            for (int wealth : listOfWealth) {
                tempSum += wealth; // Add each account's wealth to the temporary sum.
            }

            max = Math.max(max, tempSum); // Update the maximum wealth if the temporary sum is greater.
        }

        return max;
    }
}

LeetCode 236. Lowest Common Ancestor of a Binary Tree Java Solution

Problem

Lowest Common Ancestor of a Binary Tree - LeetCode

Problem Solution

• This problem asks whether you know about the Lowest Common Ancestor (LCA) and if you can implement it.
• In this problem, the preprocessing step for LCA cannot be used because we cannot modify the tree nodes.
• Therefore, the usual LCA algorithm involves comparing from the two target nodes and going up to their common parent. However, in this problem, we traverse from the root down the tree, comparing each node with nodes p and q to find the LCA.

Reference

What is LCA(Lowest Common Ancestor)

Github Link

https://github.com/eunhanlee/LeetCode_236_LowestCommonAncestorofaBinaryTree_Solution.git

Time Complexity: O(n), Space Complexity: O(n)

n = depth of the binary tree

public class Solution {
    /**
     * Find the lowest common ancestor of two nodes in a binary tree.
     *
     * @param root The root node of the binary tree.
     * @param p    The first node.
     * @param q    The second node.
     * @return The lowest common ancestor of nodes p and q.
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // If the root is null or either p or q is the root, return the root.
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recursively find the lowest common ancestor in the left and right subtrees.
        TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);

        // If both leftLCA and rightLCA are not null, it means p and q are in different subtrees, and the current root is the lowest common ancestor.
        if (leftLCA != null && rightLCA != null) {
            return root;
        }
        // If leftLCA is not null, it means p and q are in the left subtree, and the lowest common ancestor is in the left subtree.
        else if (leftLCA != null) {
            return leftLCA;
        }
        // If rightLCA is not null, it means p and q are in the right subtree, and the lowest common ancestor is in the right subtree.
        else {
            return rightLCA;
        }
    }
}

Code Sequence Example

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

LeetCode 1512. Number of Good Pairs Java Solution

Problem

Number of Good Pairs - LeetCode

Problem Solving Approach

This is a problem that tests your ability to work with nested loops (for loop inside another for loop) and multiple conditions (if statements with the && operator).

Github Link

https://github.com/eunhanlee/LeetCode_1512_NumberofGoodPairs_Solution.git

Time Complexity: O(n^2), Space Complexity: O(k)

class Solution {
    /**
     * Calculates the number of identical pairs in the given array.
     *
     * @param nums An array of integers.
     * @return The number of identical pairs in the array.
     */
    public int numIdenticalPairs(int[] nums) {
        int counter = 0; // A variable to count the number of identical pairs.

        // Iterate through each element of the array.
        for (int i = 0; i < nums.length; i++) {
            // Compare the current element with the rest of the elements in the array.
            for (int j = 0; j < nums.length; j++) {
                // Check if the element at index j is equal to the element at index i
                // and ensure that j is greater than i to avoid duplicates.
                if (nums[j] == nums[i] && j > i) {
                    counter++; // Increment the counter if a good pair is found.
                }
            }
        }

        return counter; // Return the total number of identical pairs in the array.
    }
}

LeetCode 2235. Add Two Integers Java Solution

Problem

Add Two Integers - LeetCode

Problem Solving Approach

• This problem tests the ability to perform simple arithmetic operations and return the result.
• The parentheses () are not necessary to use, considering Java operator precedence.

Reference

Java Operator Precedence

Github Link

https://github.com/eunhanlee/LeetCode_2235_AddTwoIntegers_Solution.git

Time Complexity: O(1), Space Complexity: O(1)

class Solution {
    /**
     * Returns the sum of two integers.
     *
     * @param num1 The first integer.
     * @param num2 The second integer.
     * @return The sum of num1 and num2.
     */
    public int sum(int num1, int num2) {
        return num1 + num2;
    }
}

LeetCode 1431. Kids With the Greatest Number of Candies Java Solution

Problem

Kids With the Greatest Number of Candies - LeetCode

Approach

• Algorithm
  • First, find the maximum value in the given array.
  • Traverse each element in the array, and for each kid, check if adding the extra candies makes their candy count greater than or equal to the maximum count.
  • If it is greater, add true to the result list, otherwise add false.
• There is no need to put candy + extraCandies inside parentheses in the if statement (if(candy + extraCandies < max)). Java operator precedence will handle it correctly without the need for explicit grouping.
• The if statement can be replaced with the ternary operator:

result.add(candy + extraCandies >= max ? true : false);

References

Java Operator Precedence

What is Java Ternary Operator(?:)

Github Link

https://github.com/eunhanlee/LeetCode_1431_KidsWiththeGreatestNumberofCandies_Solution.git

Time Complexity: O(n), Space Complexity: O(n)

/**
 * Determines whether each kid can have the maximum number of candies considering the extra candies.
 *
 * @param candies       An integer array representing the number of candies each kid has.
 * @param extraCandies  The number of extra candies each kid can have.
 * @return              A list of booleans representing whether each kid can have the maximum number of candies.
 */
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
    // Find the maximum number of candies in the given array.
    int max = 0;
    for (int candy : candies) {
        max = Math.max(max, candy);
    }

    // Check if each kid can have the maximum number of candies.
    List<Boolean> result = new ArrayList<>(candies.length);
    for (int candy : candies) {
        // If adding the extra candies makes the current kid's candy count greater than or equal to the maximum count,
        // consider them able to have the maximum number of candies.
        result.add(candy + extraCandies >= max ? true : false);
    }

    return result;
}

LeetCode 217. Contains Duplicate Java Solution

Problem

Problem Link

Time Complexity: O(n), Space Complexity: O(n)

class Solution {
    public boolean containsDuplicate(int[] nums) {
        // Create a HashMap to store the elements of the array.
        HashMap<Integer, Integer> map = new HashMap<>();

        // Traverse all elements in the array.
        for (int temp : nums) {
            // Check if the current element exists in the HashMap.
            if (map.containsKey(temp)) {
                // If it exists, it means there is a duplicate element in the array, so return true.
                return true;
            } else {
                // If it doesn't exist, add the current element to the HashMap.
                // The value '1' is used to indicate the existence of a duplicate element.
                map.put(temp, 1);
            }
        }
        // If there are no duplicate elements, return false.
        return false;
    }
}

Explanation

• HashSet internally uses HashMap. Therefore, you can achieve the same result using HashSet.

What is Java Ternary Operator(?:)

Definition

The question mark operator (? :) is a conditional operator that selects one of two expressions based on the evaluation result of a condition. It can achieve results similar to an if statement.

Structure

if (Condition) { result = expression1; } else { result = expression2; }

result = Condition ? expression1 : expression2;

It is equivalent to an if statement.

Considerations for Use

When using the ternary operator, the following considerations should be taken into account:

Advantages

• Code Conciseness: It allows expressing logic where a value is chosen based on a condition in a single line, enhancing code readability and conciseness.
• Expression Reusability: The selected expression can be assigned to a variable or used as part of other expressions, thus increasing reusability.

Disadvantages

• Readability of Complex Conditions: While the ternary operator is suitable for simple conditions, it may reduce readability for complex condition expressions. In such cases, using if-else statements might be more appropriate.

Step-by-Step Usage

1. Write the condition expression. The condition expression should evaluate to a boolean value (true or false).
2. Follow the condition expression with a question mark (?).
3. Write the expression to be selected if the condition is true, followed by a colon (:).
4. Write the expression to be selected if the condition is false.
5. The result of the ternary operator is the value of the selected expression.

Example

int age = 18;
String message = (age >= 18) ? "You are an adult." : "You are a minor.";

System.out.println(message); // Output: "You are an adult."

In the example above, the value of the age variable is 18 or older, so the condition (age >= 18) evaluates to true. Therefore, the expression1, "You are an adult.", is selected and assigned to the message variable.

LeetCode 42. Trapping Rain Water Java Solution

Problem

Trapping Rain Water - LeetCode

Problem-solving approach

• At least three elements (1, 0, 1) are required to hold water, so we need a minimum of three elements.
• Algorithm

• We find the highest blocks on the left and right sides with respect to the position we want to check.

• 
  
  We can fill water up to the minimum of these two heights.
• Now, we subtract the block's height at the position to get the height of the water that can be filled.

• Repeat the process for all positions.
• To use the above algorithm, we need to loop in advance to get the highest block on the right and left.

• Below, you can see the necessary values for each position.

Github Link

https://github.com/eunhanlee/LeetCode_42_TrappingRainWater_Solution.git

Time Complexity: O(n), Space Complexity: O(n)

public class Solution {
    /**
     * Calculates the amount of water that can be trapped between bars.
     *
     * @param height An array representing the height of the bars
     * @return The total amount of water trapped between bars
     */
    public static int trap(int[] height) {
        int n = height.length;
        if (n <= 2) {
            return 0;
        }

        // An array to store the maximum heights of the bars on the left side of each index
        int[] leftMax = new int[n];
        // An array to store the maximum heights of the bars on the right side of each index
        int[] rightMax = new int[n];
        // A variable to store the total amount of trapped water
        int maxWater = 0;

        // Calculate the maximum heights of the bars on the left side of each index
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        // Calculate the maximum heights of the bars on the right side of each index
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        // Calculate the trapped water for each bar
        for (int i = 1; i < n - 1; i++) {
            // Find the minimum height between the current bar's left and right highest bars
            int minBarHeight = Math.min(leftMax[i], rightMax[i]);
            // If the minimum bar height is greater than the current bar's height,
            // water can be trapped on top of the current bar.
            if (minBarHeight > height[i]) {
                // The trapped water amount is the difference between the minimum bar height and the current bar's height.
                maxWater += minBarHeight - height[i];
            }
        }

        // Return the total amount of trapped water.
        return maxWater;
    }
}

LeetCode 771. Jewels and Stones Java Solution

Problem

Jewels and Stones - LeetCode

Solution Approach

• This problem is about checking whether each character from one input string exists in another input string.
• Since each character needs to be checked at least once, the time complexity is O(n^2), where n is the length of the input string.
• It tests your basic string handling skills.
• To solve it, you need to understand the toCharArray() method and how to compare characters using the char data type in Java.

Java's Primitive Data Types and Reference Data Types

Github Link

https://github.com/eunhanlee/LeetCode_771_JewelsandStones_Solution.git

Time Complexity: O(n^2), Space Complexity: O(1)

class Solution {
    /**
     * Method to count the number of jewels in the stones.
     *
     * @param jewels The string representing types of jewels.
     * @param stones The string representing the stones you have.
     * @return The number of jewels found in the stones.
     */
    public int numJewelsInStones(String jewels, String stones) {
        int counter = 0;

        for (char stone : stones.toCharArray()) {
            for (char jewel : jewels.toCharArray()) {
                if (stone == jewel) {
                    counter++;
                }
            }
        }

        return counter;
    }
}

LeetCode 35. Search Insert Position Java Solution

Problem

Search Insert Position - LeetCode

Problem Solving Approach

• The given problem deals with a sorted array.
• The condition is to solve it in O(log n) time complexity.
• The only method to achieve this in a sorted list is Binary Search.
• This problem tests your understanding of Binary Search and its implementation.
• When implementing Binary Search, you need to decide whether to use recursion or iteration.
• Since this problem does not require previous results or sub-problems, it is more effective to implement it using iteration.
• When the target value is not found, the function should return the index where the target should be inserted.
• The function returns 'low' value because it is closer to the target than 'high', where 'mid' is unchanged and 'mid' divided by 2 and floored is less than or equal to 'high'.

Github Link

https://github.com/eunhanlee/LeetCode_35_SearchInsertPosition_Solution.git

Time Complexity: O(log n), Space Complexity: O(1)

class Solution {
    /**
     * Search for the insertion position of the target value in the given sorted array.
     *
     * @param nums   Sorted integer array.
     * @param target Value to search for.
     * @return The index where the target should be inserted.
     */
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == target)
                return mid; // Return the index if the target value exists.
            else if (nums[mid] < target)
                low = mid + 1; // Move to the right half if the target is greater than the current middle value.
            else
                high = mid - 1; // Move to the left half if the target is less than the current middle value.
        }

        // If the loop exits, it means the target does not exist in the array, and 'low' indicates the insertion position.
        return low;
    }
}

LeetCode 1603. Design Parking System Solution

Problem

Design Parking System - LeetCode

Approach to Problem Solving

• This is a question about object creation in Java.
• The first solution demonstrates basic object creation, making it suitable for collaboration and future updates.
• The second solution is highly efficient for this specific problem, but it might be challenging to update later.

Github Link

https://github.com/eunhanlee/LeetCode_1603_DesignParkingSystem_Solution.git

1st Solution

class ParkingSystem {
    private int bigSlots;
    private int mediumSlots;
    private int smallSlots;

    /**
     * Creates a new ParkingSystem with specified slots for each vehicle type.
     *
     * @param big    Number of available slots for big vehicles.
     * @param medium Number of available slots for medium vehicles.
     * @param small  Number of available slots for small vehicles.
     */
    public ParkingSystem(int big, int medium, int small) {
        this.bigSlots = big;
        this.mediumSlots = medium;
        this.smallSlots = small;
    }

    /**
     * Adds a vehicle of the given type to the parking system.
     *
     * @param carType Type of the vehicle to be parked (1 for big, 2 for medium, 3 for small).
     * @return True if the vehicle is successfully parked, otherwise false.
     */
    public boolean addCar(int carType) {
        switch (carType) {
            case 1:
                if (this.bigSlots > 0) {
                    this.bigSlots--;
                    return true;
                }
                break;
            case 2:
                if (this.mediumSlots > 0) {
                    this.mediumSlots--;
                    return true;
                }
                break;
            case 3:
                if (this.smallSlots > 0) {
                    this.smallSlots--;
                    return true;
                }
                break;
        }
        return false;
    }
}

2nd Solution

class ParkingSystem {
    int[] slots;

    /**
     * Creates a new parking system with given slot sizes.
     *
     * @param big    Number of slots available for big vehicles.
     * @param medium Number of slots available for medium vehicles.
     * @param small  Number of slots available for small vehicles.
     */
    public ParkingSystem(int big, int medium, int small) {
        slots = new int[]{big, medium, small};
    }

    /**
     * Adds a vehicle of the given type to the parking system.
     *
     * @param carType Type of the vehicle to be parked (1 for big, 2 for medium, 3 for small).
     * @return True if the vehicle is successfully parked, otherwise false.
     */
    public boolean addCar(int carType) {
        return --slots[carType - 1] >= 0;
    }
}

Reference

Reasons for Using 'this' Keyword in Java Object Creation

Reasons for Using 'this' Keyword in Java Object Creation

Question

What is the difference between using and not using the 'this' keyword in Java?

Overview

Using and not using the 'this' keyword in Java has differences in preventing variable collisions, method chaining, readability, and clarity.

Reasons

• Preventing variable collisions: When the parameter name of a method is the same as an instance variable, using 'this' helps differentiate between the instance variable and the parameter.
• Method chaining: By returning 'this,' it allows consecutive method calls on the same object.
• Readability and clarity: 'this' provides a clear reference to instance variables or methods, improving code readability and clarity.

Differences

• When using 'this':

public class MyClass {
    private int value;

    public void setValue(int value) {
        this.value = value; // Using the "this" keyword to refer to the instance variable
    }
}

• When not using 'this':

public class MyClass {
    private int value;

    public void setValue(int newValue) {
        value = newValue; // Directly referring to the instance variable
    }
}

Example

Preventing variable collisions

Using the 'this' keyword helps prevent variable collisions when the method's parameter name is the same as an instance variable name.

For example, consider the situation where the 'setValue' method has a parameter named 'value' which is the same as the instance variable 'value':

public class MyClass {
    private int value;

    public void setValue(int value) {
        this.value = value; // Using the "this" keyword to refer to the instance variable
    }
}

In this example, this.value refers to the instance variable, and value refers to the method parameter. This avoids variable collisions and correctly assigns the value to the intended variable.

Method chaining

Using 'this' allows implementing method chaining, which means consecutively calling methods on the same object.

public class MyClass {
    private int value;

    public MyClass setValue(int value) {
        this.value = value;
        return this; // Returning the same object to enable method chaining
    }

    public MyClass printValue() {
        System.out.println(value);
        return this;
    }
}

MyClass obj = new MyClass();
obj.setValue(10).printValue(); // Method chaining

In the above example, the 'setValue' method returns 'this', and the 'printValue' method also returns 'this'. This allows method chaining as shown in the code snippet.

Readability and clarity

However, using the 'this' keyword is not always mandatory. If a method does not reference instance variables and only uses parameters, the 'this' keyword can be omitted.

public class MyClass {
    public void printName(String name) {
        System.out.println("Hello, " + name);
    }
}

When not using 'this' to refer to instance variables or methods, it is assumed that those variables or methods belong to the current object. This may introduce some ambiguity in readability and clarity. Therefore, the 'this' keyword should be used when necessary, based on the readability and purpose of the code.

Conclusion

Using the 'this' keyword helps prevent variable collisions, enables method chaining, and improves code readability and clarity. However, it is not always mandatory, and the decision to use 'this' depends on the specific context and requirements.

LeetCode 116. Populating Next Right Pointers in Each Node Java Solution

Problem

Populating Next Right Pointers in Each Node - LeetCode

Approach

• Given a basic tree, the task is to connect its nodes.
• Essentially, we need an algorithm to traverse the tree in level order and connect each node accordingly.
  • The problem assumes a perfect binary tree, meaning there are no empty nodes.
  • At level 1, connect all nodes at level 2.
  • Set the level's leftmost node as levelStart.
  • Connect the next node with its sibling (since the upper level is already connected, moving is easy).
  • If the next node's left child does not exist, it means the current level is fully connected.
• BFS (level order) or recursive function can be used.
• Recursive functions are often used when they can simplify complex tasks. However, this problem only requires a simple level order traversal without the need for previous calculated values, making recursion unnecessary.
• Moreover, if the tree is large, there is a possibility of a stack overflow, so it's better to avoid recursion.

Github Link

https://github.com/eunhanlee/LeetCode_116_PopulatingNextRightPointersinEachNode_Solution.git

Time Complexity: O(n), Space Complexity: O(1)

class Solution {
    /**
     * Connects each node of the given binary tree with its right pointer.
     *
     * @param root The root node of the binary tree
     * @return The root node of the connected binary tree
     */
    public Node connect(Node root) {
        if (root == null)
            return null;

        // The leftmost node of the level
        Node levelStart = root;

        while (levelStart.left != null) {
            // Current node
            Node curr = levelStart;

            while (curr != null) {
                // Set the left child's next pointer to the right child
                curr.left.next = curr.right;
                // Set the right child's next pointer to the left child of the next node
                if (curr.next != null) curr.right.next = curr.next.left;
                // Move to the next node in the same level
                curr = curr.next;
            }

            // Move to the leftmost node of the next level
            levelStart = levelStart.left;
        }

        return root;
    }
}

LeetCode 2114. Maximum Number of Words Found in Sentences Java Problem Solving

 

Problem

Maximum Number of Words Found in Sentences - LeetCode

Solution Approach

• This problem is about counting the number of words in a sentence and finding the maximum count among all sentences.

• You should be familiar with loops, counting words, and finding the maximum value to solve this problem.

• Algorithm:

  • Use a loop to iterate through each sentence.

  • Calculate the number of words in each sentence.

  • Compare the word counts to find the maximum value.

• There are several ways to achieve this, such as different types of loops (for loop, while loop, advanced for loop), word counting methods (using split to split the sentence and count the words, or using character arrays to find the number of spaces and adding 1), and finding the maximum value (using if statements for comparison, using the ternary operator ? for comparison, or using Math.max).

• The provided code uses an advanced for loop, split method to count words, and Math.max for comparison to solve the problem.

Github Link

https://github.com/eunhanlee/LeetCode_2114_MaximumNumberofWordsFoundinSentences_Solution

Time Complexity: O(nm), Space Complexity: O(1)

public class Solution {
    /**
     * Finds the maximum number of words in the given array of sentences.
     *
     * @param sentences An array of strings representing sentences.
     * @return The maximum number of words found in any sentence.
     */
    public int mostWordsFound(String[] sentences) {
        int max = 0;

        for (String sentence : sentences) {
            max = Math.max(max, sentence.split(" ").length);
        }

        return max;
    }
}

136. Single Number Problem Solved: Uncover the Most Efficient Java Algorithm

Problem

Problem_Link

Problem Solving Approach

• Find the single number in an array with a linear runtime complexity of O(n) and use only constant extra space with a complexity of O(1).
• One possible approach is to use a hash map to keep track of the frequency of each number, but this requires extra space proportional to the size of the array, which violates the space complexity constraint.
• Since O(n) and O(2n) have the same complexity of O(n), we can use a sorting algorithm to sort the array and then compare adjacent elements to find the single number.
• The approach can be summarized as follows:
  • Sort the array.
  • Iterate through the array and compare each pair of adjacent elements.
  • If the two elements are not equal, the first element is the single number, so return its value.
• This algorithm has a linear runtime complexity of O(n) and uses only constant extra space with a complexity of O(1).

Time O(n), Space O(1)

https://github.com/eunhanlee/leetcode_136_Single_Number

import java.util.*;

class Solution {
    /**
     * This method finds the single number in an integer array.
     *
     * @param nums an integer array
     * @return the single number
     * @throws NoSuchElementException if the single number is not found
     */
    public int singleNumber(int[] nums) {
        // Sort the given array
        Arrays.sort(nums);
        // Compare consecutive pairs of elements
        for (int i = 0; i < nums.length; i += 2) {
            // If the two elements are different, the first one is the single number, so return its value.
            if (i == nums.length - 1) return nums[i];
            else if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }

        // If the single number is not found until the end of the array, throw a NoSuchElementException.
        // Note that leetcode does not allow throwing a NoSuchElementException.
        // However, since the problem guarantees the existence of a single number, you can replace this line with 'return 0;'.
        throw new NoSuchElementException();
    }
}

118. Pascal's Triangle Problem Solved: Uncover the Most Efficient Java Algorithm

 

Problem

Problem_Link

Problem Solving Approach

1. Possible cases

   if startpos or endpos, add end
   else currpos = lastList[prevpos+currpost]
   

2. Requirements: Previous row list, Previous row list length or current row length

3. Be careful: In Java, add() method for list is a shallow copy by default.

4. That is, if you put 1 for the first and last elements in each list and add the sum of two elements above it in the previous row to the current list, Pascal's triangle will be generated.

Time O(n), Space O(n)

https://github.com/eunhanlee/leetcode_118PascalsTriangle

import java.util.*;

class Solution {
    /**
     * This method generates Pascal's triangle up to a given number of rows.
     *
     * @param numRows the number of rows to generate
     * @return a list of lists representing the rows of Pascal's triangle
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>(); // Create a new list to hold the triangle
        List<Integer> currList = null; // Initialize the current list
        List<Integer> prevList = null; // Initialize the previous list

        for (int i = 0; i < numRows; i++) { // Loop through each row
            currList = new ArrayList<>(); // Create a new list for the current row
            for (int j = 0; j < (i + 1); j++) { // Loop through each element in the current row
                if (j == 0 || j == i) currList.add(1); // The first and last elements are always 1
                else {
                    // Calculate the element as the sum of the two elements above it in the previous row
                    currList.add(prevList.get(j - 1) + prevList.get(j));
                }
            }
            prevList = currList; // Set the current row as the previous row for the next iteration
            result.add(currList); // Add the current row to the result list
        }

        return result; // Return the completed Pascal's triangle
    }

}

Explanation

• If you want to use a pre-declared list, you need to perform deep copy as follows:

//            prevList.clear();
//            prevList.addAll(currList);
//            result.add(List.copyOf(currList));
//            currList.clear();