Posts tagged as “easy”

花花酱 LeetCode 1450. Number of Students Doing Homework at a Given Time

By zxi on May 16, 2020

Given two integer arrays startTime and endTime and given an integer queryTime.

The ith student started doing their homework at the time startTime[i] and finished it at time endTime[i].

Return the number of students doing their homework at time queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

Example 1:

Input: startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
Output: 1
Explanation: We have 3 students where:
The first student started doing homework at time 1 and finished at time 3 and wasn't doing anything at time 4.
The second student started doing homework at time 2 and finished at time 2 and also wasn't doing anything at time 4.
The third student started doing homework at time 3 and finished at time 7 and was the only student doing homework at time 4.

Example 2:

Input: startTime = [4], endTime = [4], queryTime = 4
Output: 1
Explanation: The only student was doing their homework at the queryTime.

Example 3:

Input: startTime = [4], endTime = [4], queryTime = 5
Output: 0

Example 4:

Input: startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
Output: 0

Example 5:

Input: startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
Output: 5

Constraints:

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {

int ans = 0;

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

if (startTime[i] <= queryTime && queryTime <= endTime[i]) ++ans;

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:

return sum(s <= queryTime <= e for s, e in zip(startTime, endTime))

花花酱 LeetCode 1441. Build an Array With Stack Operations

By zxi on May 11, 2020

Given an array target and an integer n. In each iteration, you will read a number from list = {1,2,3..., n}.

Build the target array using the following operations:

Push: Read a new element from the beginning list, and push it in the array.
Pop: delete the last element of the array.
If the target array is already built, stop reading more elements.

You are guaranteed that the target array is strictly increasing, only containing numbers between 1 to n inclusive.

Return the operations to build the target array.

You are guaranteed that the answer is unique.

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: 
Read number 1 and automatically push in the array -> [1]
Read number 2 and automatically push in the array then Pop it -> [1]
Read number 3 and automatically push in the array -> [1,3]

Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]

Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: You only need to read the first 2 numbers and stop.

Example 4:

Input: target = [2,3,4], n = 4
Output: ["Push","Pop","Push","Push","Push"]

Constraints:

1 <= target.length <= 100
1 <= target[i] <= 100
1 <= n <= 100
target is strictly increasing.

Solution: Simulation

For each number in target, keep discarding i if i != num by “Push” + “Pop”, until i == num. One more “Push”.

Time complexity: O(n)
Space complexity: O(n) or O(1) w/o output.

C++

// Author: Huahua

class Solution {

public:

vector<string> buildArray(vector<int>& target, int n) {

vector<string> ans;

int i = 1;

for (int num : target) {

while (i != num) {

ans.push_back("Push");

ans.push_back("Pop");

++i;

}

ans.push_back("Push");

++i;

}

return ans;

}

};

花花酱 LeetCode 1436. Destination City

By zxi on May 3, 2020

You are given the array paths, where paths[i] = [cityA_i, cityB_i] means there exists a direct path going from cityA_i to cityB_i. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are: 
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]
Output: "Z"

Constraints:

1 <= paths.length <= 100
paths[i].length == 2
1 <= cityA_i.length, cityB_i.length <= 10
cityA_i!= cityB_i
All strings consist of lowercase and uppercase English letters and the space character.

Solution: Count in / out degree for each node

Note: this is a more general solution to this type of problems.

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

Destination City: in_degree == 1 and out_degree == 0

C++

// Author: Huahua

class Solution {

public:

string destCity(vector<vector<string>>& paths) {

unordered_map<string, int> in, out;

for (const auto& path : paths) {

++out[path[0]];

++in[path[1]];

}

for (const auto& [city, degree] : in)

if (degree == 1 && out[city] == 0) return city;

return "";

}

};

LeetCode 1422. Maximum Score After Splitting a String

By zxi on April 25, 2020

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

Constraints:

2 <= s.length <= 500
The string s consists of characters ‘0’ and ‘1’ only.

Solution 1: Brute Force

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

Solution 2: Counting

2.1 Two passes,
1st, count the number of ones of the entire string
2nd, inc zeros or dec ones according to s[i]
ans = max(zeros + ones)

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

C++

// Author: Huahua

class Solution {

public:

int maxScore(string s) {

int ones = 0;

for (char c : s)

if (c == '1') ++ones;

int zeros = 0;

int ans = 0;

for (int i = 0; i < s.length() - 1; ++i) {

if (s[i] == '0') ++zeros;

else --ones;

ans = max(ans, zeros + ones);

}

return ans;

}

};

花花酱 LeetCode 1417. Reformat The String

By zxi on April 20, 2020

Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2:

Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

Example 3:

Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.

Example 4:

Input: s = "covid2019"
Output: "c2o0v1i9d"

Example 5:

Input: s = "ab123"
Output: "1a2b3"

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.

Solution: Two streams

Create two stacks, one for alphas, another for numbers. If the larger stack has more than one element than the other one then no solution, return “”. Otherwise, interleave two stacks, start with the larger one.

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

C++

// Author: Huahua

class Solution {

public:

string reformat(string s) {

string q1;

string q2;

for (char c : s) {

if (isalpha(c))

q1 += c;

else

q2 += c;

}

if (q1.length() < q2.length())

swap(q1, q2);

if (q1.length() > q2.length() + 1)

return "";

string ans;

while (!q1.empty()) {

ans += q1.back();

q1.pop_back();

if (q2.empty()) break;

ans += q2.back();

q2.pop_back();

}

return ans;

}

};