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.

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.

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

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();

48. Rotate Image Problem Solved: Uncover the Most Efficient Java Algorithm

 

Problem

Problem_Link

Problem Solving Approach

1. "Rotating a position" means that each position has a designated position to be moved to.

2. For example, when n is 3:

   (0,0)->(0,2)
   (0,2)->(2,2)
   (2,2)->(2,0)
   (2,0)->(0,0)
   
   (0,1)->(1,2)
   (1,2)->(2,1)
   (2,1)->(2,1)
   (1,0)->(0,1)
   

3. The above rule can be calculated by how far it is from n.

   First loop
   n=3
   Distance from the y-axis = i = 0
   Distance from the x-axis = j = 0
   
   Starting point = (i,(i+distance from the x axis)) = (0,0)
   ((n-1-distance from the x axis-distance from the y axis),i)=((3-1-0-0),0)=(2,0)
   ((n-1-distance from the y axis),(n-1-distance from the x axis-distance from the y axis))=((3-1-0),(3-0-1-0))=(2,2)
   (((i+distance from the x axis)),(n-1-distance from the y axis))=((0+0),(3-1-0))=(0,2)
   
   Second loop
   n=3
   Distance from the y-axis = i = 0
   Distance from the x-axis = j = 1
   
   Starting point = (i,(i+distance from the x axis)) = (0,1)
   ((n-1-distance from the x axis-distance from the y axis),i)=((3-1-1-0),0)=(1,0)
   ((n-1-distance from the y axis),(n-1-distance from the x axis-distance from the y axis))=((3-1-0),(3-1-1-0))=(2,1)
   (((i+distance from the x axis)),(n-1-distance from the y axis))=((0+1),(3-1-0))=(1,2)
   

4. first loop only half of all and second loop inside the first loop should skip as first lopped

5. For example, when n is 3:

   (0,0) (0,1) (0,2)
   (1,0) (1,1) (1,2)
   (2,0) (2,1) (2,2)
   

   Only (0,0) and (0,1) should be included in the loop.

6. For example, when n is 4:

   (0,0) (0,1) (0,2) (0,3)
   (1,0) (1,1) (1,2) (1,3)
   (2,0) (2,1) (2,2) (2,3)
   (3,0) (3,1) (3,2) (3,3)
   

   Only (0,0), (0,1), (0,2), (1,1), and (1,2) should be included in the loop.

7. In order to determine which elements to swap in each rotation, we can calculate the distance that each element has from the outermost layer of the matrix.

8. For example, if n is 3, the first rotation involves swapping elements at position (0,0), (0,2), (2,2), and (2,0). The second rotation involves swapping elements at position (0,1), (1,2), (2,1), and (1,0). We can see that the distance that each element has from the outermost layer of the matrix corresponds to the number of rotations it needs to undergo.

9. To implement this, we can use two nested loops. The outer loop iterates from 0 to n/2 - 1, since we only need to perform rotations for the first n/2 layers of the matrix. The inner loop iterates from the current layer (i) to n - i - 2, since we only need to perform rotations within the current layer.

10. Using these loops, we can determine the four elements that need to be rotated in each step, and then swap them accordingly.

11. Therefore, the time complexity of this solution is O(n^2), since we need to visit every element in the matrix. The space complexity is also O(1), since we are performing the rotations in-place.

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

https://github.com/eunhanlee/leetcode_48_Rotate_Image

class Solution {
    /**
     * Rotates a 2D array clockwise by 90 degrees.
     * @param matrix a 2D array
     */
    public void rotate(int[][] matrix) {
        // Get the last position in the array (subtract 1 since the array is zero-indexed)
        int lastPos = matrix.length - 1;
        // Only loop through half of the array's length for i since each iteration swaps two values
        int i_loop = matrix.length / 2;
        for (int i = 0; i < i_loop; i++) {
            // j_loop determines how many values to swap based on the current i index
            int j_loop = lastPos - 2 * i;
            for (int j = 0; j < j_loop; j++) {
                setNewPos(matrix, i, j, lastPos);
            }
        }
    }

    /**
     * Swaps the value at the current position with the value 90 degrees clockwise from it.
     * @param matrix a 2D array
     * @param i the row index of the current position
     * @param j the column index of the current position
     * @param lastPos the last index of the array
     */
    public static void setNewPos(int[][] matrix, int i, int j, int lastPos) {
        // Swaps the value at the current position with the value 90 degrees clockwise from it.
        // (i,j) -> (lastPos-i-j,i) -> (lastPos-i,lastPos-i-j) -> (j,lastPos-i) -> (i,j)

        int temp = matrix[i][i + j];
        matrix[i][i + j] = matrix[lastPos - i - j][i];
        matrix[lastPos - i - j][i] = matrix[(lastPos - i)][lastPos - i - j];
        matrix[(lastPos - i)][lastPos - i - j] = matrix[i + j][(lastPos - i)];
        matrix[i + j][(lastPos - i)] = temp;
    }
}

Problem Solving Approach2

1. Rotating a matrix by 90 degrees can be difficult, but flipping it is easy.
2. If we flip a matrix along its diagonal, and then flip it horizontally, this is equivalent to rotating it by 90 degrees.

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

https://github.com/eunhanlee/leetcode_48_Rotate_Image

public class Solution {
    /**
     * Rotates a 2D array clockwise by 90 degrees.
     *
     * @param matrix a 2D array
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Flip the array diagonally.
        for (int i = 0; i < n; i++) {
            // j should start from i, since elements below the diagonal have already been swapped.
            for (int j = i; j < n; j++) {
                int temp = 0;
                temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // Flip each row horizontally.
        for (int i = 0; i < n; i++) {
            // j should be less than n/2, since flipping beyond the middle would cause duplicates.
            for (int j = 0; j < n / 2; j++) {
                int temp = 0;
                temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

22. Generate Parentheses Problem Solved: Uncover the Most Efficient Java Algorithm

Problem

Problem_Link

Problem Solving Approach

• To generate all combinations, typically use recursive function DFS.
• Must open ‘(’ and then close ‘)’ to get valid combinations only (backtracking algorithm).
  • if (open < length)
  • if (close < open)
• When the length of the string becomes twice of n, it's the end of the recursion (base case).

Time O((2^n) / 2**)=O(4^n/sqrt(n)), Space O((2^n) / 2)**

https://github.com/eunhanlee/leetcode_22.GenerateParentheses/blob/master/README.md

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * Generates all combinations of well-formed parentheses.
     *
     * @param n the number of pairs of parentheses
     * @return a list of all combinations of well-formed parentheses
     */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateParenthesisRecur(result, "", 0, 0, n);
        return result;
    }

    /**
     * Generates all combinations of well-formed parentheses using recursion.
     *
     * @param result the list of generated combinations
     * @param currentString the current string being built
     * @param open the number of open parentheses in the current string
     * @param close the number of close parentheses in the current string
     * @param len the desired length of the current string
     */
    private void generateParenthesisRecur(List<String> result, String currentString, int open, int close, int len) {
        if (currentString.length() == len * 2) {
            result.add(currentString);
            return;
        }

        if (open < len) {
            generateParenthesisRecur(result, currentString + "(", open + 1, close, len);
        }
        if (close < open) {
            generateParenthesisRecur(result, currentString + ")", open, close + 1, len);
        }
    }
}

Explanation

• The total number of combinations is 2^n, but this is reduced to half by the backtracking algorithm. Therefore, the time complexity is O(2^(2n)/2) = O(4^n/sqrt(n)).

94. Binary Tree Inorder Traversal Problem Solved: Uncover the Most Efficient Java Algorithm

Problem

Problem_Link

Problem Solving Approach

• To traverse a binary tree in in-order, we use depth-first search (DFS).
• The problem also requires us to solve it using a simple loop, so it tests our ability to convert between while loops and recursive calls.

Time O(n), Space O(n)

https://github.com/eunhanlee/leetcode_94.BinaryTreeInorderTraversal_Solution/blob/master/README.md

import java.util.*;

class Solution {

    /**
     * Traverses a binary tree in-order recursively and returns a list of node values.
     *
     * @param root the root node of the binary tree to traverse
     * @return a list of node values in in-order traversal order
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        // Call the recursive function to traverse the tree in-order
        inorderRecur(root, list);
        // Return the resulting list
        return list;
    }

    /**
     * Helper method that recursively traverses a binary tree in-order and adds node values to a list.
     *
     * @param root the root node of the binary tree to traverse
     * @param list the list to add node values to
     */
    public static void inorderRecur(TreeNode root, List<Integer> list) {
        // Base case: if the node is null, return immediately
        if (root == null) return;

        // Traverse the left subtree recursively
        inorderRecur(root.left, list);

        // Add the current node value to the list
        list.add(root.val);

        // Traverse the right subtree recursively
        inorderRecur(root.right, list);
    }

    /**
     * Traverses a binary tree in-order iteratively and returns a list of node values.
     *
     * @param root the root node of the binary tree to traverse
     * @return a list of node values in in-order traversal order
     */
    public List<Integer> inorderTraversalIterative(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;

        while (node != null || !stack.isEmpty()) {
            // Add nodes in the left subtree to the stack
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            // Pop a node from the stack, set it as the current node, and add its value to the list
            node = stack.pop();
            list.add(node.val);

            // Move to the right subtree
            node = node.right;
        }

        return list;
    }
}