# Posts tagged as “hashtable”

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.


Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.


Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr[i] < arr[j] for 1 <= i < j <= arr.length

## Solution 1: HashTable

Store all the elements into a hashtable, and check from 1 to max(arr).

Time complexity: O(max(arr)) ~ O(1000)
Space complexity: O(n)

## Solution 2: Binary Search

We can find the smallest index l using binary search, s.t.
arr[l] – l + 1 >= k
which means we missed at least k numbers at index l.
And the answer will be l + k.

Time complexity: O(logn)
Space complexity: O(1)

## Python3

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).


Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.


Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]


Example 4:

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]


Constraints:

• 1 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• labels.length == n
• labels is consisting of only of lower-case English letters.

## Solution: Post order traversal + hashtable

For each label, record the count. When visiting a node, we first record the current count of its label as before, and traverse its children, when done, increment the current count, ans[i] = current – before.

Time complexity: O(n)
Space complexity: O(n)

## Python3

Given a date string in the form Day Month Year, where:

• Day is in the set {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"}.
• Month is in the set {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}.
• Year is in the range [1900, 2100].

Convert the date string to the format YYYY-MM-DD, where:

• YYYY denotes the 4 digit year.
• MM denotes the 2 digit month.
• DD denotes the 2 digit day.

Example 1:

Input: date = "20th Oct 2052"
Output: "2052-10-20"


Example 2:

Input: date = "6th Jun 1933"
Output: "1933-06-06"


Example 3:

Input: date = "26th May 1960"
Output: "1960-05-26"


Constraints:

• The given dates are guaranteed to be valid, so no error handling is necessary.

## Solution: String + HashTable

Time complexity: O(1)
Space complexity: O(1)

## Python

Given a string path, where path[i] = 'N''S''E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return True if the path crosses itself at any point, that is, if at any time you are on a location you’ve previously visited. Return False otherwise.

Example 1:

Input: path = "NES"
Output: false
Explanation: Notice that the path doesn't cross any point more than once.


Example 2:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

Constraints:

• 1 <= path.length <= 10^4
• path will only consist of characters in {'N', 'S', 'E', 'W}

## Solution: Simulation + Hashtable

Time complexity: O(n)
Space complexity: O(n)

## C++

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.

Given an integer array rains where:

• rains[i] > 0 means there will be rains over the rains[i] lake.
• rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

• ans.length == rains.length
• ans[i] == -1 if rains[i] > 0.
• ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.


Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.


Example 3:

Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.


Example 4:

Input: rains = [69,0,0,0,69]
Output: [-1,69,1,1,-1]
Explanation: Any solution on one of the forms [-1,69,x,y,-1], [-1,x,69,y,-1] or [-1,x,y,69,-1] is acceptable where 1 <= x,y <= 10^9


Example 5:

Input: rains = [10,20,20]
Output: []
Explanation: It will rain over lake 20 two consecutive days. There is no chance to dry any lake.


Constraints:

• 1 <= rains.length <= 10^5
• 0 <= rains[i] <= 10^9

## Solution: Binary Search

Store the days we can dry a lake in a treeset.
Store the last day when a lake becomes full in a hashtable.
Whenever we encounter a full lake, try to find the first available day that we can dry it. If no such day, return no answer.

Time complexity: O(nlogn)
Space complexity: O(n)

## C++

Mission News Theme by Compete Themes.