Find missing elements from an array

The problem of finding missing elements in a sorted array is a common programming task. Given an array that is sorted in ascending order and may contain duplicate elements, the goal is to identify and display the missing elements in the sequence. This task can be approached using a simple algorithm that iterates through the array and identifies gaps between consecutive elements.

Problem Statement

You are given a sorted array of integers that may contain duplicates. Your task is to find and display the missing elements in the sequence. For example, if the input array is [1, 2, 3, 4, 4, 7, 7], the missing elements are 5 and 6.

Solution Approach

To solve this problem, we can iterate through the sorted array and for each pair of consecutive elements arr[i] and arr[i+1], we check for the missing elements in the range (arr[i] + 1) to (arr[i+1] - 1). If the difference between arr[i+1] and arr[i] is greater than 1, then there are missing elements in between.

Pseudocode

class MyArray:
    method find_missing(arr, size):
        for i from 0 to size - 2:
            for j from (arr[i] + 1) to (arr[i + 1] - 1):
                print j

Algorithm Explanation

1. Create a class MyArray to encapsulate the array manipulation logic.
2. In the find_missing method, iterate through the array using i from 0 to size - 2. This loop goes up to the second-to-last element of the array to ensure that we can access arr[i+1].
3. Inside the first loop, use another loop with variable j ranging from (arr[i] + 1) to (arr[i + 1] - 1). This loop iterates through the range between consecutive elements to find the missing elements.
4. Print the value of j, which represents the missing element in the sequence.
5. The loops will automatically handle duplicate elements and only consider the gaps between unique consecutive elements.

Example

Let's take the input array [1, 2, 3, 4, 4, 7, 7] as an example to demonstrate the algorithm.

1. For i = 0, arr[i] = 1 and arr[i + 1] = 2:

   • The loop for j runs from 2 to 1, but there are no missing elements. So, no output for this iteration.

2. For i = 1, arr[i] = 2 and arr[i + 1] = 3:

   • The loop for j runs from 3 to 2, and the missing element is 2.

3. For i = 2, arr[i] = 3 and arr[i + 1] = 4:

   • The loop for j runs from 4 to 3, and the missing element is 3.

4. For i = 3, arr[i] = 4 and arr[i + 1] = 4:

   • The loop for j doesn't run since there's no gap between the same element.

5. For i = 4, arr[i] = 4 and arr[i + 1] = 7:

   • The loop for j runs from 5 to 6, and the missing elements are 5 and 6.

6. For i = 5, arr[i] = 7 and arr[i + 1] = 7:

   • The loop for j doesn't run since there's no gap between the same element.

Code Solution

• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• C

/*
  C++ Program
  Find missing elements from an array
*/
#include<iostream>

using namespace std;


class MyArray {
	public:

		//Find all missing element in given sorted array
		void find_missing(int arr[], int size) {
			if (size <= 1) {
				return;
			} else {
				for (int i = 0; i < size - 1; ++i) {
					//Find the all missing elements
					for (int j = arr[i] + 1; j < arr[i + 1]; ++j) {
						//display missing element
						cout << " " << j;
					}
				}
			}
		}
};
int main() {
	MyArray obj ;
	int arr[] = {
		1,
		2,
		3,
		4,
		4,
		7,
		7
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	obj.find_missing(arr, size);
	return 0;
}

 5 6

/*
  Java Program
  Find missing elements from an array
*/

public class MyArray 
{
  //Find all missing element in given sorted array
  public void find_missing(int []arr,int size)
  {
    if(size<=1)
    {
      return;
    }
    else
    {
      for (int i = 0; i < size-1; ++i)
      {
        //Find the all missing elements
        for (int j = arr[i]+1; j < arr[i+1]; ++j)
        {
          //display missing element
          System.out.print("  "+j);
        }
      }
    }
  }
  public static void main(String[] args) {
    MyArray obj = new MyArray();
    //Define the value of array elements
    int []arr = {1, 2, 3, 4, 4, 7, 7} ;
    //Get the size of array
    int size = arr.length;

    obj.find_missing(arr,size);
  }
}

 5 6

/*
  C# Program
  Find missing elements from an array
*/
using System;

public class MyArray {
	//Find all missing element in given sorted array
	public void find_missing(int[] arr, int size) {
		if (size <= 1) {
			return;
		} else {
			for (int i = 0; i < size - 1; ++i) {
				//Find the all missing elements
				for (int j = arr[i] + 1; j < arr[i + 1]; ++j) {
					Console.Write(" " + j);
				}
			}
		}
	}
	public static void Main(String[] args) {
		MyArray obj = new MyArray();
		
		//Define the value of array elements
		int[] arr = {
			1,
			2,
			3,
			4,
			4,
			7,
			7
		};
		//Get the size of array
		int size = arr.Length;
		obj.find_missing(arr, size);
	}
}

 5 6

<?php
/*
  Php Program
  Find missing elements from an array
*/
class MyArray {
	//Find all missing element in given sorted array

	public 	function find_missing($arr, $size) {
		if ($size <= 1) {
			return;
		} else {
			for ($i = 0; $i < $size - 1; ++$i) {
				//Find the all missing elements
				for ($j = $arr[$i] + 1; $j < $arr[$i + 1]; ++$j) {
					//display missing element

					echo(" ". $j);
				}
			}
		}
	}
}

function main() {
	$obj = new MyArray();
	//Define the value of array elements
	$arr = array(1, 2, 3, 4, 4, 7, 7);
	//Get the size of array
	$size = count($arr);
	$obj->find_missing($arr, $size);

}
main();

 5 6

/*
  Node Js Program
  Find missing elements from an array
*/
class MyArray {
	//Find all missing element in given sorted array
	find_missing(arr, size) {
		if (size <= 1) {
			return;
		} else {
			for (var i = 0; i < size - 1; ++i) {
				//Find the all missing elements

				for (var j = arr[i] + 1; j < arr[i + 1]; ++j) {
					//display missing element

					process.stdout.write(" " + j);
				}
			}
		}
	}
}

function main(args) {
	var obj = new MyArray();
	//Define the value of array elements
	var arr = [1, 2, 3, 4, 4, 7, 7];
	//Get the size of array
	var size = arr.length;
	obj.find_missing(arr, size);
}

main();

 5 6

# Python 3 Program
# Find missing elements from an array
class MyArray :
	# Find all missing element in given sorted array
	def find_missing(self, arr, size) :
		if (size <= 1) :
			return
		else :
			i = 0
			while (i < size - 1) :
				# Find the all missing elements
				j = arr[i] + 1
				while (j < arr[i + 1]) :
					print(" ", j, end = "")
					j += 1
				
				i += 1


def main() :
	obj = MyArray()
	arr = [1, 2, 3, 4, 4, 7, 7]
	size = len(arr)
	obj.find_missing(arr, size)


if __name__ == "__main__":
	main()

  5  6

# Ruby Program
# Find missing elements from an array
class MyArray 
	# Find all missing element in given sorted array
	def find_missing(arr, size) 
		if (size <= 1) 
			return
		else 
			i = 0
			while (i < size - 1) 
				# Find the all missing elements
				j = arr[i] + 1
				while (j < arr[i + 1]) 
					print(" ", j)
					j += 1
				end
				i += 1
			end
		end
	end
end
def main() 
	obj = MyArray.new()
	arr = [1, 2, 3, 4, 4, 7, 7]
	size = arr.length
	obj.find_missing(arr, size)
end
main()

 5 6

/*
  Scala Program
  Find missing elements from an array
*/
class MyArray {
	//Find all missing element in given sorted array
	def find_missing(arr: Array[Int], size: Int): Unit = {
		if (size <= 1) {
			return;
		} else {
			var i: Int = 0;
			while (i < size - 1) {
				//Find the all missing elements
				var j: Int = arr(i) + 1;
				while (j < arr(i + 1)) {
					print(" " + j);
					j += 1;
				}
				i += 1;
			}
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyArray = new MyArray();
		val arr: Array[Int] = Array(1, 2, 3, 4, 4, 7, 7);
		val size: Int = arr.length;
		obj.find_missing(arr, size);
	}
}

 5 6

/*
  Swift Program
  Find missing elements from an array
*/
class MyArray {
	//Find all missing element in given sorted array
	func find_missing(_ arr: [Int], _ size: Int) {
		if (size <= 1) {
			return;
		} else {
			var i: Int = 0;
			while (i < size - 1) {
				//Find the all missing elements
				var j: Int = arr[i] + 1;
				while (j < arr[i + 1]) {
					print(" ", j, terminator: "");
					j += 1;
				}
				i += 1;
			}
		}
	}
}
func main() {
	let obj: MyArray = MyArray();
	let arr: [Int] = [1, 2, 3, 4, 4, 7, 7];
	let size: Int = arr.count;
	obj.find_missing(arr, size);
}
main();

  5  6

//C Program 
//Find missing elements from an array
#include <stdio.h>

//Find all missing element in given sorted array
void find_missing(int arr[],int size)
{
  if(size<=1)
  {
    return;
  }
  else
  {
    for (int i = 0; i < size-1; ++i)
    {
      //Find the all missing elements
      for (int j = arr[i]+1; j < arr[i+1]; ++j)
      {
        //display missing element
        printf("  %d\n",j);
      }
    }
  }
}
int main()
{

  //Define the value of array elements
  int arr[] ={1, 2, 3, 4, 4, 7, 7} ;
  //Get the size of array
  int size=sizeof(arr) / sizeof(arr[0]);

  find_missing(arr,size);

  return 0;
  
}

  5
  6

Time Complexity

Let n be the size of the input array.

• The outer loop runs n-1 times.
• The inner loop can potentially run up to n-1 times in total (when all elements are consecutive).
• Therefore, the time complexity of the algorithm is O(n).