LeetCode: Find All Numbers Disappeared in an Array Solution
Hash table to check existingApproach
Use hash table (Set) as existing reference
Implementation
1/**2 * @param {number[]} nums3 * @return {number[]}4 */5var findDisappearedNumbers = function (nums) {6 const set = new Set(nums)7 const res = []89 for (let num = 1; num <= nums.length; num++) {10 if (set.has(num) === false) {11 res.push(num)12 }13 }1415 return res16}
O(1) memory approach
Different existence marking strategy:
- use index-based to mark the existence of a number (eg. for number 4 to exist, use index 3 to mark)
- transfrom numsarray to existence checking array
- if a number is existed, the array value at its index-based will be negative
1For array2[4, 3, 2, 7, 8, 2, 3, 1]34Transformation5[ 4, 3, 2, -7, 8, 2, 3, 1]6[ 4, 3, -2, -7, 8, 2, 3, 1]7[ 4, -3, -2, -7, 8, 2, 3, 1]8[ 4, -3, -2, -7, 8, 2, -3, 1]9[ 4, -3, -2, -7, 8, 2, -3, -1]10[ 4, -3, -2, -7, 8, 2, -3, -1]11[ 4, -3, -2, -7, 8, 2, -3, -1]12[-4, -3, -2, -7, 8, 2, -3, -1]
Implementation
1/**2 * @param {number[]} nums3 * @return {number[]}4 */5var findDisappearedNumbers = function (nums) {6 for (const num of nums) {7 const i = Math.abs(num) - 18 nums[i] = -Math.abs(nums[i])9 // console.log(nums) // use this to see how things work10 }1112 return nums.map((num, i) => (num < 0 ? 0 : i + 1)).filter(Boolean)13}
Comments
Loading comments...
Tags
leetcode
array
hash table
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.