Find All Numbers that are not present in Java Array from 1 to n
Problem Description :
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums array.
Example 1 :
Input: nums = [1, 3, 5, 1, 3]
Output: [2, 4]Example 2 :
Input: nums = [2, 4, 2, 4]
Output: [1, 3]Example 3 :
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [5, 6]Example 4 :
Input: nums = [1, 1]
Output: [2]In given problem, we have to return List of Integers that are not present in given array range [1 to n].
Lets see solution and its explanation step by step.
Solution 1 : Using in-place array (Without use if extra space)
import java.util.ArrayList;
import java.util.List;class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
// Get current value-1
int numberIndex = Math.abs(nums[i]) - 1;
// change positive value to negative
if (nums[numberIndex] > 0) {
nums[numberIndex] = -nums[numberIndex];
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
list.add(i + 1);
}
}
return list;
}
}
Solution explanation :
- Traverse through given array from left to right.
- Get current index value. Math.abs() used for get negative integers to positive integers. Subtract number by 1. (Array index start from 0 and we have to check from 1 to n).
- Check numberIndex is greater or not. If it is greater than 0, change that value from positive to negative.
- In second for loop, add those numbers into list that are greater than 0.
- return list of integers.
Output explanation :
nums = [1, 3, 5, 1, 3]
- i = 0
- Get positive value | numberIndex = Math.abs(nums[i]) | 1
- Subtract -1 from value | 1 - 1 = 0
- nums[numberIndex] > 0 | 1 > 0 becomes true.
- nums[numberIndex] = -nums[numberIndex];
- Change 1 to -1 | 1 = -1
- i = 1, nums = [-1, 3, 5, 1, 3]
- 3 - 1 = 2
- 5 > 0 becomes true.
- 5 = -5
- i = 2, nums = [-1, 3, -5, 1, 3]
- 5 - 1 = 4
- 3 > 0 becomes true.
- 3 = -3
- i = 3, nums = [-1, 3, -5, 1, -3]
- 1 - 1 = 0
- -1 > 0 becomes false
- i = 4, nums = [-1, 3, -5, 1, -3]
- 3 - 1 = 2
- -5 > 0 becomes false
- Traversal of first for loop is done. nums = [-1, 3, -5, 1, -3]
- Second For loop
- i = 0, list = []
- nums[i] > 0 | -1 > 0 becomes false
- i = 1, list = []
- 3 > 0 becomes true
- list.add(i + 1) | list = [2]
- i = 2, list = [2]
- -5 > 0 becomes false
- i = 3, list = [2]
- 1 > 0 becomes true
- list.add(i + 1) | list = [2, 4]
- i = 4, list = [2, 4]
- -5 > 0 becomes false
- Traversal of second for loop is done.
- return list = [2, 4]
Lets see second solution using extra space.
Solution 2 : Using extra space
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> list = new ArrayList();
int[] duplicateArray = new int[nums.length + 1];
for (int n : nums) {
duplicateArray[n]++;
}
for (int i = 1; i < duplicateArray.length; i++) {
if (duplicateArray[i] == 0) {
list.add(i);
}
}
return list;
}
}
Solution explanation :
- Declare new array by +1 length of given nums array.
- Traverse through nums array and increment given index where current n is located in duplicateArray.
- Traverse through duplicateArray array from 1 to array length and check if any index contains 0 then add in list.
- Return list.
Output explanation :
nums = [4, 3, 2, 7, 8, 2, 3, 1]
- duplicateArray = [0, 0, 0, 0, 0, 0, 0, 0, 0]
- for each loop
- n = 4
- duplicateArray = [0, 0, 0, 0, 1, 0, 0, 0, 0]
- n = 3
- duplicateArray = [0, 0, 0, 1, 1, 0, 0, 0, 0]
- n = 2
- duplicateArray = [0, 0, 1, 1, 1, 0, 0, 0, 0]
- n = 7
- duplicateArray = [0, 0, 1, 1, 1, 0, 0, 1, 0]
- n = 8
- duplicateArray = [0, 0, 1, 1, 1, 0, 0, 1, 1]
- n = 2
- duplicateArray = [0, 0, 2, 1, 1, 0, 0, 1, 1]
- n = 3
- duplicateArray = [0, 0, 2, 2, 1, 0, 0, 1, 1]
- n = 1
- duplicateArray = [0, 1, 2, 2, 1, 0, 0, 1, 1]
- duplicateArray = [0, 1, 2, 2, 1, 0, 0, 1, 1]
- For loop (Start from 1), duplicateArray = [0, 1, 2, 2, 1, 0, 0, 1, 1]
- i = 1,
- duplicateArray[1] == 0 | 1 == 0 becomes false
- i = 2, list = []
- 2 == 0 becomes false
- i = 3, list = []
- 2 == 0 becomes false
- i = 4, list = []
- 1 == 0 becomes false
- i = 5, list = []
- 0 == 0 becomes true
- list.add(i) | list = [5]
- i = 6, list = [5]
- 0 == 0 becomes true
- list.add(i) | list = [5, 6]
- i = 7, list = [5, 6]
- 1 == 0 becomes false
- i = 8, list = [5, 6]
- 1 == 0 becomes false
- Return list = [5, 6]
Lets see another solution using java 8 approach
Solution 3 : Using java 8
import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
return IntStream.range(1, nums.length + 1)
.filter(number -> !set.contains(number))
.boxed()
.collect(Collectors.toList());
}
}
Solution explanation :
- Convert array to set. set deos not store duplicate values.
- .boxed() method converts a stream of objects to a collection.
- IntStream.range returns a sequential ordered IntStream from startInclusive to endExclusive by an incremental step of 1 (here we are range from 1 to nums array length + 1).
- using Java 8 stream filter() method, we are filtering value that are not present in set and collect using Collectors.toList() to list and return list.
- Learn about java 8 collect method.
Happy coding.
Recommended articles :
- Third Maximum Number LeetCode solution in Java
- Compare two arrays and Check both values are matched or not in Java
Comments
Post a Comment