CS · 테크 — Lief Tech

Filling form

###
#### 1. 문제
[문제 URL]()
#### 2. 나의 풀이
##### 시도 1

java \

#### 3. 다른 사람의 풀이

java \

#### 4. 생각해보기
---

909. Snakes and Ladders

1. Problem

Problem URL Due to the problem of moving on a snake or ladder, the bonus move is only possible once and the goal is to move to the last space.

Board configuration:

n x n

You get an integer matrix board. Each cell is numbered from 1 in Boustrophedon style.

n^2

They are numbered up to.

Start and End: Starting from space 1 on the board

n^2

The game ends on the first space.

Movement rules:
Each move simulates a dice roll, choosing a number from 1 to 6.
The destination space is determined according to the selected number, and if there is a snake or ladder in that space, it moves to that location.
You can only ride a snake or ladder once.
Goal:

n^2

Find the minimum number of moves required to reach the first space.

If unreachable, -1 should be returned.

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation:
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.

2. My solution

Attempt 1

Boustrophedon style is used to describe how one line flows from left to right and then the next line flows from right to left. That means we can see that the intent of this issue is BFS.

In the problem, you can see that the numbers are connected as if the number 6 is 7 in the picture. You should keep this in mind.
Since you have to throw the minimum number of dice to get there, you have to worry about being able to climb the ladder. Here, depending on the problem

-1

In cases where there are only possible outcomes, the board is so small that it takes only 1 die to get there, which is eliminated. And if you look at the board, the number of moving points (destination) is written where you move, so the secondary arrangement is rather confusing, so the primary arrangement is

newBoard

convert to

sumBoard

created.

class Solution {
int length=0, result=0;
public int snakesAndLadders(int[][] board) {
length = board.length;
if(length==0) return -1;
for(int[] arr:board){
if(arr.length!=length) return -1;
}
if(length<3) return 1;
int[] newBoard = sumBoard(board);
boolean[] visited = new boolean[length*length];
bfs(newBoard, visited);
return result;
}
public int[] sumBoard(int[][] board) {
int newBoard = new int[length*length];
int cnt=0;
for(int i=length-1; i>=0; i--){
if(i%2==0){
for(int j=0; j<length; j++){
newBoard[cnt] = board[i][j];
}
}else{
for(int j=length-1; j>=0; j--){
newBoard[cnt] = board[i][j];
}
}
cnt++;
}
return newBoard;
}
}

Then in the next step

bfs(newBoard, visited);

You need to create a method to check whether it has arrived. I wasn't able to write the detailed code inside BFS, but I wrote some expected scenarios. I didn't write the code, but when I thought about it, case 3 seemed the most appropriate.

Go through the loop and find the case where you can go the furthest with the ladder. Then, calculate the number of cases in which you can reach the ladder's starting point the fastest and the number of dice that can reach the ladder's arrival point the fastest and add them up.
If there is no ladder, it is still as fast as 6, so keep the result value above, but check if there is a snake. If you have a snake, calculate the minimum number of dice you can move by 5.
Receive the position values of the ladder and snake as an array.

And consider a number of options, such as when all are used, when only some are used, when all are moved to 6, etc.
If the number of people being cut by a snake is the same as the number of people benefiting from a ladder, you should consider whether there is any point in using it. Then you have to avoid snakes.
However, even if you use a snake as in the example, if you can climb two ladders, the snake may be effective.

public void bfs(int[] newBoard, boolean[] visited) {
result = (length*length)%6>0? (length*length)/6+1 : (length*length)/6;
int location=0, cnt=0;
while(location<length*length){
// 예상 시나리오가 구현될 부분
}
result = Math.min(result, cnt);
}

3. Someone else’s solution

In actual gameplay we don't need 2D coordinates, so we convert them to a one-dimensional array.
Uses BFS (Breadth-First Search) to traverse the game board, and starts by adding the starting position to the queue.
Uses BFS to explore all possible paths, considering the 6 possible outcomes of a die roll. If you come across a snake or ladder, move to that location.
If the end point is reached, returns the number of moves up to that point, or -1 if it cannot be reached.

class Solution {
public int snakesAndLadders(int[][] board) {
final int n = board.length;
final int endSquare = n * n;
short[] brd = new short[endSquare + 1];
int brdIdx = 1;
for (int row = n - 1; row >= 0; row--) {
for (int col = 0; col < n; col++)  brd[brdIdx++] = (short)board[row][col];
if (--row < 0)  break;
for (int col = n - 1; col >= 0; col--)  brd[brdIdx++] = (short)board[row][col];
}
final int bfsQueueLen = Math.min(n * n, 8 * n);
short[] bfsQueue = new short[bfsQueueLen];
int bfsQueueRead = 0;
int bfsQueueWrite = 0;
bfsQueue[bfsQueueWrite++] = 1;  // Initialize BFS queue to start at square #1
byte[] count = new byte[endSquare + 1];
count[1] = 1;                   // Mark the starting location as already visited.
while (bfsQueueRead != bfsQueueWrite) {
int currSquare = bfsQueue[bfsQueueRead++];
bfsQueueRead %= bfsQueueLen;
if (currSquare + 6 >= endSquare)  return count[currSquare];
int maxOpenMove = 0;
for (int move = 6; move >= 1; move--) {
int nextSquare = currSquare + move;
if (brd[nextSquare] >= 0) {
if ((nextSquare = brd[nextSquare]) == endSquare)  return count[currSquare];
}
else {
if (move < maxOpenMove)  // If we already moved to an open square 1 to 6
continue;
maxOpenMove = move;
}
if (count[nextSquare] == 0) {
count[nextSquare] = (byte)(count[currSquare] + 1);
bfsQueue[bfsQueueWrite++] = (short)nextSquare;
if ((bfsQueueWrite %= bfsQueueLen) == bfsQueueRead)  return 0; // Queue overflow
}
}
}
return -1;
}
}

4. Think about it

The traditional board of the game Snakes and Ladders is shown on a two-dimensional plane. However, when approaching this problem programmatically, especially as a graph traversal problem, it may be simpler to think of it as a one-dimensional array. I need to solve more BFS problems to become familiar with them.

133. Clone Graph

1. Problem

Problem URL

This problem is a deep copy of a given connected undirected graph.
Each node has an int type representing its value and a list of neighboring nodes.

List<Node>

Includes. This problem can be implemented through deep copy through DFS and BFS.

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

2. My solution

Attempt 1

I solved it with DFS and thought that all nodes were newly created, but in fact

You must return a copy of all the nodes in the original graph

As shown, we could see that all nodes could not be cloned.

I looked at the problem again and decided to reconsider the fact that it is a connected undirected node.

class Solution {
public Node cloneGraph(Node node) {
if(node==null) return null;
if(node.neighbors.size()==0) return new Node(1);
Node newNode = new Node(node.val);
boolean[] visited = new boolean[100];
dfs(node, newNode, visited);
return newNode;
}
public void dfs(Node node, Node newNode, boolean[] visited) {
List<Node> newNeighbors =  newNode.neighbors;
visited[node.val] = true;
for (Node n : node.neighbors) {
if (!visited[n.val]) {
newNeighbors.add(new Node(n.val));
newNode.neighbors = newNeighbors;
dfs(n, new Node(n.val), visited);
}
}
}
}

Attempt 2

Because it is a connected undirected node

boolean

see

map

This may be a neater solution. Since there are no nodes with duplicate values, the value can be used as a key.

map

If there is no key value, that is, it is in an unvisited state, so the original node can be accessed using a for statement.

neighbor

listen to them one by one

cloneNode

Add it to .

public class Solution {
HashMap<Integer, Node> map = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) return null;
if(node.neighbors.size()==0) return new Node(1);
return dfs(node);
}
private Node dfs(Node node) {
if (map.containsKey(node.val)) {
return map.get(node.val);
}
Node cloneNode = new Node(node.val, new ArrayList<Node>());
map.put(node.val, cloneNode);
for (Node neighbor : node.neighbors) {
cloneNode.neighbors.add(dfs(neighbor));
}
return cloneNode;
}
}

3. Someone else’s solution

pinned

I brought it after seeing the solution. Based on a given node, we use DFS to traverse the graph, copying the node.

Checks the visited nodes and returns the node if it has already been copied. If the node has not been copied yet, it creates a new node and recursively copies neighboring nodes.
At this time, the Node[] array is used to check visited nodes.
In this array, all elements are initially initialized to null, and the val value of each node is used as an index to check whether the node has already been copied.
The cloneGraph function implemented in this way returns the result of deep copying the given graph.

class Solution {
public void dfs(Node node , Node copy , Node[] visited){
visited[copy.val] = copy;// store the current node at it's val index which will tell us that this node is now visited
//         now traverse for the adjacent nodes of root node
for(Node n : node.neighbors){
//             check whether that node is visited or not
//              if it is not visited, there must be null
if(visited[n.val] == null){
//                 so now if it not visited, create a new node
Node newNode = new Node(n.val);
//                 add this node as the neighbor of the prev copied node
copy.neighbors.add(newNode);
//                 make dfs call for this unvisited node to discover whether it's adjacent nodes are explored or not
dfs(n , newNode , visited);
}else{
//                 if that node is already visited, retrieve that node from visited array and add it as the adjacent node of prev copied node
//                 THIS IS THE POINT WHY WE USED NODE[] INSTEAD OF BOOLEAN[] ARRAY
copy.neighbors.add(visited[n.val]);
}
}
}
public Node cloneGraph(Node node) {
if(node == null) return null; // if the actual node is empty there is nothing to copy, so return null
Node copy = new Node(node.val); // create a new node , with same value as the root node(given node)
Node[] visited = new Node[101]; // in this question we will create an array of Node(not boolean) why ? , because i have to add all the adjacent nodes of particular vertex, whether it's visited or not, so in the Node[] initially null is stored, if that node is visited, we will store the respective node at the index, and can retrieve that easily.
Arrays.fill(visited , null); // initially store null at all places
dfs(node , copy , visited); // make a dfs call for traversing all the vertices of the root node
return copy; // in the end return the copy node
}
}

4. Think about it

To review the implementation code of DFS and BFS, I implemented it with ChatGPT. DFS is implemented using recursive functions, and BFS is implemented using queues. DFS Implementation

public void dfs(Node node, boolean[] visited) {
visited[node.val] = true;
for (Node neighbor : node.neighbors) {
if (!visited[neighbor.val]) {
dfs(neighbor, visited);
}
}
}

BFS Implementation In BFS, the current node's neighbors are added to the queue, then the nodes are removed from the queue one by one and the process of visiting them is repeated. When a queue is used in this way, breadth-first search is possible because neighboring nodes added first are visited in order.

public void bfs(Node node, boolean[] visited) {
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
visited[node.val] = true;
while (!queue.isEmpty()) {
Node curr = queue.poll();
for (Node neighbor : curr.neighbors) {
if (!visited[neighbor.val]) {
queue.offer(neighbor);
visited[neighbor.val] = true;
}
}
}
}

211. Design Add and Search Words Data Structure

1. Problem

Problem URL

It's a matter of designing a data structure to add words and check if they match previously added words.

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

class WordDictionary {
public WordDictionary() {
}
public void addWord(String word) {
}
public boolean search(String word) {
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/

2. My solution

Attempt 1

Same as problem 208, we first implemented the Trie structure. +

[".ad"],["b.."] I had to think about that part.

.

It had to be possible to accept any text.

class WordDictionary {
WordDictionary[] arr;
boolean isChar;
public WordDictionary() {
arr = new WordDictionary[26];
isChar = false;
}
public void addWord(String word) {
if(root==null) root=new WordDictionary();
WordDictionary temp=root;
for(char c:word.toCharArray()){
int ind=c-'a';
if(temp.child[ind]==null) temp.child[ind]=new WordDictionary();
temp=temp.child[ind];
}
temp.isLast=true;
}
public boolean search(String word) {
if(root==null) root=new WordDictionary();
WordDictionary temp=root;
for(char c : word.toCharArray()){
int idx = c-'a';
if(temp.children[idx] == null){
return false;
}
temp = temp.children[idx];
}
return temp.isWord == true;
}
}

3. Someone else’s solution

The WordDictionary class uses the Trie data structure to store words. The addWord method adds a word to a Trie, and the search method searches to see if a given word is in the Trie. In this code, '.' You can use characters as wildcards. '.' The character can be replaced with any character. This functionality is implemented in the checkWord method.

class WordDictionary {
boolean isLast;
WordDictionary [] child;
public WordDictionary() {
this.isLast=false;
this.child=new WordDictionary[26];
}
WordDictionary root;
public void addWord(String word) {
if(root==null) root=new WordDictionary();
WordDictionary temp=root;
for(char c:word.toCharArray()){
int ind=c-'a';
if(temp.child[ind]==null) temp.child[ind]=new WordDictionary();
temp=temp.child[ind];
}
temp.isLast=true;
}
public boolean search(String word) {
return checkWord(word,0,root);
}
public boolean checkWord(String word,int ind,WordDictionary temp){
if(ind>=word.length()) return temp.isLast;
if(temp==null) return false;
char c=word.charAt(ind);
if(c!='.'){
if(temp.child[c-'a']!=null) return checkWord(word,ind+1,temp.child[c-'a']);
else return false;
}
else{
boolean b=false;
for(int i=0;i<26;i++){
if(temp.child[i]!=null) b= b || checkWord(word,ind+1,temp.child[i]);
}
return b;
}
}
}

4. Think about it

In basic Trie implementation

search

and in this problem

search

It is necessary to check again for differences in conditions.

208. Implement Trie

1. Problem

Problem URL

Trie is a problem.
Trie(): Initializes a Trie object.
void insert(String word): string

word

trie

Insert it into .

boolean search(String word): String

word

trie

If in

true

and if not, return

false

returns .

boolean startsWith(String prefix): prefix

prefix

If there is a previously inserted string with

true

and if not, return

false

returns .

2. My solution

Attempt 1

Since child nodes are stored using Map, memory usage may increase and search speed may be slow. Therefore, using an array to store child nodes may be more efficient.

class TrieNode{
Map<Character, TrieNode> nodes = new HashMap<>();
boolean isLast;
Map<Character, TrieNode> getNodes(){
return this.nodes;
}
boolean isLast(){
return this.isLast;
}
void setIsLas(boolean isLast){
this.isLast = isLast;
}
}

class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
TrieNode node = curr.getChild(c);
if (node == null) {
node = new TrieNode();
curr.setChild(c, node);
}
curr = node;
}
curr.setEndOfWord(true);
}
public boolean search(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
TrieNode node = curr.getChild(c);
if (node == null) {
return false;
}
curr = node;
}
return curr.isEndOfWord();
}
public boolean startsWith(String prefix) {
TrieNode curr = root;
for (char c : prefix.toCharArray()) {
TrieNode node = curr.getChild(c);
if (node == null) {
return false;
}
curr = node;
}
return true;
}
}

3. Someone else’s solution

The Trie class implements the Trie data structure using the Node class. The Node class has an isWord variable that indicates the end of the string storing the string and 26 child nodes (children array).

The Trie class creates a root node in the default constructor,

insert

The method inserts the given string into the Trie. At this time, the string is iterated one letter at a time, and if there is no child node for that letter, a new node is created. +

search

The method searches whether the string exists in the Trie. At this time, the string is traversed one letter at a time, and if there is no child node for that letter, false is returned. Returns true only if the isWord variable is true after traversing until the last letter. +

startsWith

The method searches whether a string starting with the corresponding prefix exists in Trie. At this time, it iterates over the prefix one letter at a time, and returns false if there is no child node for that letter. Returns true after iterating to the last letter.

class Node{
Node children[] = new Node[26];
boolean isWord = false;
}
class Trie {
Node root;
public Trie() {
root = new Node();
}
public void insert(String word) {
Node temp = root;
for(char c : word.toCharArray()){
int idx = c-'a';
if(temp.children[idx] == null){
temp.children[idx] = new Node();
}
temp = temp.children[idx];
}
temp.isWord = true;
}
public boolean search(String word) {
Node temp = root;
for(char c : word.toCharArray()){
int idx = c-'a';
if(temp.children[idx] == null){
return false;
}
temp = temp.children[idx];
}
return temp.isWord == true;
}
public boolean startsWith(String prefix) {
Node temp = root;
for(char c : prefix.toCharArray()){
int idx = c-'a';
if(temp.children[idx] == null){
return false;
}
temp = temp.children[idx];
}
return true;
}
}

4. Think about it

The Trie structure is a tree data structure used for string searches. Each node stores a character, and there is a string prefix relationship between the parent node and child nodes. The main feature of this structure is that the search time is independent of the length of the string. In addition to string search, it is also used for auto-completion functions, etc.

637. Average of Levels in Binary Tree

1. Problem

Problem URL

Given the root of a binary tree, returns the average value of nodes at each level in the form of an array. Answers that match the actual answer with an accuracy of within 10^-5 are accepted.

2. My solution

Attempt 1

Given that it is a binary tree, I thought of adding the node values of each level and dividing them by the number if they have the same node.

However, in this solution, you can see that the calculation is performed without properly confirming that they are the same node.
Problem:

[3,9,20,null,null,15,7]

Result:

[6.00000,11.75000,10.80000,10.80000,10.80000]

Correct answer:

[3.00000,14.50000,11.00000]

class Solution {
List<Double> list = new ArrayList<>();
int valSum=0, cntSum=0;
public List<Double> averageOfLevels(TreeNode root) {
getAverage(root, 0);
return list;
}
public void getAverage(TreeNode root, int h) {
if(root==null) return;
valSum+=root.val;
cntSum++;
getAverage(root.left, h++);
getAverage(root.right, h++);
list.add((double)valSum/cntSum);
}
}

Attempt 2

Lastly, in the process of putting the average value into the list, I added a conditional statement to execute it when it is the rightmost node. And initialize the variables used in the calculation.

Even if you do this, you can see that it is not properly checking whether it is the same floor or not.

public void getAverage(TreeNode root, int h) {
if(root==null) return;
valSum+=root.val;
cntSum++;
if(root.right==null){
list.add((double)valSum/cntSum);
valSum=0;
cntSum=0;
}
getAverage(root.left, h++);
getAverage(root.right, h++);
}

3. Someone else’s solution

Queue

I wrote this because the solution using is new.

empty list

ans

Initializes , and if it is an empty tree, returns an empty list.

q

Perform BFS using and add the root node to the queue.

While performing BFS, we calculate the average by summing the values of all nodes in the current level and counting them.
Average value of each level

ans

Add to the list.

After BFS is finished

ans

Returns a list. Time complexity and space complexity

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> ans = new ArrayList<>();
if(root==null){
return ans;
}
Queue<TreeNode> q=new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
int n=q.size();
double avg=0l;
for(int i=0;i<n;i++){
TreeNode curr=q.poll();
avg=avg+(double)curr.val;
if(curr.left!=null){q.add(curr.left);}
if(curr.right!=null){q.add(curr.right);}
}
avg=avg/n;
ans.add(avg);
}
return ans;
}
}

4. Think about it

queue.offer(node)

node

means you want to add an element to the queue. Returns true if the queue is not full, false otherwise. This allows you to safely add elements to the queue.

199. Binary Tree Right Side View

1. Problem

Problem URL

Starting from the right side of the binary tree, we need to look at the tree and return the values of the rightmost nodes (the rightmost nodes at each level) in order from top to bottom.

2. My solution

Attempt 1

The first thing that came to mind when I saw the problem was that I could first save the rightmost value from each node layer in a list and return it. However, when I tried to solve it, finding and returning the position of the node on the left that is longer than the node on the right was more complicated than I thought, so I thought I should use the binary tree suggested in the problem more.

class Solution {
int h=0;
List<Integer> list = new ArrayList<>();
public hList<Integer> rightSideView(TreeNode root) {
deepth(root);
getRight(root);
if(h==list.size()) return list;
else{
}
}
public void deepth(TreeNode root){
if(root==null) return;
deepth(root.left);
h++;
deepth(root.right);
}
public void getRight(TreeNode root){
if(root==null) return;
list.add(root.val);
deepth(root.right);
}
}

Attempt 2

This solution was attempted using a binary tree, but failed.

Here, the height of the node

h

I used

rightSideView(root.right);

After going around

h++;

As this progresses, there will be a difference between the left and right node layers.

Therefore, a method of maintaining the layer of nodes must be used separately.

class Solution {
int h=0;
List<Integer> list = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
if(root==null) return null;
if(h==list.size()) list.add(root.val);
rightSideView(root.right);
h++;
rightSideView(root.left);
return list;
}
}

3. Someone else’s solution

The part I looked at carefully here is

rightView

You can see that when recursing, it starts from the right node. You can see that we can use it in reverse of the way we previously used multiple traversals to find the minimum or kth smallest number.

public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
rightView(root, result, 0);
return result;
}
public void rightView(TreeNode curr, List<Integer> result, int currDepth){
if(curr == null){
return;
}
if(currDepth == result.size()){
result.add(curr.val);
}
rightView(curr.right, result, currDepth + 1);
rightView(curr.left, result, currDepth + 1);
}
}

4. Think about it

It is important to learn how to use what you already know to solve problems without thinking too hard. In this problem, it was a problem examined from the right view, but if the same problem was solved from the left view, for example, the code could be written as follows.

public class Solution {
public List<Integer> leftSideView(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
rightView(root, result, 0);
return result;
}
public void leftView(TreeNode curr, List<Integer> result, int currDepth){
if(curr == null){
return;
}
if(currDepth == result.size()){
result.add(curr.val);
}
leftView(curr.left, result, currDepth + 1);
leftView(curr.right, result, currDepth + 1);
}
}

230. Kth Smallest Element in a BST

1. Problem

Problem URL

Roots and integers of binary search tree (BST)

k

Given a , among all node values in the binary tree,

k

Find the smallest value.

2. My solution

Attempt 1

Using in-order traversal to visit all node values in BST in ascending order

k

Find the smallest value.

530. Minimum Absolute Difference in BST It was easy to access after solving the problem.

class Solution {
List<Integer> list = new ArrayList<>();
public int kthSmallest(TreeNode root, int k) {
if(root==null){
Collections.sort(list);
if(list.size()<k) return 0;
else return list.get(k-1);
}
list.add(root.val);
kthSmallest(root.left, k);
kthSmallest(root.right, k);
Collections.sort(list);
if(list.size()<k) return 0;
else return list.get(k-1);
}
}

Although this is also a pass-through code, I decided to organize the duplicate code more neatly.

class Solution {
List<Integer> list = new ArrayList<>();
public int kthSmallest(TreeNode root, int k) {
if(root==null){
return getAnswer(list, k);
}
list.add(root.val);
kthSmallest(root.left, k);
kthSmallest(root.right, k);
return getAnswer(list, k);
}
public int getAnswer(List<Integer> list, int k) {
Collections.sort(list);
if(list.size()<k) return 0;
else return list.get(k-1);
}
}

The time complexity and space complexity of the solution I solved are as follows.

Time complexity: O(n log n)
Space complexity: O(n)

3. Someone else’s solution

This solution suffered a loss in terms of time complexity, but

sort

Unlike my code, which processes it only at the end

return

k

You can see that it comes with the smallest value. This is because it has the characteristics of a data structure called a binary search tree.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
List<Integer> list=new ArrayList<>();
public int kthSmallest(TreeNode root, int k) {
if(root==null)return 0;
help(root,k);
return list.get(k-1);
}
public void help(TreeNode root,int k)
{
if(root==null)return;
help(root.left,k);
list.add(root.val);
if(list.size()==k)return;
help(root.right,k);
}
}

4. Think about it

Let's modify part of my code (Attempt 2) by taking into account the fact that it has the characteristics of a data structure called a binary search tree. The problem with the previous code is:

The given code is adding all node values to the list, including duplicate node values, so it is not a valid infix traversal.
It is inefficient to add all node values to a list in duplicate and then sort them later to find the kth value. If you use the code below,

count

You can adjust the number and stop in the middle without having to search and sort all nodes. It is necessary to learn how to implement this style in binary search tree problems.

public class Solution {
int result;
int count;
public int kthSmallest(TreeNode root, int k) {
count = 0;
inOrderTraversal(root, k);
return result;
}
private void inOrderTraversal(TreeNode node, int k) {
if (node == null) return;
inOrderTraversal(node.left, k);
count++;
if (count == k) {
result = node.val;
return;
}
inOrderTraversal(node.right, k);
}
}

530. Minimum Absolute Difference in BST

1. Problem

Problem URL

The problem is to return the minimum absolute difference between the values of two different nodes of a given binary search tree (BST). In other words, the problem is finding the difference between the closest values in BST.
For example,

[1,null,5,3]

If root is entered, the minimum absolute difference is

2

It goes.

2. My solution

Attempt 1

I failed because I approached the problem incorrectly at first.
Since the vals are entered from left to right in order, I thought that only the difference between the leftmost node and the rightmost node needed to be considered.
But,

[5,4,7]

The minimum absolute difference from the root is

1

This is a problem of finding the difference between adjacent node values. ~~Not the height..!!~~

class Solution {
int left=0, right=0;
public int getMinimumDifference(TreeNode root) {
TreeNode lroot = root;
TreeNode rroot = root;
while(lroot.left!=null){
lroot = lroot.left;
left++;
}
while(rroot.right!=null){
rroot = rroot.right;
right++;
}
return Math.abs(left-right);
}
}

Attempt 2

Then, we solved it again by calculating the difference between adjacent node values. I made this with the idea that a recursive solution like this would work, but a timeout occurred.

Although it is an infix traversal method, because it returns the median value, the final result was a value other than the minimum difference value.

[0,null,2236,1277,2776,519]

The correct answer you want from the value is

519

The point is that it was.

In other words, the key point is that in addition to the difference between 519 and the node value 1277 above, the difference from 0 must also be calculated.
First of all, I found out that there were two problems in attempt 2.

root.val-prev

There is no need to process absolute values. Because it is a mid-level circuit.

And the initial value settings are incorrect. Given the constraint that all nodes in a binary search tree have values greater than or equal to -10000, setting the prev value to -10000 allows you to find the difference between the previous node and the current node even before visiting the root node of the binary search tree.

class Solution {
int min=10000, prev=0;
public int getMinimumDifference(TreeNode root) {
if(root==null) return min;
getMinimumDifference(root.left);
if(prev!=0) min=Math.min(min, Math.abs(root.val-prev));
prev=root.val;
getMinimumDifference(root.right);
return min;
}
}

Attempt 3

This is a passing code that reflects the concerns discussed above.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
int prev = -100000, min = 100000;
public int getMinimumDifference(TreeNode root) {
if(root==null) return min;
getMinimumDifference(root.left);
min=Math.min(min, root.val-prev);
prev=root.val;
getMinimumDifference(root.right);
return min;
}
}

3. Someone else’s solution

void inOrderTraversal

There is no return value from the method

min

This is a way to find the value.

In-order traversal allows us to compute the difference between two adjacent nodes since the nodes in the BST are visited in ascending order.
Traversing the tree in any other way than using infix traversal makes computing the minimum difference difficult because the nodes cannot be visited in the sorted order.

class Solution {
int min = Integer.MAX_VALUE;
TreeNode prev = null;
public int getMinimumDifference(TreeNode root) {
inOrderTraversal(root);
return min;
}
private void inOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.left);
if (prev != null) {
min = Math.min(min, Math.abs(node.val - prev.val));
}
prev = node;
inOrderTraversal(node.right);
}
}

4. Think about it

To summarize the binary search tree (BST), it has the following characteristics.

Every node can have at most two child nodes.
The value of all nodes in the left subtree is less than the value of the parent node.
The value of all nodes in the right subtree is greater than the value of the parent node.

33. Search in Rotated Sorted Array

1. Problem

Problem URL

2. My solution

Attempt 1

This problem also has a time complexity

O(log n)

Since this method must be considered, the following solution is not suitable.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public int search(int[] nums, int target) {
List<Integer> list = new ArrayList<>();
for(int i:nums){
list.add(i);
}
int index = list.indexOf(target);
if(index==-1) return -1;
else return index;
}
}

Attempt 2

I tried again using binary search.

left

right

Repeat for less than or equal to.

Calculate middle index: Assign (left + right) / 2, which is the middle value between left and right, to the mid variable.
Compare mid and target values: if nums[mid] is equal to target, return mid.
When the middle value belongs to the left subarray:
If the target belongs to the left subarray, update the right value to mid - 1 to narrow the right.
Otherwise, update the left value to mid + 1 to narrow the left.
When the middle value belongs to the right subarray:
If the target belongs to the right subarray, update the left value to mid + 1 to narrow the left.
Otherwise, update the right value to mid - 1 to narrow the right side.
Search failure: If the loop exits, the target value was not found, so -1 is returned. Time complexity and space complexity
Time complexity: O(log n)
Space complexity: O(n)

class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] >= nums[left]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target <= nums[right] && target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}

3. Someone else’s solution

The solution using binary search was almost similar to mine, so I looked for another solution. This problem also has a time complexity

O(log n)

Since this method must be considered, the following solution is not suitable. However, without considering time complexity, in fact

target

Since all you have to do is find the answer, there was also a solution that compared them all like this.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public int search(int[] nums, int target) {
int n = nums.length ;
for( int i = 0 ; i< n ; i++){
if( nums[i]==target ){
return i ;
}
}
return -1;
}
}

4. Think about it

Binary search is typically used on sorted arrays; it is not appropriate for use on unsorted arrays. However, in this problem, the given array is rotated, so part of the array is sorted and the remaining part is rotated. Binary search can be used in these situations as well. In attempt 2, to find the rotated partial array,

nums[mid] >= nums[left]

Conditional statements such as were used. This conditional statement determines whether the middle value belongs to the left or right subarray. In this way, you can use binary search to find the desired value even in a rotated array.

153. Find Minimum in Rotated Sorted Array

1. Problem

Problem URL

It may be confusing because it says rotated in the problem, but in the end, the given array

nums

The problem is to return the index of the smallest element in .

Refer to problem 162 to find the largest element.

2. My solution

Attempt 1

It is very simple to solve it like this, but the time complexity is

O(log n)

Please note that there are conditions that must be taken into consideration.

Time complexity: O(n)
Space complexity: O(1)

class Solution {
public int findMin(int[] nums) {
for(int i=0; i<nums.length-1; i++){
if(nums[i]>nums[i+1]) return nums[i+1];
}
return nums[0];
}
}

Attempt 2

I tried again using binary search.

left and

right

Use variables to represent the left and right endpoints of the array,

mid

Use variables to represent waypoints. +

while

At the door

left

Wow

right

Repeat until is the same,

mid

The point value is

mid+1

If it is greater than the value of the point

mid+1

Returns the value of the point,

mid

The point value is

mid-1

If it is greater than the value of the point

mid

Returns the value of the point.

mid

If the value of the point is greater than the first element of the array

left

mid+1

and if not, update with

right

mid-1

Update to .

In the end

left

The position pointed to by the variable becomes the position of the smallest element in the rotated array. Time complexity and space complexity

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public int findMin(int[] nums) {
int n = nums.length;
if(n==1) return nums[0];
int left = 0, right = n-1;
if(nums[right]>nums[0]) return nums[0];
while(left<right){
int mid = left + (right-left)/2;
if(nums[mid]>nums[mid+1]) return nums[mid+1];
if(nums[mid-1]>nums[mid]) return nums[mid];
if(nums[mid]>nums[0]){
left = mid+1;
} else {
right = mid-1;
}
}
return nums[left];
}
}

3. Someone else’s solution

It's the same method, but the variables and solutions are cleaner and look better.

Solutions

I brought you the solution.

class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
}

4. Think about it

I used binary search to find the smallest element in a rotated sorted array. When using binary search, you need to understand how to find the middle value of an array and how to determine where to search after finding that value.

162. Find Peak Element

1. Problem

Problem URL +

Peek

The problem is returning the index of an element.

In the problem

O(log n) Since you are told to use a time complexity of , you must use an algorithm that is more efficient than checking all elements.

2. My solution

Attempt 1

Simple as usual

Arrays.sort(nums);

After sorting

List

The solution was solved by finding the index value of the largest element.

The time complexity is greater than the size suggested in the problem.
Time complexity: O(n log n)
Space complexity: O(n)

class Solution {
public int findPeakElement(int[] nums) {
List<Integer> list = new ArrayList<>();
for(int i:nums){
list.add(i);
}
Arrays.sort(nums);
int answer = list.indexOf(nums[nums.length-1]);
return answer;
}
}

Attempt 2

To reduce time complexity as intended, the binary search method can be used. However, when I interpreted it this way, a timeout occurred.

class Solution {
public int findPeakElement(int[] nums) {
int left=0, right=nums.length-1;
int middle=(nums[left]+nums[right])/2;
while(left<right){
if(nums[middle-1]<nums[middle] && nums[middle+1]<nums[middle]) return middle;
if(nums[middle-1]<nums[middle]) left=middle+1;
else right=middle-1;
}
return left;
}
}

3. Someone else’s solution

return value

0

Since it is sorted in the order in which it inevitably appears, the case where the last element is peak is first excluded. Then, perform binary search using a while statement. If the median value is greater than the values on either side of the median value, the median value is retrun.

class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length;
if(n == 1 || nums[0] > nums[1]) return 0;
if(nums[n - 1] > nums[n - 2]) return n - 1;
int l = 0;
int r = n - 1;
while(l <= r)
{
int m = (l + r)/2;
int minus = m == 0 ? Integer.MIN_VALUE : nums[m-1];
int plusUltra = m == n - 1 ? Integer.MIN_VALUE : nums[m+1];
if(minus < nums[m] && plusUltra < nums[m]) return m;
if(minus < nums[m]) l = m + 1;
else r = m - 1;
}
return l;
}
}

148. Sort List

1. Problem

Problem URL

given

ListNode

Sort in ascending order

ListNode

It is a problem of returning to . +

ListNode

val

Wow

ListNode

It consists of:

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/

2. My solution

Attempt 1

This was interpreted as the process of finding the values of a given ListNode, sorting them into a List in order, and creating a new ListNode with these values.

But the problem

Follow up

The spatial complexity is

O(1)

Solving using this method failed.

Time complexity: O(n log n)
Space complexity: O(n)

class Solution {
public ListNode sortList(ListNode head) {
if(head==null) return head;
List<Integer> list = new ArrayList<>();
while(head!=null){
list.add(head.val);
head = head.next;
}
Collections.sort(list);
Collections.reverse(list);
ListNode answer = new ListNode();
for(int i=0; i<list.size(); i++){
if(i==0) answer = new ListNode(list.get(i));
else answer = new ListNode(list.get(i), answer);
}
return answer;
}
}

3. Someone else’s solution

Space complexity

O(1)

This is the solution that appears. This function sorts a linked list using merge sort. +

dummy

The value is

0

, and the next node is given

head

Creates a node.

And in node array form

sublists

sublist_tail

Split and merge the linked list, increasing the size of the sublist to 1, 2, 4, 8, ..., etc.

Since sorting is performed within the given linked list without using an additional array, the space complexity is

O(n)

It is. +

sublists

Wow

sublists_tail

is an additional array.

However, the size of these arrays is fixed to a constant value of 2 and is independent of the size of the input list.
Therefore, since no additional space proportional to the size of the input list is used, and only a constant-sized space is used, the space complexity is

O(1)

This happens.

public ListNode sortList(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode [] sublists = new ListNode[2];
ListNode [] sublists_tail = new ListNode[2];
// Grab sublists of size 1, then 2, then 4, etc, until fully merged
for (int steps = 1;; steps *= 2) {
// Record the progress of the current pass into a single semi sorted list by updating
// the next of the previous node (or the dummy on the first loop)
ListNode prev = dummy;
// Keep track of how much is left to process on this pass of the list
ListNode remaining = prev.next;
int num_loops = 0;
for (; null != remaining; ++num_loops) {
// Split 2 sublists of steps length from the front
for (int i = 0; i < 2; ++i) {
sublists[i] = remaining;
sublists_tail[i] = null;
for (int j = 0; null != remaining && j < steps; ++j) {
sublists_tail[i] = remaining;
remaining = remaining.next;
}
// Ensure the subslist (if one was made) is terminated
if (null != sublists_tail[i]) {
sublists_tail[i].next = null;
}
}
// We have two sublists of (upto) length step that are sorted, merge them onto the end into a single list of (upto) step * 2
while (null != sublists[0] && null != sublists[1]) {
if (null == sublists[1] || sublists[0].val <= sublists[1].val) {
prev.next = sublists[0];
sublists[0] = sublists[0].next;
} else {
prev.next = sublists[1];
sublists[1] = sublists[1].next;
}
prev = prev.next;
}
// One list has been finished, attach what ever is left of the other to the end
if (null != sublists[0]) {
prev.next = sublists[0];
prev = sublists_tail[0];
} else {
prev.next = sublists[1];
prev = sublists_tail[1];
}
}
// If the entire list was full processed in a single loop, it means we've completely sorted the list and are done
if (1 >= num_loops) {
return dummy.next;
}
}
}

The other solution stored the elements of the linked list in an array, then sorted the array, and updated the values in the sorted array into the linked list.

Arrays.sort(arr);

The sorting method was similar to my solution.

Time complexity: O(n log n)
Space complexity: O(n)

class Solution {
public ListNode sortList(ListNode head) {
int count = 0;
ListNode temp = head;
while(temp!=null){
count++;
temp = temp.next;
}
int[] arr = new int[count];
temp = head;
count = 0;
while(temp!=null){
arr[count++] = temp.val;
temp = temp.next;
}
Arrays.sort(arr);
temp = head;
count = 0;
while(temp!=null){
temp.val = arr[count++];
temp = temp.next;
}
return head;
}
}

4. Think about it

We found that we can reduce space complexity by performing sorting within a given linked list without using an additional array. If you only use a constant amount of space, the additional memory usage will remain constant no matter how the input size changes.

242. Valid Anagram

1. Problem

Problem URL

This problem is to check whether the two given strings are anagrams.
Here, anagram means creating a new string by arranging the letters in the string differently. All given strings must be used.

2. My solution

Attempt 1

This is a solution using HashMap. +

"hhbywxfzydbppjxnbhezsxepfexkzofxyqdvcgdvgnjbvih...

It failed in long test case number 41.

It was confirmed that s_map and t_map contained the same elements, but some test case return values were incorrect.

if(s.length()!=t.length()) return false;

here is the part

false

This was a problem that occurred while returning . Time complexity and space complexity

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public boolean isAnagram(String s, String t) {
Map<Character, Integer> s_map = makeMap(s);
Map<Character, Integer> t_map = makeMap(t);
if(s.length()!=t.length()) return false;
for(int i=0; i<t.length(); i++){
char c = t.charAt(i);
if(!s_map.containsKey(c)) return false;
if(s_map.get(c)!=t_map.get(c)) return false;
}
return true;
}
public Map<Character, Integer> makeMap(String str){
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(map.containsKey(c)) map.put(c, map.get(c)+1);
else map.put(c, 1);
}
return map;
}
}

// s_map
{a=1913, b=2003, c=2000, d=1916, e=1978, f=1880, g=1949, h=1943, i=1949, j=1891, k=1923,
l=1922, m=1936, n=1978, o=1869, p=1874, q=1875, r=1985, s=1897, t=1838, u=1879,
v=1905, w=1940, x=1942, y=1915, z=1900}
// t_map
{a=1913, b=2003, c=2000, d=1916, e=1978, f=1880, g=1949, h=1943, i=1949, j=1891, k=1923,
l=1922, m=1936, n=1978, o=1869, p=1874, q=1875, r=1985, s=1897, t=1838, u=1879,
v=1905, w=1940, x=1942, y=1915, z=1900}
50000
50000
// if(s.length()!=t.length()) return false;
false

3. Someone else’s solution

Arrays.sort

This is a code that is simply solved using . I was only thinking about implementing it as a HashTable, so I didn't think of it, but I think this would be a faster approach.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public boolean isAnagram(String s, String t) {
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
Arrays.sort(sChars);
Arrays.sort(tChars);
return Arrays.equals(sChars, tChars);
}
}

There was also a method using a Hash Table.

.getOrDefault()

I implemented the code more concisely with methods and string

s

Add to map as an element of,

t

This is a method of subtracting from the map the elements of . And at the end, if the value is not 0, the anagram is not satisfied.

false

returns .

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public boolean isAnagram(String s, String t) {
Map<Character, Integer> count = new HashMap<>();
for (char x : s.toCharArray()) {
count.put(x, count.getOrDefault(x, 0) + 1);
}
for (char x : t.toCharArray()) {
count.put(x, count.getOrDefault(x, 0) - 1);
}
for (int val : count.values()) {
if (val != 0) {
return false;
}
}
return true;
}
}

4. Think about it

.getOrDefault(x, 0)

I didn't remember the solution using , because I hadn't studied for the coding test, but I felt the need to organize the necessary methods for each data structure.

383. Ransom Note

1. Problem

Problem URL

two strings

ransomNote

Wow

magazine

Given,

ransomNote

magazine

Returns whether it can be created.

Both strings are assumed to be lowercase English letters.

2. My solution

By using Hash Table

ransomNote

Wow

magazine

Make it into a map

ransomNote

I checked whether I could create it.

class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
Map<Character, Integer> ransomNote_map = makeMap(ransomNote);
Map<Character, Integer> magazine_map = makeMap(magazine);
for(int i=0; i<ransomNote.length(); i++){
char c = ransomNote.charAt(i);
if(!magazine_map.containsKey(c)) return false;
if(ransomNote_map.getOrDefault(c,0)>magazine_map.getOrDefault(c,0)) return false;
}
return true;
}
public Map<Character, Integer> makeMap(String str){
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(map.containsKey(c)) map.put(c, map.get(c)+1);
else map.put(c, 1);
}
return map;
}
}

3. Someone else’s solution

A faster and simpler method than the approach I solved.

.toCharArray()

This is a solution using .

First,

magazine

To store the frequency of occurrence of each character in a string

charCounts

Creates an array of integers of length 26 called . This arrangement assumes the lowercase English alphabet.

Next,

magazine

While traversing the string, count the frequency of occurrence of each character.

charCounts

Save it to .

After that,

ransomNote

As you iterate through the string, each character

charCounts

Make sure it is in .

charCounts

If there is no corresponding character in

ransomNote

returns false because it cannot be created.

Otherwise,

charCounts

Reduce the frequency of occurrence of that character by one.

ransomNote

If you iterate through all the characters of ,

ransomNote

returns true because it can create .

class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] charCounts = new int[26]; // Assuming lowercase English letters
for (char c : magazine.toCharArray()) {
charCounts[c - 'a']++;
}
for (char c : ransomNote.toCharArray()) {
if ( !(charCounts[c - 'a'] > 0 ) ) {
return false;
}
charCounts[c - 'a']--;
}
return true;
}
}

4. Think about it

In the assignment, it was classified as a Hash Table, but I think we should consider other methods that are easier to implement.

219. Contains Duplicate 2

1. Problem

Problem URL

array

nums

and integer

k

Given the distance

k

Checks whether there are identical elements spaced apart within.

If there is

true

, if there is no

false

2. My solution

Attempt 1

This is a solution using HashMap. If the same value appears in the array, the element is the key and the index is the value.

class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++){
if(map.containsKey(nums[i])){
int a = map.get(nums[i]);
if(i-a<=k) return true;
}
map.put(nums[i], i);
}
return false;
}
}

3. Someone else’s solution

The HashTable method was similar to other people's solutions. The algorithm below uses a sliding window method. It was actually faster than the HashTable method and used somewhat less memory.

The front of the window is the ith element, and the back is the element k distance away. Elements within this window are maintained using Set.
When adding a new element to a Set, if the add() method returns false, that element already exists in the Set. In this case, it returns true because duplicate values exist.
In a for loop, if return true is not executed and the loop exits, it means that there are no duplicate values.

public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(i > k) set.remove(nums[i-k-1]);
if(!set.add(nums[i])) return true;
}
return false;
}

4. Think about it

If you have a problem that can be solved with a sliding window approach, such as finding duplicate values, it can be more efficient than HashTable. This is because the sliding window method processes data using a fixed-size window, so it can be more efficient in terms of space and time complexity.

1. Two Sum

1. Problem

Problem URL +

nums

in array

target

This is a problem of returning the index order for creating values as an array.

Unlike problem 167

nums

is given unsorted.

An element in an array can only be used once.

2. My solution

The simplest way to solve the problem was with a for statement, but the desired time complexity for the problem was less than O(n^2) and I could not find a method using Hash Table.

Time complexity: O(n^2)
Space complexity: O(n)

class Solution {
public int[] twoSum(int[] nums, int target) {
List<Integer> list = new ArrayList<>();
for(int i:nums){
list.add(i);
}
int i=0, a=0, b=0;
for(i=0; i<nums.length; i++){
a = target-nums[i];
b = list.lastIndexOf(a);
if(a>0 && b!=-1 && b!=i){
break;
}
}
return new int[]{i, b};
}
}

3. Someone else’s solution

This is a solution using Hash Table. At first, I thought why bother processing Map, but since it is a key-value pair lookup, it can be solved rather quickly.

first

HashMap

inside

target

It checks whether there is a key value equal to the difference between and returns the index array.

If not,

i

Add an element with the value as the key. Time complexity and space complexity

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numMap = new HashMap<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
int complement = target - nums[i];
if (numMap.containsKey(complement)) {
return new int[]{numMap.get(complement), i};
}
numMap.put(nums[i], i);
}
return new int[]{}; // No solution found
}
}

4. Think about it

Since it is not a problem of finding all keys, but a problem of obtaining candidate keys, we can conclude that it is faster to use HashMap.

150. Evaluate Reverse Polish Notation

1. Problem

Problem URL

Polish Notation tokens are given and the result is returned.
There is no division by zero, and the answer and all intermediate calculations can be expressed as 32-bit integers.

2. My solution

Attempt 1

I was looking for why reverse Polish notation is used, and based on the article on Wiki I got to write code. Implementation using stack makes calculations easier by using reverse Polish notation in calculation expressions with many parentheses. +

EmptyStackException

this happens +

Character.isDigit

When to use

-11

This was because there were cases where the was not viewed as a number.

class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
int next;
for(String s:tokens){
if(Character.isDigit(s.charAt(0))){
stack.push(Integer.parseInt(s));
}
else{
int b = stack.pop();
int a = stack.pop();
if("+".equals(s)) stack.push(a+b);
else if("-".equals(s)) stack.push(a-b);
else if("*".equals(s)) stack.push(a*b);
else stack.push(a/b);
}
System.out.println(stack);
}
return stack.pop();
}
}

Attempt 2

There is no problem with other parts

EmptyStackException

prevent this from happening

Character.isDigit

Instead, it was changed to apply conditions by checking whether the four arithmetic symbols are present.

if("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s))

3. Someone else’s solution

The rest of the overall solution is similar to the Stack method, but there are methods such as removing methods or checking the four arithmetic operations by putting them in a set as shown in the following code. If the code is long, I thought it would be a good idea to leave out the calculation part as a method for readability.

Deque

There was also a solution using

Deque

There seem to be quite a few solutions using , so it would be good to refer to them.

class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
Set<String> ops = Set.of("+", "-", "*", "/");
for (String s : tokens) {
if (ops.contains(s)) {
int a = stack.pop();
int b = stack.pop();
int c = 0;
switch(s) {
case "+" -> {c = b + a;}
case "-" -> {c = b - a;}
case "*" -> {c = b * a;}
case "/" -> {c = b / a;}
}
stack.push(c);
}
else stack.push(Integer.parseInt(s));
}
return stack.peek();
}
}
// TC: O(n), SC: O(n)

4. Think about it

Deque

is a data structure that can be implemented in both the form of a stack and a queue. Insertion and deletion of elements is possible at both ends. ArrayDeque is an array-based Deque implementation that dynamically adjusts its size, and LinkedList is a linked list-based Deque implementation.

If so, than stack or queue

Deque

ChatGPT could not find an answer to the question, "Is there a more suitable problem?"

155. Min Stack

1. Problem

Problem URL

As a matter of implementing the stack, you must be able to push, pop, top, and retrieve the smallest element at the same time.

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

2. My solution

Attempt 1

When considering the existing implementation, LinkedList is connected to the next list by address, while ArrayList has a linear structure, resulting in a time complexity of O(n). Assuming that memory is infinite, LinkedList has the advantage of being able to insert new data infinitely. ArrayList wastes memory during insertion and deletion of data. Of course, this is a simple stack implementation, but the stack was implemented as a LinkedList under the assumption that someone will use this stack.

class MinStack {
LinkedList<Integer> list;
public MinStack() {
list = new LinkedList<>();
}
public void push(int val) {
list.push(val);
}
public void pop() {
list.removeFirst();
}
public int top() {
return list.peekFirst();
}
public int getMin() {
LinkedList<Integer> sortedList =  new LinkedList<>(list);
Collections.sort(sortedList);
return sortedList.peekFirst();
}
}

3. Someone else’s solution

TplusMin

Put a class called

min

Save the value at the end

getMin()

I thought it was much more efficient that no separate sorting was required during processing. This is because you only need to worry about push processing.

class MinStack {
LinkedList<TplusMin> stack;
private class TplusMin {
int val;
int min;
public TplusMin(int val, int min) {
this.val = val;
this.min = min;
}
}
public MinStack() {
stack = new LinkedList<>();
}
public void push(int val) {
int newMin;
if (stack.size() == 0){
newMin = val;
}
else {
int currentMin = stack.getFirst().min;
newMin = val < currentMin ? val : currentMin;
}
stack.addFirst(new TplusMin(val, newMin));
}
public void pop() {
stack.removeFirst();
}
public int top() {
return stack.peekFirst().val;
}
public int getMin() {
return stack.peekFirst().min;
}
}

4. Think about it

When simply implementing a stack, I learned how to define the values to be stored in the list as a class rather than a single type and process it by creating the desired data structure. Even when writing other code, even if it is not necessarily a data structure, I started thinking about how to save it as a simple class-level object.

3. Longest Substring Without Repeating Characters

1. Problem

Problem URL

This is a problem of finding the maximum length when truncated into a string that does not contain repetition.

2. My solution

Attempt 1

I literally approached it by substringing, but I thought I should go beyond the index range and try a different approach than this approach.

class Solution {
public int lengthOfLongestSubstring(String s) {
int answer = 1;
for(int i=0; i<s.length()-1; i++){
int j=i+1;
while(j<s.length()){
j++;
String substring = s.substring(i,j);
if(substring.indexOf(""+s.charAt(j))==-1){
answer = Math.max(answer, j-i);
}
else break;
}
}
return answer;
}
}

Attempt 2

I thought about the sliding window concept I learned in Problem 209. Sliding window is an algorithmic technique that searches for partial sections that satisfy specific conditions by moving a fixed-sized window in a continuous data structure.

within code

i

Wow

j

Form a sliding window using two indices,

seen

I am using an array to check if each character is a duplicate. +

i

is the left end of the sliding window,

j

indicates the right end of the sliding window.

At this time

j

moves to the right of the sliding window through a loop and checks the condition.

here

128

is based on ASCII code. Time complexity and space complexity

Time complexity: O(n^2)
Space complexity: O(1)

class Solution {
public int lengthOfLongestSubstring(String s) {
int answer = 0;
for (int i=0; i<s.length(); i++) {
boolean[] seen = new boolean[128];
int j=i;
while (j<s.length() && !seen[s.charAt(j)]) {
seen[s.charAt(j)] = true;
j++;
}
answer = Math.max(answer, j-i);
}
return answer;
}
}

3. Someone else’s solution

It is similar to the above solution, but in this case

int[]

We are checking whether or not we are comparing using an array.

class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int maxLength = 0;
int[] charIndex = new int[128];
Arrays.fill(charIndex, -1);
int left = 0;
for (int right = 0; right < n; right++) {
if (charIndex[s.charAt(right)] >= left) {
left = charIndex[s.charAt(right)] + 1;
}
charIndex[s.charAt(right)] = right;
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}

4. Think about it

In fact, it may seem like you need to check every word to make sure it's correct, but I found out that there's no need to do that. This is because even if you check with a single character to avoid duplication, you may get the same result. You need to be familiar with sliding window concepts and methods. But this method

209. Minimum Size Subarray Sum

1. Problem

Problem URL

as the sum of the elements of the array

target

The problem is to find the minimum length of the subarray to achieve this.

array

nums

is not sorted.

If there is no subarray

0

return .

Find a method with time complexity O(n) or O(n log n).

2. My solution

Attempt 1

The only thing I could think of was a double loop, so I tried this, but as expected, it failed with a timeout.

Time complexity: O(n log n)
Space complexity: O(1)

class Solution {
public int minSubArrayLen(int target, int[] nums) {
if(Arrays.binarySearch(nums, target)>=0) return 1;
int j=1, cnt=0;
boolean b = false;
for(int i=0; i<nums.length; i++){
int value = nums[i];
j = i+1;
while(true){
if(j<=nums.length-1) value += nums[j];
if(target==value){
b=true;
break;
}
if(j==nums.length-1 || target<value) break;
}
if(b) cnt = j-i+1;
}
return cnt;
}
}

3. Look at other people’s solutions and improve them

슬라이딩 윈도우

It was a solution using a for and while statement like my previous solution, but it was different in that it was more efficient. First, if there is no subarray

0 returns . Then, the minimum length is updated by moving the left pointer so that the sum of the partial arrays is greater than target.

Time complexity: O(n)
Space complexity: O(1)

class Solution {
public int minSubArrayLen(int target, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int left = 0;
int minLength = Integer.MAX_VALUE;
int currentSum = 0;
for (int right = 0; right < nums.length; right++) {
currentSum += nums[right];
while (currentSum >= target) {
minLength = Math.min(minLength, right - left + 1);
currentSum -= nums[left];
left++;
}
}
if (minLength != Integer.MAX_VALUE)
return minLength;
else
return 0;
}
}

4. Things to think about

It was a little different from the two-pointer method, and I thought I needed to become more proficient in using the sliding window.

167. Two Sum 2 Input Array Is Sorted

1. Problem

Problem URL

This is a problem of creating the desired value by adding two elements in a sorted array.
At this time, the ordered pair of two elements in the array is returned.

2. My solution

Attempt 1

Arrays.binarySearch

I was able to find the matching index.

When I solved it like this, I passed all the basic examples, but

[5,25,75]

100

Failed to find a possible value.

output

[1,-3]

came out

indexOf

I'm mistaken

-1

Because I assumed it would return only . +

Arrays.binarySearch

returns a negative value if not found. The return value is a negative value indicating where the key should be inserted, rather than the exact location of the key.

class Solution {
public int[] twoSum(int[] numbers, int target) {
int i=0, j=0;
for(i=0; i<numbers.length; i++){
j = Arrays.binarySearch(numbers, target-numbers[i]);
if(j>0) break;
}
return new int[]{i+1, j+1};
}
}

Attempt 2

from above

Arrays.binarySearch

The code was modified to take into account the negative number problem, the problem of returning the same index when the same number is consecutive, and the sorting problem of the return array.

Time complexity: O(n log n)
Space complexity: O(1)

class Solution {
public int[] twoSum(int[] numbers, int target) {
int i=0, j=0;
for(i=0; i<numbers.length; i++){
j = Arrays.binarySearch(numbers, target-numbers[i]);
if(j>=0 && i!=j) break;
}
if(i<j) return new int[]{i+1, j+1};
else return new int[]{j+1, i+1};
}
}

3. Look at other people’s solutions and improve them

given

nums

Since the array is a sorted value, add the values on both sides

target

The method was to change the pointer depending on whether it was smaller or larger. The code is much cleaner and I thought it would be a good idea to keep this approach in mind.

class Solution {
public int[] twoSum(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (nums[l] + nums[r] != target) {
if (nums[l] + nums[r] < target)
l++;
else
r--;
}
return new int[]{l + 1, r + 1};
}
}

4. Things to think about

In the content written by the author of the reference solution, the following items were recommended as things to consider when given a sorted array. In this problem, the method using two pointers was used.

binary search
Two (or three) pointers
sliding window
The core idea of the sliding window algorithm is to perform the necessary operations while controlling the start and end of the window. This allows you to reduce unnecessary calculations, reduce problem complexity, and solve problems efficiently.
Traverse from the right

125. Valid Palindrome

1. Problem

Problem URL

The problem is finding whether it is a Palindrome. For example, it checks whether strings such as tomato, wild goose, or Wooyoungwoo are present.

true

false

return to

Except for special characters and spaces, upper and lower case letters are considered the same.

" "

An empty string is also considered a Palindrome.

2. My solution

Attempt 1

The solution was solved by converting the string to a char[] array and comparing it with the values of the array behind it.

In this case, test cases 458 / 485 passed, but

0P

did not pass.

in the problem

Alphanumeric characters include letters and numbers.

Because numbers had to be taken into account as well, modifications were necessary.

class Solution {
public boolean isPalindrome(String s) {
if(s.isEmpty()) return true;
int end = s.length()-1;
char[] arr = s.toCharArray();
for(int i=0; i<arr.length/2; i++){
if(!(arr[i] >= 'A' && arr[i] <= 'Z') && !(arr[i] >= 'a' && arr[i] <= 'z'))
continue;
while(true){
if((arr[end] >= 'A' && arr[end] <= 'Z') || (arr[end] >= 'a' && arr[end] <= 'z'))
break;
else end--;
}
if(Character.toLowerCase(arr[i]) != Character.toLowerCase(arr[end]))
return false;
else end--;
}
return true;
}
}

Attempt 2

I wrote a code that reflected the numbers back in the code above, but a timeout occurred. +

!(start >= 0 && start <= 9) && !(start >= 'a' && start <= 'z')

class Solution {
public boolean isPalindrome(String s) {
if(s.isEmpty()) return true;
int end = s.length()-1;
char[] arr = s.toCharArray();
for(int i=0; i<arr.length/2; i++){
int start = Character.toLowerCase(arr[i]);
int compare = Character.toLowerCase(arr[end]);
if(!(start >= 0 && start <= 9) && !(start >= 'a' && start <= 'z'))
continue;
while(true){
if((compare >= 0 && compare <= 9) || (compare >= 'a' && compare <= 'z'))
break;
else end--;
}
if(start != compare) return false;
else end--;
}
return true;
}
}

Attempt 3

I thought it was caused by a double loop, so I thought of another way. Instead of processing it with a while statement,

s

Characters other than numbers and English letters are treated as blank.

In this case, test cases 462 / 485 passed, but

0P

did not pass. +

if(!(arr[i] >= 0 && arr[i] <= 9) && !(arr[i] >= 'a' && arr[i] <= 'z')) arr[i]=' ';

In this part

0

was left blank,

}```

It was changed to .
In the end, I passed, but it wasn't a solution I liked.
+ Time complexity: O(n)
+ Space complexity: O(n)


```java
class Solution {
public boolean isPalindrome(String s) {
if(s.isEmpty()) return true;
s = s.toLowerCase();
char[] arr = s.toCharArray();
for(int i=0; i<arr.length; i++){
if(!(arr[i] >= '0' && arr[i] <= '9') && !(arr[i] >= 'a' && arr[i] <= 'z')) arr[i]=' ';
}
String str = String.valueOf(arr).replaceAll(" ", "");
arr = str.toCharArray();
for(int i=0, j=arr.length-1; i<arr.length/2; i++, j--){
if(arr[i]!=arr[j]) return false;
}
return true;
}
}

3. Look at other people’s solutions and improve them

Character.isLetterOrDigit

I was able to see that the code was definitely processed neatly. And I went through the process of converting it to an array and combining it into a string, and I just went through a loop to find the character positions in the string.

left

Wow

right

I learned how to process and compare.

Time complexity: O(n)
Space complexity: O(1)

class Solution {
public boolean isPalindrome(String s) {
if (s.isEmpty()) {
return true;
}
int left = 0;
int right = s.length() - 1;
while (left < right) {
char leftChar = s.charAt(left);
char rightChar = s.charAt(right);
if (!Character.isLetterOrDigit(leftChar)) {
left++;
} else if (!Character.isLetterOrDigit(rightChar)) {
right--;
} else {
if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
return false;
}
left++;
right--;
}
}
return true;
}
}

4. Things to think about

Instead of thinking about it too complicatedly, I thought I should try to solve the problem without converting the existing string as much as possible.

169. Majority Element

1. Problem

Problem URL

This is a problem of finding the maximum frequency value in an array.
The mode is at least

배열의 길이/2

It has a frequency of more than

Additionally, this is a problem to see if it can be solved with a time complexity of O(n) and a space complexity of O(1).

2. My solution

First, the method I came up with was to input values with the same key into the map, and if there are duplicate keys, input the duplicate number as the value. It passed, but was lacking in the complexity aspect that should be considered in the problem.

Time complexity: O(n + n log n)
Space complexity: O(n)

class Solution {
public int majorityElement(int[] nums) {
int limit = nums.length/2;
Map<Integer, Integer> map = new HashMap<>();
for(int i:nums){
if(map.containsKey(i) map.put(i, map.get(i)+1);
else map.put(i, 1);
}
List<Integer> keySet = new ArrayList<>(map.keySet());
keySet.sort((o1, o2) -> map.get(o2).compareTo(map.get(o1)));
return keySet.get(0);
}
}

3. Look at other people’s solutions and improve them

Arrays.sort(nums)

Use** The first solution I saw was this method, and I thought it would work like this, but when I thought about it,

limit

I forgot that part while solving the problem. The maximum frequency value is

배열의 길이/2

Because the frequency was above that, the value could be obtained just by deriving the median value by sorting. However, the time and space complexity was not what I wanted.

Time complexity: O(n log n)
Space complexity: O(1)

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

Moore Voting Algorithm Moore Voting Algorithm to find the majority factor.

Initialize the variable candidate to the majority element candidate, and initialize count to 0.
Traverse the array, doing the following for each element:
If count is 0, sets the current element as candidate.
If the current element is equal to candidate, increment count.
Otherwise decrement count.
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int candidate = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
if (num == candidate) {
count++;
} else {
count--;
}
}
return candidate;
}
}

4. Things to think about

Moore Voting Algorithm was unfamiliar to me, but I took this opportunity to study a good algorithm to find more than half of the elements. The part above that I didn't understand the most was

candidate = num; It was natural to enter the value at first, but I did not understand at first that after entering the value, the value (count) was reduced by frequency with another element and when it reached 0, another element was inserted as a candidate. But for simplicity, the array given as an example

2,2,1,1,1,2,2

If you think about it, it was rather easy, but in the end, this algorithm was possible because it had the premise that there are more than half of the elements, so this part needs to be taken into consideration.

80. Remove Duplicates from Sorted Array 2

1. Problem

Problem URL

This is a problem where you need to make sure that there are no more than 3 consecutive elements in a given array.

1,1,2,2,2,3

When,

1,1,2,2,3,_

and returns the number of elements.

2. My solution

First, I thought about how to solve it. I wanted to solve it using the pointer method I learned when solving problem 26, but I couldn't think of a method for the second if statement.

class Solution {
public int removeDuplicates(int[] nums) {
int a=1, cnt=0;
for(int i=1; i<nums.length; i++){
if(nums[i]==nums[i-1]) cnt++;
if(cnt>=2 || nums[i]!=nums[i-1]){
//cnt=0;
nums[a++]=nums[i];
}
}
return a;
}
}

3. Look at other people’s solutions and improve them

class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length <= 2) {
return nums.length;
}
int index = 2;
for (int i = 2; i < nums.length; i++) {
if (nums[i] != nums[index - 2]) {
nums[index] = nums[i];
index++;
}
}
return index;
}
}

first

nums

If is less than 2, of course no separate calculation is needed, so the length is returned.

And it begins

i

Wow

index

Let us proceed from the values in Figure 2.

Time complexity: O(n)
Space complexity: O(1)

4. Things to think about

if (nums[i] != nums[index - 2]) {
nums[index] = nums[i];
index++;
}

I was confused about this part, but actually

index

The arrays entered are values that allow up to two duplicates.

nums[i]

If the value of is different from the existing values (different from the newly stacked array),

nums[index] = nums[i];

Insert other elements with .

26. Remove Duplicates from Sorted Array

1. Problem

Problem URL

sorted array

nums

The problem is to return the number of elements excluding duplicate values.

There must be no duplicate values in the array.

2. My solution

class Solution {
public int removeElement(int[] nums, int val) {
nums = Arrays.stream(nums).distinct().toArray();
return nums.length;
}
}

Unlike in the IDE

nums

The output of the value came out without duplicate values being removed, so I had to think about it again.

Time complexity: O(n)
Space complexity: O(n)

3. Look at other people’s solutions and improve them

class Solution {
public int removeDuplicates(int[] nums) {
int a=1;
for(int i=1; i<nums.length; i++){
if(nums[i]!=nums[i-1]){
nums[a++]=nums[i];
}
}
return a;
}
}

nums

If the value of is not the same as the previous value, it is assigned to the index a position.

4. Things to think about

used in stream

distinct()

Wow

toArray()

The spatial complexity results were poor in that new objects were created and additional memory was required. given rather than creating a new object.

nums

You should think about solving the problem by changing the object value.

27. Remove Element

1. Problem

Problem URL +

nums

You are given an array and the elements that need to be deleted from the array.

The return value is the number of elements in the array excluding the deleted elements.

2. My solution

class Solution {
public int removeElement(int[] nums, int val) {
int answer = 0;
for(int i=0; i<nums.length; i++){
if(nums[i]!=val){
nums[answer] = nums[i];
answer++;
}
}
return answer;
}
}

At first, I created a for statement considering only the return value.

nums[answer] = nums[i];

in the same way as

nums

I added it because I had to reconsider the arrangement. If you do this

val

Only values that are not equal to

nums

You can put it in front of an array.

Time complexity: O(n)
Space complexity: O(1)

3. Look at other people’s solutions and improve them

class Solution {
public int removeElement(int[] nums, int val) {
int count=0; //variable for occurance
int i=0;
int j=nums.length-1;
while(i<nums.length){
if(nums[i]==val){
nums[i]=nums[j];
nums[j]=-1;
j--;
count++;
}
else{
i++;
}
}
return nums.length-count;
}
}

Some people also approached this problem using pointers, and the time complexity and space complexity were the same as my solution in this case.

val

If the value is equal to

nums

The part where you add the element value at the end is new.

4. Things to think about

Solving using pointers is a way to reduce time complexity in sorting problems, so we need to become more familiar with it.

88. Merge Sorted Array

1. Problem

Problem URL +

nums1

and

nums2

is given

nums1

It's a matter of sorting after merging inside.

There is no separate return value.

2. My solution

class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for(int i=0; i<n; i++){
nums1[m+i] = nums2[i];
}
Arrays.sort(nums1);
}
}

nums1

Since the size of is given as the size of n+m in the original problem, the values other than m are assumed to be 0, and only the values after that are assumed to be 0.

nums2

I received it from This is done using a for statement. The final sort after merging is

Arrays.sort

Sorted by method.

Time complexity: O(n + m * log(m+n))
Space complexity: O(1)

3. Look at other people’s solutions and improve them

class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
}

It was the cleanest and freshest approach among other solutions. It is a solution to solve using two pointers and the time complexity is

O(n+m)

is improved.

Variables i, j, k respectively

nums1

nums2

병합한 nums2

Initialize with the index of .

Taking advantage of the feature that the given array is already sorted, large values are ordered sequentially from the back.

nums1

Fill the array.

Larger value when merging

nums1

Store it at index k starting from the end of the array. if

nums1

The elements of the array are

nums2

If it is larger than an element in the array, put that element first.

nums1[k]

Save it to a location, otherwise

nums2[j]

value

nums1[k]

Save it to a location.

For each array element processed, decrement i, j, and k.

nums2

all elements of the array

nums1

Repeat the above process until you merge them into an array.

4. Things to think about

I had never thought about an approach using pointers, but it was an opportunity to learn a new approach considering time complexity.

Arrays.sort

It was confirmed that the time complexity of solving using increases. And there is no separate return value.

nums1

The premise of merging values is different from other code testing sites, so I thought I should read the problem more carefully.

Leetcode 100

Filling form

909. Snakes and Ladders

1. Problem

2. My solution

Attempt 1

3. Someone else’s solution

4. Think about it

133. Clone Graph

1. Problem

2. My solution

Attempt 1

Attempt 2

3. Someone else’s solution

4. Think about it

211. Design Add and Search Words Data Structure

1. Problem

2. My solution

Attempt 1

3. Someone else’s solution

4. Think about it

It is necessary to check again for differences in conditions.

208. Implement Trie

1. Problem

2. My solution

Attempt 1

3. Someone else’s solution

4. Think about it

637. Average of Levels in Binary Tree

1. Problem

2. My solution

Attempt 1

Attempt 2

3. Someone else’s solution

4. Think about it

means you want to add an element to the queue. Returns true if the queue is not full, false otherwise. This allows you to safely add elements to the queue.

199. Binary Tree Right Side View

1. Problem

2. My solution

Attempt 1

Attempt 2

3. Someone else’s solution

4. Think about it

230. Kth Smallest Element in a BST

1. Problem

2. My solution

Attempt 1

3. Someone else’s solution

4. Think about it

530. Minimum Absolute Difference in BST

1. Problem

2. My solution

Attempt 1

Attempt 2

Attempt 3

3. Someone else’s solution

4. Think about it

33. Search in Rotated Sorted Array

1. Problem

2. My solution

Attempt 1

Attempt 2

3. Someone else’s solution

4. Think about it

Conditional statements such as were used. This conditional statement determines whether the middle value belongs to the left or right subarray. In this way, you can use binary search to find the desired value even in a rotated array.

153. Find Minimum in Rotated Sorted Array

1. Problem

2. My solution

Attempt 1

Attempt 2

3. Someone else’s solution

4. Think about it

I used binary search to find the smallest element in a rotated sorted array. When using binary search, you need to understand how to find the middle value of an array and how to determine where to search after finding that value.

162. Find Peak Element

1. Problem

2. My solution

Attempt 1

Attempt 2

3. Someone else’s solution

148. Sort List