Press "Enter" to skip to content

Posts tagged as “hard”

花花酱 LeetCode 1192. Critical Connections in a Network

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Constraints:

  • 1 <= n <= 10^5
  • n-1 <= connections.length <= 10^5
  • connections[i][0] != connections[i][1]
  • There are no repeated connections.

Solution: Tarjan

Time complexity: O(v+e)
Space complexity: O(v+e)

C++

花花酱 LeetCode 1187. Make Array Strictly Increasing

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

  • 1 <= arr1.length, arr2.length <= 2000
  • 0 <= arr1[i], arr2[i] <= 10^9

Solution: DP

Time complexity: O(mn)
Space complexity: O(mn) -> O(m + n)

C++

花花酱 LeetCode 1178. Number of Valid Words for Each Puzzle

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

  • word contains the first letter of puzzle.
  • For each letter in word, that letter is in puzzle.
    For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Example :

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Constraints:

  • 1 <= words.length <= 10^5
  • 4 <= words[i].length <= 50
  • 1 <= puzzles.length <= 10^4
  • puzzles[i].length == 7
  • words[i][j]puzzles[i][j] are English lowercase letters.
  • Each puzzles[i] doesn’t contain repeated characters.

Solution: Subsets

Preprocessing:
Compress each word to a bit map, and compute the frequency of each bit map.
Since there are at most |words| bitmaps while its value ranging from 0 to 2^26, thus it’s better to use a hashtable instead of an array.

Query:
Use the same way to compress a puzzle into a bit map.
Try all subsets (at most 128) of the puzzle (the bit of the first character is be must), and check how many words match each subset.

words = [“aaaa”,”asas”,”able”,”ability”,”actt”,”actor”,”access”],
puzzle = “abslute”
bitmap(“aaaa”) = {0}
bitmap(“asas”) = {0, 18}
bitmap(“able”) = {0,1,4,11}
bitmap(“actt”) = {0, 2, 19}
bitmap(“actor”) = {0, 2, 14, 17, 19}
bitmap(“access”) = {0, 2, 4, 18}

bitmap(“abslute”) = {0, 1, 4, 11, 18, 19, 20}

Time complexity: O(sum(len(w_i)) + |puzzles|)
Space complexity: O(|words|)

C++

花花酱 LeetCode 1172. Dinner Plate Stacks

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

  • DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
  • void push(int val) pushes the given positive integer val into the leftmost stack with size less than capacity.
  • int pop() returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
  • int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index is empty.

Example:

Input: 
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
Output: 

[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

Explanation: DinnerPlates D = DinnerPlates(2); // Initialize with capacity = 2 D.push(1); D.push(2); D.push(3); D.push(4); D.push(5); // The stacks are now: 2  4   1  3  5 ﹈ ﹈ ﹈ D.popAtStack(0); // Returns 2. The stacks are now:  4   1  3  5 ﹈ ﹈ ﹈ D.push(20); // The stacks are now: 20 4   1  3  5 ﹈ ﹈ ﹈ D.push(21); // The stacks are now: 20 4 21   1  3  5 ﹈ ﹈ ﹈ D.popAtStack(0); // Returns 20. The stacks are now: 4 21   1  3  5 ﹈ ﹈ ﹈ D.popAtStack(2); // Returns 21. The stacks are now: 4   1  3  5 ﹈ ﹈ ﹈ D.pop() // Returns 5. The stacks are now: 4   1  3 ﹈ ﹈ D.pop() // Returns 4. The stacks are now: 1  3 ﹈ ﹈ D.pop() // Returns 3. The stacks are now: 1 ﹈ D.pop() // Returns 1. There are no stacks. D.pop() // Returns -1. There are still no stacks.

Constraints:

  • 1 <= capacity <= 20000
  • 1 <= val <= 20000
  • 0 <= index <= 100000
  • At most 200000 calls will be made to pushpop, and popAtStack.

Solution: Array of stacks + TreeSet

Store all the stacks in an array, and store the indices of all free stacks in a tree set.
1. push(): find the first free stack and push onto it, if it becomes full, remove it from free set.
2. pop(): pop element from the last stack by calling popAtIndex(stacks.size()-1).
3. popAtIndex(): pop element from given index
3.1 add it to free set if it was full
3.2 remove it from free set if it becomes empty
3.2.1 remove it from stack array if it is the last stack

Time complexity:
Push: O(logn)
Pop: O(logn)
PopAtIndex: O(logn)

Space complexity: O(n)

C++

花花酱 LeetCode 212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

  1. All inputs are consist of lowercase letters a-z.
  2. The values of words are distinct.

Solution 1: DFS

Time complexity: O(sum(m*n*4^l))
Space complexity: O(l)

C++

Solution 2: Trie

Store all the words into a trie, search the board using DFS, paths must be in the trie otherwise there is no need to explore.

Time complexity: O(sum(l) + 4^max(l))
space complexity: O(sum(l) + l)

C++