O(N) runtime C++ AC Solution


  • 1
    class Solution {
    public:
        vector<int> findDisappearedNumbers(vector<int>& nums) {
            for (int i : nums) {
                int idx = abs(i) - 1;
                nums[idx] = -1 * abs(nums[idx]);
            }
            vector<int> res;
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] > 0) res.emplace_back(i + 1);
            }
            return res;
        }
    };
    

  • 0
    Y

    Hi Ren
    This is a great solution but I am unable to understand how is this working. Can you please explain ? How did you come up with it ?


  • 0
    L

    @yashvardhan90
    The idea is if certain number i exists, the corresponding nums[i] will be convert to a negative one. Then you loop to find all those that are still positive ones, which will be non-existing.
    Brilliant solution!


Log in to reply
 

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