Commit1a10b4d

authored

Merge pull requestneetcode-gh#1446 from VigneshIyer25/main

create: 448-Find-All-Numbers-Disappeared-In-An-Array

2 parents3bd69e7 +9b1765a commit1a10b4dCopy full SHA for 1a10b4d

File tree

+26

-0

lines changed

+26

-0

lines changed

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,26 @@`
	`1`	`+classSolution {`
	`2`	`+public:`
	`3`	`+/*`
	`4`	`+ Approach:`
	`5`	`+ Traverse the entire array from start to end. Since the numbers are in a range [1, n] we can use this simple trick.`
	`6`	`+ At every index mark the position arr[arr[i]] as negative.`
	`7`	`+ Repeat this for every index in the array.`
	`8`	`+ At the end, which ever places are positive, add them to our answer.`
	`9`	`+`
	`10`	`+ Time complexity: O(n)`
	`11`	`+ Space complexity: O(1)`
	`12`	`+*/`
	`13`	`+ vector<int>findDisappearedNumbers(vector<int>& nums) {`
	`14`	`+ vector<int> ans;`
	`15`	`+`
	`16`	`+for(int x : nums){/* Mark values as negative*/`
	`17`	`+int currentVal =abs(x);`
	`18`	`+ nums[currentVal-1] =0 -abs(nums[currentVal-1]);`
	`19`	`+ }`
	`20`	`+`
	`21`	`+for(int i =1; i <= nums.size(); i++)`
	`22`	`+if(nums[i-1] >0) ans.push_back(i);/* Find unmarked values*/`
	`23`	`+`
	`24`	`+return ans;`
	`25`	`+ }`
	`26`	`+};`

Comments

(0)