My 0ms, O(n) time simple solution by maintaining start index


  • 0
    V

    If we are allowed to modified input array:

    vector<string> findMissingRanges(vector<int>& n, int l, int u) {
            vector<string> ans;
            n.insert(n.begin(), l-1);
            n.push_back(u+1);
            int i, sp = l, ep;
            for (i = 0; i < n.size(); i++) {
                if (n[i] > sp) {
                    ep = n[i] - 1;
                    if (ep > sp)
                        ans.push_back(to_string(sp) + "->" + to_string(ep));
                    else
                        ans.push_back(to_string(sp));
                }
                sp = n[i] + 1;
            }
            return ans;
        }
    

    Otherwise:

        void add(vector<string>& a, int sp, int ep) {
            if (ep > sp)
                a.push_back(to_string(sp) + "->" + to_string(ep));
            else
                a.push_back(to_string(sp));
        }
        vector<string> findMissingRanges(vector<int>& n, int l, int u) {
            vector<string> ans;
            if (n.size() == 0) {
                add(ans, l, u);
                return ans;
            }
            int i, sp = l;
            for (i = 0; i < n.size(); i++) {
                if (n[i] > sp) {
                    add(ans, sp, n[i] - 1);
                }
                sp = n[i] + 1;
            }
            if (n[i-1] < u) {
                add(ans, sp, u);
            }
            return ans;
        }
    

Log in to reply
 

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