PermMissingElem – Codility – Solution

Java solution to Codility PermMissingElem (Permutation Missing Element) problem (Lesson 3 – Time Complexity) which scored 100%. The problem is to find the missing element in a given permutation. The main strategy is use a HashSet to store elements which will also order them. Then check all values from 1 to max to see if it’s missing from HashSet.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package com.codility.lesson03.timecomplexity;

import java.util.HashSet;
import java.util.Set;

public class PermutationMissingElement {
  public int solution(int[] A) {
    int max = A.length + 1;
   
    //load array elements into array so would be quick to check if elements exist
    Set incompleteSet = new HashSet();
    for(int i=0; i<A.length; i++) {
      incompleteSet.add(A[i]);
    }

    for(int i=1; i<max+1; i++) {
      if(!incompleteSet.contains(i)) {
        return (i);
      }
    }
    throw new RuntimeException("shouldn't reach here");
  }
}

TestNG test cases for this problem which all passed:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package test.com.codility.lesson03.timecomplexity;

import org.testng.Assert;
import org.testng.annotations.*;

import com.codility.lesson03.timecomplexity.PermutationMissingElement;

public class PermutationMissingElementTests {
  private PermutationMissingElement solution;
 
  @BeforeTest
  public void setUp() {
    solution = new PermutationMissingElement();
  }
 
  @DataProvider(name = "test1")
  public Object [][] createData1() {
    return new Object [][] {
      new Object [] { new int [] {                        }, 1 },
      new Object [] { new int [] {                      1 }, 2 },
      new Object [] { new int [] {                      2 }, 1 },
      new Object [] { new int [] {                   1, 3 }, 2 },
      new Object [] { new int [] {                   2, 3 }, 1 },
      new Object [] { new int [] {                1, 2    }, 3 },
      new Object [] { new int [] {                1, 3, 4 }, 2 },
      new Object [] { new int [] {                2, 4, 3 }, 1 },
      new Object [] { new int [] {             2, 3, 1, 5 }, 4 },
      new Object [] { new int [] { 4, 2, 3, 1, 5, 6, 8, 9 }, 7 },
      new Object [] { new int [] { 4, 2, 3, 1, 5, 6, 8, 7 }, 9 },
    };
  }

  @Test(dataProvider = "test1")
  public void verifySolution(int [] pA, int pExpectedMissingValue) {
    Assert.assertEquals(solution.solution(pA), pExpectedMissingValue);
  }
}