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:

Advertisements

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:

239. Sliding Window Maximum

Difficulty: Hard

Frequency: N/A

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

Hint:

  1. How about using a data structure such as deque (double-ended queue)?
  2. The queue size need not be the same as the window’s size.
  3. Remove redundant elements and the queue should store only elements that need to be considered.

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> results;
        for (int i = 0; i < nums.size(); i++) {
            if (!dq.empty() && dq.front() == i - k) dq.pop_front();
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }
            dq.push_back(i);
            if (i >= k - 1) {
                results.push_back(nums[dq.front()]);
            }
        }
        return results;
    }
};

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:

218. The Skyline Problem

Difficulty: Hard

Frequency: N/A

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings Skyline ContourThe geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        multimap<int, int> coords;
        for (auto& b : buildings) {
            coords.emplace(b[0], b[2]);
            coords.emplace(b[1], -b[2]);
        }
        
        multiset<int> heights = {0};
        vector<pair<int, int>> corners;
        int x = -1, y = 0;
        for (auto& p : coords) {
            if ((x >= 0) && (p.first != x) && (corners.empty() || corners.rbegin()->second != y)) {
                corners.emplace_back(x, y);
            }
            if (p.second >= 0) {
                heights.insert(p.second);
            } else {
                heights.erase(heights.find(-p.second));
            }
            x = p.first;
            y = *heights.rbegin();
        }
        
        if ((!corners.empty()) && (corners.rbegin()->second != 0)) {
            corners.emplace_back(x, 0);
        }

        return corners;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

126. Word Ladder II

Difficulty: Hard

Frequency: N/A

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
        m.clear();
        results.clear();
        path.clear();
        
        wordList.insert(beginWord);
        wordList.insert(endWord);
        
        unordered_set<string> cur_lev;
        cur_lev.insert(beginWord);
        unordered_set<string> next_lev;
        path.push_back(endWord);
        
        while (true) {
            // delete previous level words
            for (auto it = cur_lev.begin(); it != cur_lev.end(); it++) {
                wordList.erase(*it);
            }
            // find current level words
            for (auto it = cur_lev.begin(); it != cur_lev.end(); it++) {
                findDict(*it, wordList, next_lev);
            }
            if (next_lev.empty()) {
                return results;
            }
            // if find endWord
            if (next_lev.find(endWord) != wordList.end()) {
                output(beginWord, endWord);
                return results;
            }
            cur_lev.clear();
            cur_lev = next_lev;
            next_lev.clear();
        }
        return results;
    }
private:
    unordered_map<string, vector<string>> m;
    vector<vector<string>> results;
    vector<string> path;
    void findDict(string word, unordered_set<string>& wordList, unordered_set<string>& next_level) {
        int n = word.size();
        string s = word;
        for (int i = 0; i < n; i++) {
            s = word;
            for (int j = 0; j < 26; j++) {
                s[i] = 'a' + j;
                if (wordList.find(s) != wordList.end()) {
                    next_level.insert(s);
                    m[s].push_back(word);
                }
            }
        }
    }
    void output(string& start, string last) {
        if (last == start) {
            reverse(path.begin(), path.end());
            results.push_back(path);
            reverse(path.begin(), path.end());
        } else {
            for (int i = 0; i < m[last].size(); i++) {
                path.push_back(m[last][i]);
                output(start, m[last][i]);
                path.pop_back();
            }
        }
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

210. Course Schedule II

Difficulty: Medium

Frequency: N/A

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:

  1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
private:
    vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_set<int>> graph(numCourses);
        for (auto pre : prerequisites) {
            graph[pre.second].insert(pre.first);
        }
        return graph;
    }
    bool dfs(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited, vector<int>& result) {
        if (visited[node]) return false;
        visited[node] = onpath[node] = true;
        for (int neighbor : graph[node]) {
            if (onpath[neighbor] || dfs(graph, neighbor, onpath, visited, result)) {
                return true;
            }
        }
        result.push_back(node);
        return onpath[node] = false;
    }
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
        vector<bool> onpath(numCourses, false), visited(numCourses, false);
        vector<int> result;
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i] && dfs(graph, i, onpath, visited, result)) {
                return {};
            }
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn: