277. (Locked)Find the Celebrity

Difficulty: Medium

Frequency: N/A

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a functionint findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
int findCelebrity(int n) {
if (n <= 1) return n;
int cand = 0;
for (int i = 1; i < n; i++) {
if (!know(i, cand) {
cand = i;
}
}
for (int j = 0; j < n; j++) {
if (j == cand) continue;
if (!know(j, cand) || know(cand, j)) return -1;
}
return cand;
}
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

339. (Locked)Nested List Weight Sum

Difficulty: Easy

Frequency: N/A

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]], return 10. (four 1’s at depth 2, one 2 at depth 1)

Example 2:
Given the list [1,[4,]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
*   public:
*     // Return true if this NestedInteger holds a single integer, rather than a nested list.
*     bool isInteger() const;
*
*     // Return the single integer that this NestedInteger holds, if it holds a single integer
*     // The result is undefined if this NestedInteger holds a nested list
*     int getInteger() const;
*
*     // Return the nested list that this NestedInteger holds, if it holds a nested list
*     // The result is undefined if this NestedInteger holds a single integer
*     const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
int depthSum(vector<NestedInteger>& nestedList) {
return DFS(nestedList, 1);
}
int DFS(vector<NestedInteger>& nestedList, int level) {
int sum = 0;
for (int i = 0; i < nestedList.size(); i++) {
if (nestedList[i].isInterger()) {
sum += nestedList[i].getInteger() * level;
} else {
sum += DFS(nestedList[i].getList(), level + 1);
}
}
return sum;
}
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

325. (Locked)Maximum Size Subarray Sum Equals k

Difficulty: Easy

Frequency: N/A

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Can you do it in O(n) time?

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<int, int> m;
int result = 0, cur_sum = 0;
for (int i = 0; i < nums.size(); i++) {
cur_sum += nums[i];
if (cur_sum == k) result = i + 1;
else if (m.find(k - cur_sum) != m.end()) {
result = max(result, i - m[k - cur_sum]);
}
if (m.find(cur_sum) == m.end()) m[cur_sum] = i;
}
return result;
}
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

266. (Locked)Palindrome Permutation

Difficulty: Easy

Frequency: N/A

Given a string, determine if a permutation of the string could form a palindrome.

For example,
"code" -> False, "aab" -> True, "carerac" -> True.

Hint:

1. Consider the palindromes of odd vs even length. What difference do you notice?
2. Count the frequency of each character.
3. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
bool canPermutePalindrome(string s) {
vector<int> count(256, 0);
for (auto c : s) count[c]++;
int oddCount = 0;
for (auto i : count) {
if (i % 2 != 0) oddCount++;
}
return oddCount <= 1;
}
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

245. (Locked)Shortest Word Distance III

Difficulty: Medium

Frequency: N/A

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”, word2 = “coding”, return 1. Given word1 = “makes”, word2 = “makes”, return 3.

Note: You may assume word1 and word2 are both in the list.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
int shortestWordDistance(vector<string>& words, string word1, string word2) {
int dist = INT_MAX, idx1 = -1, idx2 = -1;
for (int i = 0; i < n; i++) {
if (words[i] == word1) idx1= i;
if (words[i] == word2) {
if (word1 == word2) idx1 = idx2;
idx2 = i;
}
if (idx1 != -1 && idx2 != -1) dist = min(dist, abs(idx1 - idx2));
}
return dist;
}
}

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

243. (Locked)Shortest Word Distance

Difficulty: Easy

Frequency: N/A

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example, Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = “makes”, word2 = “coding”, return 1.

Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
int shortestDistance(vector<string>& words, string word1, string word2) {
int n = words.size(), idx1 = -1, idx2 = -1, dist = INT_MAX;
for (int i = 0 ; i < n; i++) {
if (words[i] == word1) idx1 = i;
else if (words[i] == word2) idx2 = i;
if (idx1 != -1 && idx2 != -1) dist = min(dist, abs(idx1, idx2));
}
return dist;
}
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

265. (Locked)Paint House II

Difficulty: Hard

Frequency: N/A

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs0 is the cost of painting house 0 with color 0; costs1 is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Note: All costs are positive integers.

Follow up: Could you solve it in O(nk) runtime?

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
if (costs.empty()) return 0;
int n = costs.size(), k = costs.size(), m1 = 0, m2 = 0;
vector<int> dp(k, 0);
for (int i = 0; i < n; i++) {
int t1 = m1, t2 = m2;
m1 = m2 = INT_MAX;
for (int j = 0; j < k; j++) {
dp[j] = (dp[j] != t1 ? t1 : t2) + costs[i][j];
if (m1 <= dp[j]) m2 = min(m2, dp[j]);
else {
m2 = m1;
m1 = dp[j];
}
}
}
}
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn: