Solution: Missing Number

Let's solve the Missing Number problem using the Cyclic Sort pattern.

We'll cover the following

Statement

Given an array, nums, containing nn distinct numbers in the range [0,n][0, n], return the only number in the range that is missing from the array.

Constraints:

  • n=n = nums.length
  • 1≤n≤1031 \leq n \leq 10^3
  • 0≤0 \leq nums[i] ≤n\leq n
  • There are no duplicates in the array.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach would be to first sort the array using quick sort and then traverse the array with two adjacent pointers. Since the integers are sorted, the difference between two adjacent array elements should be 11 if there is no missing integer. We can start by having the first pointer at index 0 and the second pointer at index 1, moving both 11 step forward each time. If the difference is greater than 1, our missing value would be the value of the first pointer ++ 11.

The time complexity for this approach becomes O(nlog⁡n)+O(n)O(n \log n) + O(n). The space complexity is O(n)O(n).

Optimized approach using cyclic sort

The intuition behind using this approach uses the unique property where each element should match its index, given data in a specific range. The algorithm starts by sorting the array so that each element is placed in its correct position (i.e., its value matches its index). After sorting, the first instance where an element does not match its index indicates the missing number.

Let’s walkthrough the detailed steps of this algorithm:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

The first step is to sort the array using cyclic sort. We’ll start the traversal from the first element of the array. If it’s not equal to its index, we swap the element with the element on its correct index. For example, if 3 is on index 0, swap it with the element on index 3.

class MissingNumber {
  public static String printArraywithMarkers(int[] arr, List < Integer > iValue) {
    String out = "[";
    for (int i = 0; i < arr.length - 1; i++) {
      if (i == iValue.get(0) || i == iValue.get(1)) {
        out += "«";
        out += String.valueOf(arr[i]) + "»" + ", ";
      }
      else {
        out += String.valueOf(arr[i]) + ", ";
      }
    }
    if (iValue.get(0) == arr.length - 1 || iValue.get(1) == arr.length - 1) {
      out += "«" + String.valueOf(arr[arr.length - 1]) + "»";
      out += "]";
    }
    else {
      out += arr[arr.length - 1];
      out += "]";
    }
    return out;
  }
  public static void findMissingNumber(int[] nums) {
    List < Integer > parms;
    int lenNums = nums.length;
    int index = 0;
    int value = 0;
    System.out.println("\n\tSorting the array");
    while (index < lenNums) {
      parms = new ArrayList < Integer > (Collections.nCopies(2, -88));
      System.out.println("\t\tLoop iteration " + index + ":");
      parms.set(0, index);
      System.out.println("\t\t\t" + printArraywithMarkers(nums, parms));
      value = nums[index];
      System.out.println("\t\t\tindex = " + index);
      System.out.println("\t\t\tvalue = " + value);
      //check if value is at the incorrect position
      if (value != nums[value]) {
        System.out.println("\t\t\tSwapping the value: " + value + " with the value on index " + value + ": " + nums[value]);
        parms.set(1, value);
        System.out.println("\t\t\t\t" + printArraywithMarkers(nums, parms));
        //swap the value with its correct index
        int temp = nums[index];
        nums[index] = nums[value];
        nums[value] = temp;
        System.out.println("\t\t\t\tAfter swapping: " + printArraywithMarkers(nums, parms));
        // Move to the next loop
        continue;
      }
      // if the element is at the correct index, move one element forward
      index += 1;
    }
  }
  public static void main(String[] args) {
    int[][] inputNumbers = {
      {4, 0, 3, 1},
      {8, 3, 5, 2, 4, 6, 0, 1},
      {1, 2, 3, 4, 6, 7, 8, 9, 10, 5},
      {0},
      {1, 2, 3, 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23}
    };
    for (int i = 0; i < inputNumbers.length; i++) {
      System.out.print(i + 1 + ".\tnums: ");
      for (int j = 0; j < inputNumbers[i].length - 1; j++) {
        System.out.print(inputNumbers[i][j]);
        System.out.print(", ");
      }
      System.out.println(inputNumbers[i][inputNumbers[i].length - 1]);
      findMissingNumber(inputNumbers[i]);
      //System.out.println(find_missing_number(inputnumbers[i]));
      System.out.println(PrintHyphens.repeat("-", 100));
    }
  }
}
Missing Number

However, the above code throws an error. This happens when we encounter a value that’s greater than the array length. To cater to this, we’ll add a condition that ensures that the number we swap is less than the length of our array. Else, we’ll skip it and move one step forward.

class MissingNumber {
  
  public static String printArraywithMarkers(int[] arr, List < Integer > iValue) {
    String out = "[";
    for (int i = 0; i < arr.length - 1; i++) {
      if (i == iValue.get(0) || i == iValue.get(1)) {
        out += "«";
        out += String.valueOf(arr[i]) + "»" + ", ";
      }
      else {
        out += String.valueOf(arr[i]) + ", ";
      }
    }
    if (iValue.get(0) == arr.length - 1 || iValue.get(1) == arr.length - 1) {
      out += "«" + String.valueOf(arr[arr.length - 1]) + "»";
      out += "]";
    }
    else {
      out += arr[arr.length - 1];
      out += "]";
    }
    return out;
  }
  public static void findMissingNumber(int[] nums) {
    List < Integer > parms;
    int lenNums = nums.length;
    int index = 0;
    int ind = 0;
    int value = 0;
    System.out.println("\n\tSorting the array");
    while (index < lenNums) {
      parms = new ArrayList < Integer > (Collections.nCopies(2, -88));
      System.out.println("\t\tLoop iteration " + ind + ":");
      ind += 1;
      parms.set(0, index);
      System.out.println("\t\t\t" + printArraywithMarkers(nums, parms));
      value = nums[index];
      System.out.println("\t\t\tindex = " + index);
      System.out.println("\t\t\tvalue = " + value);
      //check if value is at the incorrect position
      if (value < lenNums && value != nums[value]) {
        System.out.println("\t\t\tSwapping the value: " + value + " with the value on index " + value + ": " + nums[value]);
        parms.set(1, value);
        System.out.println("\t\t\t\t" + printArraywithMarkers(nums, parms));
        //swap the value with its correct index
        int temp = nums[index];
        nums[index] = nums[value];
        nums[value] = temp;
        System.out.println("\t\t\t\tAfter swapping: " + printArraywithMarkers(nums, parms));
      }
      else if (value >= lenNums) {
        System.out.println("\t\t\tvalue > length of array, hence we skip it");
        // move to the next loop
        index += 1;
      }
      else {
        // if the element is at the correct index, move one element forward
        System.out.println("\t\t\tThe value is at its correct index, hence we move one step forward");
        // move to the next loop
        index += 1;
      }
    }
  }
  public static void main(String[] args) {
    int[][] inputNumbers = {
      {4, 0, 3, 1},
      {8, 3, 5, 2, 4, 6, 0, 1},
      {1, 2, 3, 4, 6, 7, 8, 9, 10, 5},
      {0},
      {1, 2, 3, 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23}
    };
    for (int i = 0; i < inputNumbers.length; i++) {
      System.out.print(i + 1 + ".\tnums: ");
      for (int j = 0; j < inputNumbers[i].length - 1; j++) {
        System.out.print(inputNumbers[i][j]);
        System.out.print(", ");
      }
      System.out.println(inputNumbers[i][inputNumbers[i].length - 1]);
      findMissingNumber(inputNumbers[i]);
      //System.out.println(find_missing_number(inputnumbers[i]));
      System.out.println(PrintHyphens.repeat("-", 100));
    }
  }
}
Missing Number

Now that our array is sorted, we’ll compare each element with its index. The first element that’s not equal to its index isn’t in the correct position. This index will be equal to the missing element.

class MissingNumber {
  public static String printArraywithMarkers(int[] arr, List < Integer > iValue) {
    String out = "[";
    for (int i = 0; i < arr.length - 1; i++) {
      if (i == iValue.get(0) || i == iValue.get(1)) {
        out += "«";
        out += String.valueOf(arr[i]) + "»" + ", ";
      }
      else {
        out += String.valueOf(arr[i]) + ", ";
      }
    }
    if (iValue.get(0) == arr.length - 1 || iValue.get(1) == arr.length - 1) {
      out += "«" + String.valueOf(arr[arr.length - 1]) + "»";
      out += "]";
    }
    else {
      out += arr[arr.length - 1];
      out += "]";
    }
    return out;
  }
  public static int findMissingNumber(int[] nums) {
    List < Integer > parms;
    int lenNums = nums.length;
    int index = 0;
    int ind = 0;
    int value = 0;
    System.out.println("\n\tSorting the array");
    while (index < lenNums) {
      parms = new ArrayList < Integer > (Collections.nCopies(2, -88));
      System.out.println("\t\tLoop iteration " + ind + ":");
      ind += 1;
      parms.set(0, index);
      System.out.println("\t\t\t" + printArraywithMarkers(nums, parms));
      value = nums[index];
      System.out.println("\t\t\tindex = " + index);
      System.out.println("\t\t\tvalue = " + value);
      //check if value is at the incorrect position
      if (value < lenNums && value != nums[value]) {
        System.out.println("\t\t\tSwapping the value: " + value + " with the value on index " + value + ": " + nums[value]);
        parms.set(1, value);
        System.out.println("\t\t\t\t" + printArraywithMarkers(nums, parms));
        //swap the value with its correct index
        int temp = nums[index];
        nums[index] = nums[value];
        nums[value] = temp;
        System.out.println("\t\t\t\tAfter swapping: " + printArraywithMarkers(nums, parms));
      }
      else if (value >= lenNums) {
        System.out.println("\t\t\tvalue > length of array, hence we skip it");
        // move to the next loop
        index += 1;
      }
      else {
        // if the element is at the correct index, move one element forward
        System.out.println("\t\t\tThe value is at its correct index, hence we move one step forward");
        // move to the next loop
        index += 1;
      }
    }
    System.out.println("\n\tFinding the missing number");
    parms = new ArrayList < Integer > (Collections.nCopies(2, -88));
    // find the first number missing from its index
    for (int x = 0; x < lenNums; x++) {
      System.out.println("\t\tLoop iteration " + x);
      parms.set(0, x);
      System.out.println("\t\t\t" + printArraywithMarkers(nums, parms));
      if (x != nums[x]) {
        //index for the mismatched pair is the missing number
        System.out.println("\t\t\t" + nums[x] + " is not at the correct index: " + x);
        return x;
      }
      System.out.println("\t\t\t" + nums[x] + " is at the correct index: " + x);
    }
    return lenNums;
  }
  public static void main(String[] args) {
    int[][] inputNumbers = {
      {4, 0, 3, 1},
      {8, 3, 5, 2, 4, 6, 0, 1},
      {1, 2, 3, 4, 6, 7, 8, 9, 10, 5},
      {0},
      {1, 2, 3, 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23}
    };
    for (int i = 0; i < inputNumbers.length; i++) {
      System.out.print(i + 1 + ".\tnums: ");
      for (int j = 0; j < inputNumbers[i].length - 1; j++) {
        System.out.print(inputNumbers[i][j]);
        System.out.print(", ");
      }
      System.out.println(inputNumbers[i][inputNumbers[i].length - 1]);
      System.out.println("\n\tMissing number: " + findMissingNumber(inputNumbers[i]));
      System.out.println(PrintHyphens.repeat("-", 100));
    }
  }
}
Missing Number

Just the code

Here’s the complete solution to this problem:

class MissingNumber {
  public static int findMissingNumber(int[] nums) {
    int lenNums = nums.length;
    int index = 0;
    int value = 0;
    while (index < lenNums) {
      value = nums[index];
      if (value < lenNums && value != nums[value]) {
        int temp = nums[index];
        nums[index] = nums[value];
        nums[value] = temp;
      }
      else if (value >= lenNums) {
        index += 1;
      }
      else {
        index += 1;
      }
    }
    for (int x = 0; x < lenNums; x++) {
      if (x != nums[x]) {
        return x;
      }
    }
    return lenNums;
  }
  public static void main(String[] args) {
    int[][] inputNumbers = {
      {4, 0, 3, 1},
      {8, 3, 5, 2, 4, 6, 0, 1},
      {1, 2, 3, 4, 6, 7, 8, 9, 10, 5},
      {0},
      {1, 2, 3, 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23}
    };
    for (int i = 0; i < inputNumbers.length; i++) {
      System.out.print(i + 1 + ".\tnums: [");
      for (int j = 0; j < inputNumbers[i].length - 1; j++) {
        System.out.print(inputNumbers[i][j]);
        System.out.print(", ");
      }
      System.out.println(inputNumbers[i][inputNumbers[i].length - 1] + "]");
      
      System.out.println("\n\tMissing number: " + findMissingNumber(inputNumbers[i]));
      System.out.println(PrintHyphens.repeat("-", 100));
    }
  }
}
Missing Number

Solution summary

To recap, the solution to this problem can be divided into the following parts:

  1. Sort the elements in-place.
  2. Compare the array elements and their indices.
  3. The index of the first mismatch is the missing number.

Time complexity

The time complexity of the above algorithm is O(n)O(n), where nn is the number of elements in the input array.

Space complexity

The algorithm runs in constant space O(1)O(1).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.