WITHOUT using extra space and O(n) solution for Find All Numbers Disappeared
Hanumantappa Budihal
513
exploreFun With Arrays!

Problem statement : https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Solution : WITHOUT using extra space and runtime is O(n).

Problem statement says : Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

it's imporant statement here, it's saying that only positive numbers in list. So that we can use the negative number to achieve the requirement.

Whichever number is present, mark that index to negative. In the end all the numbers whose missing will be having index marked as positive.
[4,3,2,7,8,3,2,1]

  for (int i = 0; i < numbers.Length; i++)
  {
      var value = Math.Abs(numbers[i]) - 1;
      if (!(numbers[value] < 0))
          numbers[value] = (-1 * numbers[value]);
  }
 
 [-4,-3,-2,-7,8,3,-2,-1]

 As 8 and 3 are positive and they are at index 5 and 6, so the missing numbers are 5 and 6
 
 after that just get assign missing values in existing array

 int counter = 0;
 for (int i = 0; i < numbers.Length; i++)
 {
     if (numbers[i] > 0)
         numbers[counter++] = i + 1;
 }
 
 Array will have items like [5,6,-2,-7,8,3,-2,-2] , first two are expected answer
 
counter variable has total missed number, so take sub array from numbers. It's done
return numbers.Take(counter).ToArray();

return only required array.
This worked for me and I submitted code successfully.

Comments (0)