Huahua's Tech Road

花花酱 LeetCode 230. Kth Smallest Element in a BST

By zxi on April 13, 2019

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Solution: Inorder traversal

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

C++

class Solution {

public:

int kthSmallest(TreeNode* root, int k) {

return inorder(root, k);

}

private:

int inorder(TreeNode* root, int& k) {

if (!root) return -1;

int x = inorder(root->left, k);

if (k == 0) return x;

if (--k == 0) return root->val;

return inorder(root->right, k);

}

};

花花酱 LeetCode 209. Minimum Size Subarray Sum

By zxi on April 13, 2019

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguoussubarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Solution 1: Two Pointers (Sliding Window)

Maintain a sliding window [l, r) such that sum(nums[l:r)) >= s, then move l to l + 1, and move r accordingly to make the window valid.

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

C++

class Solution {

public:

int minSubArrayLen(int s, vector<int>& nums) {

int l = 0;

int r = 0;

int t = 0;

int ans = INT_MAX;

while (l < nums.size()) {

while (t < s && r < nums.size()) t += nums[r++];

if (t < s) break;

ans = min(ans, r - l);

t -= nums[l++];

}

return ans == INT_MAX ? 0 : ans;

}

};

花花酱 LeetCode 54. Spiral Matrix

By zxi on April 12, 2019

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

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

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Solution: Simulation

Keep track of the current bounds (left, right, top, bottom).

Init: left = 0, right = n – 1, top = 0, bottom = m – 1

Each time we move in one direction and shrink the bounds and turn 90 degrees:
1. go right => –top
2. go down => –right
3. go left => ++bottom
4. go up => ++left

C++

class Solution {

public:

vector<int> spiralOrder(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

int l = 0;

int t = 0;

int r = matrix[0].size();

int b = matrix.size();

const int total = (r--) * (b--);

int d = 0;

int x = 0;

int y = 0;

vector<int> ans;

while (ans.size() < total - 1) {

if (d == 0) {

while (x < r) ans.push_back(matrix[y][x++]);

++t;

} else if (d == 1) {

while (y < b) ans.push_back(matrix[y++][x]);

--r;

} else if (d == 2) {

while (x > l) ans.push_back(matrix[y][x--]);

--b;

} else if (d == 3) {

while (y > t) ans.push_back(matrix[y--][x]);

++l;

}

d = (d + 1) % 4;

}

if (ans.size() != total) ans.push_back(matrix[y][x]);

return ans;

}

};

花花酱 LeetCode 417. Pacific Atlantic Water Flow

By zxi on April 11, 2019

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

The order of returned grid coordinates does not matter.
Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

Solution: DFS/BFS

Be careful with the input range, easy to TLE with a naive implementation. Have to search from the boards.

Time complexity: O(mn)
Space complexity: O(mn)

DFS

// Author: Huahua, running time: 48 ms

class Solution {

public:

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

const int n = matrix.size();

const int m = matrix[0].size();

vector<vector<int>> p(n, vector<int>(m));

vector<vector<int>> a(n, vector<int>(m));

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

dfs(matrix, x, 0, 0, p); // top

dfs(matrix, x, n - 1, 0, a); // bottom

}

for (int y = 0; y < n; ++y) {

dfs(matrix, 0, y, 0, p); // left

dfs(matrix, m - 1, y, 0, a); // right

}

vector<pair<int, int>> ans;

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

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

if (p[i][j] && a[i][j]) ans.emplace_back(i, j);

return ans;

}

private:

void dfs(vector<vector<int>>& b, int x, int y, int h, vector<vector<int>>& v) {

if (x < 0 || y < 0 || x == b[0].size() || y == b.size()) return;

if (v[y][x] || b[y][x] < h) return;

v[y][x] = true;

dfs(b, x + 1, y, b[y][x], v);

dfs(b, x - 1, y, b[y][x], v);

dfs(b, x, y + 1, b[y][x], v);

dfs(b, x, y - 1, b[y][x], v);

}

};

BFS

class Solution {

public:

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

const int n = matrix.size();

const int m = matrix[0].size();

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

auto bfs = [&](queue<pair<int, int>>& q, vector<vector<int>>& v) {

while (!q.empty()) {

const int y = q.front().first;

const int x = q.front().second;

q.pop();

const int h = matrix[y][x];

v[y][x] = true;

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

int tx = x + dirs[i];

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

if (tx < 0 || ty < 0 || tx == m || ty == n || matrix[ty][tx] < h) continue;

if (v[ty][tx]) continue;

q.push({ty, tx});

}

};

queue<pair<int, int>> qp;

queue<pair<int, int>> qa;

vector<vector<int>> vp(n, vector<int>(m));

vector<vector<int>> va(n, vector<int>(m));

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

qp.push({0, x}); // top

qa.push({n - 1, x}); // bottom

}

for (int y = 0; y < n; ++y) {

qp.push({y, 0}); // left

qa.push({y, m - 1}); // right

}

bfs(qp, vp);

bfs(qa, va);

vector<pair<int, int>> ans;

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

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

if (vp[i][j] && va[i][j]) ans.emplace_back(i, j);

return ans;

}

};

DP

// Author: Huahua, running time: 104 ms

class Solution {

public:

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

const int n = matrix.size();

const int m = matrix[0].size();

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

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

dp[0][x] |= 1;

dp[n - 1][x] |= 2;

}

for (int y = 0; y < n; ++y) {

dp[y][0] |= 1;

dp[y][m - 1] |= 2;

}

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

while (true) {

bool changed = false;

for (int y = 0; y < n; ++y)

for (int x = 0; x < m; ++x)

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

const int tx = x + dirs[d];

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

if (tx < 0 || ty < 0 || tx == m || ty == n

|| matrix[y][x] < matrix[ty][tx]

|| (dp[y][x] | dp[ty][tx]) == dp[y][x]) continue;

dp[y][x] |= dp[ty][tx];

changed = true;

}

if (!changed) break;

}

vector<pair<int, int>> ans;

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

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

if (dp[i][j] == 3) ans.emplace_back(i, j);

return ans;

}

};

花花酱 LeetCode 394. Decode String

By zxi on April 10, 2019

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Solution 1: Recursion

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

C++

// Author: Huahua, 4ms

class Solution {

public:

string decodeString(string s) {

if (s.empty()) return "";

string ans;

int i = 0;

int n = s.length();

int c = 0;

while (isdigit(s[i]) && i < n)

c = c * 10 + (s[i++] - '0');

int j = i;

if (i < n && s[i] == '[') {

int open = 1;

while (++j < n && open) {

if (s[j] == '[') ++open;

if (s[j] == ']') --open;

}

} else {

while (j < n && isalpha(s[j])) ++j;

}

// "def2[ac]" => "def" + decodeString("2[ac]")

// | |

// i j

if (i == 0)

return s.substr(0, j) + decodeString(s.substr(j));

// "3[a2[c]]ef", ss = decodeString("a2[c]") = "acc"

// | |

// i j

string ss = decodeString(s.substr(i + 1, j - i - 2));

while (c--)

ans += ss;

// "3[a2[c]]ef", ans = "abcabcabc", ans += decodeString("ef")

ans += decodeString(s.substr(j));

return ans;

}

};