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)).

Determining Whether a Number is a Fibonacci Number in Java: A Quick Guide

 

Definition

A sequence of numbers that follows a specific pattern. The first two numbers are always 0 and 1, and the third number is the sum of the first and second numbers.

Example of Fibonacci sequence

1,1,2,3,5,8,13,21,34,55...

Examples

Index	Fibonacci Number	Calculation
0	0	0
1	1	1
2	1	0+1
3	2	1+1
4	3	1+2
5	5	2+3
6	8	3+5
7	13	5+8
8	21	8+13
9	34	13+21
10	55	21+34
11	89	34+55
12	144	55+89
13	233	89+144
14	377	144+233
15	610	233+377
16	987	377+610

How to find the Fibonacci number at a specific index

Mathematical (Binet’s simplified formula)

    public static int fib(int num) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int) Math.round(Math.pow(goldenRatio, num) / Math.sqrt(5));
    }

Recursive Function

    public static int fibRecursive(int num) {
        if (num == 0) return 0;
        else if (num == 1) return 1;
        else return fibRecursive(num - 2) + fibRecursive(num - 1);
    }

Loop

    public static int fib(int num) {
        if (num == 0) return 0;
        else if (num == 1) return 1;

        else {
            int result = 0;
            int iterA = 0;
            int iterB = 1;

            for (int i = 2; i <= num; i++) {

                result = iterA + iterB;
                iterA = iterB;
                iterB = result;

            }

            return result;
        }

    }

How to determine if a number is a Fibonacci number

If a number is a Fibonacci number, then either one or both of the expressions below will result in a perfect square:

Perfect Square

When x is a perfect square,

where root{x} must be an integer.

For example, 9 is a perfect squa

Mastering Graphs and Trees: Essential Concepts and Traversal Techniques

preorder = root left right
DFS use stack = inorder= left root right
postorder = left right root
BFS use queue = print each level

Graph

• Used to represent various real-world scenarios such as social networks, transportation systems, and computer networks.
• A collection of nodes or vertices connected by edges.
• Edges represent relationships or connections between nodes.
• Edges can be directed or undirected.
• Cycles (paths with the same starting and ending points) may be present.

Graph Terminology

• Node: A single vertex in a graph or tree. Nodes can contain data or objects and are connected to other nodes through edges.
• Edge: A line representing a connection between nodes in a graph or tree. Edges can be directed or undirected.
• Depth: The length of the path from a node to the root node. The depth of a specific node is the number of edges connecting it to the root node. In a tree, the root node has a depth of 0, and the depth increases by 1 for each subsequent level.
• Breadth: Although not typically used in the context of trees, breadth is a term used in breadth-first search (BFS). Nodes at the same level (depth) in the tree are visited "all at once" in BFS, which is why the term "breadth" is used. Therefore, in BFS, "breadth" refers to the level (depth) of a node in the tree, not the order of traversal.

Example

Traversal Methods

Graph traversal is generally tailored to recursive functions.

DFS Depth-First Search

• Push the starting node 1 into the stack.
• The stack currently contains [1].
• Pop node 1 from the stack and print it.
• The stack currently contains [].
• Following edges a, b, and c connected to node 1, push nodes 2, 3, and 5 into the stack.
• The stack currently contains [5, 3, 2].
• Pop node 2 from the stack and print it.
• The stack currently contains [5, 3].
• Following edge d connected to node 2, push node 3 into the stack.
• The stack currently contains [5, 3, 3].
• Pop node 3 from the stack and print it.
• The stack currently contains [5, 3].
• Following edges e and f connected to node 3, push nodes 4 and 5 into the stack.
• The stack currently contains [5, 4, 5].
• Pop node 5 from the stack and print it.
• The stack currently contains [4].
• Following edge g connected to node 5, push node 4 into the stack.
• The stack currently contains [4, 4].
• Pop node 4 from the stack and print it.
• The stack currently contains [].
• As there are no more nodes to pop from the stack, the DFS traversal ends.

BFS (Breadth-First Search)

• Insert the starting node 1 into the queue.
• The queue now contains [1].
• Remove node 1 from the queue and print it.
• The queue now contains [].
• Traverse the edges a, b, and c connected to node 1 and insert nodes 2, 3, and 5 into the queue, respectively.
• The queue now contains [2, 3, 5].
• Remove node 2 from the queue and print it.
• The queue now contains [3, 5].
• Traverse the edge d connected to node 2 and insert node 3 into the queue.
• The queue now contains [3, 5, 3].
• Remove node 3 from the queue and print it.
• The queue now contains [5, 3].
• Traverse the edges e and f connected to node 3 and insert nodes 4 and 5 into the queue, respectively.
• The queue now contains [5, 3, 4, 5].
• Remove node 5 from the queue and print it.
• The queue now contains [3, 4, 5].
• Traverse the edge g connected to node 5 and insert node 4 into the queue.
• The queue now contains [3, 4, 3].
• Remove node 3 from the queue and print it.
• The queue now contains [4, 3].
• Node 5 connected to node 3 has already been inserted into the queue, so it is ignored.
• Remove node 4 from the queue and print it.
• The queue now contains [3].
• Remove node 3 from the queue and print it.
• The queue now contains [].
• Since there are no more nodes to be removed from the queue, the BFS search is complete.

Tree

• Used to represent hierarchical structures such as file systems, organization charts, and family trees.
• A type of graph.
• There is only one path between any two nodes.
• There are no cycles (paths that start and end at the same node).

Tree Terminology

• Branch: An edge that connects a node in a tree to a root or another node. There can be multiple branches between a root and another node.
• Root: The topmost node in a tree. Every other node is either a branch starting from the root or a leaf node.
• Leaf: The final node in a tree that has no children. It is the last node that does not extend to any other node.
• Parent: A node in a tree that has one or more child nodes. It is the node located above the current node when following the edges of the tree towards the root.
• Child: A node in a tree that has a parent node. It is the node located below the current node when following the edges of the tree towards the leaves.

Example

Tree Traversal Methods

Preorder (Preorder Traversal)

Preorder traversal is a method where the root node is visited first. That is, after printing the root node, traverse the left subtree, and then the right subtree. Preorder traversal visits nodes in the following order:

1. Root node
2. Left subtree
3. Right subtree

• Example: Preorder: 1 2 4 5 8 9 3 6 7

Inorder (Inorder Traversal)

Inorder traversal is a method where the root node is visited in the middle. That is, after traversing the left subtree, print the root node, and then traverse the right subtree. Inorder traversal visits nodes in the following order:

1. Left subtree
2. Root node
3. Right subtree

• Example: Inorder: 4 2 8 5 9 1 6 3 7

Postorder (Postorder Traversal)

Postorder traversal is a method where the root node is visited last. That is, after traversing the left subtree and the right subtree, print the root node. Postorder traversal visits nodes in the following order:

1. Left subtree
2. Right subtree
3. Root node

• Example: Postorder: 4 8 9 5 2 6 7 3 1

Understanding these traversal methods is essential for solving various tree-related problems in computer science. Each traversal method has its unique use-cases and can be applied according to the requirements of a specific problem.

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

Powerfull Integer Problem Solved: Uncover the Most Efficient Java Algorithm

 

Problem

Problem_Link

Problem Solving Approach

1. Traverse through all the numbers in the intervals and store their frequencies in a HashMap.
2. Sort the hashmap based on the keys.→in worst case, O(n log n)
3. Find the maximum powerful integer by iterating through the sorted hashmap, which occurs at least k times.

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

https://github.com/eunhanlee/powerfullInteger/blob/master/read%20me.md

import java.util.*;
class Solution {

    /**
     * This method takes in the number of intervals n, the 2D integer array of intervals interval, and the minimum number of occurrences k for a number to be considered powerful.
     * It returns the powerful integer which occurs at least k times. If multiple integers have at least k occurrences, the maximum integer out of all those elements is returned.
     * If no integer occurs at least k times, -1 is returned.
     *
     * @param n         the number of intervals
     * @param interval  the 2D integer array of intervals where interval[i] = [start, end]
     * @param k         the minimum number of occurrences for a number to be considered powerful
     * @return the powerful integer which occurs at least k times, or -1 if no integer occurs at least k times
     */
    public static int powerfullInteger(int n, int[][] interval, int k) {
        // A hashmap to store the frequency of each number
        Map<Integer, Integer> map = new HashMap<>();
        // The maximum powerful integer that occurs at least k times, if there is no, return -1
        int maxPowerful = -1;

        // Loop through each interval and update the frequency of each number in the hashmap
        for (int i = 0; i < n; i++) {
            for (int j = interval[i][0]; j <= interval[i][1]; j++) {
                map.put(j, map.getOrDefault(j, 0) + 1);
            }
        }

        // Sort the hashmap by key
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Map.Entry.comparingByKey());

        // find the maximum powerful integer
        for (Map.Entry<Integer, Integer> val : list) {
            if (val.getValue() >= k) {
                maxPowerful = val.getKey();
            }
        }

        return maxPowerful;
    }
}

Ascii Table

 Decimal ASCII table

Octal Ascii Table

Hexadecimal Ascii Table

Hex	Oct	Dec	Char
0	0	0	Ctrl-@ NUL
1	1	1	Ctrl-A SOH
2	2	2	Ctrl-B STX
3	3	3	Ctrl-C ETX
4	4	4	Ctrl-D EOT
5	5	5	Ctrl-E ENQ
6	6	6	Ctrl-F ACK
7	7	7	Ctrl-G BEL
8	10	8	Ctrl-H BS
9	11	9	Ctrl-I HT
0A	12	10	Ctrl-J LF
0B	13	11	Ctrl-K VT
0C	14	12	Ctrl-L FF
0D	15	13	Ctrl-M CR
0E	16	14	Ctrl-N SO
0F	17	15	Ctrl-O SI
10	20	16	Ctrl-P DLE
11	21	17	Ctrl-Q DCI
12	22	18	Ctrl-R DC2
13	23	19	Ctrl-S DC3
14	24	20	Ctrl-T DC4
15	25	21	Ctrl-U NAK
16	26	22	Ctrl-V SYN
17	27	23	Ctrl-W ETB
18	30	24	Ctrl-X CAN
19	31	25	Ctrl-Y EM
1A	32	26	Ctrl-Z SUB
1B	33	27	Ctrl-[ ESC
1C	34	28	Ctrl- FS
1D	35	29	Ctrl-] GS
1E	36	30	Ctrl-^ RS
1F	37	31	Ctrl_ US
20	40	32	Space
21	41	33	!
22	42	34	"
23	43	35	#
24	44	36	$
25	45	37	%
26	46	38	&
27	47	39	'
28	50	40	(
29	51	41	)
2A	52	42	*
2B	53	43	+
2C	54	44	,
2D	55	45	-
2E	56	46	.
2F	57	47	/
30	60	48	0
31	61	49	1
32	62	50	2
33	63	51	3
34	64	52	4
35	65	53	5
36	66	54	6
37	67	55	7
38	70	56	8
39	71	57	9
3A	72	58	:
3B	73	59	;
3C	74	60	<
3D	75	61	=
3E	76	62	>
3F	77	63	?
40	100	64	@
41	101	65	A
42	102	66	B
43	103	67	C
44	104	68	D
45	105	69	E
46	106	70	F
47	107	71	G
48	110	72	H
49	111	73	I
4A	112	74	J
4B	113	75	K
4C	114	76	L
4D	115	77	M
4E	116	78	N
4F	117	79	O
50	120	80	P
51	121	81	Q
52	122	82	R
53	123	83	S
54	124	84	T
55	125	85	U
56	126	86	V
57	127	87	W
58	130	88	X
59	131	89	Y
5A	132	90	Z
5B	133	91	[
5C	134	92	￦
5D	135	93	]
5E	136	94	^
5F	137	95	_
60	140	96	`
61	141	97	a
62	142	98	b
63	143	99	c
64	144	100	d
65	145	101	e
66	146	102	f
67	147	103	g
68	150	104	h
69	151	105	i
6A	152	106	j
6B	153	107	k
6C	154	108	l
6D	155	109	m
6E	156	110	n
6F	157	111	o
70	160	112	p
71	161	113	q
72	162	114	r
73	163	115	s
74	164	116	t
75	165	117	u
76	166	118	v
77	167	119	w
78	170	120	x
79	171	121	y
7A	172	122	z
7B	173	123	{
7C	174	124	|
7D	175	125	}
7E	176	126	~
7F	177	127	DEL

Hexadecimal Ascii Table

 Decimal ASCII table

Octal Ascii Table

Ascii Table

0	Ctrl-@ NUL
1	Ctrl-A SOH
2	Ctrl-B STX
3	Ctrl-C ETX
4	Ctrl-D EOT
5	Ctrl-E ENQ
6	Ctrl-F ACK
7	Ctrl-G BEL
8	Ctrl-H BS
9	Ctrl-I HT
0A	Ctrl-J LF
0B	Ctrl-K VT
0C	Ctrl-L FF
0D	Ctrl-M CR
0E	Ctrl-N SO
0F	Ctrl-O SI
10	Ctrl-P DLE
11	Ctrl-Q DCI
12	Ctrl-R DC2
13	Ctrl-S DC3
14	Ctrl-T DC4
15	Ctrl-U NAK
16	Ctrl-V SYN
17	Ctrl-W ETB
18	Ctrl-X CAN
19	Ctrl-Y EM
1A	Ctrl-Z SUB
1B	Ctrl-[ ESC
1C	Ctrl- FS
1D	Ctrl-] GS
1E	Ctrl-^ RS
1F	Ctrl_ US
20	Space
21	!
22	"
23	#
24	$
25	%
26	&
27	'
28	(
29	)
2A	*
2B	+
2C	,
2D	-
2E	.
2F	/
30	0
31	1
32	2
33	3
34	4
35	5
36	6
37	7
38	8
39	9
3A	:
3B	;
3C	<
3D	=
3E	>
3F	?
40	@
41	A
42	B
43	C
44	D
45	E
46	F
47	G
48	H
49	I
4A	J
4B	K
4C	L
4D	M
4E	N
4F	O
50	P
51	Q
52	R
53	S
54	T
55	U
56	V
57	W
58	X
59	Y
5A	Z
5B	[
5C	￦
5D	]
5E	^
5F	_
60	`
61	a
62	b
63	c
64	d
65	e
66	f
67	g
68	h
69	i
6A	j
6B	k
6C	l
6D	m
6E	n
6F	o
70	p
71	q
72	r
73	s
74	t
75	u
76	v
77	w
78	x
79	y
7A	z
7B	{
7C	|
7D	}
7E	~
7F	DEL