Huahua’s Tech Road

花花酱 LeetCode 155. Min Stack

By zxi on November 28, 2021

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output

[null,null,null,null,-3,null,0,-2]

Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints:

-2³¹ <= val <= 2³¹ - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

Solution 1: Two Stacks

One normal stack, one monotonic stack to store the min values.

Time complexity: O(1) per op
Space complexity: O(n)

C++

// Author: Huahua

class MinStack {

public:

void push(int x) {

m_data.push(x);

if (m_s.empty() || x <= m_s.top())

m_s.push(x);

}

void pop() {

if (!m_s.empty() && m_data.top() == m_s.top())

m_s.pop();

m_data.pop();

}

int top() {

return m_data.top();

}

int getMin() {

return m_s.empty() ? m_data.top() : m_s.top();

}

private:

stack<int> m_data;

stack<int> m_s;

};

花花酱 LeetCode 151. Reverse Words in a String

By zxi on November 28, 2021

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Example 4:

Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"

Example 5:

Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"

Constraints:

1 <= s.length <= 10⁴
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Solution: Stack

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

C++

// Author: Huahua

class Solution {

public:

string reverseWords(string s) {

stringstream ss(s);

stack<string> st;

string w;

while (ss >> w)

st.push(w);

string ans;

while (!st.empty()) {

ans += st.top();

st.pop();

if (!st.empty()) ans += ' ';

}

return ans;

}

};

Solution: In-Place

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

C++

// Author: Huahua

class Solution {

public:

string reverseWords(string& s) {

reverse(begin(s), end(s));

int l = 0;

for (int i = 0, j = 0; i < s.length(); ++i) {

if (s[i] == ' ') continue;

if (l) ++l;

j = i;

while (j < s.length() && s[j] != ' ') ++j;

reverse(begin(s) + l, begin(s) + j);

l += (j - i);

i = j;

}

s.resize(l);

return s;

}

};

花花酱 LeetCode 2092. Find All People With Secret

By zxi on November 28, 2021

You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [x_i, y_i, time_i] indicates that person x_i and person y_i have a meeting at time_i. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person x_i has the secret at time_i, then they will share the secret with person y_i, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.

Example 1:

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Example 2:

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.

Example 3:

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3.
Note that person 2 can share the secret at the same time as receiving it.
At time 2, person 3 shares the secret with person 4.
Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

Example 4:

Input: n = 6, meetings = [[0,2,1],[1,3,1],[4,5,1]], firstPerson = 1
Output: [0,1,2,3]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 0 shares the secret with person 2, and person 1 shares the secret with person 3.
Thus, people 0, 1, 2, and 3 know the secret after all the meetings.

Constraints:

2 <= n <= 10⁵
1 <= meetings.length <= 10⁵
meetings[i].length == 3
0 <= x_i, y_i<= n - 1
x_i != y_i
1 <= time_i <= 10⁵
1 <= firstPerson <= n - 1

Solution: Union Find

Sorting meetings by time.

At each time stamp, union people who meet.
Key step: “un-union” people if they DO NOT connected to 0 / known the secret after each timestamp.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {

map<int, vector<pair<int, int>>> events;

for (const auto& m : meetings)

events[m[2]].emplace_back(m[0], m[1]);

vector<int> p(n);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return p[x] == x ? x : (p[x] = find(p[x]));

};

p[firstPerson] = 0;

for (const auto& [t, s] : events) {

for (const auto [u, v] : s)

p[find(u)] = find(v);

for (const auto [u, v] : s) {

if (find(u) != find(0)) p[u] = u;

if (find(v) != find(0)) p[v] = v;

}

vector<int> ans;

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

if (find(i) == find(0)) ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 2091. Removing Minimum and Maximum From Array

By zxi on November 28, 2021

You are given a 0-indexed array of distinct integers nums.

There is an element in nums that has the lowest value and an element that has the highest value. We call them the minimum and maximum respectively. Your goal is to remove both these elements from the array.

A deletion is defined as either removing an element from the front of the array or removing an element from the back of the array.

Return the minimum number of deletions it would take to remove both the minimum and maximum element from the array.

Example 1:

Input: nums = [2,10,7,5,4,1,8,6]
Output: 5
Explanation: 
The minimum element in the array is nums[5], which is 1.
The maximum element in the array is nums[1], which is 10.
We can remove both the minimum and maximum by removing 2 elements from the front and 3 elements from the back.
This results in 2 + 3 = 5 deletions, which is the minimum number possible.

Example 2:

Input: nums = [0,-4,19,1,8,-2,-3,5]
Output: 3
Explanation: 
The minimum element in the array is nums[1], which is -4.
The maximum element in the array is nums[2], which is 19.
We can remove both the minimum and maximum by removing 3 elements from the front.
This results in only 3 deletions, which is the minimum number possible.

Example 3:

Input: nums = [101]
Output: 1
Explanation:  
There is only one element in the array, which makes it both the minimum and maximum element.
We can remove it with 1 deletion.

Constraints:

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
The integers in nums are distinct.

Solution: Three ways

There are only three ways to remove min/max elements.
1) Remove front elements
2) Remove back elements
3) Remove one with front elements, and another one with back elements.

Just find the best way to do it.

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

C++

// Author: Huahua

class Solution {

public:

int minimumDeletions(vector<int>& nums) {

const int n = nums.size();

auto [it1, it2] = minmax_element(begin(nums), end(nums));

int i = it1 - begin(nums);

int j = it2 - begin(nums);

return min({max(i, j) + 1, // remove front elements

n - min(i, j), // remove back elements

min(i, j) + 1 + n - max(i, j)} // front + back

);

}

};

Huahua's Tech Road

花花酱 LeetCode 155. Min Stack

Solution 1: Two Stacks

C++

花花酱 LeetCode 151. Reverse Words in a String

Solution: Stack

C++

Solution: In-Place

C++

花花酱 LeetCode 142. Linked List Cycle II

Solution 1: Hashtset

C++

Solution: Fast slow pointers

C++

花花酱 LeetCode 2092. Find All People With Secret

Solution: Union Find

C++

Related Problems

花花酱 LeetCode 2091. Removing Minimum and Maximum From Array

Solution: Three ways

C++