Posts tagged as “medium”

花花酱 LeetCode 962. Maximum Width Ramp

By zxi on December 25, 2018

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i.

Find the maximum width of a ramp in A. If one doesn’t exist, return 0.

Example 1:

Input: [6,0,8,2,1,5] 
Output: 4 
Explanation:  The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1] 
Output: 7 
Explanation:  The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

Solution: Stack

Using a stack to store start candidates’ (decreasing order) index
Scan from right to left, compare the current number with the one on the top of the stack, pop if greater.

e.g.
A = [6,0,8,2,1,5]
stack = [0, 1] => [6, 0]
cur: A[5] = 5, stack.top = A[1] = 0, ramp = 5, stack.pop()
cur: A[4] = 1, stack.top = A[0] = 6
cur: A[3] = 2, stack.top = A[0] = 6
cur: A[2] = 8, stack.top = A[0] = 6, ramp = 2, stack.pop()
stack.isEmpty() => END

C++

// Author: Huahua, running time: 44 ms

class Solution {

public:

int maxWidthRamp(vector<int>& A) {

stack<int> s;

for (int i = 0; i < A.size(); ++i)

if (s.empty() || A[i] < A[s.top()])

s.push(i);

int ans = 0;

for (int i = A.size() - 1; i >= 0; --i)

while (!s.empty() && A[i] >= A[s.top()]) {

ans = max(ans, i - s.top());

s.pop();

}

return ans;

}

};

Python3

# Author: Huahua, running time: 92 ms

class Solution:

def maxWidthRamp(self, A):

s = []

for i in range(len(A)):

if not s or A[i] < A[s[-1]]: s.append(i)

ans = 0

for i in range(len(A) - 1, -1, -1):

while s and A[i] >= A[s[-1]]:

ans = max(ans, i - s.pop())

return ans

花花酱 LeetCode 78. Subsets

By zxi on December 22, 2018

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]

Solution: Combination

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

Implemention 1: DFS

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

vector<vector<int>> ans;

vector<int> cur;

for (int i = 0; i <= nums.size(); ++i)

dfs(nums, i, 0, cur, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (n == cur.size()) {

ans.push_back(cur);

return;

}

for (int i = s; i < nums.size(); ++i) {

cur.push_back(nums[i]);

dfs(nums, n, i + 1, cur, ans);

cur.pop_back();

}

};

Python3

# Author: Huahua, running time: 60 ms

class Solution:

def subsets(self, nums):

ans = []

def dfs(n, s, cur):

if n == len(cur):

ans.append(cur.copy())

return

for i in range(s, len(nums)):

cur.append(nums[i])

dfs(n, i + 1, cur)

cur.pop()

for i in range(len(nums) + 1):

dfs(i, 0, [])

return ans

Implementation 2: Binary

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

const int n = nums.size();

vector<vector<int>> ans;

for (int s = 0; s < 1 << n; ++s) {

vector<int> cur;

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

if (s & (1 << i)) cur.push_back(nums[i]);

ans.push_back(cur);

}

return ans;

}

};

Python3

# Author: Huahua, 40 ms

class Solution:

def subsets(self, nums):

n = len(nums)

return [[nums[i] for i in range(n) if s & 1 << i > 0] for s in range(1 << n)]

花花酱 LeetCode 220. Contains Duplicate III

By zxi on December 20, 2018

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Solution: Sliding Window + Multiset (OrderedSet)

Maintaining a sliding window of sorted numbers of k + 1. After the i-th number was inserted into the sliding window, check whether its left and right neighbors satisfy abs(nums[i] – neighbor) <= t

Time complexity: O(nlogk)
Space complexity: O(k)

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

multiset<long> s;

for (int i = 0; i < nums.size(); ++i) {

if (i > k)

s.erase(s.find(nums[i - k - 1]));

auto it = s.insert(nums[i]);

if (it != begin(s) && *it - *prev(it) <= t)

return true;

if (next(it) != end(s) && *next(it) - *it <= t)

return true;

}

return false;

}

};

花花酱 LeetCode 959. Regions Cut By Slashes

By zxi on December 18, 2018

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space. These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as "\\".)

Return the number of regions.

Example 1:

Input:[  " /",  "/ "]
Output: 2
Explanation: The 2x2 grid is as follows:

Example 2:

Input:[  " /",  "  "]
Output: 1
Explanation: The 2x2 grid is as follows:

Example 3:

Input:[  "\\/",  "/\\"]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)The 2x2 grid is as follows:

Example 4:

Input:[  "/\\",  "\\/"]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)The 2x2 grid is as follows:

Example 5:

Input:[  "//",  "/ "]
Output: 3
Explanation: The 2x2 grid is as follows:

Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either '/', '\', or ' '.

Solution 1: Split grid into 4 triangles and Union Find Faces

Divide each grid into 4 triangles and union them if not split.
Time complexity: O(n^2*alphn(n^2))
Space complexity: O(n^2)

C++

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

int n = grid.size();

DSU dsu(4 * n * n);

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

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

int index = 4 * (r * n + c);

switch (grid[r][c]) {

case '/':

dsu.merge(index + 0, index + 3);

dsu.merge(index + 1, index + 2);

break;

case '\\':

dsu.merge(index + 0, index + 1);

dsu.merge(index + 2, index + 3);

break;

case ' ':

dsu.merge(index + 0, index + 1);

dsu.merge(index + 1, index + 2);

dsu.merge(index + 2, index + 3);

break;

default: break;

}

if (r + 1 < n)

dsu.merge(index + 2, index + 4 * n + 0);

if (c + 1 < n)

dsu.merge(index + 1, index + 4 + 3);

}

int ans = 0;

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

if (dsu.find(i) == i) ++ans;

return ans;

}

private:

class DSU {

public:

DSU(int n): parent_(n) {

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

parent_[i] = i;

}

int find(int x) {

if (parent_[x] != x) parent_[x] = find(parent_[x]);

return parent_[x];

}

void merge(int x, int y) {

parent_[find(x)] = find(y);

}

private:

vector<int> parent_;

};

Solution 2: Euler’s Formula / Union-Find vertices

C++

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

int n = grid.size();

p_ = vector<int>((n + 1) * (n + 1));

// All vertices on the boundaries are merged into root(0).

for (int r = 0; r < n + 1; ++r)

for (int c = 0; c < n + 1; ++c)

p_[getIndex(n, r, c)] = (r == 0 || r == n || c == 0 || c == n) ? 0 : getIndex(n, r, c);

int f = 1;

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

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

if (grid[r][c] == ' ') continue;

// A new face will created if two vertices are already in the same group.

if (grid[r][c] == '/') {

f += merge(getIndex(n, r, c + 1),

getIndex(n, r + 1, c));

} else {

f += merge(getIndex(n, r, c),

getIndex(n, r + 1, c + 1));

}

return f;

}

private:

vector<int> p_;

int getIndex(int n, int r, int c) { return r * (n + 1) + c; }

int find(int x) {

if (p_[x] != x) p_[x] = find(p_[x]);

return p_[x];

}

int merge(int x, int y) {

int rx = find(x);

int ry = find(y);

if (rx == ry) return 1;

p_[ry] = rx;

return 0;

}

};

Solution 3: Pixelation (Upscale 3 times)

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

C++

// Author: Huahua, running time: 20 ms

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

const int n = grid.size();

vector<vector<int>> g(n * 3, vector<int>(n * 3));

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

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

if (grid[i][j] == '/') {

g[i * 3 + 0][j * 3 + 2] = 1;

g[i * 3 + 1][j * 3 + 1] = 1;

g[i * 3 + 2][j * 3 + 0] = 1;

} else if (grid[i][j] == '\\') {

g[i * 3 + 0][j * 3 + 0] = 1;

g[i * 3 + 1][j * 3 + 1] = 1;

g[i * 3 + 2][j * 3 + 2] = 1;

}

int ans = 0;

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

for (int j = 0; j < 3 * n; ++j) {

if (g[i][j]) continue;

visit(g, j, i, n * 3);

++ans;

}

return ans;

}

private:

void visit(vector<vector<int>>& g, int x, int y, int n) {

if (x < 0 || x >= n || y < 0 || y >= n) return;

if (g[y][x]) return;

g[y][x] = 1;

visit(g, x + 1, y, n);

visit(g, x, y + 1, n);

visit(g, x - 1, y, n);

visit(g, x, y - 1, n);

}

};

花花酱 LeetCode 958. Check Completeness of a Binary Tree

By zxi on December 18, 2018

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Example 1:

Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Note:

The tree will have between 1 and 100 nodes.

Solution:

Level order traversal, if any nodes appears after a missing node then the tree is not a perfect binary tree.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isCompleteTree(TreeNode* root) {

if (!root) return true;

queue<TreeNode> q;

q.push(root);

bool missing = false;

while (!q.empty()) {

auto size = q.size();

while (size--) {

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

if (node) {

if (missing) return false;

q.push(node->left);

q.push(node->right);

} else {

missing = true;

}

return true;

}

};

Python3

class Solution:

def isCompleteTree(self, root):

if not root: return True

q = collections.deque([root])

missing = False

while q:

size = len(q)

while size > 0:

size -= 1

node = q.popleft()

if node:

if missing: return False

q.append(node.left)

q.append(node.right)

else:

missing = True

return True