Contains Duplicate III -- LeetCode

[Question]
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

[Analysis]
If using brute force, going through each nums[i] and checking whether any of nums[i+1],..., nums[i+k] values are within the range of [ nums[i]-t, nums[i]+t ], the time complexity is O( K^2 * N ).

Making a BST for the sub-array { nums[i+1],..., nums[i+k] }, and find if any values in the BST fall into [ nums[i]-t, nums[i]+t ], the time complexity is O(log K * N).

The interesting part of the C++ code below is, how to use "multiset" as a BST and fulfill the above logic in just a few lines.

Update: Using bucket sort is a better solution. The time complexity is O(N).

[Solution]
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (nums.empty() || k<=0 || t<0) return false;

        multiset<int> bst (nums.begin(), nums.begin()+k);
        for (int i=0; i<nums.size(); i++) {
            bst.erase(bst.find(nums[i]) );
            if (i+k<nums.size()) bst.insert(nums[i+k]);
         
            // -- make sure the boundary condition --
            if (bst.find(nums[i]+t)!=bst.end() || bst.find(nums[i]-t)!=bst.end() ) return true;

            if (bst.upper_bound(nums[i]+t) != bst.upper_bound(nums[i]-t)) return true;
        }
        return false;
    }
};

//-- Bucket Sort --
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (k<1 || t<0) return false;
        int min_elem = *min_element(nums.begin(), nums.end());
     
        unordered_map<long, long> buckets;
        for(int i=0; i<nums.size(); i++) {
            long key = (nums[i]-min_elem) / (t+1);
            if (buckets.count(key)>0) return true;
            if (buckets.count(key-1)>0 && abs(nums[i]-buckets[key-1]) <= t
                || buckets.count(key+1)>0 && abs(nums[i]-buckets[key+1]) <=t)
                return true;
            buckets[key] = (long)nums[i];
         
            if (i>=k) buckets.erase( (nums[i-k]-min_elem)/(t+1) );
        }
        return false;
    }
};

Largest Rectangle in Histogram -- LeetCode

[Question]

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

[Analysis]
If we can calculate each rectangle with max height of H[i], we can get the maximum area. To calculate such rectangles, for each H[i], we need to get the first H[j] where H[j]<H[i], j<i and the first H[k]<H[i], where k>i. 

Using a stack can help to find such j and k. The Time Complexity is O(N).

[Solution]
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int area=0;
        heights.push_back(0);
        for(int i=0; i<heights.size(); i++) {
            while(!st.empty() && heights[st.top()]>heights[i] ) {
                int h = heights[st.top()];
                st.pop();
                int j=st.empty()?-1:st.top();
                area = max(area, (i-j-1)* h);
            }
            //--this loop is not necessary but save calculation above.
            while (!st.empty() && heights[st.top()]==heights[i])
                st.pop();
            st.push(i);
        }
        return area;
    }
};

Course Schedule -- LeetCode

[Question]
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

[Analysis]
This is equivalent to the question of finding a circle in a Directed Graph (DiGraph). Using DFS and find if one path will cross itself.

Another approach is to use BFS. Define a node without incoming going edges as Root Node. The assumption is a DiGraph without Root Node must have a circle -- this can be proven by mathematical induction. Therefore, remove Root Node one by one from the DiGraph one by one; if the reminding graph does not have Root Node, it has a circle. Time complexity O(E+V).

[Solutions]
//-- DFS --
class Solution {
public:
    vector<unordered_set<int> > graph;
    vector<bool> visited;
   
    bool dfs_findCircle(int i, unordered_set<int> &path) {
        if (visited[i]) {
            return (path.find(i)!=path.end());
        }
        visited[i] = true;
        path.insert(i);
        for(auto j : graph[i]) {
            if (dfs_findCircle(j, path)) return true;
        }
        path.erase(i);
        return false;
    }
   
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        if (prerequisites.empty()) return true;
        visited.resize(numCourses, false);
        graph.resize(numCourses, unordered_set<int>() );
        for (auto p: prerequisites) {
            graph[p.first].insert(p.second);
        }
        for (int i=0; i<numCourses; i++) {
            if (!visited[i]) {
                unordered_set<int> set;
                bool found = dfs_findCircle(i, set);
                if (found) return false;
            }
        }
        return true;
    }
}; 
 
//-- BFS --
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        if (prerequisites.empty()) return true;
       
        unordered_set <int> src;
        unordered_map <int, unordered_set<int>> fwd, bwd;
       
        for (auto pair: prerequisites) {
            src.insert(pair.first);
            fwd[pair.first].insert(pair.second);
            bwd[pair.second].insert(pair.first);
        }
       
        for (auto& x: bwd) src.erase(x.first);

        while (!src.empty()) {
            unordered_set<int> src1;
            for(auto x: src) {
                for(auto y: fwd[x]) {
                    bwd[y].erase(x);
                    if (bwd[y].empty()) {
                        src1.insert(y);
                    }
                }
                fwd.erase(x);
            }
            src = src1;
        }
           
        return fwd.empty();
    }
};

Job Schedule with Weights

[Questions]
Given a set of jobs in the format of {start, end, weight}, where "start" is starting time, "end" is ending time, find the maximum sum of weights of non-overlapping jobs.

[Analysis]
Sort the Jobs by the ending points. Suppose Cost[i] is the maximum sum of weights of Job[0] ... Job[i],
      Cost[i+1] = max( Cost[j] + Job[i+1] ),   // where j is the last Job not overlapping with Job[i+1]
                                  Cost[i] );                     // Job[i+1] is not selected.

Padding Cost[] with an extra element at the beginning to handle the case where Job[i+1] overlaps with all previous jobs.

[Solution]
struct Job {
    int start;
    int end;
    int cost;

};

int max_cost_subset (vector<Job> &jobs ) {

    auto comp = [](Job a, Job b) { return a.end < b.end; };

    sort(jobs.begin(), jobs.end(),  comp );

    vector<int> cost(jobs.size()+1, 0);

    cost[0] = 0;

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

       Job tmp = jobs[i];

       swap(tmp.start, tmp.end);

       auto it = upper_bound(jobs.begin(), jobs.begin()+i+1, tmp, comp);  // -- Binary Search

       cost[i+1] = max( cost[it-jobs.begin() ] + jobs[i].cost, cost[i] );  

    }

    return cost.back();

}