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:

289. Game of Life

Difficulty: Medium

Frequency: N/A

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up:

  1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = m ? board[0].size() : 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = 0;
                for (int I = max(i - 1, 0); I < min(i + 2, m); I++) {
                    for (int J = max(j - 1, 0); J < min(j + 2, n); J++) {
                        count += board[I][J] & 1;
                    }
                }
                if (count == 3 || count - board[i][j] == 3) {
                    board[i][j] |= 2;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;
            }
        }
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

229. Majority Element II

Difficulty: Medium

Frequency: N/A

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

  1. How many majority elements could it possibly have?
  2. Do you have a better hint? Suggest it!

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int cnt1 = 0, cnt2 = 0, a = 0, b = 1;
        for (int n : nums) {
            if (a == n) cnt1++;
            else if (b == n) cnt2++;
            else if (cnt1 == 0) {
                a = n;
                cnt1 = 1;
            } else if (cnt2 == 0) {
                b = n;
                cnt2 = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }
        cnt1 = cnt2 = 0;
        for (int n : nums) {
            if (n == a) cnt1++;
            else if (n == b) cnt2++;
        }
        vector<int> results;
        if (cnt1 > nums.size() / 3) results.push_back(a);
        if (cnt2 > nums.size() / 3) results.push_back(b);
        return results;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

188. Best Time to Buy and Sell Stock IV

Difficulty: Hard

Frequency: N/A

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

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (k >= n / 2) return helper(prices);
        vector<vector<int>> dp(k + 1, vector<int>(n, 0));
        for (int i = 1; i <= k; i++) {
            int tmpMax = -prices[0];
            for (int j = 1; j < n; j++) {
                dp[i][j] = max(dp[i][j - 1], tmpMax + prices[j]);
                tmpMax = max(tmpMax, dp[i - 1][j - 1] - prices[j]);
            }
        }
        return dp[k][n - 1];
    }
    int helper(vector<int>& prices) {
        int n = prices.size(), result = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1]) {
                result += prices[i] - prices[i - 1];
            }
        }
        return result;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

128. Longest Consecutive Sequence

Difficulty: Medium

Frequency: N/A

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int longestConsecutive(vector<int> nums) {
        unordered_set<int> s;
        for (int n : nums) s.insert(n);
        int maxLen = 1;
        for (int n : nums) {
            if (s.empty()) break;
            int curNum = n;
            int curLen = 0;
            while (s.count(curNum)) {
                s.erase(curNum);
                curLen++;
                curNum++;
            }
            curNum = n - 1;
            while (s.count(curNum)) {
                s.erase(curNum);
                curLen++;
                curNum--;
            }
            maxLen = max(maxLen, curLen);
        }
        return maxLen;
    }
};

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)

Follow Up:
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:

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: