Jan 21 - Daily Programming Diary

21.01.2021 — Diary, Programming — 1 min read

23:00

Writing pretty late tonight. So I gave the test for Delhivery today and I think it went pretty well. For what it's worth, I think that there is a good chance but then again, luck never has my side now does it!

Since I forgot to complete yesterday's Leetcode Challenge. Of course, a standard stack application, checking balanced parentheses.

valid-paretheses.cpp

1bool isValid(string s) {
2    stack<char> stk;
3    for (int i = 0; i < s.length(); i++) {
4        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
5            stk.push(s[i]);
6        } else if (stk.empty()) {
7            return false;
8        } else {
9            if (s[i] == ')' && stk.top() == '(') {
10                stk.pop();
11            } else if (s[i] == ']' && stk.top() == '[') {
12                stk.pop();
13            } else if (s[i] == '}' && stk.top() == '{') {
14                stk.pop();
15            } else return false;
16        }
17    }
18    return stk.empty();
19}

Now, today's question seemed to be out of my league but I thought about a stack based solution that can find the smallest element in the first n-k elements and then proceed with the rest of the array.

find-the-most-competitive-subsequence.cpp

1vector<int> mostCompetitive(vector<int> &nums, int k) {
2    int permitted_ops = nums.size() - k;
3    stack<int> stk;
4    for (int i = 0; i < nums.size(); i++) {
5        while (!stk.empty() && nums[i] < stk.top() && permitted_ops > 0) {
6            stk.pop();
7            permitted_ops--;
8        }
9        stk.push(nums[i]);
10    }
11
12    stack<int> temp;
13    vector<int> ans;
14
15    while (!stk.empty()) {
16        temp.push(stk.top());
17        stk.pop();
18    }
19
20    while (!temp.empty() && k--) {
21        ans.push_back(temp.top());
22        temp.pop();
23    }
24
25    return ans;
26}

That's all for today. I think I'll read a book now. Not gonna write more since I don't wanna jinx it.

Bye!

EOD Checklist

Leetcode January Challenge
Raahee
This blog