Hello Friends, this is the fourth problem in the series of the algorithm and data structure interview questions. This is Daily coding problem – 4 with Solution in C# and Java.
This problem was asked by Stripe.
Daily coding problem – 4
Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
You can modify the input array in-place.
Solution:
There are couple of points we need to keep in mind while solving this problem. First one is that we are dealing with arrays and we have to find the missing positive integer in the linear time. Second is we can modify the input array.
While coming up with the solution for the problem we should first get the sub array with only positive elements. That logic is written in the method getThePositiveElements.
Once we have the array of only positive elements, we can traverse the array and make the index element of each array element as negative. The index at which the element is not negative is the missing element.
While finding the solution if the maximum element is the array is equal to the length of the element, than the missing element is equal to the length of the element. This is to cover the edge cases.
public static int findTheMissingElement(int[] inputArray) { int[] positiveElements = getThePositiveElements(inputArray); for (int i = 0; i < positiveElements.Length; i++) { int currentNumber = Math.Abs(positiveElements[i]); if(positiveElements.Max() == positiveElements.Length) return positiveElements.Length; if(currentNumber - 1 < positiveElements.Length && currentNumber > 0) { positiveElements[currentNumber - 1] *= -1; } } for (int i = 0; i < positiveElements.Length; i++) { if(positiveElements[i] >= 0) return i + 1; } return 0; } private static int[] getThePositiveElements(int[] inputArray) { int i = 0; int j = inputArray.Length - 1; while(i < j) { if(inputArray[i] > 0 && inputArray[j - 1] < 0) { int temp = inputArray[j - 1]; inputArray[j - 1] = inputArray[i]; inputArray[i] = temp; i++; j--; } else if(inputArray[i] < 0) { i++; } else { j--; } } int pivot = inputArray[i] > 0 ? i : i+1; int[] positiveIntArray = new int[inputArray.Length - pivot]; Array.Copy(inputArray, pivot, positiveIntArray, 0, (inputArray.Length - pivot)); return positiveIntArray; }
Below is the Java code for the same.
public int findTheMissingElement(int[] inputArray) { int[] positiveElements = getThePositiveElements(inputArray); if(Collections.max(Arrays.asList(positiveElements)) == positiveElements.length) return positiveElements.length; for (int i = 0; i < positiveElements.length; i++) { int currentNumber = Math.abs(positiveElements[i]); if(currentNumber - 1 < positiveElements.length) { positiveElements[currentNumber - 1] *= -1; } } for (int i = 0; i < positiveElements.length; i++) { if(positiveElements[i] > 0) return i + 1; } return 0; } private int[] getThePositiveElements(int[] inputArray) int i = 0; int j = inputArray.length - 1; while(i < j) { if(inputArray[i] > 0 && inputArray[j - 1] <= 0) { int temp = inputArray[j - 1]; inputArray[j - 1] = inputArray[i]; inputArray[i] = temp; i++; j--; } else if(inputArray[i] < 0) { i++; } else { j--; } } int pivot = inputArray[i] > 0 ? i : i+1; return Arrays.copyOfRange(inputArray, pivot, inputArray.length); }
Leave a Reply