Posts tagged as “hashtable”

花花酱 LeetCode 1232. Check If It Is a Straight Line

By zxi on December 23, 2021

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Example 1:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

Example 2:

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false

Constraints:

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates contains no duplicate point.

Solution: Slope and Hashset

This is not a easy problem, a few corner cases:

dx == 0
dy == 0
dx < 0

Basically we are counting (dx / gcd(dx, dy), dy / gcd(dx, dy)). We will have only ONE entry if all the points are on the same line.

Time complexity: O(n)
Space complexity: O(1) w/ early exit.

C++

// Author: Huahua

class Solution {

public:

bool checkStraightLine(vector<vector<int>>& coordinates) {

set<pair<int, int>> s;

for (int i = 1; i < coordinates.size(); ++i) {

int dx = coordinates[i][0] - coordinates[0][0];

int dy = coordinates[i][1] - coordinates[0][1];

if (dy == 0)

s.emplace(1, 0);

else if (dx == 0)

s.emplace(0, 1);

else {

if (dx < 0) dx *= -1, dy *= -1;

const int d = gcd(dx, dy);

s.emplace(dx / d, dy / d);

}

if (s.size() > 1) return false;

}

return true;

}

};

花花酱 LeetCode 835. Image Overlap

By zxi on December 23, 2021

You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s as values.

We translate one image however we choose by sliding all the 1 bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1 in both images.

Note also that a translation does not include any kind of rotation. Any 1 bits that are translated outside of the matrix borders are erased.

Return the largest possible overlap.

Example 1:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

The number of positions that have a 1 in both images is 3 (shown in red).

Example 2:

Input: img1 = [[1]], img2 = [[1]]
Output: 1

Example 3:

Input: img1 = [[0]], img2 = [[0]]
Output: 0

Constraints:

n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 <= n <= 30
img1[i][j] is either 0 or 1.
img2[i][j] is either 0 or 1.

Solution: Hashtable of offsets

Enumerate all pairs of 1 cells (x1, y1) (x2, y2), the key / offset will be ((x1-x2), (y1-y2)), i.e how should we shift the image to have those two cells overlapped. Use a counter to find the most common/best offset.

Time complexity: O(n⁴) Note: this is the same as brute force / simulation method if the matrix is dense.
Space complexity: O(n²)

C++

// Author: Huahua

class Solution {

public:

int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {

const int n = img1.size();

unordered_map<int, int> m;

for (int y1 = 0; y1 < n; ++y1)

for (int x1 = 0; x1 < n; ++x1)

if (img1[y1][x1])

for (int y2 = 0; y2 < n; ++y2)

for (int x2 = 0; x2 < n; ++x2)

if (img2[y2][x2])

++m[(x1 - x2) * 100 + (y1 - y2)];

int ans = 0;

for (const auto [key, count] : m)

ans = max(ans, count);

return ans;

}

};

花花酱 LeetCode 219. Contains Duplicate II

By zxi on December 5, 2021

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

Solution: Sliding Window + Hashtable

Hashtable to store the last index of a number.

Remove the number if it’s k steps behind the current position.

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

C++

// Author: Huahua

class Solution {

public:

bool containsNearbyDuplicate(vector<int>& nums, int k) {

unordered_map<int, int> m; // num -> last index

for (int i = 0; i < nums.size(); ++i) {

if (i > k && m[nums[i - k - 1]] < i - k + 1)

m.erase(nums[i - k - 1]);

if (m.count(nums[i])) return true;

m[nums[i]] = i;

}

return false;

}

};

花花酱 LeetCode 211. Design Add and Search Words Data Structure

By zxi on December 5, 2021

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation 
WordDictionary wordDictionary = new WordDictionary(); 
wordDictionary.addWord("bad"); 
wordDictionary.addWord("dad"); 
wordDictionary.addWord("mad"); 
wordDictionary.search("pad"); // return False 
wordDictionary.search("bad"); // return True 
wordDictionary.search(".ad"); // return True 
wordDictionary.search("b.."); // return True

Constraints:

1 <= word.length <= 500
word in addWord consists lower-case English letters.
word in search consist of '.' or lower-case English letters.
At most 50000 calls will be made to addWord and search.

Solution: Hashtables

The first hashtable stores all the words, if there is no dot in the search pattern. Do a full match.

There are also per length hashtable to store words of length k. And do a brute force match.

Time complexity: Init: O(n*l)
search: best: O(l) worst: O(n*l)

C++

// Author: Huahua

class WordDictionary {

public:

// Adds a word into the data structure.

void addWord(string word) {

words.insert(word);

ws[word.length()].insert(word);

}

// Returns if the word is in the data structure. A word could

// contain the dot character '.' to represent any one letter.

bool search(string word) {

if (word.find(".") == string::npos)

return words.count(word);

for (const string& w : ws[word.length()])

if (match(word, w)) return true;

return false;

}

bool match(const string& p, const string& w) {

for (int i = 0; i < p.length(); ++i) {

if (p[i] == '.') continue;

if (p[i] != w[i]) return false;

}

return true;

}

private:

unordered_set<string> words;

unordered_map<int, unordered_set<string>> ws;

};

花花酱 LeetCode 205. Isomorphic Strings

By zxi on December 5, 2021

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Constraints:

1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ascii character.

Solution: Counting

The # of distinct pairs e.g. (s[i], t[i]), should be equal to the # of distinct chars in s and t.
ex1:
set of pairs: {(e, a), (g,d)}
set of s: {e, g}
set of t: {a, d}
For s, we can replace e with a, and replace g with d.
ex2:
set of pairs: {(f, b), (o, a), (o, r)}
set of s: {f, o}
set of t: {b, a, r}
o can not pair with a, r at the same time.
ex3:
set of pairs: {(p, t), (a, i), (e, l), (r, e)}
set of s: {p, a, e, r}
set of t: {t, i, l, e}

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

C++

// Author: Huahua

class Solution {

public:

bool isIsomorphic(string s, string t) {

const int n = s.length();

unordered_set<int> s1;

for (int i = 0; i < n; ++i)

s1.insert((s[i] << 8) | t[i]);

unordered_set<int> s2(begin(s), end(s));

unordered_set<int> s3(begin(t), end(t));

return s1.size() == s2.size() && s2.size() == s3.size();

}

};