Posts tagged as “medium”

花花酱 LeetCode 912. Sort an Array

By zxi on February 1, 2020

Given an array of integers nums, sort the array in ascending order.

Example 1:

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

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

Since n <= 50000, any O(n^2) won’t pass, we need O(nlogn) or better

Solution 1: QuickSort

Time complexity: O(nlogn) ~ O(n^2)
Space complexity: O(logn) ~ O(n)

C++

// Author: Huahua, 60 ms

class Solution {

public:

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

function<void(int, int)> quickSort = [&](int l, int r) {

if (l >= r) return;

int i = l;

int j = r;

int p = nums[l + rand() % (r - l + 1)];

while (i <= j) {

while (nums[i] < p) ++i;

while (nums[j] > p) --j;

if (i <= j)

swap(nums[i++], nums[j--]);

}

quickSort(l, j);

quickSort(i, r);

};

quickSort(0, nums.size() - 1);

return nums;

}

};

Solution 2: Counting Sort

Time complexity: O(n)
Space complexity: O(max(nums) – min(nums))

C++

// Author: Huahua, 54 ms

class Solution {

public:

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

auto [min_it, max_it] = minmax_element(begin(nums), end(nums));

int l = *min_it, r = *max_it;

vector<int> count(r - l + 1);

for (int n : nums) ++count[n - l];

int index = 0;

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

while (count[i]--) nums[index++] = i + l;

return nums;

}

};

Solution 2: HeapSort

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

C++

// Author: Huahua, 72ms

class Solution {

public:

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

priority_queue<int> q(begin(nums), end(nums));

int i = nums.size();

while (!q.empty()) {

nums[--i] = q.top();

q.pop();

}

return nums;

}

};

C++

// Author: Huahua

class Solution {

public:

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

auto heapify = [&](int i, int e) {

while (i <= e) {

int l = 2 * i + 1;

int r = 2 * i + 2;

int j = i;

if (l <= e && nums[l] > nums[j]) j = l;

if (r <= e && nums[r] > nums[j]) j = r;

if (j == i) break;

swap(nums[i], nums[j]);

swap(i, j);

}

};

const int n = nums.size();

// Init heap

for (int i = n / 2; i >= 0; i--)

heapify(i, n - 1);

// Get min.

for (int i = n - 1; i >= 1; i--) {

swap(nums[0], nums[i]);

heapify(0, i - 1);

}

return nums;

}

};

Solution 3: MergeSort

Time complexity: O(nlogn)
Space complexity: O(logn + n)

C++

// Author: Huahua

class Solution {

public:

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

vector<int> t(nums.size());

function<void(int, int)> mergeSort = [&](int l, int r) {

if (l + 1 >= r) return;

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

mergeSort(l, m);

mergeSort(m, r);

int i1 = l;

int i2 = m;

int index = 0;

while (i1 < m || i2 < r)

if (i2 == r || (i1 < m && nums[i1] < nums[i2]))

t[index++] = nums[i1++];

else

t[index++] = nums[i2++];

std::copy(begin(t), begin(t) + index, begin(nums) + l);

};

mergeSort(0, nums.size());

return nums;

}

};

Solution 4: BST

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

C++

// Author: Huahua

class Solution {

public:

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

multiset<int> s(begin(nums), end(nums));

return {begin(s), end(s)};

}

};

花花酱 LeetCode 1302. Deepest Leaves Sum

By zxi on January 31, 2020

Given a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

Solution 1: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int deepestLeavesSum(TreeNode* root) {

int sum = 0;

int max_depth = 0;

function<void(TreeNode*, int)> dfs = [&](TreeNode* n, int d) {

if (!n) return;

if (d > max_depth) {

max_depth = d;

sum = 0;

}

if (d == max_depth) sum += n->val;

dfs(n->left, d + 1);

dfs(n->right, d + 1);

};

dfs(root, 0);

return sum;

}

};

花花酱 LeetCode 162. Find Peak Element

By zxi on January 31, 2020

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Solution: Binary Search

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

C++

// Author: Huahua

class Solution {

public:

int findPeakElement(const vector<int> &num) {

int l = 0, r = num.size() - 1; // preventing OOB

while (l < r) {

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

// Find the first m s.t. num[m] > num[m + 1]

if (num[m] > num[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 138. Copy List with Random Pointer

By zxi on January 29, 2020

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

-10000 <= Node.val <= 10000
Node.random is null or pointing to a node in the linked list.
Number of Nodes will not exceed 1000.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

Node* copyRandomList(Node* head) {

if (!head) return head;

unordered_map<Node*, Node*> m;

Node* cur = m[head] = new Node(head->val);

Node* ans = cur;

while (head) {

if (head->random) {

auto it = m.find(head->random);

if (it == end(m))

it = m.emplace(head->random, new Node(head->random->val)).first;

cur->random = it->second;

}

if (head->next) {

auto it = m.find(head->next);

if (it == end(m))

it = m.emplace(head->next, new Node(head->next->val)).first;

cur->next = it->second;

}

head = head->next;

cur = cur->next;

}

return ans;

}

};

花花酱 LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

By zxi on January 26, 2020

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between cities from_i and to_i, and given the integer distanceThreshold.

Return the city with the smallest numberof cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges’ weights along that path.

Example 1:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Example 2:

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

Constraints:

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i, distanceThreshold <= 10^4
All pairs (from_i, to_i) are distinct.

Solution1: Floyd-Warshall

All pair shortest path

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

C++

// Author: Huahua

class Solution {

public:

int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {

vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 2));

for (const auto& e : edges)

dp[e[0]][e[1]] = dp[e[1]][e[0]] = e[2];

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

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

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

dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v]);

int ans = -1;

int min_nb = INT_MAX;

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

int nb = 0;

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

if (v != u && dp[u][v] <= distanceThreshold)

++nb;

if (nb <= min_nb) {

min_nb = nb;

ans = u;

}

return ans;

}

};

Solution 2: Dijkstra’s Algorithm

Time complexity: O(V * ElogV) / worst O(n^3*logn), best O(n^2*logn)
Space complexity: O(V + E)

C++

// Author: Huahua

class Solution {

public:

int findTheCity(int n, vector<vector<int>>& edges, int t) {

vector<vector<pair<int, int>>> g(n);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

// Returns the number of nodes within t from s.

auto dijkstra = [&](int s) {

vector<int> dist(n, INT_MAX / 2);

set<pair<int, int>> q; // <dist, node>

vector<set<pair<int, int>>::const_iterator> its(n);

dist[s] = 0;

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

its[i] = q.emplace(dist[i], i).first;

while (!q.empty()) {

auto it = cbegin(q);

int d = it->first;

int u = it->second;

q.erase(it);

if (d > t) break; // pruning

for (const auto& p : g[u]) {

int v = p.first;

int w = p.second;

if (dist[v] <= d + w) continue;

// Decrease key

q.erase(its[v]);

its[v] = q.emplace(dist[v] = d + w, v).first;

}

return count_if(begin(dist), end(dist), [t](int d) { return d <= t; });

};

int ans = -1;

int min_nb = INT_MAX;

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

int nb = dijkstra(i);

if (nb <= min_nb) {

min_nb = nb;

ans = i;

}

return ans;

}

};