c++ o(N) with comments


  • 0
    G
    class Solution {
    public:
        vector<int> constructArray(int n, int k) {
         
            // k has to be less than n - 1 for this to work
            if(k > n - 1){
                return vector<int>();
            }
            
            vector<int> res;
            int start = 1; // start with one
            int end = k + 1; // up to k + 1 (to have k different pairs)
            
            for(int i = 0; i <= k; ++i){
                if(i % 2 == 0){
                    res.push_back(start++);
                }
                else{
                    res.push_back(end--);
                }
            }
            
            //after we added k number which differ, the next n - k should give us the same diff 
            if(end > start){
                for(int i = n; i >= k + 2; --i){
                    res.push_back(i);
                }
            }
            else{
                for(int i = k + 2; i <= n; ++i){
                    res.push_back(i);
                }
            }
          
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.