Given an array nums containing n distinct numbers in the range [0, n], return the only
number in the range that is missing from the array.
Example:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
- n = 9 since there are 9 numbers, so all numbers are in the range [0,9].
- 8 is the missing number in the range since it does not appear in nums.
Solve Here: Leetcode 268
Approach 1: Nested Loops
Use nested loops to iterate over all numbers in the range [0, n] and check if the
number is present in nums. If a number is not present, return that number.
Algorithm
Sample inputs
Searching fornum = —
3
0
1
0
1
2
n= 3
num= —
j= —
found= —
Pointer jMatchNo matchIdle
1public int missingNumber(int[] nums) {
2
3 int n = nums.length;
4
5 for (int num = 0; num <= n; num++) {
6 boolean found = false;
7 // Check if num is present in the array
8 for (int j = 0; j < n; j++) {
9 if (num == nums[j]) {
10 found = true;
11 break;
12 }
13 }
14 // If the number is not found, return it
15 if (found == false) return num;
16 }
17
18 return -1;
19
20}
Ready
Press Step or Start to walk through the nested-loop algorithm. Pick a preset below to try a different array.
0/17
Time Complexity
The outer loop runs n+1 times and the inner loop runs n times. Hence, overall time
complexity = O(n²).
Space Complexity
We are not using any extra space. Hence, overall space complexity = O(1).