Press "Enter" to skip to content

Posts published in “Hashtable”

花花酱 LeetCode 2564. Substring XOR Queries

You are given a binary string s, and a 2D integer array queries where queries[i] = [firsti, secondi].

For the ith query, find the shortest substring of s whose decimal valueval, yields secondi when bitwise XORed with firsti. In other words, val ^ firsti == secondi.

The answer to the ith query is the endpoints (0-indexed) of the substring [lefti, righti] or [-1, -1] if no such substring exists. If there are multiple answers, choose the one with the minimum lefti.

Return an array ans where ans[i] = [lefti, righti] is the answer to the ith query.

substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "101101", queries = [[0,5],[1,2]]
Output: [[0,2],[2,3]]
Explanation: For the first query the substring in range [0,2] is "101" which has a decimal value of 5, and 5 ^ 0 = 5, hence the answer to the first query is [0,2]. In the second query, the substring in range [2,3] is "11", and has a decimal value of 3, and 3 ^ 1 = 2. So, [2,3] is returned for the second query. 

Example 2:

Input: s = "0101", queries = [[12,8]]
Output: [[-1,-1]]
Explanation: In this example there is no substring that answers the query, hence [-1,-1] is returned.

Example 3:

Input: s = "1", queries = [[4,5]]
Output: [[0,0]]
Explanation: For this example, the substring in range [0,0] has a decimal value of 1, and 1 ^ 4 = 5. So, the answer is [0,0].

Constraints:

  • 1 <= s.length <= 104
  • s[i] is either '0' or '1'.
  • 1 <= queries.length <= 105
  • 0 <= firsti, secondi <= 109

Solution: Pre-compute

We can pre-compute all possible substrings

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

C++

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