September Week 1

24.09.01 - 2022. Convert 1D Array Into 2D Array

나

// 81ms, 89.91MB
class Solution {
public:
    vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
        int SIZE = original.size();

        vector<vector<int>> answer;
        if(m * n != SIZE) return answer;

        for(int i{};i<m;++i) {
            answer.push_back(vector<int>(n, 0));
            for(int j{};j<n;++j) {
                answer[i][j] = original[n * i + j];
            }
        }

        return answer;
    }
};

gpt

The "Convert 1D Array Into 2D Array" problem requires transforming a given 1D array into a 2D array with specified row and column dimensions. If the total number of elements in the 1D array doesn't match rows * cols, return an empty array.

Approach:

Check if the conversion is possible by verifying the array size.
Traverse the 1D array and map each element to the corresponding position in the 2D array.

Here's the C++ code to solve it:

// 78ms, 88.03MB
class Solution {
public:
    vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
        if (original.size() != m * n)
            return {};
        
        vector<vector<int>> result(m, vector<int>(n));
        for (int i = 0; i < original.size(); ++i) {
            result[i / n][i % n] = original[i];
        }
        return result;
    }
};

Explanation:

Check Validity: If the size of the 1D array isn't m * n, return an empty array.
Filling the 2D Array: Use integer division and modulus to map each element from the 1D array into the appropriate 2D position.

Time Complexity:

$O(m \times n)$ for filling the 2D array.

24.09.02 - 1894. Find the Student that Will Replace the Chalk

문제 링크

나

// 79ms, 77.10MB
class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        int answer{};
        int sum{}; // k <= 10^9 : no need to long long
        for(int s{}, e{static_cast<int>(chalk.size())}; s<e; ++s) {
            sum += chalk[s];
            if(sum > k) {
                answer = s; // 조기 종료
                break;
            }
        }
        if(answer) return answer;

        k %= sum;
        sum = 0;
        for(int s{}, e{static_cast<int>(chalk.size())}; s<e; ++s) {
            sum += chalk[s];
            if(sum > k) {
                answer = s; // 조기 종료
                break;
            }
        }

        return answer;
    }
};

Solution

Approach 1: Prefix Sum

Intuition

In this problem, we have an array chalk of n elements representing the number of chalks used by each student, and an integer k indicating the total number of chalks available. The brute force approach would involve repeatedly subtracting the number of chalks from k until it reaches zero, cycling through the array if necessary. Given that k can be as large as 1,000,000,000, this approach is impractical.

To optimize, observe that the total number of chalks used in one complete cycle through the array is given by sum, the sum of all elements in chalk. If k is less than sum, we will reach zero within the first cycle. If k is greater than sum, after the first cycle, k will be reduced to k - sum, and after subsequent cycles, it will be reduced further. This process continues until k becomes less than sum, which is equivalent to computing k \% sum.

This is because k reduced by multiples of sum will eventually be less than sum, and this final value is equivalent to k \% sum.

We then need to find the first index in the chalk array where the remaining k \% sum becomes negative. We do this by maintaining a running prefix sum of chalk elements and iterating through the array to find the index where the prefix sum exceeds k \% sum.

Algorithm

Initialize an integer variable sum to 0.
Iterate over the chalk array from 0 to chalk.size() - 1:
- Add the value at the current index i to sum.
- If at any point sum exceeds k, exit the loop.
Calculate k as k \% sum, representing the remaining chalk after full rounds.
Iterate over the chalk array again from 0 to chalk.size() - 1:
- If k is less than the value at the current index i, return i as the index of the student who will run out of chalk.
- Otherwise, subtract the value at chalk[i] from k.
If no student is found within the loop, return 0 (though this should not be reached given the problem constraints).

Implementation

// 96ms, 77.05MB
class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        // Find the sum of all elements.
        int sum = 0;
        for (int i = 0; i < chalk.size(); i++) {
            sum += chalk[i];
            if (sum > k) {
                break;
            }
        }
        // Find modulo of k with sum.
        k = k % sum;
        for (int i = 0; i < chalk.size(); i++) {
            if (k < chalk[i]) {
                return i;
            }
            k = k - chalk[i];
        }
        return 0;
    }
};

Complexity Analysis

Let n be the size of the chalk array.

Time complexity: $O(n)$
We iterate through the chalk array exactly twice. Apart from this, all operations are performed in constant time. Therefore, the total time complexity is given by $O(n)$.
Space complexity: $O(1)$
No additional space is used proportional to the array size n. Therefore, the space complexity is given by $O(1)$.

Approach 2: Binary Search

Intuition

Instead of iterating through the array to find the first index, we can use binary search. Binary search is ideal here because it quickly narrows down the search space in a sorted array.

We start by defining a predicate function that checks if the prefix sum at a given index is greater than the k modulo sum. This function returns true for indices where the prefix sum exceeds the target and false otherwise. Since the array is sorted based on the prefix sums, true indicates indices with no chalk left, while false indicates indices with some chalk remaining.

Using binary search, we locate the smallest index where the predicate returns true.

If the predicate returns true, it means there might be smaller indices with true values, so we adjust the upper bound of the search space to the current index.
If the predicate returns false, it means all true values are beyond the current index, so we adjust the lower bound of the search space to the current index.

Algorithm

Main Function - chalkReplacer(chalk, k):

Create an array prefixSum of length n to store prefix sums.
Initialize prefixSum[0] with chalk[0].
Iterate through the chalk array from index 1 to n-1 and update prefixSum[i] as the sum of prefixSum[i-1] and chalk[i].
Calculate sum as prefixSum[n-1], representing the total chalk needed for one full round.
Calculate remainingChalk as k \% sum.
Call the helper function binarySearch(prefixSum, remainingChalk) to find the student who will run out of chalk and return the result of binarySearch.

Helper Function - binarySearch(arr, remainingChalk):

Set low to 0 and high to arr.length - 1.
While low is less than high:
- Calculate mid as the average of low and high.
- If arr[mid] is less than or equal to remainingChalk, update low to mid + 1.
- Otherwise, update high to mid.
Return high as the index of the student who will run out of chalk.

Implementation

// 89ms, 83.93MB
class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        int n = chalk.size();

        vector<long> prefixSum(n);
        prefixSum[0] = chalk[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + chalk[i];
        }

        long sum = prefixSum[n - 1];
        long remainingChalk = (k % sum);

        return binarySearch(prefixSum, remainingChalk);
    }

private:
    int binarySearch(vector<long>& arr, long tar) {
        int low = 0, high = arr.size() - 1;

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

            if (arr[mid] <= tar) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return high;
    }
};

Complexity Analysis

Let $n$ be the size of the chalk array.

Time complexity: $O(n)$
We iterate through the chalk array once. Apart from this, the binary search operation takes $O(\log n)$ time. Therefore, the total time complexity is given by $O(n)$.
Space complexity: $O(n)$
We initialize an array prefixSum of size n to store the prefix sums of the chalk array. Apart from this, no additional space is used. Therefore, the space complexity is given by $O(n)$.

24.09.03 - 1945. Sum of Digits of String After Convert

문제 링크

나

// 5ms, 10.12MB
class Solution {
public:
    int getLucky(string s, int k) {
        string convertedS;
        for(char c : s) {
            convertedS += to_string(c - 'a' + 1);
        }
        int num{};
        for(int i{};i<k;++i) {
            num = 0;
            for(char c : convertedS) {
                num += c - '0';
            }
            convertedS = to_string(num);
        }
        return  num;
    }
};

gpt

The "Sum of Digits of String After Convert" problem asks you to convert a string into its numeric form based on the position of each letter in the alphabet (a = 1, b = 2, ..., z = 26). After that, you perform a transformation k times where you sum the digits of the resulting number.

Approach:

Convert the string to a numeric string based on the alphabet's position.
Sum the digits of this number for k iterations.

C++ Solution:

// 6ms, 10.19MB
class Solution {
public:
    int getLucky(string s, int k) {
        // Convert string to a numerical string based on alphabetic position
        string numStr = "";
        for (char c : s) {
            numStr += to_string(c - 'a' + 1);
        }

        // Perform the transformation k times
        int sum = 0;
        for (int i = 0; i < k; ++i) {
            sum = 0;
            for (char c : numStr) {
                sum += c - '0';  // Sum digits
            }
            numStr = to_string(sum);  // Update the number as string
        }
        return sum;
    }
};

Explanation:

Step 1: Conversion: Convert each character in the string to its position in the alphabet. For example, "zbax" becomes "26213124".
Step 2: Transformation: Sum the digits of the resulting number and repeat this process k times.

Time Complexity:

$O(n + k \times d)$, where $n$ is the length of the string and $d$ is the number of digits in the number after conversion.

24.09.04 - 874. Walking Robot Simulation

문제 링크

나

simulation은 생각했는데, 장애물 처리 아이디어가 없다.

또 궁금했던 건 장애물이 (0, 0)에 있을 때 그냥 못 가는 건지, 처음에는 갈 수 있는 건지 도 애매했는 것 같다.
- 장애물 처리 아이디어 해설 참고!

$\Rightarrow$ 해설 참고

Solution

Overview

We have a robot facing north at the origin (0, 0) of an infinite 2D grid. The robot receives a series of instructions from a given list of commands, where instruction can be of three types:

-2: Turn left 90 degrees while staying at the current coordinate.
-1: Turn right 90 degrees while staying at the current coordinate.
Any positive integer k from 1 to 9: Advance k units in the current direction.

Additionally, we are given a list of obstacles containing the coordinates of various obstacles on the grid. If the robot encounters an obstacle while moving forward, it stops its motion at the coordinate just before the obstacle and proceeds to the next command.

Our goal is to find the farthest squared distance from the origin that the robot reaches during its journey. In other words, we need to find the maximum value of $x \times x + y \times y$ that can be achieved at any point (x, y) visited by the robot.

Keep in mind when planning your approach that the farthest traveled distance during the robot's journey is not the same as its distance from the origin at the end of its journey.

Note: An obstacle may exist at the origin (0, 0). In this case, the robot can move away from the starting point but will be unable to return to (0, 0).

Approach: Simulation

Intuition

The robot's state is defined by two factors:

The coordinates of the robot's position: we can use a simple integer array [x, y].
The direction the robot is facing: we can use an integer value (0, 1, 2, 3) representing North, East, South, and West respectively. Consequently, we need a directions array representing the direction of motion of the robot, where each index corresponds to [North, East, South, West].

The presence of obstacles prevents us from being able to simply loop over each command and simulate the robot's motion on the grid. A naive approach would be to loop through the obstacle array to check if the next attempted move is blocked by an obstacle. However, this results in quadratic complexity, which is inefficient given our constraints.

Checking whether a given coordinate is an obstacle using hash sets allows for constant-time lookups. If you're unfamiliar with hash sets, this LeetCode Explore Card provides an in-depth explanation.

Our challenge becomes how to look up coordinates in a hash set.

We solve this by hashing the coordinates of each obstacle to a unique integer value and storing these values in the hash set. To check if a coordinate contains an obstacle, we hash the coordinates using the same function and check if the value is present in the hash set.

There are various methods to create hashing functions. For this problem, we'll create a simple one that generates a unique integer value for all coordinates within the given problem constraints.

hash(x, y) = x + HASH_MULTIPLIER * y

Where HASH_MULTIPLIER is a constant slightly larger than twice the maximum possible coordinate value. In this case, we choose 60013.

We choose 60013 because it is the smallest prime number greater than 60000 (twice the maximum possible coordinate). This helps reduce the number of potential collisions in our hash function.

slideshow 생략

Algorithm

Create a constant HASH_MULTIPLIER to use in the hashing function.

robotSim Function:

Convert the list of obstacles into a set of hashed coordinates for quick lookup during the simulation.
Define the four possible movement directions corresponding to North, East, South, and West.
Initialize the robot's starting position at the origin (0, 0) and set the initial maximum distance squared to zero.
Initialize the current direction of the robot facing North.
Iterate through the list of commands:
- If the command is -1, turn the robot 90 degrees to the right by adjusting the current direction index.
- If the command is -2, turn the robot 90 degrees to the left by adjusting the current direction index.
- Otherwise, for a positive command, move the robot forward step by step:
  - Calculate the next potential position by adding the current direction vector to the robot's position.
  - If the next position is an obstacle, stop moving forward.
  - Otherwise, update the robot's position to the new coordinates.
- Update the maximum distance squared if the current position is farther from the origin than before.
Return the maximum distance squared as the result of the simulation.

hashCoordinates Function:

Combine the x and y coordinates into a unique hash value by multiplying the y coordinate by a constant multiplier and adding the x coordinate.
Return the computed hash value to be used for obstacle lookup.

Implementation

// 76ms, 38.18MB
class Solution {
private:
    static const long long HASH_MULTIPLIER =
        60013;  // Slightly larger than 2 * max coordinate value

    // Hash function to convert (x, y) coordinates to a unique integer value
    long long hashCoordinates(long long x, long long y) {
        return x + HASH_MULTIPLIER * y;
    }

public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        // Store obstacles in an unordered_set for efficient lookup
        unordered_set<long long> obstacleSet;
        for (auto& obstacle : obstacles) {
            obstacleSet.insert(hashCoordinates(obstacle[0], obstacle[1]));
        }

        // Define direction vectors: North, East, South, West
        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        vector<int> currentPosition = {0, 0};
        int maxDistanceSquared = 0;
        int currentDirection = 0;  // 0: North, 1: East, 2: South, 3: West

        for (int command : commands) {
            if (command == -1) {
                // Turn right
                currentDirection = (currentDirection + 1) % 4;
                continue;
            }
            if (command == -2) {
                // Turn left
                currentDirection = (currentDirection + 3) % 4;
                continue;
            }

            // Move forward
            vector<int> direction = directions[currentDirection];
            for (int step = 0; step < command; step++) {
                int nextX = currentPosition[0] + direction[0];
                int nextY = currentPosition[1] + direction[1];
                if (obstacleSet.contains(hashCoordinates(nextX, nextY))) {
                    break;
                }
                currentPosition[0] = nextX;
                currentPosition[1] = nextY;
            }

            maxDistanceSquared =
                max(maxDistanceSquared,
                    currentPosition[0] * currentPosition[0] +
                        currentPosition[1] * currentPosition[1]);
        }

        return maxDistanceSquared;
    }
};

Complexity Analysis

Let $m$ and $n$ be the length of commands and obstacles, respectively.

Time complexity: $O(m + n)$
The algorithm initially iterates over the obstacles array and hashes each obstacle’s coordinates, taking $O(n)$ time.

The algorithm then loops over the commands array. In the worst case, each command is a positive integer k. Since the maximum value of k is limited to 9, this step has a time complexity of $O(9 \cdot m) = O(m)$.

Thus, the overall time complexity of the algorithm is $O(n) + O(m) = O(m + n)$.
Space complexity: $O(n)$
The only additional space used by the algorithm is the obstacleSet, which stores up to $n$ hashed obstacle positions. The directions and currentPosition arrays and all other primitive variables use constant space.

Thus, the space complexity of the algorithm is $O(n)$.

gpt

In the "Walking Robot Simulation" problem, you are given a robot starting at the origin of a 2D plane, facing north. The robot receives a series of commands (positive for movement and negative for turns) and obstacles scattered on the plane. The goal is to determine the farthest distance (squared) the robot can be from the origin after executing all commands while avoiding obstacles.

Approach:

Movement Logic: Track robot's position and direction (north, east, south, west).
Obstacle Handling: Skip commands that would move the robot into obstacles.

C++ Code Solution:

// 124ms, 39.64MB
class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        // Directions: north, east, south, west
        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        unordered_set<string> obsSet;

        // Add obstacles to a hash set for O(1) lookup
        for (const auto& obs : obstacles) {
            obsSet.insert(to_string(obs[0]) + "," + to_string(obs[1]));
        }

        int x = 0, y = 0;  // Robot's position
        int dir = 0;  // Start facing north
        int maxDist = 0;

        for (int cmd : commands) {
            if (cmd == -1) {
                // Turn right (clockwise)
                dir = (dir + 1) % 4;
            } else if (cmd == -2) {
                // Turn left (counterclockwise)
                dir = (dir + 3) % 4;
            } else {
                // Move forward by 'cmd' units
                for (int step = 0; step < cmd; ++step) {
                    int newX = x + directions[dir][0];
                    int newY = y + directions[dir][1];

                    if (obsSet.count(to_string(newX) + "," + to_string(newY))) {
                        break;  // Hit an obstacle, stop moving
                    }

                    x = newX;
                    y = newY;
                    maxDist = max(maxDist, x * x + y * y);  // Update max distance
                }
            }
        }

        return maxDist;
    }
};

Explanation:

Direction Control: Use an array to manage directional changes (north, east, south, west).
Obstacle Checking: Store obstacles in a hash set for quick lookup and stop movement when hitting one.
Distance Calculation: Track the maximum squared distance from the origin.

Time Complexity:

$O(n + m)$, where $n$ is the number of commands and $m$ is the number of obstacles.

24.09.05 - 2028. Find Missing Observations

문제 링크

나

// 98ms, 126.21MB
class Solution {
public:
    vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
        int sum{};
        for(int roll : rolls) sum += roll;
        int m = rolls.size();

        int rest = mean * (n + m) - sum; // missing: n

        vector<int> answer;
        if(n <= rest && rest <= 6 * n) { // 답 만들 수 있음.
            // n개의 수로 others 만들기.
            for(;rest != n;--n) {
                int r = rest - (n - 1);
                if(1 <= r && r <= 6) {
                    answer.push_back(r);
                    rest -= r;
                }
                else {
                    answer.push_back(6);
                    rest -= 6;
                }
            }
            for(int i{};i<n;++i) answer.push_back(1);
        }
        
        return answer;
    }
};

gpt

To solve the LeetCode problem "Find Missing Observations", you need to find n missing dice rolls given m observed rolls and the mean of all n + m rolls.

The task is to determine what values those missing rolls should have to maintain the overall average.

Approach:

Calculate the total sum:
- The sum of all n + m rolls must be mean * (n + m).
- Calculate the sum of the observed rolls (rolls[]) and subtract it from this total to get the sum of the missing rolls.
Check for feasibility:
- The sum of the missing n rolls should be between n (all 1s) and 6 * n (all 6s) because each dice roll is between 1 and 6.
- If the sum is outside this range, it's impossible to generate valid rolls, and you return an empty array.
Distribute the sum:
- Distribute the sum of the missing rolls evenly. Start by assigning each missing roll the floor value of the average (total_sum_of_missing // n).
- Then, distribute the remainder (total_sum_of_missing % n) by adding 1 to the first few rolls to balance the total.

Code Implementation:

// 107ms, 116.37MB
class Solution {
public:
    vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
        int m = rolls.size();
        int total_sum = mean * (n + m);
        int observed_sum = 0;
        
        for (int roll : rolls) {
            observed_sum += roll;
        }
        
        int missing_sum = total_sum - observed_sum;
        
        // Check if it's possible to generate valid missing rolls
        if (missing_sum < n || missing_sum > 6 * n) {
            return {};
        }
        
        // Distribute the missing_sum
        vector<int> result(n, missing_sum / n);
        int remainder = missing_sum % n;
        
        for (int i = 0; i < remainder; ++i) {
            result[i]++;
        }
        
        return result;
    }
};

Explanation:

We first compute the total sum of all n + m rolls.
Then, subtract the observed sum to get the sum of the missing rolls.
If this sum is not within the valid range (n <= sum <= 6 * n), return an empty vector because it's impossible.
Otherwise, we distribute the sum evenly among the missing rolls, ensuring that the total remains consistent.

Time Complexity:

The time complexity is $O(m + n)$, where m is the size of rolls and n is the number of missing rolls.

Space Complexity:

The space complexity is $O(n)$ for the result array.

24.09.06 - 3217. Delete Nodes From Linked List Present in Array

문제 링크

나

// 387ms, 319.5MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        const int SIZE = 100'010;
        vector<int> dat(SIZE, 0);
        for(int num : nums) dat[num] = 1;

        // 시작점 찾기
        while(head -> next) {
            if(dat[head->val]) {
                head = head->next;
            }
            else break;
        }

        ListNode* now = head; // 첫 시작점은 무조건 존재하는 head
        while(now -> next) {
            ListNode* next = now -> next;
            if(dat[next->val]) {
                now -> next = next -> next;
            }
            else {
                if(!(now->next)) break;
                now = now -> next;
            }
        }

        return head;
    }
};

gpt

To solve the problem "Delete Nodes From Linked List Present in Array" on LeetCode, the goal is to remove all nodes from the linked list whose values are present in the given array nums. Here's an efficient approach using a hash set for constant-time lookups.

Approach:

Create a Set: Store all elements from the array nums in an unordered set for $O(1)$ lookup time.
Use a Dummy Node: Create a dummy node pointing to the head of the linked list. This simplifies edge cases like removing the head node.
Traverse the List: Iterate through the linked list and check if the value of the current node's next is in the set:
- If it is, bypass that node by adjusting the pointers.
- Otherwise, move to the next node.
Return the Modified List: Finally, return the list starting from dummy.next (to skip the dummy node itself).

C++ Solution:

// 405ms, 258.36MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        unordered_set<int> values(nums.begin(), nums.end());
        ListNode* dummy = new ListNode(0, head);
        ListNode* current = dummy;
        
        while (current->next != nullptr) {
            if (values.count(current->next->val)) {
                current->next = current->next->next;  // Remove the node
            } else {
                current = current->next;
            }
        }
        
        return dummy->next;  // Return the modified list
    }
};

Complexity:

Time Complexity: $O(n + m)$, where n is the size of the array nums and m is the number of nodes in the linked list.
Space Complexity: $O(n)$, for storing the elements of nums in a set.

This approach efficiently handles large inputs due to its linear complexity.

24.09.07 - 1367. Linked List in Binary Tree

문제 링크

나

TLE가 나서 해설 참고..

// TLE
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool answer{};
    ListNode* listStart;
    void traverseSubPath(ListNode* head, TreeNode* root) {
        if(answer) return;
        
        if(head == nullptr) { // reach the end.
            answer = true;
            return;
        }

        if(root == nullptr) return; // leaf

        if(head->val == root->val) { // 같다면 유지
            traverseSubPath(head->next, root->left);
            traverseSubPath(head->next, root->right);
        }

        // 아닌 경우 새로 시작
        traverseSubPath(listStart, root->left);
        traverseSubPath(listStart, root->right);
    }

    bool isSubPath(ListNode* head, TreeNode* root) {
        listStart = head;
        traverseSubPath(head, root);

        return answer;
    }
};

Solution

Overview

We are given a binary tree and a linked list. Our task is to determine if the linked list is represented by any downward path in the binary tree. A downward path in the binary tree is defined as a path that starts at any node and extends to its subsequent child nodes, going downward.

Approach 1: DFS

Intuition

A direct approach is to explore every possible path in the tree using Depth-First Search (DFS). This method allows us to examine each path fully before moving to the next.

We begin at the root of the tree and compare its value to the head of the linked list. If they match, we continue by checking the left and right children of the tree node against the next node in the linked list. If the tree node's value does not match the linked list node, we stop exploring that path since it can't lead to a match. We then backtrack and try the next possible path.

Algorithm

If root is null, return false (base case).
Call checkPath(root, head) to start checking for the linked list path in the tree.
checkPath function:
- If node is null, return false (base case).
- Call dfs(node, head) to check if a matching path starts from node.
  - If dfs returns true, return true (a matching path is found).
- Recursively call checkPath on both left and right subtrees with the same head.
dfs function:
- If head is null, return true (all nodes in the list have been matched).
- If node is null, return false (reached end of the tree without matching all nodes).
- If the value of node does not match head, return false (value mismatch).
- Recursively call dfs on both left and right children of node with head->next.
Return true if checkPath or dfs finds a matching path; otherwise, continue checking.

Implementation

// 25ms, 30.86MB
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!root) return false;
        return checkPath(root, head);
    }

private:
    bool checkPath(TreeNode* node, ListNode* head) {
        if (!node) return false;
        if (dfs(node, head)) return true;  // If a matching path is found
        // Recursively check left and right subtrees
        return checkPath(node->left, head) || checkPath(node->right, head);
    }

    bool dfs(TreeNode* node, ListNode* head) {
        if (!head) return true;  // All nodes in the list matched
        if (!node)
            return false;  // Reached end of tree without matching all nodes
        if (node->val != head->val) return false;  // Value mismatch
        return dfs(node->left, head->next) || dfs(node->right, head->next);
    }
};

Complexity Analysis

Let $n$ be the number of nodes in the tree and $m$ be the length of the linked list.

Time complexity: $O(n \times m)$
In the worst case, we might need to check every node in the tree as a potential starting point for the linked list. For each node, we might need to traverse up to $m$ nodes in the linked list.
Space complexity: $O(n + m)$
The space complexity remains the same as Approach 1 due to the recursive nature of the solution.

Approach 2: Iterative Approach

Intuition

A common rule of thumb is that all approaches solvable via recursion can also be solved using a stack to mimic the call stack's nature. Unlike recursion, where each function call adds a new frame to the call stack, using a stack avoids the risk of stack overflow errors in cases where the depth of recursion is too large (e.g., in a very deep tree).

We start by putting the root of the tree onto the stack. This stack helps us explore the tree without recursion. We repeatedly take the top node from the stack and check if there is a path from this node that matches the linked list. If there is, we return true. If not, we add the node's left and right children to the stack for further checking.

To match the path, we use another stack to keep track of pairs of tree nodes and linked list nodes. We compare each pair, and if they match, we continue with the next node in the linked list and the children of the current tree node. If we find that the entire linked list matches a path in the tree, we return true.

If we finish checking all possible paths without finding a match, we return false.

Fun fact: Iterative approaches often provide more control over traversal, allowing you to access every path and create patterns that do not follow traditional recursion rules.

Algorithm

Check if root is null:
- If root is null, return false (base case).
Initialize a stack nodes and push root onto the stack.
While the stack nodes is not empty:
- Pop the top node from the stack.
- Call isMatch(node, head) to check if the linked list head matches a path starting from node.
  - If isMatch returns true, return true (a matching path is found).
- If node has a left child, push it onto the stack.
- If node has a right child, push it onto the stack.
If no matching path is found after checking all nodes, return false.
isMatch function:
- Initialize a stack s and push a pair {node, lst} onto it.
- While the stack s is not empty:
  - Pop the top pair {currentNode, currentList} from the stack.
  - While both currentNode and currentList are not null:
    - If currentNode->val does not match currentList->val, break (no match).
    - Move to the next node in the linked list (currentList = currentList->next).
    - If currentList is not null:
      - If currentNode has a left child, push {currentNode->left, currentList} onto the stack.
      - If currentNode has a right child, push {currentNode->right, currentList} onto the stack.
      - Break to continue with the next pair in the stack.
  - If currentList becomes null, return true (all nodes in the list matched).
Return false if no matching path is found after exploring all possibilities.

Implementation

// 47ms, 50.24MB
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!root) return false;

        // Initialize a stack for DFS on the tree
        stack<TreeNode*> nodes;
        nodes.push(root);

        // Perform DFS
        while (!nodes.empty()) {
            TreeNode* node = nodes.top();
            nodes.pop();

            // Check if the current node's path matches the linked list
            if (isMatch(node, head)) {
                return true;
            }

            // Push left and right children onto the stack
            if (node->left) {
                nodes.push(node->left);
            }
            if (node->right) {
                nodes.push(node->right);
            }
        }

        return false;
    }

private:
    bool isMatch(TreeNode* node, ListNode* lst) {
        stack<pair<TreeNode*, ListNode*>> s;
        s.push({node, lst});

        while (!s.empty()) {
            auto [currentNode, currentList] = s.top();
            s.pop();

            while (currentNode && currentList) {
                if (currentNode->val != currentList->val) {
                    break;
                }
                currentList = currentList->next;

                if (currentList) {
                    if (currentNode->left) {
                        s.push({currentNode->left, currentList});
                    }
                    if (currentNode->right) {
                        s.push({currentNode->right, currentList});
                    }
                    break;
                }
            }

            if (!currentList) {
                return true;
            }
        }

        return false;
    }
};

Complexity Analysis

Let $n$ be the number of nodes in the tree and $m$ be the length of the linked list.

Time complexity: $O(n \times m)$
We potentially visit each node in the tree once. For each node, we might need to check up to $m$ nodes in the linked list.
Space complexity: $O(n)$
The space is used by the stack, which in the worst case might contain all nodes of the tree. We don't need extra space for the linked list traversal as it's done iteratively.

Approach 3: Knuth-Morris-Pratt (KMP) Algorithm

Intuition

Approach 3 is more advanced and requires an understanding of the Knuth-Morris-Pratt (KMP) string-matching algorithm. We suggest reviewing 28. Find the Index of the First Occurrence in a String - Easy Tagged and solving it using the KMP algorithm before diving into this approach.

The previous approaches all involve searching the tree from the root and checking each path independently, which can be repetitive. By adjusting the idea behind the KMP algorithm, we can reduce this repetition and optimize the approach.

The KMP algorithm efficiently finds occurrences of a pattern (in this case, the linked list) within a text by using a prefix table, or failure function, to skip unnecessary comparisons.

The key to KMP is the prefix table, also known as the failure function. This table helps us understand how to skip certain comparisons based on what we’ve already matched.

We first build a table that indicates the longest proper prefix of the pattern that is also a suffix. This table tells us where to resume the search in the pattern after a mismatch. For example, consider the pattern ABABCABAB. The prefix table for this pattern helps us understand that if a mismatch occurs after AB, we don’t need to start from the beginning of the pattern but can skip to the next best position that aligns with what we’ve already matched.

As we search for the pattern in the text, if we encounter a mismatch, the prefix table tells us how far back we should go in the pattern to continue the search efficiently. Instead of starting the comparison from the beginning of the pattern again, we use the prefix table to skip over parts of the pattern that have already been matched. This reduces unnecessary comparisons.

Similarly, we construct the prefix table for the linked list by following the same principle of finding the longest prefix that is also a suffix. This helps in efficiently finding where to resume the search if a mismatch occurs while traversing paths in the tree.

We perform a DFS on the tree, treating each node's value as part of the text where we want to match our pattern (the linked list). As we traverse the tree, if a mismatch occurs, the prefix table tells us how much of the pattern we can skip, based on what we’ve already matched.

Note: Running through a dry run of this approach will help you get a better grip on how it works. It’s a great way to see the logic in action with a few concrete examples and spot any issues.

Algorithm

Build the pattern and prefix table from the linked list:
- Initialize pattern with the value of the head node of the linked list.
- Initialize prefixTable with 0 to store prefix lengths.
- Iterate through the linked list to construct pattern and prefixTable:
  - For each value, update the patternIndex to find matching prefixes using the prefixTable.
  - Add the current value to pattern and update prefixTable accordingly.
  - Move to the next node in the linked list.
Perform DFS to search for the pattern in the tree:
- Call searchInTree with the root of the tree, starting pattern index 0, and the pattern and prefixTable.
searchInTree function:
- If node is null, return false (base case).
- Update patternIndex to find the matching prefix:
  - If the current node value does not match the pattern at patternIndex, use the prefixTable to backtrack to the correct index.
  - Increment patternIndex if there is a match.
- Check if the entire pattern has been matched (patternIndex == pattern.size()):
  - If matched, return true.
- Recursively search in both left and right subtrees of the current node:
  - Return true if either subtree contains a matching path; otherwise, continue searching.

Implementation

// 34ms, 30.95MB
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        // Build the pattern and prefix table from the linked list
        vector<int> pattern = {head->val}, prefixTable = {0};
        int patternIndex = 0;
        head = head->next;

        while (head) {
            while (patternIndex && head->val != pattern[patternIndex])
                patternIndex = prefixTable[patternIndex - 1];
            patternIndex += head->val == pattern[patternIndex];
            pattern.push_back(head->val);
            prefixTable.push_back(patternIndex);
            head = head->next;
        }

        // Perform DFS to search for the pattern in the tree
        return searchInTree(root, 0, pattern, prefixTable);
    }

private:
    bool searchInTree(TreeNode* node, int patternIndex,
                      const vector<int>& pattern,
                      const vector<int>& prefixTable) {
        if (!node) return false;

        while (patternIndex && node->val != pattern[patternIndex])
            patternIndex = prefixTable[patternIndex - 1];
        patternIndex += node->val == pattern[patternIndex];

        // Check if the pattern is fully matched
        if (patternIndex == pattern.size()) return true;

        // Recursively search left and right subtrees
        return searchInTree(node->left, patternIndex, pattern, prefixTable) ||
               searchInTree(node->right, patternIndex, pattern, prefixTable);
    }
};

Complexity Analysis

Let $n$ be the number of nodes in the tree and $m$ be the length of the linked list.

Time complexity: $O(n + m)$
Building the pattern and prefix table takes $O(m)$, and searching the tree is $O(n)$.
Space complexity: $O(n + m)$
We need $O(m)$ space for the pattern and prefix table. The recursive call stack in the worst case (skewed tree) can take up to $O(n)$ space.

24.09.08 - 725. Split Linked List in Parts

문제 링크

나

// 0ms, 13.9MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int cnt{};
        /*
        // 이 부분이 틀렸네..
        for(ListNode* now = head;now->next;now = now->next, ++cnt)
        if(head) ++cnt; // 초기 원소 누락
        */
        ListNode* now = head;
        while (now) {
            ++cnt;
            now = now->next;
        }

        int quotient = cnt / k, remainder = cnt % k;
        vector<int> sizes(k, quotient); // 크기 k, 원소 값: quotient
        for(int i{};i<remainder;++i) sizes[i]++;

        vector<ListNode*> answer;
        now = head;
        for(int i{}; i<k; ++i) {
            answer.push_back(now); // if nullptr => push_back nullptr.

            for(int j{};j<sizes[i] && now;++j) {
                if(j == sizes[i] - 1) {
                    ListNode* tmp = now->next; // 마지막 원소 연결 끊기
                    now->next = nullptr;
                    now = tmp;
                }
                else now = now->next;
            }
        }

        return answer;
    }
};

개수 카운팅할 때

for(ListNode* now = head;now->next;now = now->next, ++cnt)
if(head) ++cnt; // 초기 원소 누락

위의 코드에서 틀렸는데, 반례가 없을까..

수정한 코드

for(ListNode* now = head;now;now = now->next) { // 조건 수정
    ++cnt;
}

ListNode* now = head;
while (now) {
    ++cnt;
    now = now->next;
}

gpt

To solve the problem "Split Linked List in Parts", the idea is to divide the linked list into k parts where each part has an approximately equal number of nodes. The first few parts may have an extra node if the number of nodes is not perfectly divisible by k.

Steps to Solve:

Calculate the Length of the Linked List: Traverse the entire list to determine its total length N.
Determine the Size of Each Part:
- Each part should have a base size of N // k.
- There will be N % k parts that need one extra node. These parts should be handled first.
Split the List: Traverse the list again to split it into parts. For each part:
- Determine its size (either N // k or N // k + 1).
- Detach it from the main list by updating the next pointer.
Handle Remaining Parts: If k is larger than N, the remaining parts will be empty (null).

Code Example in C++:

// 5ms, 13.88MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        vector<ListNode*> result(k, nullptr);
        int length = 0;
        ListNode* temp = head;

        // Step 1: Calculate the total length of the linked list
        while (temp != nullptr) {
            length++;
            temp = temp->next;
        }

        int base_size = length / k;
        int extra = length % k;

        temp = head;
        for (int i = 0; i < k; ++i) {
            result[i] = temp;
            int part_size = base_size + (i < extra ? 1 : 0);

            // Split the list and prepare the next part
            for (int j = 0; j < part_size - 1; ++j) {
                if (temp != nullptr) {
                    temp = temp->next;
                }
            }

            if (temp != nullptr) {
                ListNode* next_part = temp->next;
                temp->next = nullptr;
                temp = next_part;
            }
        }

        return result;
    }
};

Complexity:

Time Complexity: $O(N)$, where N is the number of nodes in the list (two passes).
Space Complexity: $O(k)$ for storing the result.

FilesExpand file tree

Week1.md

Latest commit

History

Week1.md

File metadata and controls

ToC

September Week 1

24.09.01 - 2022. Convert 1D Array Into 2D Array

나

gpt

Approach:

Explanation:

Time Complexity:

24.09.02 - 1894. Find the Student that Will Replace the Chalk

나

Solution

Approach 1: Prefix Sum

Intuition

Algorithm

Implementation

Complexity Analysis

Approach 2: Binary Search

Intuition

Algorithm

Implementation

Complexity Analysis

24.09.03 - 1945. Sum of Digits of String After Convert

나

gpt

Approach:

C++ Solution:

Explanation:

Time Complexity:

24.09.04 - 874. Walking Robot Simulation

나

Solution

Overview

Approach: Simulation

Intuition

Algorithm

Implementation

Complexity Analysis

gpt

Approach:

C++ Code Solution:

Explanation:

Time Complexity:

24.09.05 - 2028. Find Missing Observations

나

gpt

Approach:

Code Implementation:

Explanation:

Time Complexity:

Space Complexity:

24.09.06 - 3217. Delete Nodes From Linked List Present in Array

나

gpt

Approach:

C++ Solution:

Complexity:

24.09.07 - 1367. Linked List in Binary Tree

나

Solution

Overview

Approach 1: DFS

Intuition

Algorithm

Implementation

Complexity Analysis

Approach 2: Iterative Approach

Intuition

Algorithm

Implementation

Complexity Analysis

Approach 3: Knuth-Morris-Pratt (KMP) Algorithm

Intuition

Algorithm

Implementation