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.

Java Operator Precedence

Java Operator Precedence Table

Operator Precedence Definition

Operator precedence is not about calculating operations based on priority. When there are multiple operators in a complex expression, operator precedence is used to group them.

This does not determine the order of execution of operations.

Example

Suppose we have the following expression, and the computer needs to decide whether to evaluate a > 0 first or 0 && b.

int a = 1, b = 1;
a > 0 && b - ++a == 1;

Following the Java Operator Precedence Table, we start grouping the expression:

a > 0 && b - ++a == 1;

a > 0 && b - (++a) == 1;

a > 0 && (b - (++a)) == 1;

a > 0 && (b - (++a)) == 1;

(a > 0) && (b - (++a)) == 1;

(a > 0) && ((b - (++a)) == 1);

Now, we evaluate the Logical AND from left to right:

(1 > 0) && ((b - (++a)) == 1);

true && ((b - (++a)) == 1);

true && ((b - (++1)) == 1);

Next, we apply the pre-Increment unary operator, increasing the operand's value by 1 before other calculations:

true && ((b - 2) == 1);

true && ((1 - 2) == 1);

true && (-1 == 1);

true && false;

false;

Increment and Decrement Operators

Operator	Description
++A	Increases the operand's value by 1 before other calculations
--A	Decreases the operand's value by 1 before other calculations
A++	Increases the operand's value by 1 after other calculations
A--	Decreases the operand's value by 1 after other calculations

Logical OR Operator

The logical OR operator (||) evaluates expressions from left to right. If the first expression is true, it doesn't evaluate the second expression, as only one true result is required.

(1 == 1) || (1 == 2);

In the above case, (1 == 1) is true, so (1 == 2) is not evaluated, and the result is immediately true.

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;
    }
}