Daily Coding Challenge #6

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

``````/*
LeetCode - Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

1
/ \
2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42
*/

/**
* 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:
int maxPathSum(TreeNode* root) {
helper(root);
return ans;
}
private:
int ans=INT_MIN;
int helper(TreeNode* root){
// base case
if(!root) return 0;
// l and r store max path sum going thru left and right child of root
int l = helper(root->left);
int r = helper(root->right);
// max path for parent call of root
// include at most 1 child of root
int max_single = max(root->val, root->val+max(l,r));
// the maxsum path of the node
int max_top = max(max_single,root->val+l+r);
// store the max result
ans=max(ans,max_top);
return max_single;
}
};

static const auto io_sync_off = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
``````

``````/*
LeetCode - Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
*/

class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int sz=(int)nums.size();
if(!sz) return 0;
int ans=1,cnt=1;
sort(nums.begin(),nums.end());
for(int i=1;i<sz;i++){
// since the array is sorted, the diff between nums[i] and nums[i-1] must be 1
if(nums[i]==nums[i-1]+1){
cnt++;
ans=max(ans,cnt);
}
// if they are same, skip it
else if(nums[i]==nums[i-1]) continue;
else{
// reset counter
cnt=1;
if(i+ans>sz) break;
}
}
return ans;
}
};
static const auto io_sync_off = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
``````

``````/*
LeetCode - Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Could you solve it in linear time?

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
*/

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q;
vector<int> ans;
for(int i=0;i<nums.size();i++){
// remove the elements which are out of this window
while(!q.empty() && q.front()<=i-k) q.pop_front();
// remove all elements smaller than the currently
// being added element (remove useless elements)
while(!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
// add the current element at the end of q
q.push_back(i);
// add the front before sliding a window
if(i>=k-1) ans.push_back(nums[q.front()]);
}
return ans;
}
};

static const auto io_sync_off = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
``````

The source code is available in corresponding repo below. Star and watch for timely updates!

wingkwong / atcoder

Posted on by:

Wing-Kam

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.