Hashtable – Page 19 – Huahua’s Tech Road

花花酱 LeetCode 1331. Rank Transform of an Array

By zxi on January 26, 2020

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints:

0 <= arr.length <= 10⁵
-10⁹ <= arr[i] <= 10⁹

Solution: Sorting + HashTable

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

C++

// Author: Huahua

class Solution {

public:

vector<int> arrayRankTransform(vector<int>& arr) {

set<int> s(begin(arr), end(arr));

unordered_map<int, int> m;

int r = 0;

for (const int v : s) m[v] = ++r;

vector<int> ans(arr.size());

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

ans[i] = m[arr[i]];

return ans;

}

};

花花酱 LeetCode 1329. Sort the Matrix Diagonally

By zxi on January 26, 2020

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

Example 1:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

Solution: HashTable

Collect each diagonal’s (keyed by i – j) elements into an array and sort it separately.
If we offset the key by n, e.g. i – j + n, we can use an array instead of a hashtable.

Time complexity: O(m*n + (m+n) * (m+n) * log(m + n))) = (n^2*logn)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {

const int m = mat.size();

const int n = mat[0].size();

vector<deque<int>> qs(m + n);

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

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

qs[i - j + n].push_back(mat[i][j]);

for (auto& q : qs)

sort(begin(q), end(q));

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

for (int j = 0; j < n; ++j) {

mat[i][j] = qs[i - j + n].front();

qs[i - j + n].pop_front();

}

return mat;

}

};

花花酱 LeetCode 1233. Remove Sub-Folders from the Filesystem

By zxi on October 21, 2019

Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d/" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i] contains only lowercase letters and ‘/’
folder[i] always starts with character ‘/’
Each folder name is unique.

Solution: HashTable

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

C++

// Author: Huahua

class Solution {

public:

vector<string> removeSubfolders(vector<string>& folder) {

unordered_set<string> s(begin(folder), end(folder));

vector<string> ans;

for (const auto& cur : folder) {

string f = cur;

bool valid = true;

while (!f.empty() && valid) {

while (f.back() != '/') f.pop_back();

f.pop_back();

if (s.count(f)) valid = false;

}

if (valid) ans.push_back(cur);

}

return ans;

}

};

花花酱 LeetCode 49. Group Anagrams

By zxi on October 2, 2019

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

All inputs will be in lowercase.
The order of your output does not matter.

Solution: HashTable

The sorted word will be the key of each group

Time complexity: O(sum(l*log(l)))
Space complexity: O(sum(l))

C++

// Author: Huahua

class Solution {

public:

vector<vector<string>> groupAnagrams(vector<string>& strs) {

vector<vector<string>> ans;

unordered_map<string, vector<int>> m;

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

string c = strs[i];

sort(begin(c), end(c));

m[c].push_back(i);

}

for (const auto& kv : m) {

ans.push_back({});

for (int i : kv.second)

ans.back().push_back(strs[i]);

}

return ans;

}

};

Posts published in “Hashtable”

花花酱 LeetCode 1331. Rank Transform of an Array

Solution: Sorting + HashTable

C++

花花酱 LeetCode 1329. Sort the Matrix Diagonally

Solution: HashTable

C++

花花酱 LeetCode 1282. Group the People Given the Group Size They Belong To

Solution: HashMap + Greedy

C++

花花酱 LeetCode 1233. Remove Sub-Folders from the Filesystem

Solution: HashTable

C++

花花酱 LeetCode 49. Group Anagrams

Solution: HashTable

C++