Posts tagged as “hashtable”

You are given an integer array cards where cards[i] represents the value of the ith card. A pair of cards are matching if the cards have the same value.

Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.

Example 1:

Input: cards = [3,4,2,3,4,7]
Output: 4
Explanation: We can pick up the cards [3,4,2,3] which contain a matching pair of cards with value 3. Note that picking up the cards [4,2,3,4] is also optimal.


Example 2:

Input: cards = [1,0,5,3]
Output: -1
Explanation: There is no way to pick up a set of consecutive cards that contain a pair of matching cards.


Constraints:

• 1 <= cards.length <= 105
• 0 <= cards[i] <= 106

Solution: Hashtable

Record the last position of each number,
ans = min{cardi – last[cardi]}

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

C++

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array ofnums sorted in ascending order.

Example 1:

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation:
The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2:

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation:
There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].


Constraints:

• 1 <= nums.length <= 1000
• 1 <= sum(nums[i].length) <= 1000
• 1 <= nums[i][j] <= 1000
• All the values of nums[i] are unique.

Solution: Hashtable

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

C++

You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level.

Return the minimum rounds required to complete all the tasks, or -1 if it is not possible to complete all the tasks.

Example 1:

Input: tasks = [2,2,3,3,2,4,4,4,4,4]
Output: 4
Explanation: To complete all the tasks, a possible plan is:
- In the first round, you complete 3 tasks of difficulty level 2.
- In the second round, you complete 2 tasks of difficulty level 3.
- In the third round, you complete 3 tasks of difficulty level 4.
- In the fourth round, you complete 2 tasks of difficulty level 4.
It can be shown that all the tasks cannot be completed in fewer than 4 rounds, so the answer is 4.


Example 2:

Input: tasks = [2,3,3]
Output: -1
Explanation: There is only 1 task of difficulty level 2, but in each round, you can only complete either 2 or 3 tasks of the same difficulty level. Hence, you cannot complete all the tasks, and the answer is -1.


Constraints:

• 1 <= tasks.length <= 105
• 1 <= tasks[i] <= 109

Solution: Math

Count the frequency of each level. The only case that can not be finished is 1 task at some level. Otherwise we can always finish it by 2, 3 tasks at a time.

if n = 2: 2 => 1 round
if n = 3: 3 => 1 round
if n = 4: 2 + 2 => 2 rounds
if n = 5: 3 + 2 => 2 rounds

if n = 3k, n % 3 == 0 : 3 + 3 + … + 3 = k rounds
if n = 3k + 1, n % 3 == 1 : 3*(k – 1) + 2 + 2 = k + 1 rounds
if n = 3k + 2, n % 3 == 2 : 3*k + 2 = k + 1 rounds

We need (n + 2) / 3 rounds.

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

C++

You are given an integer array matches where matches[i] = [winneri, loseri] indicates that the player winneri defeated player loseri in a match.

Return a list answer of size 2 where:

• answer[0] is a list of all players that have not lost any matches.
• answer[1] is a list of all players that have lost exactly one match.

The values in the two lists should be returned in increasing order.

Note:

• You should only consider the players that have played at least one match.
• The testcases will be generated such that no two matches will have the same outcome.

Example 1:

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.


Example 2:

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.


Constraints:

• 1 <= matches.length <= 105
• matches[i].length == 2
• 1 <= winneri, loseri <= 105
• winneri != loseri
• All matches[i] are unique.

Solution: Hashtable

Use a hashtable to store the number of matches each player has lost. Note, also create an entry for those winners who never lose.

Time complexity: O(m), m = # of matches
Space complexity: O(n), n = # of players

C++

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

• answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
• answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].


Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• -1000 <= nums1[i], nums2[i] <= 1000

Solution: Hashtable

Use two hashtables to store the unique numbers of array1 and array2 respectfully.

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