[Leetcode 1146] Snapshot Array

 1146. Snapshot Array

Implement a SnapshotArray that supports the following interface:

SnapshotArray(int length) initializes an array-like data structure with the given length.  Initially, each element equals 0.

void set(index, val) sets the element at the given index to be equal to val.

int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.

int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Constraints:

1 <= length <= 50000

At most 50000 calls will be made to set, snap, and get.

0 <= index < length

0 <= snap_id < (the total number of times we call snap())

0 <= val <= 10^9

Analysis:

This question is designed for data structure.

The snap_id is increased one by one, which means we can use a vector to record the snap information. The id of the vector becomes the snap_id naturally;

The length could be very large, like 50000, so if we use a something with similar sizes, it would be too large. Instead, we just need to record the elements that are updated (or set with values). One solution can use a unordered_map for this. The key will be the data index, and the value is the data value to be set.

Thus, the overall data structure is vector<unordered_map<int, int>>.

See the code below:

class SnapshotArray {
public:
    SnapshotArray(int length) {
        vmps.resize(1);
    }
    
    void set(int index, int val) {
        // assume index and snap_id are always valid
        vmps[id][index] = val;
    }
    
    int snap() {
        vmps.push_back(vmps[id]);
        return id++;
    }
    
    int get(int index, int snap_id) {
        // assume index and snap_id are always valid
        return vmps[snap_id][index];
    }
private:
    int id = 0;
    vector<unordered_map<int, int>> vmps;
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

 

Lintcode 803: Shortest Distance from All Buildings

https://www.lintcode.com/problem/shortest-distance-from-all-buildings/description

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.
• Each 1 marks a building which you cannot pass through.
• Each 2 marks an obstacle which you cannot pass through.

Example

Example 1

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation:
In this example, there are three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Example 2

Input: [[1,0],[0,0]]
Output: 1
In this example, there is one buildings at (0,0).
1 - 0
|   |
0 - 0
The point (1,0) or (0,1) is an ideal empty land to build a house, as the total travel distance of 1 is minimal. So return 1.

Notes:

This question is labeled as hard in both Leetcode and Lintcode, but actually the idea is pretty straightforward:

1): we can use bfs search for each house, then record the minimum distance results for each "empty" position into a hash map;

2): then we need to go through the hash map, to find the empty position having the minimum sum distances to all the houses.

See the code below:

class Solution {
public:
    /**
     * @param grid: the 2D grid
     * @return: the shortest distance
     */
    int shortestDistance(vector<vector<int>> &grid) {
        // write your code here
        if(!grid.size() || !grid.front().size()) return 0;
        int res = INT_MAX, m = grid.size(), n = grid.front().size(), ct = 0;
        unordered_map<int, vector<int>> mp;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 1) {
                    ++ct;
                    bfs(grid, i, j, mp);
                }
            }
        }
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 0 && mp[i*n+j].size() == ct) {
                    int sum = 0;
                    for(auto &a : mp[i*n+j]) sum += a;
                    res = min(res, sum);
                }
            }
        }
        return res==INT_MAX? -1 : res;
    }

private:
    void bfs(vector<vector<int>>& grid, int i, int j, unordered_map<int, vector<int>>& mp) {
        int m = grid.size(), n = grid.front().size();
        vector<vector<int>> visit(m, vector<int>(n, 0));
        queue<pair<int, int>> q;
        q.push({i, j});
        visit[i][j] = 1;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        int step = 1;
        while(q.size()) {
            int k = q.size();
            for(int i=0; i<k; ++i) {
                auto t = q.front();
                q.pop();
                for(int j=0; j+1<dirs.size(); ++j) {
                    int a = t.first + dirs[j], b = t.second + dirs[j+1];
                    if(a<0 || a>=m || b<0 || b>=n || grid[a][b] != 0 || visit[a][b]) continue;
                    q.push({a, b});
                    visit[a][b] = 1;
           //         cout<<a<<" "<<b<<" "<<step<<endl;
                    mp[a*n+b].push_back(step);
                }
            }
            ++step;
        }
    }
};

Leetcode 1072: Flip Columns For Maximum Number of Equal Rows

https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/description/

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column.  Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.

Return the maximum number of rows that have all values equal after some number of flips.

Example 1:

Input: [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Example 2:

Input: [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.

Example 3:

Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

Note:

1. 1 <= matrix.length <= 300
2. 1 <= matrix[i].length <= 300
3. All matrix[i].length's are equal
4. matrix[i][j] is 0 or 1

Notes:

The key to this question is to understand the key logic here.

One way is that we can start with a smaller size. Let say we only have two  rows only. Then how can we reach the maximum?

There are only two cases that we can reach 2, otherwise it is 1.

One is that these two arrays are valid by themselves, so we do not need any flip;

The other is that every elements of the two arrays are just opposite.

After figuring out this, this question is asking for the maximum number of "similar" rows: either the same or just opposite on every column.

See the code below:

class Solution {

public:

    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {

        int res = 0;

      //  if(!matrix.size() || !matrix.front().size()) return res;

        int m = matrix.size(), n = matrix.front().size();

       // vector<int> used(m, 0);

        unordered_map<string, int> mp;

        for(auto &a : matrix) {

            string s1, s2;

            for(auto &b : a) {

                s1.push_back(b+'0');

                s2.push_back(1-b+'0');

            }

            ++mp[s1];

            ++mp[s2];

            res = max(res, max(mp[s1], mp[s2]));

         }

        return res;

    }

};

Leetcode 525: Contiguous Array

https://leetcode.com/problems/contiguous-array/description/

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

Notes:

This is another classic question about the subarray (or continuous subarray).

For these kinds of question, it seems always have O(N) or O(NlogN) solutions. And the brute force solution is O(N^2).

To this question, the only trick part is how to count 0 and 1?

One way to do this is using a counting variable. When meets with 1, ++count; when 0, --count. When the same count value appears,  the subarray between them should have equal number of 0 and 1.

See the code below:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int res = 0, sum = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;
        for(int i=0; i<nums.size(); ++i) {
            if(nums[i]) ++sum;
            else --sum;
            if(mp.count(sum)) res = max(res, i - mp[sum]);
            else mp[sum] = i;
        }
        return res;
    }
};
auto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

Leetcode 1224: Maximum Equal Frequency

https://leetcode.com/problems/maximum-equal-frequency/description/

Given an array nums of positive integers, return the longest possible length of an array prefix of nums, such that it is possible to remove exactly one element from this prefix so that every number that has appeared in it will have the same number of occurrences.

If after removing one element there are no remaining elements, it's still considered that every appeared number has the same number of ocurrences (0).

Example 1:

Input: nums = [2,2,1,1,5,3,3,5]
Output: 7
Explanation: For the subarray [2,2,1,1,5,3,3] of length 7, if we remove nums[4]=5, we will get [2,2,1,1,3,3], so that each number will appear exactly twice.

Example 2:

Input: nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
Output: 13

Example 3:

Input: nums = [1,1,1,2,2,2]
Output: 5

Example 4:

Input: nums = [10,2,8,9,3,8,1,5,2,3,7,6]
Output: 8

Constraints:

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Notes:

This question is labeled as a hard question, but its algorithm is quick straightforward. The most difficult part is that it has so many corner cases.

Let us look at the algorithm:

First we will use one hash table to count the frequency of each elements; then we need a second has table to count the frequency of the frequencies.

Now we need figure out what results are the valid ones.

If the size of the second hash table is 1: 

(1) for example, [1, 2, 3, 4, 5], there is only 1 frequency, and mp[1] = 5. In this case, we need the val of the mp[key] is (i+1); where i the index where we scan at;

(2) for example, [1, 1, 1, 1, 1], there is only 1 frequency, and mp[5] = 1. In this case, we need the val ==1, and the key == (i + 1).

(3) otherwise, it cannot be valid

If the size of the second hash table is 2:

(1) If is easy to see that, there must be at least one frequency is 1;

(2) if both are 1, there are two situations:

         (a)  [1, 2, 2, 2], in this case, mp[1] == 1, and mp[3] == 1, and it is valid. So we need min(key) == 1;
         (b) [1, 1, 2, 2, 2], mp[2] ==1, and mp[3] == 1, and it is also valid. So we need abs(key1 - key2) == 1;

(3) if only one of them is 1:

there are two cases:
         
        (a) the key of the 1 value is 1 (then it can be removed); so key1 == 1

        (b) the key of the 1 value is larger than the other key by 1 (the the first key can be removed by 1); so key1 - key2 == 1.

If the size of the second hash table is larger than 2, there is no valid case.

See the code below:

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        int res = 0, len = nums.size();
        if(!len) return res;
        ++res;
        unordered_map<int, int> mp;
        unordered_map<int, int> mp1;
        for(int i=0; i<nums.size(); ++i) {
            int t = nums[i];
            if(mp1.count(mp[t])) {
                --mp1[mp[t]];
                if(mp1[mp[t]] == 0) mp1.erase(mp[t]);
            }
            ++mp[t];
            ++mp1[mp[t]];
            if(mp1.size() == 2) {
                auto it = mp1.begin();
                int k1 = it->first, k2 = next(it, 1)->first;
                int v1 = it->second, v2 = next(it, 1)->second;
                if(v1 != 1 && v2 != 1) continue;//one of them has to be 1; or both 1;
                if(v1 == 1 && v2 == 1) {//both are 1's;
                    if(min(k1, k2) == 1 || abs(k1-k2) == 1) res = i + 1;
                }
                else {//one is 1;
                    if(v1 != 1) {//set v1 is 1 if it is not;
                        swap(k1, k2);
                        swap(v1, v2);
                    }
                    if(k1 == 1 || k1 - k2 == 1) res = i + 1;
                }
            }
            else if(mp1.size() == 1 && (mp1.begin()->first == i + 1 || mp1.begin()->second == i + 1)) res = i + 1;
          //two special cases:  [1, 1, 1, 1, 1], and [1, 2, 3, 4, 5]
        }
        return res;
    }
};

Leetcode 249: Group Shifted String

https://leetcode.com › problems › group-shifted-strings

Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Note: For the return value, each inner list's elements must follow the lexicographic order.

Notes:

This question is not hard to come up a solution, but it seems not easy to make the code clean.

Below is one way to code. Basically, if two strings belong to the same group, the difference of between all the letters and the first letter are the same for both strings. So we use this as a key to a hash table.

See the code below:

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        vector<vector<string>> res;
        unordered_map<string, multiset<string>> m;
        for (auto a : strings) {
            string s = "";
            for (char &c : a) {
                s += to_string((c + 26 - a[0]) % 26) + ",";
            }
            m[s].insert(a);
        }
        for(auto it = m.begin(); it != m.end(); ++it) {
            res.push_back(vector<string>(it->second.begin(), it->second.end()));
        }
        return res;
    }
};

Lintcode 386: Longest Substring with At Most K Distinct Characters

https://www.lintcode.com/problem/longest-substring-with-at-most-k-distinct-characters/description

Notes:

This question is labeled as a hard question in Leetcode, but actually it is not that hard, many be a medium one.

The basic idea is to use a sliding window. When the total kinds of the letter is less than k, we just continue, and count both kind and number of each kind of letter. A hash map can do this.

When the number of kind is larger than k, we need to move the left side of the window, until the number of kind is no more larger than k. Then we can record the length of this valid string, and update the global maximum.

See the code below:

class Solution {
public:
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    int lengthOfLongestSubstringKDistinct(string &s, int k) {
        // write your code here
        int res = 0, left = 0, len = s.size(), ct = 0;
        if(!k) return res;
        unordered_map<char, int> mp;
        for(int i=0; i<len; ++i) {
            if(!mp.count(s[i]) || mp[s[i]] == 0) {
                ++ct;
                ++mp[s[i]];
                if(ct>k) {
                    while(ct>k) {
                        --mp[s[left++]];
                        if(mp[s[left-1]] == 0) --ct;
                    }
                }
            }
            else ++mp[s[i]];
            res = max(res, i - left + 1);
        }
        return res;
    }
};

Here is another way to write the code, which is shorter. But we need to erase element from a hash map. 

See the code blow:

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int res = 0, left = 0, len = tree.size();
        unordered_map<int, int> mp;
        for(int i=0; i<len; ++i) {
            ++mp[tree[i]];
            while(mp.size() > 2) {
                 if(--mp[tree[left]] == 0) mp.erase(tree[left]);
                 ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

Now let us focus one the interesting part: what do the above two codes run in O(N)? It seems at some positions, we need to slide the left side of the window many times.

But if we look at the hash map, and it is clear that every element will be pushed in exactly once, and not every element (less than N) will be pop out. Thus, the total operate is less than 2N. So it is O(N).

[update: 12-07-2019] here is another version of code, which is more concise:

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string &s, int k) {
        int res = 0, left = 0, len = s.size(), ct = 0;
        if(!k) return res;
        unordered_map<char, int> mp;
        for(int i=0; i<len; ++i) {
            ++mp[s[i]];
            if(mp[s[i]] == 1) ++ct;
            while(ct>k) {
                --mp[s[left++]];
                if(mp[s[left-1]] == 0) --ct;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

Leetcode 325: Maximum Size Subarray Sum Equals K

https://leetcode.com › problems › maximum-size-subarray-sum-equals-k

Notes:

This question can be a very good interview question due to the follow up. The basic idea is that using a hash table to record the index when one unique sum shows up.

if sum[i to j] = sum[0 to j] - sum[0 to i-1] = k, then we just need to check whether (sum[0 to j] - k) is already observed or not, which is sum[0 to i-1]. Thus, we can run this in O(N).

See the code below:

class Solution {
public:
    int maxSubArrayLen(vector<int> &nums, int k) {
        int res = 0, sum = 0;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); ++i) {
            sum += nums[i];
            if(sum == k) res = max(res, i + 1);
            else if (mp.count(sum-k)) res = max(res, i - mp[sum-k]);
            if(!mp.count(sum)) mp[sum] = i;
        }
        return res;
    }
};