Sparse Table or Stack?

Last week’s contest, I met a pretty nice question which can be solved elegantly by using stack. However, before achieving that elegant solution, we can also use sparse table or segment tree to solve that problem

Problem

1673. Find the Most Competitive Subsequence

Solutions

Sparse Table O(n log n) 1852 ms

class Solution {
public:
    void Build_SparseTable (vector<int>& vec, vector<vector<int>>& sparse_table) {
int rows = vec.size();
     int cols = sparse_table[0].size();
for (int r=0; r<rows; r++)
         sparse_table[r][0] = vec[r];
for (int c=1; c <= cols; c++) {
         int range = (1 << c);
         /* For  c    Range     c-1  Previous Range
                 1   2^1 = 2     0      2^0 = 1 
                 2   2^2 = 4     1      2^1 = 2
                 3   2^3 = 8     2      2^2 = 4
                 ...        
        */
         for (int r=0; r + range <= rows; r++) {
             // Values in the current column are derived from the        
             // values in the previous column.                          
             sparse_table[r][c] = min (sparse_table[r][c-1],
                                       sparse_table[r+(1<<(c-1))][c-1]);
         }
     }
}
int RMQ (int left, int right, vector<vector<int>>& sparse_table) {
// Find the biggest block of size 2^p that fits in the range "left" till "right".
int power_of_2 = (int) log2( right + 1 - left );
    int x = right + 1 - ( 1 << power_of_2 );
//cout << "Left : " << left << " Right : " << right << endl;
    //cout << "Part 1: (" << left << ".." << left + ( 1 << power_of_2 ) - 1 << ")" << " Part 2: (" << right + 1 - ( 1 << power_of_2 ) << ".." << right << ")" << endl;
if ( sparse_table[left][power_of_2] <= sparse_table[right + 1 - ( 1 << power_of_2 )][power_of_2] )
        return sparse_table[left][power_of_2];
    else
        return sparse_table[right + 1 - ( 1 << power_of_2)][power_of_2];
}
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        //int sz = ceil (log2 (vec.size()) ) + 1;
int sz = ceil (log2 (nums.size()) ) + 1;
        unordered_map<int, vector<int>> m;
        for (int i =0; i < nums.size(); i++) {
            m[nums[i]].push_back(i);
        }
// Create a sparse table of size [number_count][ceil ( log2 (number_count)) + 1]
    vector<vector<int>> sparse_table (nums.size(), vector<int>(sz));
        
       
        Build_SparseTable(nums, sparse_table);
         vector<int> ret;
        int l = 0, r = nums.size() - k;
        for (int i = 0; i < k; ++i) {
            r = nums.size() - k + i;
           int this_ret = RMQ(l, r,sparse_table );
            ret.push_back(this_ret);
            l = *(lower_bound(m[this_ret].begin(), m[this_ret].end(), l)) + 1;
            //cout<<"l"<<l<<endl;
            if (nums.size() - l == k - i -1) {
                for (int j = l; j < nums.size();++j){
                    ret.push_back(nums[j]);
                }
                return ret;
            }
            
        }
        return ret;
        
    }
};

Stack (O(n)) [1] 400 ms

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        vector<int> stack;
        const int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (!stack.empty() && stack.back() > nums[i] &&
                   stack.size() - 1 + n - i >=k ){
                stack.pop_back();
            }
            if (stack.size() < k) {
                stack.push_back(nums[i]);
            }
        }
        return stack;
        
    }
};

Hard to understand at the beginning? Understand from an example.
Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]

Output the whole process

nums0: 2
 2
nums1: 4
 2 4
nums2: 3
 2 3
nums3: 3
 2 3 3
nums4: 5
 2 3 3 5
nums5: 4
 2 3 3 4
nums6: 9
 2 3 3 4
nums7: 6
 2 3 3 4

Happy weekend. Happy coding and software engineering.

Similar problems [1]

Reference

[1] https://leetcode.com/problems/find-the-most-competitive-subsequence/discuss/952786/JavaC++Python-One-Pass-Stack-Solution