LeetCode 81. Search in Rotated Sorted Array II

 81. Search in Rotated Sorted Array II

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

 

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

 

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums is guaranteed to be rotated at some pivot.
• -104 <= target <= 104

 

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

	class Solution {
	public:
	bool search(vector<int>& nums, int target) {
	int l = 0;
	int r = nums.size() - 1;
	while(l <= r)
	{
	int mid = l + (r-l) / 2;
	if (nums[mid] == target)
	return true;
	// with duplicates we can have this contdition, just update left & right
	if((nums[l] == nums[mid]) && (nums[r] == nums[mid]))
	{
	l++;
	r--;
	}
	// first half
	// first half is in order
	else if(nums[l] <= nums[mid])
	{
	// target is in first half
	if((nums[l] <= target) && (nums[mid] > target))
	r = mid - 1;
	else
	l = mid + 1;
	}
	// second half
	// second half is order
	// target is in second half
	else
	{
	if((nums[mid] < target) && (nums[r]>= target))
	l = mid + 1;
	else
	r = mid - 1;
	}
	}
	return false;
	}
	};

view raw 81. Search in Rotated Sorted Array II.cpp hosted with ❤ by GitHub

LeetCode 1274. Number of Ships in a Rectangle

 1274. Number of Ships in a Rectangle

(This problem is an interactive problem.)

Each ship is located at an integer point on the sea represented by a cartesian plane, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true If there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points: the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

 

Example :

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.

Example 2:

Input: ans = [[1,1],[2,2],[3,3]], topRight = [1000,1000], bottomLeft = [0,0]
Output: 3

 

Constraints:

• On the input ships is only given to initialize the map internally. You must solve this problem "blindfolded". In other words, you must find the answer using the given hasShips API, without knowing the ships position.
• 0 <= bottomLeft[0] <= topRight[0] <= 1000
• 0 <= bottomLeft[1] <= topRight[1] <= 1000
• topRight != bottomLeft

	/**
	* // This is Sea's API interface.
	* // You should not implement it, or speculate about its implementation
	* class Sea {
	* public:
	* bool hasShips(vector<int> topRight, vector<int> bottomLeft);
	* };
	*/
	class Solution {
	public:
	int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
	// If the current rectangle does not contain any ships, return 0.
	if (bottomLeft[0] > topRight[0] || bottomLeft[1] > topRight[1])
	return 0;
	if (!sea.hasShips(topRight, bottomLeft))
	return 0;
	// If the rectangle represents a single point, a ship is located
	if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
	return 1;
	// Recursively check each of the 4 sub-rectangles for ships
	int midX = (topRight[0] + bottomLeft[0]) / 2;
	int midY = (topRight[1] + bottomLeft[1]) / 2;
	return countShips(sea, {midX, midY}, bottomLeft) +
	countShips(sea, topRight, {midX + 1, midY + 1}) +
	countShips(sea, {midX, topRight[1]}, {bottomLeft[0], midY + 1}) +
	countShips(sea, {topRight[0], midY}, {midX + 1, bottomLeft[1]});
	}
	};

view raw 1274. Number of Ships in a Rectangle.cpp hosted with ❤ by GitHub

LeetCode 1029. Two City Scheduling

1029. Two City Scheduling

 A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

 

Example 1:

Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Example 2:

Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859

Example 3:

Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086

 

Constraints:

• 2 * n == costs.length
• 2 <= costs.length <= 100
• costs.length is even.
• 1 <= aCosti, bCosti <= 1000

	class Solution {
	public:
	int twoCitySchedCost(vector<vector<int>>& costs) {
	// sort by difference
	sort(costs.begin(), costs.end(), [&](vector<int> a, vector<int> b){
	return a[0] - a[1] < b[0] - b[1];
	});
	int sum = 0;
	for(int i = 0; i < costs.size(); i++){
	// left half: it is best to use a
	if(i < costs.size() / 2)
	sum += costs[i][0];
	// right half: it is best to use b
	else
	sum += costs[i][1];
	}
	return sum;
	}
	};

view raw 1029. Two City Scheduling.cpp hosted with ❤ by GitHub

LeetCode 716. Max Stack

 716. Max Stack

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

• MaxStack() Initializes the stack object.
• void push(int x) Pushes element x onto the stack.
• int pop() Removes the element on top of the stack and returns it.
• int top() Gets the element on the top of the stack without removing it.
• int peekMax() Retrieves the maximum element in the stack without removing it.
• int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

 

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

 

Constraints:

• -107 <= x <= 107
• At most 104 calls will be made to push, pop, top, peekMax, and popMax.
• There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

 

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call? 

	class MaxStack {
	public:
	// 構造体
	struct Node {
	int val;
	Node* next;
	Node* prev;
	Node(int x) {
	this->val = x;
	this->next = NULL;
	this->prev = NULL;
	}
	};
	Node* tail;
	map<int, stack<Node*>> hash;
	MaxStack() {
	tail = nullptr;
	}
	void push(int x) {
	Node* n = new Node(x);
	if(!tail) tail = n;
	else {
	tail->next = n;
	n->prev = tail;
	tail = n;
	}
	hash[x].push(n);
	}
	int pop() {
	int t = this->top();
	if(tail->prev){
	tail->prev->next = nullptr;
	tail = tail->prev;
	} else
	tail = nullptr;
	hash[t].pop();
	if(hash[t].empty()) hash.erase(t);
	return t;
	}
	int top() {
	return tail->val;
	}
	int peekMax() {
	return hash.rbegin()->first;
	}
	int popMax() {
	int t = this->peekMax();
	Node* n = hash[t].top();
	if(tail->val == t){
	this->pop();
	} else {
	// remove from hash
	hash[t].pop();
	if(hash[t].empty()) hash.erase(t);
	// remove from list
	if(n->prev)
	n->prev->next = n->next;
	if(n->next)
	n->next->prev = n->prev;
	}
	return t;
	}
	};
	/**
	* Your MaxStack object will be instantiated and called as such:
	* MaxStack* obj = new MaxStack();
	* obj->push(x);
	* int param_2 = obj->pop();
	* int param_3 = obj->top();
	* int param_4 = obj->peekMax();
	* int param_5 = obj->popMax();
	*/

view raw 716. Max Stack.cpp hosted with ❤ by GitHub

LeetCode 155. Min Stack

 155. Min Stack

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:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

	class MinStack {
	public:
	// keep with min value
	stack<pair<int, int>> st;
	MinStack() {
	}
	void push(int val) {
	if(st.empty()) st.push({val, val});
	else st.push({val, min(val, st.top().second)});
	}
	void pop() {
	st.pop();
	}
	int top() {
	return st.top().first;
	}
	int getMin() {
	return st.top().second;
	}
	};
	/**
	* Your MinStack object will be instantiated and called as such:
	* MinStack* obj = new MinStack();
	* obj->push(val);
	* obj->pop();
	* int param_3 = obj->top();
	* int param_4 = obj->getMin();
	*/

view raw 155. Min Stack.cpp hosted with ❤ by GitHub

LeetCode 200. Number of Islands

 200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

	class Solution {
	public:
	vector<vector<bool>> seen;
	vector<vector<char>> grid;
	int m, n;
	int ans = 0;
	// travel through island
	void bfs(int i, int j){
	queue<pair<int, int>> que;
	que.emplace(i, j);
	seen[i][j] = true;
	while(!que.empty()){
	int x = que.front().first;
	int y = que.front().second;
	que.pop();
	for(int dx = -1; dx <= 1; dx++){
	for(int dy = -1; dy <= 1; dy++){
	if(abs(dx + dy) != 1) continue;
	int nx = x + dx;
	int ny = y + dy;
	if(nx < 0 or nx >= m or ny < 0 or ny >= n or
	seen[nx][ny] or grid[nx][ny] == '0') continue;
	que.emplace(nx, ny);
	seen[nx][ny] = true;
	}
	}
	}
	}
	int numIslands(vector<vector<char>>& grid) {
	m = grid.size();
	n = grid[0].size();
	this->grid = grid;
	seen.resize(m, vector<bool>(n, false));
	for(int i = 0; i < m; i++)
	for(int j = 0; j < n; j++)
	if(grid[i][j] == '1' and !seen[i][j]){
	bfs(i, j);
	ans++;
	}
	return ans;
	}
	};

view raw 200. Number of Islands.cpp hosted with ❤ by GitHub

(Template BFS) LeetCode 286. Walls and Gates

 286. Walls and Gates

You are given an m x n grid rooms initialized with these three possible values.

• -1 A wall or an obstacle.
• 0 A gate.
• INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

 

Example 1:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2:

Input: rooms = [[-1]]
Output: [[-1]]

 

Constraints:

• m == rooms.length
• n == rooms[i].length
• 1 <= m, n <= 250
• rooms[i][j] is -1, 0, or 231 - 1.

	class Solution {
	public:
	void wallsAndGates(vector<vector<int>>& rooms) {
	queue<pair<int, int>> que;
	int m = rooms.size();
	int n = rooms[0].size();
	vector seen(m, vector<bool>(n));
	for(int i = 0; i < m; i++){
	for(int j = 0; j < n; j++){
	if(rooms[i][j] != 0) continue;
	que.emplace(i, j);
	seen[i][j] = true;
	}
	}
	while(!que.empty()){
	auto cur = que.front(); que.pop();
	// 4 side move
	for(int dx = - 1; dx <= 1; dx++){
	for(int dy = - 1; dy <= 1; dy++){
	if(abs(dx + dy) != 1) continue;
	int nx = cur.first + dx;
	int ny = cur.second + dy;
	if(nx >= 0 and nx < m and ny >= 0 and ny < n
	and rooms[nx][ny] != -1 and !seen[nx][ny]){
	// increase moves
	rooms[nx][ny] = rooms[cur.first][cur.second] + 1;
	que.emplace(nx, ny);
	seen[nx][ny] = true;
	}
	}
	}
	}
	}
	};

view raw 286. Walls and Gates hosted with ❤ by GitHub

LeetCode 311. Sparse Matrix Multiplication

 311. Sparse Matrix Multiplication

Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2. You may assume that multiplication is always possible.

 

Example 1:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

Example 2:

Input: mat1 = [[0]], mat2 = [[0]]
Output: [[0]]

 

Constraints:

• m == mat1.length
• k == mat1[i].length == mat2.length
• n == mat2[i].length
• 1 <= m, n, k <= 100
• -100 <= mat1[i][j], mat2[i][j] <= 100

	class Solution {
	public:
	vector<vector<pair<int, int>>> compressMatrix(vector<vector<int>>& matrix) {
	int rows = matrix.size();
	int cols = matrix[0].size();
	vector<vector<pair<int, int>>> compressedMatrix(rows);
	for (int row = 0; row < rows; ++row) {
	for (int col = 0; col < cols; ++col) {
	if (matrix[row][col] != 0) {
	compressedMatrix[row].push_back({matrix[row][col], col});
	}
	}
	}
	return compressedMatrix;
	}
	vector<vector<int>> multiply(vector<vector<int>>& mat1, vector<vector<int>>& mat2) {
	int m = mat1.size();
	int k = mat1[0].size();
	int n = mat2[0].size();
	// Store the non-zero values of each matrix.
	vector<vector<pair<int, int>>> A = compressMatrix(mat1);
	vector<vector<pair<int, int>>> B = compressMatrix(mat2);
	vector<vector<int>> ans(m, vector<int>(n, 0));
	for (int mat1Row = 0; mat1Row < m; ++mat1Row) {
	// Iterate on all current 'row' non-zero elements of mat1.
	for (auto [element1, mat1Col] : A[mat1Row]) {
	// Multiply and add all non-zero elements of mat2
	// where the row is equal to col of current element of mat1.
	for (auto [element2, mat2Col] : B[mat1Col]) {
	ans[mat1Row][mat2Col] += element1 * element2;
	}
	}
	}
	return ans;
	}
	};

view raw 311. Sparse Matrix Multiplication.cpp hosted with ❤ by GitHub

(Technique) Design the Hash Table Key - Summary

  Design the Key - Summary

Here are some takeaways about how to design the key for you.

1. When the order of each element in the string/array doesn't matter, you can use the sorted string/array as the key.
2. If you only care about the offset of each value, usually the offset from the first value, you can use the offset as the key.
3. In a tree, you might want to directly use the TreeNode as key sometimes. But in most cases, the serialization of the subtree might be a better idea.
4. In a matrix, you might want to use the row index or the column index as key.
5. In a Sudoku, you can combine the row index and the column index to identify which block this element belongs to.
6. Sometimes, in a matrix, you might want to aggregate the values in the same diagonal line. 

LeetCode 249. Group Shifted Strings

 249. Group Shifted Strings

We can shift a string by shifting each of its letters to its successive letter.

• For example, "abc" can be shifted to be "bcd".

We can keep shifting the string to form a sequence.

• For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".

Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.

 

Example 1:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]
Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

Example 2:

Input: strings = ["a"]
Output: [["a"]]

 

Constraints:

• 1 <= strings.length <= 200
• 1 <= strings[i].length <= 50
• strings[i] consists of lowercase English letters.

	class Solution {
	public:
	char shiftLetter(char letter, int shift) {
	// if circular
	return (letter - shift + 26) % 26 + 'a';
	}
	// Create a hash value
	string getHash(string& s) {
	// Calculate the number of shifts to make the first character to be 'a'
	int shift = s[0];
	string hashKey;
	for (char letter : s) {
	hashKey += shiftLetter(letter, shift);
	}
	return hashKey;
	}
	vector<vector<string>> groupStrings(vector<string>& strings) {
	unordered_map<string, vector<string>> mapHashToList;
	// Create a hash_value (hashKey) for each string and append the string
	// to the list of hash values i.e. mapHashToList["abc"] = ["abc", "bcd"]
	for (string str : strings) {
	string hashKey = getHash(str);
	mapHashToList[hashKey].push_back(str);
	}
	// Iterate over the map, and add the values to groups
	vector<vector<string>> groups;
	for (auto it : mapHashToList) {
	groups.push_back(it.second);
	}
	return groups;
	}
	};

view raw 249. Group Shifted Strings.cpp hosted with ❤ by GitHub