Press "Enter" to skip to content

Posts published in “Hashtable”

花花酱 LeetCode 3. Longest Substring Without Repeating Characters


Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution: HashTable + Sliding Window

Using a hashtable to remember the last index of every char.  And keep tracking the starting point of a valid substring.

start = max(start, last[s[i]] + 1)

ans = max(ans, i – start + 1)

Time complexity: O(n)

Space complexity: O(128)




花花酱 LeetCode 888. Fair Candy Swap


Alice and Bob have candy bars of different sizes: A[i] is the size of the i-th bar of candy that Alice has, and B[j] is the size of the j-th bar of candy that Bob has.

Since they are friends, they would like to exchange one candy bar each so that after the exchange, they both have the same total amount of candy.  (The total amount of candy a person has is the sum of the sizes of candy bars they have.)

Return an integer array ans where ans[0] is the size of the candy bar that Alice must exchange, and ans[1] is the size of the candy bar that Bob must exchange.

If there are multiple answers, you may return any one of them.  It is guaranteed an answer exists.

Example 1:

Input: A = [1,1], B = [2,2]
Output: [1,2]

Example 2:

Input: A = [1,2], B = [2,3]
Output: [1,2]

Example 3:

Input: A = [2], B = [1,3]
Output: [2,3]

Example 4:

Input: A = [1,2,5], B = [2,4]
Output: [5,4]


  • 1 <= A.length <= 10000
  • 1 <= B.length <= 10000
  • 1 <= A[i] <= 100000
  • 1 <= B[i] <= 100000
  • It is guaranteed that Alice and Bob have different total amounts of candy.
  • It is guaranteed there exists an answer.


Solution: HashTable

Time complexity: O(A+B)

Space complexity: O(B)

Clean version

Faster version


花花酱 LeetCode 561. Array Partition I


Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).


  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

Solution 1: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

Solution 2: HashTable

Time complexity: O(n + max(nums) – min(nums))

Space complexity: O(max(nums) – min(nums))



花花酱 LeetCode 888. Uncommon Words from Two Sentences


We are given two sentences A and B.  (A sentence is a string of space separated words.  Each word consists only of lowercase letters.)

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Return a list of all uncommon words.

You may return the list in any order.

Example 1:

Input: A = "this apple is sweet", B = "this apple is sour"
Output: ["sweet","sour"]

Example 2:

Input: A = "apple apple", B = "banana"
Output: ["banana"]


  1. 0 <= A.length <= 200
  2. 0 <= B.length <= 200
  3. A and B both contain only spaces and lowercase letters.

Solution: HashTable

Time complexity: O(m+n)

Space complexity: O(m+n)



花花酱 LeetCode 874. Walking Robot Simulation


A robot on an infinite grid starts at point (0, 0) and faces north.  The robot can receive one of three possible types of commands:

  • -2: turn left 90 degrees
  • -1: turn right 90 degrees
  • 1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)


  1. 0 <= commands.length <= 10000
  2. 0 <= obstacles.length <= 10000
  3. -30000 <= obstacle[i][0] <= 30000
  4. -30000 <= obstacle[i][1] <= 30000
  5. The answer is guaranteed to be less than 2 ^ 31.

Solution: Simulation

Time complexity: O(n + sum(x)) = O(n)

Space complexity: O(n)