loading...

Daily Coding Challenge #127

wingkwong profile image Wing-Kam ・2 min read

About

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.


/*
Best Time to Buy and Sell Stock
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
*/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // peaks and valleys 
        int mi=INT_MAX, mx=0;
        for(int i=0;i<prices.size();i++){
            if(prices[i]<mi) mi=prices[i];
            else if(prices[i]-mi>mx) mx=prices[i]-mi;
        }
        return mx;
    }
};

/*
Linked List Deletion
https://binarysearch.io/problems/Linked-List-Deletion

Given a singly linked list node, and an integer target, return the same linked list with all nodes whose value is target removed.

Example 1
Input

node = 0 → 1 → 1 → 2
target = 1
Output

0 → 2
*/

#include "solution.hpp"
using namespace std;

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
class Solution {
    public:
    LLNode* solve(LLNode* node, int target) {
        while(node&&node->val==target) node=node->next;
        LLNode* cur=node;
        while(cur&&cur->next){
            if(cur->next->val==target) cur->next = cur->next->next; 
            else cur = cur->next;
        }
        return node;
    }
};


/*
Sum of Three Numbers Sequel
https://binarysearch.com/problems/Sum-of-Three-Numbers-Sequel

Given a list of integers nums and an integer k, find three distinct entries in nums, a, b, c, such that abs(a + b + c - k) is minimized and return the absolute difference.

Constraints

n ≤ 1,000 where n is length of nums.
Example 1
Input

nums = [2, 4, 25, 7]
k = 15
Output

2
Explanation

Taking [2, 4, 7] will get us closest to 15 and the absolute difference is abs(13 - 15) = 2.
*/

#include "solution.hpp"
using namespace std;


class Solution {
    public:
    int solve(vector<int>& nums, int k) {
        // 3 sum approach
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans=INT_MAX;
        for(int i=0;i<n;i++){
            int l=i+1, r=n-1;
            while(l<r){
                if(abs(nums[i]+nums[l]+nums[r]-k)<ans){
                    ans=abs(nums[i]+nums[l]+nums[r]-k);
                }else if(nums[i]+nums[l]+nums[r]>k) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        return ans;
    }
};


There are other programming solutions in the following repositories below. Star and watch for timely updates!

GitHub logo wingkwong / competitive-programming

🌟 My CP Journey - This repository contains CP solutions (mostly written in C++) from different OJs and contest sites 🌟

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

pic
Editor guide