Posts tagged as “path”

花花酱 LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another

By zxi on December 5, 2021

You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.

Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:

'L' means to go from a node to its left child node.
'R' means to go from a node to its right child node.
'U' means to go from a node to its parent node.

Return the step-by-step directions of the shortest path from node s to node t.

Example 1:

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.

Example 2:

Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.

Constraints:

The number of nodes in the tree is n.
2 <= n <= 10⁵
1 <= Node.val <= n
All the values in the tree are unique.
1 <= startValue, destValue <= n
startValue != destValue

Solution: Lowest common ancestor

It’s no hard to see that the shortest path is from the start node to the lowest common ancestor (LCA) of (start, end), then to the end node. The key is to find the LCA while finding paths from root to two nodes.

We can use recursion to find/build a path from root to a target node.
The common prefix of these two paths is the path from root to the LCA that we need to remove from the shortest path.
e.g.
root to start “LLRLR”
root to dest “LLLR”
common prefix is “LL”, after removing, it becomes:
LCA to start “RLR”
LCA to dest “LR”
Final path becomes “UUU” + “LR” = “UUULR”

The final step is to replace the L/R with U for the start path since we are moving up and then concatenate with the target path.

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

C++

// Author: Huahua

class Solution {

public:

string getDirections(TreeNode* root, int startValue, int destValue) {

string startPath;

string destPath;

buildPath(root, startValue, startPath);

buildPath(root, destValue, destPath);

// Remove common suffix (shared path from root to LCA)

while (!startPath.empty() && !destPath.empty()

&& startPath.back() == destPath.back()) {

startPath.pop_back();

destPath.pop_back();

}

reverse(begin(destPath), end(destPath));

return string(startPath.size(), 'U') + destPath;

}

private:

bool buildPath(TreeNode* root, int t, string& path) {

if (!root) return false;

if (root->val == t) return true;

if (buildPath(root->left, t, path)) {

path.push_back('L');

return true;

} else if (buildPath(root->right, t, path)) {

path.push_back('R');

return true;

}

return false;

}

};

花花酱 LeetCode 257. Binary Tree Paths

By zxi on January 29, 2020

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Solution: Recursion

Time complexity: O(n)
Space complexity: O(n) / output can be O(n^2)

C++

// Author: Huahua

class Solution {

public:

vector<string> binaryTreePaths(TreeNode* root) {

vector<string> ans;

string s;

function<void(TreeNode*, int)> preorder = [&](TreeNode* node, int l) {

if (!node) return;

s += (l > 0 ? "->" : "") + to_string(node->val);

if (!node->left && !node->right)

ans.push_back(s);

preorder(node->left, s.size());

preorder(node->right, s.size());

while (s.size() != l) s.pop_back();

};

preorder(root, 0);

return ans;

}

};

花花酱 LeetCode 1233. Remove Sub-Folders from the Filesystem

By zxi on October 21, 2019

Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d/" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i] contains only lowercase letters and ‘/’
folder[i] always starts with character ‘/’
Each folder name is unique.

Solution: HashTable

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

C++

// Author: Huahua

class Solution {

public:

vector<string> removeSubfolders(vector<string>& folder) {

unordered_set<string> s(begin(folder), end(folder));

vector<string> ans;

for (const auto& cur : folder) {

string f = cur;

bool valid = true;

while (!f.empty() && valid) {

while (f.back() != '/') f.pop_back();

f.pop_back();

if (s.count(f)) valid = false;

}

if (valid) ans.push_back(cur);

}

return ans;

}

};

花花酱 LeetCode 778. Swim in Rising Water

By zxi on January 31, 2019

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example 1:

Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Note:

2 <= N <= 50.
grid[i][j] is a permutation of [0, …, N*N – 1].

Solution 1: Dijkstra’s Algorithm

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

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int swimInWater(vector<vector<int>>& grid) {

const int n = grid.size();

priority_queue<pair<int, int>> q; // {-time, y * N + x}

q.push({-grid[0][0], 0 * n + 0});

vector<int> seen(n * n);

vector<int> dirs{-1, 0, 1, 0, -1};

seen[0 * n + 0] = 1;

while (!q.empty()) {

auto node = q.top(); q.pop();

int t = -node.first;

int x = node.second % n;

int y = node.second / n;

if (x == n - 1 && y == n - 1) return t;

for (int i = 0; i < 4; ++i) {

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || ty < 0 || tx >= n || ty >= n) continue;

if (seen[ty * n + tx]) continue;

seen[ty * n + tx] = 1;

q.push({-max(t, grid[ty][tx]), ty * n + tx});

}

return -1;

}

};

Solution 2: Binary Search + BFS

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

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int swimInWater(vector<vector<int>>& grid) {

const int n = grid.size();

auto hasPath = [&grid, n](int t) {

if (grid[0][0] > t) return false;

queue<int> q;

vector<int> seen(n * n);

vector<int> dirs{1, 0, -1, 0, 1};

q.push(0);

while (!q.empty()) {

const int x = q.front() % n;

const int y = q.front() / n;

q.pop();

if (x == n - 1 && y == n - 1) return true;

for (int i = 0; i < 4; ++i) {

const int tx = x + dirs[i];

const int ty = y + dirs[i + 1];

if (tx < 0 || ty < 0 || tx >= n || ty >= n || grid[ty][tx] > t) continue;

const int key = ty * n + tx;

if (seen[key]) continue;

seen[key] = 1;

q.push(key);

}

return false;

};

int l = 0;

int r = n * n;

while (l < r) {

int m = l + (r - l) / 2;

if (hasPath(m)) {

r = m;

} else {

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 931. Minimum Falling Path Sum

By zxi on October 28, 2018

Problem

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row. The next row’s choice must be in a column that is different from the previous row’s column by at most one.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:

[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

The falling path with the smallest sum is [1,4,7], so the answer is 12.

Note:

1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100

Solution: DP

Time complexity: O(mn)

Space complexity: O(mn)

C++

// Author: Huahua, 12 ms

class Solution {

public:

int minFallingPathSum(vector<vector<int>>& A) {

int n = A.size();

int m = A[0].size();

vector<vector<int>> dp(n + 2, vector<int>(m + 2));

for (int i = 1; i <= n; ++i) {

dp[i][0] = dp[i][m + 1] = INT_MAX;

for (int j = 1; j <= m; ++j)

dp[i][j] = *min_element(dp[i - 1].begin() + j - 1,

dp[i - 1].begin() + j + 2) + A[i - 1][j - 1];

}

return *min_element(dp[n].begin() + 1, dp[n].end() - 1);

}

};

C++/in place

// Author: Huahua, 12 ms

class Solution {

public:

int minFallingPathSum(vector<vector<int>>& A) {

int n = A.size();

int m = A[0].size();

for (int i = 1; i < n; ++i)

for (int j = 0; j < m; ++j) {

int sum = A[i - 1][j];

if (j > 0) sum = min(sum, A[i - 1][j - 1]);

if (j < m - 1) sum = min(sum, A[i - 1][j + 1]);

A[i][j] += sum;

}

return *min_element(begin(A.back()), end(A.back()));

}

};