Codility MissingInteger Javascript solution (proposal)

February 18, 2021 by admin

This afternoon I try to resolve the demo test of Codility. After thinking a lot how to increase the performance (and searching a little bit), I created this code:

function solution(A) {
    let array = [...Array(1000001).keys()];

    const onlyPositives = A.filter(n => n>0);
    if(onlyPositives.length == 0) return 1

    onlyPositives.forEach(a => {
        if(array[a] != null)
            array[a] = null;
    });
    array[0] = null;

   return array.findIndex(e => e != null);
}

Anyone have another Idea?

8 thoughts on “Codility MissingInteger Javascript solution (proposal)”

Futhermore, you can use the same code without filtering, but in some cases the effective are less.

function solution(A) {
    let array = [...Array(1000001).keys()];

    A.forEach(a => {
        if(array[a] != null)
            array[a] = null;
    });
    array[0] = null;

   return array.findIndex(e => e != null);
}

Another approach might be to sort the array and search for the first gap:

function solution(arr) {
  arr.sort((a, b) => a - b);
  for(var i = 1; i < arr.length; i++) {
    if(arr[i] >= 0 && arr[i] - arr[i - 1] <= 1) 
       return arr[i - 1] + 1;
  }
  return arr[i - 1] + 1;
}

Admin

February 18, 2021 at 7:00 pm
Another way to deal with the positive only thing. My JS solution got 100 across the board. Basically, I generate a new array whose keys will be the values of the original array and set each to some truthy value. This does two things: it takes the negative values out of the iteration loop of the new array, and also allows you to loop from the smallest value up and return the first index that gives you undefined.
```
function solution(A) {
    orderedArr = [];
    for (let i = 0; i < A.length; i++) {
        if (!orderedArr[A[i]]) {
            orderedArr[A[i]] = true;
         }
    }
    if (orderedArr.length === 0) return 1;
    for (let i = 1; i < orderedArr.length; i++) {
        if (!orderedArr[i]) {
            return i;
        }
    }
    return orderedArr.length;
}
```
Reply

O(n) solution javascript.
using two loops.
first loop puts all elements bigger then 0 into a map/object
second loop check if value existing in map.

function solution(A) {
    let obj = {};
    let min = 1;

   //iterate over all items in the array and store the value in a object;
    for (let i = 0, len=A.length; i < len; i++) {
        const num = A[i];
        if (num > 0) {
            obj[num] = true;
        }
    }
    //start with min===1 check if it's in the object
    // if it is if it's in the object then increment min and repeat until min not in object.
    while (obj[min]) {
        min++;
    }
    //this will return the smallest value not in array bigger or equal to 1
    return min;
}

Here is the Java 8 version of the solution which resulted in 100% after submission. I used HashSet to eliminate the duplicate element.

import java.util.*;

class Solution {

public int solution(int[] A) {

    // sort the array
    Arrays.sort(A);
    int len = A.length;

    int result = 1;

    if (len == 0) {
        result = 1;
    }else {
        // populate hashset from the array to eliminate duplicate
        HashSet<Integer> aSet = new HashSet<Integer>();
        for(int i=0; i<len; i++) {
            aSet.add(A[i]);
        }

        // now loop through from 1 to len in the array and check if index exists
        for(int j=1; j<len+1;j++) {
            boolean exists = aSet.contains(j);
            if(!exists) {
                result = j;
                break;
            }else {
                if(j>0) {
                    result = j+1;
                }
            }
        }
    }

    return result;

}

}

function solution(A) {
    const numbers = []

    for (let i = 0; i < A.length; i++) {
        numbers[A[i]] = true
    }

    if (numbers.length === 0) {
        return 1   
    }

    for (let i = 1; i < numbers.length; i++) {
        if(numbers[i] === undefined) {
            return i
        }
    }

    return numbers.length
}

Here is my 100% performant solution

function solution(A) {
    let missingInteger = 1;
    A = A.sort((a, b) => a - b);
    for(let i = 0; i < A.length; i++){
        if(A[i] == missingInteger ) missingInteger++;
        if(A[i] > missingInteger) return missingInteger;
    }
    return missingInteger;
}

PROBLEM

Write a function: int solution(NSMutableArray *A);

that, given an array A of N integers, returns the smallest positive integer
(greater than 0) that does not occur in A.

For example,

Given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].

OBJECTIVE-C SOLUTION O(N)

Results given by Codility

Task Score: 100%
Correctness: 100%
Performance: 100%

Time Complexity

The worst case time complexity is O(N) or O(N * log(N))

Xcode Solution Here

+(int)solution:(NSMutableArray*)array {

    /******** Algorithm Explanation  ********/
    // STEP 1
    //       Check for edge cases - when the array is empty [], we should return 1
    // STEP 2
    //       Generate NSSet from the Array in oder to eliminate possible duplicates
    // STEP 3
    //      Implement a loop taking in consideration:
    //          N always starts from 1 and so on (1,2,3...n)
    //          There is always one missing element in the array
    //          So, in the Array we sould have N => (1,2,3...n+1)
    //
    // STEP 4
    //      Look for the current element in the SET
    //      If the element does't exist, that means we have found the smallest one missing element.
    //      Break the loop.


    // STEP 1
    int smallestCandidate = 0;
    int n = (int)[array count];
    if (n==0) {
        smallestCandidate = 1;
    }
    else {
        // STEP 2
        NSSet *elements = [NSSet setWithArray:array];

        // STEP 3
        for (int i=1; i<=(n+1); i++) {
            BOOL exist = [elements containsObject:@(i)];
            if(!exist) {
                // STEP 4
                smallestCandidate = i;
                return smallestCandidate;
            }
        }
    }
    return smallestCandidate;
}

8 thoughts on “Codility MissingInteger Javascript solution (proposal)”

Leave a Comment Cancel reply