Blind75 Part1 Arrays

Arrays & Hashing

49. Group Anagrams

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

Categorize by Sorted String

map: sorted string, original strings
unordered_map<string, vector<string>> map

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for (string str : strs) {
            string key = str;
            sort(key.begin(), key.end());
            map[key].push_back(str);
        }
        vector<vector<string>> res;
        for (auto p : map) {
            res.push_back(p.second);
        }
        return res;
    }
};

Time Complexity: $O(NKlogK)$
Space Complexity: $O(NK)$
where $N$ is the length of strs, and $K$ is the maximum length of a string in strs

Categorize by Count

count[26]
Time Complexity: $O(NK)$

347. Top K Frequent Elements

1. Brute Force

sort the freq
-> use a priority queue for the top k elements
$O(nlogk)$

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(); // <integer, freq>
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        for (int key : map.keySet()) {
            if (!maxHeap.contains(key)) {
                maxHeap.add(key);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = maxHeap.poll();
        }
        return res;
    }
}

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (auto num : nums) freq[num]++;
        
        priority_queue<pair<int, int>> pq;
        for (auto [a, b] : freq) pq.push({b, a});
        
        vector<int> res;
        while (k) {
            res.push_back(pq.top().second);
            pq.pop();
            k--;
        }
        
        return res;
    }
};

2. Binary Search

$O(nlogc)$ where c is the number of guesses

class Solution {
public:
    
    unordered_map<int, int> freq;
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        for (auto x : nums)
            freq[x]++;
        
        int l = 0, r = nums.size();
        while (l < r) {
            int m = (l + r + 1) >> 1;
            if (countFreqGreaterOrEqual(m) >= k) l = m;
            else r = m - 1;
        }
        
        vector<int> res;
        for (auto x : freq) {
            if (x.second >= l)
                res.push_back(x.first);
        }
        return res;
    }
    
    int countFreqGreaterOrEqual(int n) {
        int count = 0;
        for (auto x : freq) {
            if (x.second >= n) 
                count++;
        }
        return count;
    }
};

3. Quick Select

Time Complexity: $O(N)$ in the average case, $O(N^2)$ in the worst case.

4. Bucket Sort

Time Complexity: $O(N)$

must know the range of the frequency
use map and array list (buckets) to “sort” by frequency

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

freq map: freq[num] <freq, num>

num	1	2	3	4	5	6	7
freq	3	3	1

bucket[freq] = {num1, num2, …}

freq	3	1
nums	{1, 2}	3

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (auto num : nums) freq[num]++;
        
        vector<vector<int>> buckets(nums.size()+1);
        for (auto [a, b] : freq)
            buckets[b].push_back(a);
        
        vector<int> res;

        // use the bucket to sort by freq with O(N) time
        for (int i = nums.size(); k > 0; i--) { // freq from high to low
            for (auto a : buckets[i]) {
                res.push_back(a);
                k--;
            }
        }
        
        return res;
    }
};

238. Product of Array Except Self

Input: nums = [1, 2, 3, 4]

       left = [1, 1, 2, 6]
      right = [24,12,4, 1]

Output:       [24,12,8, 6]

Left and right product lists

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n, 1);
        vector<int> post(n, 1);
        vector<int> res(n, 1);
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            post[i] = post[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < n; i++) {
            res[i] = pre[i] * post[i];
        }
        
        return res;
    }
};

Time Complexity: $O(N)$
Space Complexity: $O(N)$

---

Follow up: How to improve to O(1) space?
(The output array does not count as extra space for space complexity analysis.)

O(1) space approach

Input: nums = [1, 2, 3, 4]

       res  = [1, 1, 2, 6]   left to right
    postsum:   24 12 4
       res =  [24,12,8, 6]   right to left

Output:       [24,12,8, 6]

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size(), postsum = 1;
        vector<int> res(n, 1);
        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            postsum *= nums[i + 1];
            res[i] = res[i] * postsum;
        }
        return res;
    }
};

Time Complexity: $O(N)$
Space Complexity: $O(1)$

271. Encode and Decode Strings

Input: dummy_input = ["Hello","World"]
Output: ["Hello","World"]

Explanation:
    Codec decoder = new Codec();
    String[] strs = decoder.decode(msg);

one possible way to encode and decode is: len + “#” + word, 5#hello5#World

class Codec:
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string.
        """
        res = ""
        for s in strs:
            res += str(len(s)) + "#" + s
        return res

    def decode(self, s: str) -> List[str]:
        """Decodes a single string to a list of strings.
        """
        res, i = [], 0
        
        while i < len(s):
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i: j])
            res.append(s[j + 1: j + 1 + length])
            i = j + 1 + length
            
        return res


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))

# eg. "5#hello5#World"

Time: $O(N)$
Space: $O(1)$

128. Longest Consecutive Sequence

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

sorting

Time: $O(NlogN)$

two pointers

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        maxLen = 0
        for x in nums:
            if x - 1 not in nums:
                y = x + 1
                while y in nums:
                    y += 1
                maxLen = max(maxLen, y - x)
        return maxLen

Time: $O(N)$