O(N) runtime C++ AC Solution

  • 2
    class Solution {
        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

    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

    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.