Press "Enter" to skip to content

Posts published in “Hashtable”

花花酱 LeetCode 2441. Largest Positive Integer That Exists With Its Negative

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

Example 1:

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the only valid k we can find in the array.

Example 2:

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3:

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no a single valid k, we return -1.

Constraints:

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • nums[i] != 0

Solution 1: Hashtable

We can do in one pass by checking whether -x in the hashtable and update ans with abs(x) if so.

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

C++

Solution 2: Sorting

Sort the array by abs(x) in descending order.

[-1,10,6,7,-7,1] becomes = [-1, 1, 6, -7, 7, 10]

Check whether arr[i] = -arr[i-1].

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

C++

Solution 3: Two Pointers

Sort the array.

Let sum = nums[i] + nums[j], sum == 0, we find one pair, if sum < 0, ++i else –j.

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

C++

花花酱 LeetCode 2399. Check Distances Between Same Letters

You are given a 0-indexed string s consisting of only lowercase English letters, where each letter in s appears exactly twice. You are also given a 0-indexed integer array distance of length 26.

Each letter in the alphabet is numbered from 0 to 25 (i.e. 'a' -> 0'b' -> 1'c' -> 2, … , 'z' -> 25).

In a well-spaced string, the number of letters between the two occurrences of the ith letter is distance[i]. If the ith letter does not appear in s, then distance[i] can be ignored.

Return true if s is a well-spaced string, otherwise return false.

Example 1:

Input: s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: true
Explanation:
- 'a' appears at indices 0 and 2 so it satisfies distance[0] = 1.
- 'b' appears at indices 1 and 5 so it satisfies distance[1] = 3.
- 'c' appears at indices 3 and 4 so it satisfies distance[2] = 0.
Note that distance[3] = 5, but since 'd' does not appear in s, it can be ignored.
Return true because s is a well-spaced string.

Example 2:

Input: s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: false
Explanation:
- 'a' appears at indices 0 and 1 so there are zero letters between them.
Because distance[0] = 1, s is not a well-spaced string.

Constraints:

  • 2 <= s.length <= 52
  • s consists only of lowercase English letters.
  • Each letter appears in s exactly twice.
  • distance.length == 26
  • 0 <= distance[i] <= 50

Solution: Hashtable

Use a hastable to store the index of first occurrence of each letter.

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

C++

花花酱 LeetCode 2404. Most Frequent Even Element

Given an integer array nums, return the most frequent even element.

If there is a tie, return the smallest one. If there is no such element, return -1.

Example 1:

Input: nums = [0,1,2,2,4,4,1]
Output: 2
Explanation:
The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most.
We return the smallest one, which is 2.

Example 2:

Input: nums = [4,4,4,9,2,4]
Output: 4
Explanation: 4 is the even element appears the most.

Example 3:

Input: nums = [29,47,21,41,13,37,25,7]
Output: -1
Explanation: There is no even element.

Constraints:

  • 1 <= nums.length <= 2000
  • 0 <= nums[i] <= 105

Solution: Hashtable

Use a hashtable to store the frequency of even numbers.

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

C++

花花酱 LeetCode 2260. Minimum Consecutive Cards to Pick Up

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++

花花酱 LeetCode 2248. Intersection of Multiple Arrays

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++